We provide an online convex optimization algorithm with regret that interpolates between the regret of an algorithm using an optimal preconditioning matrix and one using a diagonal preconditioning matrix. Our regret bound is never worse than that obtained by diagonal preconditioning, and in certain setting even surpass…
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,695 papers · 148 categories
Trend · papers per month
48 results for “matrix preconditioning”
PolarGrad optimizes deep learning models by considering matrix structure, outperforming Adam and Muon.
problem Efficient optimization of large-scale neural networks and language models.
method A unifying framework for analyzing matrix-aware preconditioned methods, including PolarGrad.
result PolarGrad outperforms Adam and Muon in various tasks.
Preconditioned non-convex gradient descent improves noisy matrix estimation.
problem Estimating low-rank matrices from noisy measurements.
method Preconditioned non-convex gradient descent for noisy measurements.
result Preconditioned method converges to minimax optimal estimate at a linear rate.
Improved convergence for overparameterized low-rank matrix sensing.
problem Overparameterized low-rank matrix sensing with unknown rank and ill-conditioning.
method ScaledGD() - preconditioned gradient descent method.
result ScaledGD() converges at a constant linear rate after a logarithmic number of iterations.
Adaptive regularization methods pre-multiply a descent direction by a preconditioning matrix. Due to the large number of parameters of machine learning problems, full-matrix preconditioning methods are prohibitively expensive. We show how to modify full-matrix adaptive regularization in order to make it practical and e…
This paper optimizes diagonal preconditioning to improve matrix condition numbers.
problem Optimizing diagonal preconditioning to reduce matrix condition numbers.
method Reformulated as a quasi-convex problem, solved with bisection and Newton updates.
result Optimal diagonal preconditioners can significantly improve iterative methods.
Optimal preconditioning improves Langevin sampling efficiency.
problem Improving sampling efficiency in high-dimensional target distributions.
method Optimal preconditioning using Fisher information, applied to MALA.
result Adaptive MCMC scheme significantly outperforms other methods.
Nonnegative matrix factorization (NMF) under the separability assumption can provably be solved efficiently, even in the presence of noise, and has been shown to be a powerful technique in document classification and hyperspectral unmixing. This problem is referred to as near-separable NMF and requires that there exist…
Adaptive learning rate algorithms such as RMSProp are widely used for training deep neural networks. RMSProp offers efficient training since it uses first order gradients to approximate Hessian-based preconditioning. However, since the first order gradients include noise caused by stochastic optimization, the approxima…
Standard gradient descent methods are susceptible to a range of issues that can impede training, such as high correlations and different scaling in parameter space.These difficulties can be addressed by second-order approaches that apply a pre-conditioning matrix to the gradient to improve convergence. Unfortunately, s…
APGD algorithm efficiently recovers over-parameterized matrices from noisy measurements.
problem Matrix sensing problem with over-parameterization and noisy measurements.
method Alternating preconditioned gradient descent (APGD) algorithm incorporating preconditioning terms.
result APGD converges to a near-optimal error at a linear rate.
New methods improve solving linear systems and preconditioning with reduced complexity.
problem Efficiently solving linear systems and preconditioning matrices.
method Developed structured semidefinite programming algorithms.
result Improved runtimes for preconditioning and solving linear systems.
Preconditioned SGD accelerates convergence for ill-conditioned huge-scale matrix completion.
problem Recovering a low-rank matrix from incomplete data with high condition number.
method Preconditioned Stochastic Gradient Descent (SGD) for huge-scale online optimization.
result Preconditioned SGD converges to ε-accuracy in O(log(1/ε)) iterations, compared to O(κlog(1/ε)) for unpreconditioned SGD.
Universal preconditioning reduces sequential prediction regret.
problem Improving sequential prediction performance.
method Convolve target sequence with orthogonal polynomial coefficients.
result First sublinear and hidden-dimension-independent regret bounds.
Preconditioned gradient methods are among the most general and powerful tools in optimization. However, preconditioning requires storing and manipulating prohibitively large matrices. We describe and analyze a new structure-aware preconditioning algorithm, called Shampoo, for stochastic optimization over tensor spaces.…
APO optimizes neural network parameters by amortizing proximal point methods.
problem Optimizing neural network parameters online and adaptively.
method APO framework that meta-learns proximal point parameters.
result APO can recover and outperform existing optimizers and schedules.
Two methods solve kernel ridge regression problems efficiently.
problem Solving kernel ridge regression problems with large datasets.
method RPCholesky and KRILL preconditioning techniques.
result Efficient solutions to KRR problems with strong guarantees.
Randomized block-diagonal preconditioning improves parallel learning convergence.
problem Improving convergence of gradient-based optimization methods in parallel settings.
method Randomization of coordinates during optimization to repartition tasks.
result Randomization significantly improves convergence of block-diagonal preconditioned methods.
This paper improves linear system solving by optimizing matrix diagonal scaling.
problem Improving the condition number of a matrix for faster iterative methods.
method Left or right diagonal rescaling of the matrix A, with new bounds and algorithms.
result Jacobi preconditioning reduces A's condition number to within a quadratic factor of the best possible scaling.
Stein variational gradient descent (SVGD) is a particle-based inference algorithm that leverages gradient information for efficient approximate inference. In this work, we enhance SVGD by leveraging preconditioning matrices, such as the Hessian and Fisher information matrix, to incorporate geometric information into SV…
Bias correction improves language model training performance.
problem Stochastic update bias in preconditioned optimizers.
method Cross-fitted preconditioning and variance-corrected inversion.
result Reduces held-out pretraining loss by 0.15 nats.
NeuralIF uses neural networks to improve preconditioning for faster CG convergence.
problem Improving convergence of conjugate gradient method for large-scale sparse systems.
method Data-driven approach using graph neural networks to generate incomplete factorization.
result Data-driven preconditioners accelerate convergence of conjugate gradient method.
A new method improves convergence in low-rank approximation.
problem Efficiently solving large-scale numerical linear algebra problems.
method Error-Powered Sketched Inverse Iteration (EPSI) Method.
result Convergence rate improves at least linearly with sketch size.
We propose a novel Riemannian manifold preconditioning approach for the tensor completion problem with rank constraint. A novel Riemannian metric or inner product is proposed that exploits the least-squares structure of the cost function and takes into account the structured symmetry that exists in Tucker decomposition…
New method speeds up solving orthogonality constrained problems.
problem Solving orthogonality constrained problems efficiently.
method Riemannian optimization and Riemannian preconditioning.
result Preconditioning improves computational costs and convergence.
Muon optimizer simplifies matrix optimization with spectral orthogonalization.
problem Matrix optimization challenges, especially with large condition numbers.
method Simplified Muon optimizer using spectral orthogonalization of gradients.
result Simplified Muon converges linearly with independent scalar sequences, outperforming gradient descent and Adam.
In this paper, we analyze different preconditionings designed to enhance robustness of pure-pixel search algorithms, which are used for blind hyperspectral unmixing and which are equivalent to near-separable nonnegative matrix factorization algorithms. Our analysis focuses on the successive projection algorithm (SPA), …
A note relating ridge regression and OLS p-values to preconditioned sparse penalized regressionstat.ML
When the design matrix has orthonormal columns, "soft thresholding" the ordinary least squares (OLS) solution produces the Lasso solution [Tibshirani, 1996]. If one uses the Puffer preconditioned Lasso [Jia and Rohe, 2012], then this result generalizes from orthonormal designs to full rank designs (Theorem 1). Theorem …
The study characterizes the conditioning of the Gauss-Newton matrix in neural networks.
problem Understanding the conditioning of the Gauss-Newton matrix in neural networks.
method Theoretical analysis of the GN matrix in deep linear and ReLU networks, extending to residual connections and convolutional layers.
result Established tight bounds on the condition number of the GN matrix in neural networks.
AI-driven framework optimizes MCMC-based preconditioners for faster linear system solving.
problem Slow convergence of Krylov subspace solvers for ill-conditioned matrices.
method Graph neural surrogate and Bayesian optimization for AI-tuned MCMC parameters.
result 50% reduction in iterations to convergence on unseen system.
The successive projection algorithm (SPA) can quickly solve a nonnegative matrix factorization problem under a separability assumption. Even if noise is added to the problem, SPA is robust as long as the perturbations caused by the noise are small. In particular, robustness against noise should be high when handling th…
KrADagrad: Kronecker Approximation-Domination Gradient Preconditioned Stochastic Optimizationstat.ML
A new optimization method reduces memory and compute requirements for deep learning.
problem Memory and compute constraints in second-order stochastic optimizers for deep learning.
method Proposes KrAD, a novel factorization to approximate inverse Fisher matrix without inversion, leading to KrADagrad.
result Improves performance over Shampoo for 32-bit precision and comparable/generalization on real datasets.
We study the property of the Fused Lasso Signal Approximator (FLSA) for estimating a blocky signal sequence with additive noise. We transform the FLSA to an ordinary Lasso problem. By studying the property of the design matrix in the transformed Lasso problem, we find that the irrepresentable condition might not hold, …
The paper explores how dynamic preconditioning affects the CLT in online averaging.
problem When does dynamic preconditioning preserve the Polyak-Ruppert CLT?
method The authors decompose the averaged error and identify a stabilization-rate threshold for the CLT to hold.
result The CLT holds if the dynamic remainder vanishes in and the stabilization rate exceeds a threshold.
PrecGD restores linear convergence in over-parameterized nonconvex matrix factorization.
problem Slow convergence of local search algorithms in over-parameterized nonconvex matrix factorization.
method Preconditioned Gradient Descent (PrecGD) with an inexpensive regularization.
result PrecGD restores linear convergence rate even in the over-parameterized case.
New research shows how preconditioning can solve sparse linear regression problems efficiently.
problem Efficiently solving sparse linear regression problems without restrictive conditions.
method Preconditioned Lasso approach to solve sparse linear regression problems.
result Preconditioning can solve a large class of sparse linear regression problems nearly optimally.
The computational and storage complexity of kernel machines presents the primary barrier to their scaling to large, modern, datasets. A common way to tackle the scalability issue is to use the conjugate gradient algorithm, which relieves the constraints on both storage (the kernel matrix need not be stored) and computa…
Ginger: An Efficient Curvature Approximation with Linear Complexity for General Neural Networkscs.LG
Ginger efficiently approximates curvature with linear complexity for neural networks.
problem Quadratic memory and cubic time complexity for computing curvature matrices in deep learning.
method Ginger uses eigendecomposition to maintain the inverse of the generalized Gauss-Newton matrix, achieving linear memory and time complexity.
result Ginger provides an effective and efficient curvature approximation for non-convex objectives.
We analyze a compression scheme for large data sets that randomly keeps a small percentage of the components of each data sample. The benefit is that the output is a sparse matrix and therefore subsequent processing, such as PCA or K-means, is significantly faster, especially in a distributed-data setting. Furthermore,…
Bayesian sparse learning method improves deep neural network efficiency.
problem Sparse learning in deep neural networks with complex geometry.
method Preconditioned stochastic gradient Langevin Dynamics (PSGLD) for sampling and adaptive optimization of hyperparameters.
result The proposed algorithm achieves asymptotic convergence with controlled bias.
Gradient descent converges geometrically to optimal self-attention parameters.
problem Training softmax self-attention layers for linear regression.
method Structure-aware gradient descent with preconditioner and regularizer.
result Gradient descent converges geometrically to global minima.
Boosts linear neurons for faster convergence in neural networks.
problem Optimizing neural networks' neurons in function space.
method Reparameterizing network to whiten neuron features using Boosted Backpropagation.
result Equivalent to preconditioned gradient descent, leading to faster convergence.
One way to avoid overfitting in machine learning is to use model parameters distributed according to a Bayesian posterior given the data, rather than the maximum likelihood estimator. Stochastic gradient Langevin dynamics (SGLD) is one algorithm to approximate such Bayesian posteriors for large models and datasets. SGL…
Multiresolution Matrix Factorization (MMF) was recently introduced as a method for finding multiscale structure and defining wavelets on graphs/matrices. In this paper we derive pMMF, a parallel algorithm for computing the MMF factorization. Empirically, the running time of pMMF scales linearly in the dimension for spa…
New MCMC method learns sparse preconditioner for high-dimensional problems.
problem High-dimensional sampling with complex correlation structures.
method Adaptive MCMC with sparse preconditioner using online PCA.
result Significant reduction in computational complexity and improved performance.
RL accelerates portfolio optimization and option pricing by dynamically adjusting preconditioner sizes.
problem Large linear systems in portfolio optimization and option pricing lead to slow convergence.
method Reinforcement Learning (RL) dynamically adjusts block-preconditioner sizes to accelerate convergence.
result RL-driven solver significantly reduces computational cost and accelerates convergence.
Gradient descent with preconditioning finds global optima in overparameterized nonconvex factorization.
problem Finding global optima in nonconvex Burer-Monteiro factorization.
method Preconditioned gradient descent for overparameterized nonconvex function minimization.
result Gradient descent with preconditioning achieves linear convergence in the overparameterized case.
New analysis of Muon and SignSGD on matrix-valued least squares problems.
problem Understanding the behavior of Muon and SignSGD on matrix-valued least squares problems.
method Derive explicit deterministic dynamics to study learning behavior of Muon and SignSGD.
result Muon and SignSGD exhibit different optimal learning rates and convergence characteristics based on batch size and data covariance.