Dual Space Preconditioning speeds up gradient descent in overparameterized models.
problem Improving convergence of gradient descent in overparameterized linear models.
method Introducing a novel preconditioner of the form ablaK for convex K and applying it to overparameterized linear models. result The iterates of the preconditioned gradient descent converge to a solution W∞ satisfying XW∞=Y. New algorithm speeds up large-scale statistical inference.
problem Efficiently solving large-scale mean-field variational inference problems.
method Developed a novel primal-dual algorithm (PD-VI) and a block-preconditioned extension (P2D-VI) for mean-field variational inference. result PD-VI and P2D-VI achieve faster convergence and better solution quality compared to existing methods. Sketching techniques have become popular for scaling up machine learning algorithms by reducing the sample size or dimensionality of massive data sets, while still maintaining the statistical power of big data. In this paper, we study sketching from an optimization point of view: we first show that the iterative Hessia…
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.
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…
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.…
Gradient-based MCMC for discrete spaces improves sampling performance.
problem Sampling in discrete spaces using traditional methods is challenging.
method Introduced new discrete Metropolis-Hastings samplers inspired by MALA, with a novel preconditioning technique.
result Demonstrated strong empirical performance across various challenging sampling problems.
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.
Stochastic Gradient Descent improved for various Hilbert scales and misspecified models.
problem Understanding and optimizing SGD in Hilbert scales for machine learning.
method Extending SGD analysis to Hilbert scales, including Sobolev and Diffusion spaces, and showing the effects of smoothness and preconditioning.
result Violation of smoothness assumption affects learning rate; preconditioning in Hilbert scales reduces the number of iterations for misspecified models.
New kernel model scales to large datasets.
problem Challenges in scaling kernel machines to large datasets.
method Introduced EigenPro 3.0, an algorithm based on projected dual preconditioned SGD.
result Ability to scale model and data sizes independently.
pHMC converges on infinite-dimensional spaces with bounds.
problem Convergence of pHMC on Hilbert spaces.
method Coupling of two pHMC copies, adapted from arXiv:1805.00452.
result Proven convergence bounds in 1-Wasserstein distance.
Layer-wise preconditioning methods improve neural network optimization and feature learning.
problem Suboptimal feature learning in standard optimization algorithms.
method Layer-wise preconditioning methods that introduce preconditioners per axis of each layer's weight tensors.
result Layer-wise preconditioning is necessary for provable feature learning in linear and single-index models.
The paper explores efficient sampling for Bayesian wide neural networks.
problem Sampling from posterior distributions of wide neural networks.
method Preconditioned Crank-Nicolson and Langevin algorithms for reparametrised posterior distributions.
result The preconditioned Crank-Nicolson algorithm improves sampling efficiency in wide networks.
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…
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.
TDprop uses Jacobi preconditioning to improve adaptive optimizers in Deep RL.
problem Improving performance of adaptive optimizers in Deep RL.
method TDprop computes per-parameter learning rates based on Jacobi preconditioning of the TD update rule.
result TDprop matches or exceeds Adam's performance in Deep RL experiments, suggesting Jacobi preconditioning can improve adaptive 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.
Effective training of deep neural networks suffers from two main issues. The first is that the parameter spaces of these models exhibit pathological curvature. Recent methods address this problem by using adaptive preconditioning for Stochastic Gradient Descent (SGD). These methods improve convergence by adapting to th…
Preconditioned neural posterior estimation improves reliability in misspecified models.
problem Reliability issues in neural posterior estimation for misspecified models.
method Preconditioning with data-dependent weights and forest-proximity scores to stabilize and improve accuracy.
result Preconditioned robust neural posterior estimation increases stability and accuracy over standard methods.
Improved likelihood-free inference using preconditioned neural posterior estimation.
problem Inaccurate posterior estimation in likelihood-free inference methods.
method Preconditioned Neural Posterior Estimation (PNPE) and Sequential PNPE (PSNPE) methods.
result PNPE and PSNPE improve posterior estimation accuracy over NPE and SNPE.
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.
In this work, we study data preconditioning, a well-known and long-existing technique, for boosting the convergence of first-order methods for regularized loss minimization. It is well understood that the condition number of the problem, i.e., the ratio of the Lipschitz constant to the strong convexity modulus, has a h…
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.
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.
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.
Unified framework for understanding and optimizing training acceleration.
problem Challenges in optimizing training with regularization and acceleration techniques.
method Explains how AdaGrad, RMSProp, and Adam accelerate training, and derives a generalization for L1-regularization. result Derives a unified mathematical framework for understanding and optimizing training acceleration.
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.
New methods solve saddle point problems without line search.
problem Solving saddle point problems efficiently and adaptively.
method Auto-conditioned primal-dual hybrid gradient (AC-PDHG) and auto-conditioned ADMM (AC-ADMM) methods.
result Methods achieve optimal complexity and convergence guarantees.
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.
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.
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.
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), …
New sampling method using regularized Wasserstein proximal for Gibbs distributions.
problem Sampling from Gibbs distributions with numerical stability and efficiency.
method Preconditioned regularized Wasserstein proximal operator.
result Discrete-time convergence analysis and explicit bias characterization.
This work analyzes how preconditioning affects generalization in machine learning models.
problem The impact of preconditioning on the generalization of machine learning models.
method An asymptotic bias-variance decomposition of the generalization error for ridgeless regression under various preconditioners.
result The optimal preconditioner depends on label noise, model specification, and signal alignment, with NGD potentially better under certain conditions.
Paper analyzes Langevin dynamics for solving infinite-dimensional Bayesian inverse problems.
problem Solving high-dimensional Bayesian inverse problems in infinite-dimensional function spaces.
method Preconditioned Langevin dynamics with score-based generative models (SGMs).
result Derives error estimates and sufficient conditions for global convergence in Kullback-Leibler divergence.
Preconditioned NFs speed up sampling from complex posterior distributions in inverse problems.
problem Sampling from posterior distributions of inverse problems with expensive forward operators.
method Preconditioning a conditional normalizing flow (NF) to speed up training.
result Significant speed-ups achieved compared to training NFs from scratch.
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.
New sampling method improves accuracy for constrained spaces.
problem Sampling from constrained convex subsets of R^d.
method Metropolis-adjusted Preconditioned Langevin Algorithm.
result High-accuracy sampling with polylogarithmic error dependence.
A new method reduces complexity of normalizing flows for MCMC preconditioning.
problem Improving sampling efficiency in MCMC algorithms for complex target distributions.
method Factorized preconditioning architecture combining a linear component and a conditional NF.
result Significantly better tail samples and higher effective sample sizes on various distributions.
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…
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. 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…
SignSGD analysis quantifies its effects in high dimensions.
problem Understanding signSGD's effects in high-dimensional settings.
method High-dimensional analysis of signSGD, deriving SDE and ODE for risk.
result Quantification of signSGD's effects: effective learning rate, noise compression, diagonal preconditioning, gradient noise reshaping.
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 …
Stochastic Gradient Langevin Dynamics infuses isotropic gradient noise to SGD to help navigate pathological curvature in the loss landscape for deep networks. Isotropic nature of the noise leads to poor scaling, and adaptive methods based on higher order curvature information such as Fisher Scoring have been proposed t…
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…
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…