We use matrix iteration theory to characterize acceleration in smooth games. We define the spectral shape of a family of games as the set containing all eigenvalues of the Jacobians of standard gradient dynamics in the family. Shapes restricted to the real line represent well-understood classes of problems, like minimi…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “spectral acceleration”
New accelerators for EM improve convergence speed in complex mixture models.
problem Improving the convergence speed of the EM algorithm for complex mixture models.
method Derive a new operator connecting global descent and local convergence, and use it to develop two acceleration strategies.
result Two new acceleration strategies (G-Accelerator and Geo-Adaptive) significantly improve EM algorithm performance.
Accelerates optimal transport computation by 10x with spectral insights.
problem Exponential slow-down of convergence in Entropic Optimal Transport as regularization weakens.
method Spectral insights and spectral warm-start strategy to mitigate convergence issues.
result Faster convergence compared to the reference method Sinkhorn algorithm.
We study learning properties of accelerated gradient descent methods for linear least-squares in Hilbert spaces. We analyze the implicit regularization properties of Nesterov acceleration and a variant of heavy-ball in terms of corresponding learning error bounds. Our results show that acceleration can provides faster …
Improves learning of spectral mixture kernels with approximate Bayesian inference.
problem Difficult optimization of large number of SM kernel parameters.
method Approximate Bayesian inference using variational distribution of spectral points and random Fourier features.
result Accelerates convergence and leads to better optimal parameters.
We accelerate the power method for strong low-rank approximation using fast sketching.
problem Efficiency bottleneck in power method for large target ranks.
method Developed an algorithmic and theoretical framework for accelerating the power method using fast sketching.
result Simple and provably efficient methods for singular value decomposition, low-rank factorization, and Nyström approximation.
Spectral clustering is one of the most effective clustering approaches that capture hidden cluster structures in the data. However, it does not scale well to large-scale problems due to its quadratic complexity in constructing similarity graphs and computing subsequent eigendecomposition. Although a number of methods h…
Spectral Gradient Descent Mitigates Anisotropy-Driven Misalignment: A Case Study in Phase Retrievalstat.ML
SpecGD mitigates misalignment in phase retrieval models with anisotropic inputs.
problem Misalignment during gradient descent in phase retrieval models with anisotropic inputs.
method Spectral gradient descent modifies gradient updates to preserve directional information and remove spike amplification.
result SpecGD removes spike amplification, leading to stable alignment and accelerated noise contraction.
This paper speeds up SVC clustering by compressing data while preserving key properties.
problem Efficiently clustering large-scale real-world data sets.
method Spectrum-preserving data compression for fast support vector clustering.
result Achieved 100X and 115X speedups on real-world data sets while maintaining clustering quality.
This paper speeds up spectral clustering for large graphs by dilating their eigenspectrum.
problem Slow convergence in spectral clustering due to small eigengaps in graph Laplacians.
method Polynomial approximations to matrix operations that dilate the spectrum without changing eigenvectors.
result Significant acceleration of convergence in spectral clustering.
Two spectral clustering methods for multi-layer networks are analyzed and compared.
problem Community detection in multi-layer networks.
method Sum and debiased sum of squared adjacency matrices for spectral clustering.
result Debiased sum of squared adjacency matrices outperforms sum of adjacency matrices.
Positive weights improve kernel quadrature's accuracy.
problem Improving kernel quadrature weights to be positive and stable.
method Using convex geometry to approximate the kernel mean embedding with positive weights.
result Positive weights lead to improved kernel quadrature bounds with Monte-Carlo-beating rates.
New method shows stochastic momentum can converge quickly on optimization problems.
problem Improving convergence of stochastic optimization methods.
method Stochastic heavy ball momentum with minibatching.
result Stochastic heavy ball momentum retains fast linear rate on quadratic problems.
We propose a deep learning approach for discovering kernels tailored to identifying clusters over sample data. Our neural network produces sample embeddings that are motivated by--and are at least as expressive as--spectral clustering. Our training objective, based on the Hilbert Schmidt Information Criterion, can be o…
Spectral clustering approaches have led to well-accepted algorithms for finding accurate clusters in a given dataset. However, their application to large-scale datasets has been hindered by computational complexity of eigenvalue decompositions. Several algorithms have been proposed in the recent past to accelerate spec…
New Hermite approximations accelerate convergence with adaptive coordinate transformations.
problem Accelerating convergence of spectral approximations for Hermite expansions.
method Using normalizing flows for adaptive coordinate transformations and deriving error estimates.
result Error estimates for Hermite expansions under adaptive coordinate transformations.
Fast simulates Volterra processes using RFF, focusing on S-fBM.
problem Efficiently simulate Volterra processes for fractional Brownian motion.
method Random Fourier Features (RFF) approximation of kernel, spectral representation, Hamiltonian Monte Carlo sampling.
result Quantitative guarantees for RFF approximation, competitive in terms of efficiency and error.
This paper improves spectral clustering for large datasets using the Nystrom method.
problem Spectral clustering's scalability issues with large datasets.
method A principled spectral clustering algorithm exploiting Nystrom approximation's spectral properties.
result Improved spectral clustering efficiency and accuracy compared to existing methods.
Extends random feature analysis to spectral methods and improves learning rates.
problem Improving generalization properties of spectral methods in large-scale learning.
method Extends random feature analysis to a broad class of spectral regularization techniques, including gradient descent and Nesterov method.
result Obtains optimal learning rates for regularity classes, including those not in the RKHS.
First-order optimization methods, such as stochastic gradient descent (SGD) and its variants, are widely used in machine learning applications due to their simplicity and low per-iteration costs. However, they often require larger numbers of iterations, with associated communication costs in distributed environments. I…
Randomized spectral co-clustering speeds up large-scale directed networks.
problem Co-clustering directed networks efficiently for large-scale data.
method Randomized spectral co-clustering algorithms using random-projection and random-sampling techniques.
result Theoretical and numerical validation of approximation and misclustering error rates.
Spectral graph sparsification preserves geometry of GNN embeddings.
problem Maintaining geometric properties of graph neural network embeddings during sparsification.
method Proving spectral sparsification preserves squared pairwise distances, class means, and covariance structure in embedding space.
result Spectral sparsification preserves the geometry of learned embeddings in GNNs.
State-of-the-art algorithms for sparse subspace clustering perform spectral clustering on a similarity matrix typically obtained by representing each data point as a sparse combination of other points using either basis pursuit (BP) or orthogonal matching pursuit (OMP). BP-based methods are often prohibitive in practic…
Nystrom approximation speeds up kernel model training.
problem Slow convergence in kernel models due to poor conditioning.
method Spectral preconditioning with Nystrom approximation for scalability.
result Nystrom approximation accelerates gradient descent nearly as well as exact preconditioner.
Chebyshev steps improve convergence in deep-unfolded gradient descent.
problem Improving convergence speed in iterative algorithms.
method Introducing Chebyshev steps to bound convergence rate of gradient descent.
result Chebyshev steps lead to asymptotically optimal convergence rate.
In this paper, we provide a novel construction of the linear-sized spectral sparsifiers of Batson, Spielman and Srivastava [BSS14]. While previous constructions required running time [BSS14, Zou12], our sparsification routine can be implemented in almost-quadratic running time . The funda…
The paper analyzes the variance of different shuffling methods in stochastic gradient descent.
problem Understanding the variance of different shuffling methods in stochastic gradient descent.
method Power spectral density analysis to study the noise sequences of stochastic gradients.
result The stationary variances of iterates decrease in the order of SGD, SGD-RR, and SGD-SO.
Analyzes how diffusion models learn, revealing a spectral bias in structure mastery.
problem Understanding the learning dynamics and bias in diffusion models.
method Developed an analytical framework using a Gaussian-equivalence principle to solve gradient-flow dynamics and integrate probability-flow ODEs.
result Exposes a universal inverse-variance spectral law: high-variance structure is mastered faster than low-variance detail.
New algorithms improve community detection in network data with strong consistency.
problem Challenges in effectively adapting spectral clustering techniques and achieving strong consistency in label recovery.
method Proposed Thresholded Cosine Spectral Clustering (TCSC) and one-step Refined TCSC algorithms, with strong consistency proofs.
result One-step Refined TCSC achieves strong consistency in community detection under PABM, correctly recovering all labels with high probability.
Kernel methods obtain superb performance in terms of accuracy for various machine learning tasks since they can effectively extract nonlinear relations. However, their time complexity can be rather large especially for clustering tasks. In this paper we define a general class of kernels that can be easily approximated …
Just as semantic hashing can accelerate information retrieval, binary valued embeddings can significantly reduce latency in the retrieval of graphical data. We introduce a simple but effective model for learning such binary vectors for nodes in a graph. By imagining the embeddings as independent coin flips of varying b…
ADASAP accelerates GP inference for large datasets.
problem Scaling Gaussian process inference to large datasets.
method Approximate sketch-and-project algorithm for solving linear systems.
result Sketch-and-project rapidly converges to true posterior mean.
Consider a network of agents connected by communication links, where each agent holds a real value. The gossip problem consists in estimating the average of the values diffused in the network in a distributed manner. We develop a method solving the gossip problem that depends only on the spectral dimension of the netwo…
New method for efficient pricing of double barrier options in Lévy models.
problem Difficulties in accurately and quickly calculating prices of double barrier options in jump models.
method GWR-SINH method based on Gaver-Wynn-Rho acceleration applied to Bromwich integral.
result Accurate and fast calculations of prices of double barrier options in jump models achieved.
PASCO speeds up graph clustering for large graphs.
problem Efficiently clustering large graphs with many communities.
method Overlay method combining coarsening and parallel clustering.
result PASCO accelerates clustering with improved efficiency and quality.
Decentralized Parallel SGD (D-PSGD) and its asynchronous variant Asynchronous Parallel SGD (AD-PSGD) is a family of distributed learning algorithms that have been demonstrated to perform well for large-scale deep learning tasks. One drawback of (A)D-PSGD is that the spectral gap of the mixing matrix decreases when the …
fastkqr speeds up kernel quantile regression by up to 10x.
problem Huge computational demands of kernel quantile regression.
method A novel finite smoothing algorithm and spectral technique.
result Significantly faster computation of quantile regression.
Deep unfolding is a promising deep-learning technique in which an iterative algorithm is unrolled to a deep network architecture with trainable parameters. In the case of gradient descent algorithms, as a result of the training process, one often observes the acceleration of the convergence speed with learned non-const…
A natural way to characterize the cluster structure of a dataset is by finding regions containing a high density of data. This can be done in a nonparametric way with a kernel density estimate, whose modes and hence clusters can be found using mean-shift algorithms. We describe the theory and practice behind clustering…
Accelerates Riemannian gradient methods with extrapolation.
problem Optimizing functions on manifolds efficiently.
method Extrapolating iterates in Riemannian gradient descent.
result Achieves optimal convergence rate and computational advantage.
Subspace segmentation assumes that data comes from the union of different subspaces and the purpose of segmentation is to partition the data into the corresponding subspace. Low-rank representation (LRR) is a classic spectral-type method for solving subspace segmentation problems, that is, one first obtains an affinity…
We present MOGPTK, a Python package for multi-channel data modelling using Gaussian processes (GP). The aim of this toolkit is to make multi-output GP (MOGP) models accessible to researchers, data scientists, and practitioners alike. MOGPTK uses a Python front-end, relies on the GPflow suite and is built on a TensorFlo…
Accelerates optimization in asynchronous systems with sparse updates.
problem Optimizing finite-sum objectives in asynchronous lock-free environments.
method New accelerated SVRG variant with sparse updates.
result Achieves optimal incremental gradient complexity.
A new algorithm solves nonnegative least squares faster with nonnegative data.
problem Nonnegative least squares problems with nonnegative data.
method Primal-dual perspective accelerated algorithm with adaptive restart.
result Oracle complexity independent of matrix constants, solvable to multiplicative error.
We analyze Riemannian accelerated methods using a new framework.
problem Understanding Riemannian accelerated gradient methods.
method Riemannian A-HPE framework, focusing on Euclidean A-HPE insights and metric distortion control.
result Characterization of acceleration for various Riemannian methods.
Graph embedding techniques have been increasingly deployed in a multitude of different applications that involve learning on non-Euclidean data. However, existing graph embedding models either fail to incorporate node attribute information during training or suffer from node attribute noise, which compromises the accur…
PF-LaCG removes the need for knowing smoothness and strong convexity parameters for locally accelerated CG.
problem Locally accelerated CG requires knowledge of smoothness and strong convexity parameters.
method Parameter-Free Locally Accelerated CG (PF-LaCG) algorithm.
result PF-LaCG achieves local acceleration without requiring knowledge of smoothness and strong convexity parameters.
Accelerates coordinate descent methods for machine learning problems.
problem Slowness of coordinate descent methods in machine learning.
method Extrapolation-based accelerated coordinate descent.
result Significant speed-up in practice compared to existing methods.