Gradient descent proves global convergence for 4-layer matrix factorization.
problem Global convergence of gradient descent on four-layer matrix factorization under random initialization.
method New techniques to show saddle-avoidance properties and extend eigenvalue theories.
result Polynomial-time global convergence guarantee for randomly initialized gradient descent on four-layer matrix factorization.
Gradient descent achieves exact linear convergence rate for symmetric matrix completion.
problem Low-rank symmetric matrix completion using gradient descent.
method Local analysis of gradient descent for symmetric matrices without additional assumptions.
result Closed-form expression of exact linear convergence rate matches practice.
ScaledGD improves gradient descent for ill-conditioned low-rank matrix estimation.
problem Efficiently solving ill-conditioned low-rank matrix estimation problems.
method Scaled Gradient Descent (ScaledGD) with adaptive pre-conditioners.
result Linear convergence rate independent of condition number, low per-iteration cost.
Paper studies asymmetric matrix sensing, proving gradient descent converges to low-rank solutions.
problem Reconstructing asymmetric low-rank matrices from linear measurements.
method Factorized gradient descent with coupling and regularization properties.
result Gradient descent from small random initialization converges to globally optimal and generalizing solutions.
Paper shows robustness of gradient descent in matrix sensing despite perturbations.
problem Understanding robustness of gradient descent in matrix sensing.
method Developed perturbed gradient flow to capture noise and improve robustness.
result Gradient descent is robust to perturbations in matrix sensing.
The paper examines how gradient descent stabilizes low-rank matrix factorization in noisy conditions.
problem Stability of low-rank implicit regularization in perturbed deep matrix factorization.
method Derives spectral conditions for gradient descent to exhibit a low-rank phase in noiseless settings and analyzes perturbed dynamics.
result Gradient descent converges to a low-rank solution under perturbation, with explicit dependence on perturbation size.
New approach to analyze matrix denoising using gradient flow and fixed point equations.
problem Positive semi-definite matrix denoising in extensive-rank and high-dimensional settings.
method Gradient flow and fixed point equations derived from linear pencil techniques of random matrix theory.
result Continuous phase transitions in the extensive-rank and high-dimensional regime.
Gradient descent recovers principal components of overparametrized asymmetric matrices without explicit regularization.
problem Asymmetric matrix factorization under overparametrization with minimal rank assumptions.
method Vanilla gradient descent with small random initialization and proper early stopping.
result Gradient descent produces the best low-rank approximation without explicit regularization.
Gradient descent solves asymmetric low-rank matrix sensing without balancing.
problem Recovering asymmetric low-rank matrices from linear measurements.
method Gradient descent with spectral initialization, avoiding balancing term.
result Gradient descent converges linearly without balancing, factors stay balanced.
Adaptive algorithm improves convergence rate of Langevin dynamics.
problem Improving convergence rate of Langevin dynamics.
method Adaptive non-reversible stochastic gradient Langevin dynamics algorithm.
result Improved convergence rate of the algorithm.
Gradient descent solves rank-one matrix estimation problem with detailed time evolution analysis.
problem Estimating a rank-one symmetric matrix corrupted by noise.
method Gradient descent on a sphere, using local versions of the semi-circle law.
result Explicit formulas for the time evolution of the estimator and cost function, revealing phase transitions.
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 ℓ2 regularization. result PrecGD restores linear convergence rate even in the over-parameterized case.
NG+ method improves deep learning efficiency and accuracy.
problem Efficiency and accuracy in deep learning models.
method Proposes NG+ method using matrix-product natural gradient approach.
result Established global convergence and provided regret bound.
A deep neural network is a hierarchical nonlinear model transforming input signals to output signals. Its input-output relation is considered to be stochastic, being described for a given input by a parameterized conditional probability distribution of outputs. The space of parameters consisting of weights and biases i…
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.
A1GM method improves efficiency in reconstructing missing data using KL divergence.
problem Efficiently reconstructing missing data in matrices.
method Fast non-gradient-based rank-1 NMF using KL divergence.
result A1GM outperforms gradient methods in efficiency with competitive reconstruction errors.
NGD improves multivariate Gaussian inference by optimizing Fisher information.
problem Efficiently optimizing multivariate Gaussian models.
method Natural Gradient Descent applied to multivariate Gaussian parameters.
result NGD updates are more efficient for symmetric covariance matrices.
GD with large init shows incremental learning in matrix factorization.
problem Understanding GD's behavior with large initial values in matrix factorization.
method Signal-to-noise ratio concepts and inductive arguments.
result Uncovering an incremental learning phenomenon in GD with large initialization.
In this paper, the Riemannian gradient algorithm and the natural gradient algorithm are applied to solve descent direction problems on the manifold of positive definite Hermitian matrices, where the geodesic distance is considered as the cost function. The first proposed problem is control for positive definite Hermiti…
We address the rectangular matrix completion problem by lifting the unknown matrix to a positive semidefinite matrix in higher dimension, and optimizing a nonconvex objective over the semidefinite factor using a simple gradient descent scheme. With O(μr2κ2nmax(μ,logn)) random observations of a $n_1 \times n…
Riemannian gradient descent escapes some spurious critical points on low-rank matrix manifold.
problem Spurious critical points on the boundary of low-rank matrix manifold.
method Riemannian gradient descent with dynamical low-rank approximation and rescaled gradient flow.
result Riemannian gradient descent escapes some spurious critical points on the boundary of the manifold.
Develops accelerated methods for optimization using low-dimensional projected-gradient information.
problem Optimization with low-dimensional projected-gradient information and Nesterov acceleration.
method Randomized-subspace Nesterov accelerated gradient methods for smooth convex and strongly convex optimization.
result Established accelerated oracle-complexity guarantees and unified basis for comparing sketch families.
Gradient descent with noise converges to a unique optimum in nonconvex matrix factorization.
problem Gradient descent with noise converges to a unique optimum in nonconvex matrix factorization.
method A perturbed form of gradient descent with arbitrary initialization.
result Gradient descent with noise converges to a unique optimum.
Improved heat equation estimates without gradient curvature assumption.
problem Improving Hamilton's matrix Harnack estimate for heat equation without gradient curvature assumption.
method New ingredients include a sharp Li-Yau estimate, a suitable vector field construction, and integral arguments.
result Removed the gradient curvature assumption in Hamilton's estimate for heat equation.
We propose a generic framework based on a new stochastic variance-reduced gradient descent algorithm for accelerating nonconvex low-rank matrix recovery. Starting from an appropriate initial estimator, our proposed algorithm performs projected gradient descent based on a novel semi-stochastic gradient specifically desi…
Gradient flow with infinitesimal initialization converges to Greedy Low-Rank Learning for matrix factorization.
problem Understanding implicit regularization in gradient descent for matrix factorization.
method Theoretical and empirical analysis of gradient flow with infinitesimal initialization and Greedy Low-Rank Learning.
result Gradient flow with infinitesimal initialization is mathematically equivalent to Greedy Low-Rank Learning for depth-2 matrix factorization under reasonable assumptions.
New method improves robust low-rank matrix completion for computer vision.
problem Robust low-rank matrix completion for partially observed data.
method Formulated as a nonsmooth Riemannian optimization problem over Grassmann manifold, solved with an alternating manifold proximal gradient continuation method.
result Demonstrated advantages over existing approaches in background extraction from surveillance videos.
Gradient descent solves asymmetric low-rank matrix factorization efficiently.
problem Optimizing asymmetric low-rank matrix factorization with non-convex and non-smoothness issues.
method Randomly initialized gradient descent with new symmetrization and perturbation techniques.
result Gradient descent converges to a global minimum of the asymmetric low-rank factorization problem.
Efforts to understand the generalization mystery in deep learning have led to the belief that gradient-based optimization induces a form of implicit regularization, a bias towards models of low "complexity." We study the implicit regularization of gradient descent over deep linear neural networks for matrix completion …
LDA-GO improves LDA for high-dimensional data via gradient optimization.
problem LDA struggles in high-dimensional settings due to unreliable covariance matrix estimation.
method LDA-GO learns a low-rank precision matrix via gradient optimization, automatically selecting between Gaussian likelihood and cross-entropy loss.
result LDA-GO outperforms other LDA variants in sparse-signal high-dimensional regimes.
Gradient flow solves optimal mass transport for covariance matrices.
problem Optimal mass transport for covariance matrices.
method Gradient flow on fiber bundle structure.
result Global convergence to polar decomposition.
Optimization problems with rank constraints arise in many applications, including matrix regression, structured PCA, matrix completion and matrix decomposition problems. An attractive heuristic for solving such problems is to factorize the low-rank matrix, and to run projected gradient descent on the nonconvex factoriz…
AGD converges in polynomial iterations to optimal matrix factorization.
problem Matrix factorization optimization with alternating gradient descent.
method Alternating gradient descent with fixed step size, proving convergence in polynomial iterations.
result AGD reaches ε-optimal factorization in T iterations with high probability.
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. 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.
MFAI uses gradient boosted trees to leverage auxiliary info for scalable Bayesian matrix factorization.
problem Matrix factorization struggles with poor data quality, especially high sparsity and low SNR.
method Integrates gradient boosted trees into probabilistic matrix factorization framework.
result MFAI effectively leverages auxiliary information, improving model performance.
Gradient descent with large steps leads to chaotic parameter space and unpredictable outcomes.
problem Understanding the behavior of gradient descent with large step sizes in matrix factorization.
method Analyzing the fractal structure of the parameter space and deriving critical step sizes for convergence.
result Gradient descent with large steps exhibits chaotic behavior and sensitivity to initialization, creating a fractal boundary between converging and diverging minimizers.
Natural gradient descent is an optimization method traditionally motivated from the perspective of information geometry, and works well for many applications as an alternative to stochastic gradient descent. In this paper we critically analyze this method and its properties, and show how it can be viewed as a type of 2…
Gradient Descent with small random initialization solves rank-1 matrix completion efficiently.
problem Matrix completion for rank-1 symmetric matrices.
method Gradient Descent with small random initialization.
result Gradient Descent converges to the ground truth for rank-1 symmetric matrix completion.
Gradients help find global optima in complex functions.
problem Finding global optima in functions with many local minima.
method A principle for generating search directions from non-local quadratic approximants based on gradients.
result The proposed algorithm and CMA-ES perform better than random reinitialized BFGS.
An ADRC-incorporated SGD algorithm improves latent factor analysis speed and accuracy.
problem Slow convergence in standard SGD for HDI matrix analysis.
method Incorporates ADRC principles to refine historical and future learning error states.
result Empirically outperforms state-of-the-art LFA models in HDI matrix prediction.
SGD with mini-batches can solve convex low-rank matrix problems efficiently.
problem Solving large-scale convex low-rank matrix problems efficiently.
method Stochastic Gradient Descent with mini-batches and low-rank projections.
result SGD with mini-batches produces low-rank iterates with high probability.
Despite having various attractive qualities such as high prediction accuracy and the ability to quantify uncertainty and avoid over-fitting, Bayesian Matrix Factorization has not been widely adopted because of the prohibitive cost of inference. In this paper, we propose a scalable distributed Bayesian matrix factorizat…
Study proposes memory-efficient backpropagation for linear layers in neural networks.
problem Significant memory usage in backpropagation through linear layers in neural networks.
method Randomized matrix multiplications to reduce memory usage with a moderate decrease in test accuracy.
result Demonstrated benefits of the proposed method on fine-tuning pre-trained models.
GD learns matrix solutions incrementally, revealing insights into generalization.
problem Matrix sensing problem of recovering low-rank matrices from linear measurements.
method Fine-grained analysis of GD dynamics for matrix sensing.
result GD follows an incremental learning procedure, solving matrices of increasing ranks.
We study the problem of estimating low-rank matrices from linear measurements (a.k.a., matrix sensing) through nonconvex optimization. We propose an efficient stochastic variance reduced gradient descent algorithm to solve a nonconvex optimization problem of matrix sensing. Our algorithm is applicable to both noisy and…
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.
We study implicit regularization when optimizing an underdetermined quadratic objective over a matrix X with gradient descent on a factorization of X. We conjecture and provide empirical and theoretical evidence that with small enough step sizes and initialization close enough to the origin, gradient descent on a f…