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,742 papers · 148 categories

Trend · papers per month

count % of corpus

48 results for “Gradient Convergence”

A Methodology Establishing Linear Convergence of Adaptive Gradient Methods under PL Inequalitycs.LG

This paper proves AdaGrad and Adam converge linearly under PL inequality.

problem Understanding the convergence of adaptive gradient methods.

method Unified approach proving AdaGrad and Adam converge linearly under PL inequality.

result AdaGrad and Adam converge linearly when the cost function is smooth and satisfies PL inequality.

adaptive gradient methods AdaGrad Adam linear convergence Polyak-Łojasiewicz inequality

2024-07-17abs ↗pdf ↗

Revisiting Gradient Clipping: Stochastic bias and tight convergence guaranteescs.LG

This paper improves convergence guarantees for gradient clipping in deep learning.

problem Improving convergence guarantees for gradient clipping in deep learning models.

method Analyzes and provides precise convergence guarantees for arbitrary clipping thresholds.

result Shows tight convergence guarantees for clipped stochastic gradient descent.

gradient clipping deep learning convergence guarantees stochastic gradient descent privacy

2023-05-02abs ↗pdf ↗

Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix Completion via Gradient Descentmath.OC

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.

gradient descent matrix completion symmetric matrices low-rank linear convergence

2021-02-04abs ↗pdf ↗

On the Convergence of Adaptive Gradient Methods for Nonconvex Optimizationcs.LG

Adaptive gradient methods are workhorses in deep learning. However, the convergence guarantees of adaptive gradient methods for nonconvex optimization have not been thoroughly studied. In this paper, we provide a fine-grained convergence analysis for a general class of adaptive gradient methods including AMSGrad, RMSPr…

2018-08-16abs ↗pdf ↗

The convergence of the Stochastic Gradient Descent (SGD) : a self-contained proofstat.ML

Proof given for SGD convergence in a concise manner.

problem Convergence of Stochastic Gradient Descent (SGD)

method Self-contained proof

result SGD convergence proven

Stochastic Gradient Descent Convergence Proof Machine Learning

2021-03-26abs ↗pdf ↗

Optimization Guarantees for Square-Root Natural-Gradient Variational Inferencecs.LG

Square-root natural-gradient improves variational inference convergence.

problem Challenges in establishing theoretical convergence guarantees for natural-gradient descent.

method Square-root parameterization for Gaussian covariance.

result Establishes novel convergence guarantees for natural-gradient Gaussian inference.

variational inference natural-gradient convergence guarantees square-root parameterization Gaussian covariance

2025-07-10abs ↗pdf ↗

On the Convergence of Multicalibration Gradient Boostingcs.LG

The paper provides convergence guarantees for multicalibration gradient boosting.

problem Understanding the convergence properties of multicalibration gradient boosting.

method Computational guarantees for multicalibration gradient boosting algorithms, including adaptive variants.

result The magnitude of successive prediction updates decays at

O(1/\sqrt{T})

, leading to convergence in empirical multicalibration error.

multicalibration gradient boosting convergence empirical error smoothness assumptions

2026-02-06abs ↗pdf ↗

Stochastic Gradient Descent Revisitedmath.OC

Studied SGD convergence under weak conditions.

problem Convergence of SGD in nonconvex optimization.

method Analyzed biased nonconvex SGD under mild conditions.

result Provided convergence rates and complexities.

stochastic gradient descent nonconvex optimization convergence analysis weak conditions

2024-12-08abs ↗pdf ↗

On Linear Convergence of Policy Gradient Methods for Finite MDPscs.LG

Policy gradient methods achieve linear convergence in simple MDPs.

problem Analyzing convergence rates of policy gradient methods in finite MDPs.

method Connections with policy iteration to show linear convergence with large step-sizes.

result Policy gradient methods succeed with large step-sizes and achieve linear rate of convergence.

policy gradient policy iteration finite MDPs linear convergence

2020-07-21abs ↗pdf ↗

A Novel Stochastic Stratified Average Gradient Method: Convergence Rate and Its Complexitycs.LG

SGD (Stochastic Gradient Descent) is a popular algorithm for large scale optimization problems due to its low iterative cost. However, SGD can not achieve linear convergence rate as FGD (Full Gradient Descent) because of the inherent gradient variance. To attack the problem, mini-batch SGD was proposed to get a trade-o…

2017-10-21abs ↗pdf ↗

Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradientsmath.OC

New method for natural policy gradients converges linearly.

problem Improving natural policy gradient methods for better convergence.

method Fisher-Rao gradient flow applied to state-action distributions.

result Linear convergence rate with geometry-dependent factor.

natural policy gradients Fisher-Rao gradient flow linear convergence state-action distributions

2024-03-28abs ↗pdf ↗

Toward Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixture Modelscs.LG

Gradient EM converges globally for over-parameterized Gaussian mixtures.

problem Global convergence of gradient EM for Gaussian mixtures with more than 2 components.

method Likelihood-based convergence analysis framework.

result Gradient EM converges globally with a sublinear rate of O(1/√t).

Gaussian Mixture Models Gradient EM Over-parameterized Global Convergence Sublinear Rate

2024-06-29abs ↗pdf ↗

Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Accelerationcs.LG

Paper explores whether gradient normalization can replace clipping for SGD in heavy-tailed noise.

problem Ensuring convergence of SGD in heavy-tailed noise.

method Revisits gradient clipping and normalization, proving their sufficiency and effectiveness.

result Gradient normalization alone is sufficient for nonconvex SGD convergence under smoothness assumptions.

SGD Gradient Clipping Gradient Normalization Heavy-Tailed Noise Nonconvex Optimization

2024-10-21abs ↗pdf ↗

Gradient Descent Converges Linearly to Flatter Minima than Gradient Flow in Shallow Linear Networkscs.LG

GD converges faster to flatter minima than gradient flow in shallow networks.

problem Understanding the dynamics of gradient descent in shallow linear networks.

method Analyzing the convergence rate and solution of gradient descent in depth-2 linear neural networks.

result GD converges linearly to flatter minima than gradient flow, even with large step sizes.

gradient descent shallow neural networks linear dynamics flatter minima implicit regularization

2025-01-15abs ↗pdf ↗

On the Convergence of Gradient Descent in GANs: MMD GAN As a Gradient Flowcs.LG

Gradient descent on MMD GAN parameter space converges globally to target distribution.

problem Convergence of gradient descent in Maximum Mean Discrepancy (MMD) GANs.

method Proposes a parametric kernelized gradient flow that mimics the min-max game in gradient regularized MMD GAN.

result Gradient descent on the generator's parameter space in gradient regularized MMD GAN is globally convergent to the target distribution under certain conditions.

Gradient Descent Maximum Mean Discrepancy (MMD)Generative Adversarial Networks (GANs)Statistical Manifold Riemannian Structure

2020-11-04abs ↗pdf ↗

Convergence of Sobolev gradient trajectories to elasticamath.AP

Gradient flow of elastic energy converges to elastica.

problem Optimizing closed curves to minimize elastic energy.

method Proving the existence of a unique global solution and convergence via Łojasiewicz--Simon gradient inequality.

result Convergence to elastica established for the

H^2(ds)

-gradient flow of modified elastic energy.

gradient flow closed curves elastic energy Łojasiewicz--Simon inequality elastica

2021-07-14abs ↗pdf ↗

Iterative Pre-Conditioning for Expediting the Gradient-Descent Method: The Distributed Linear Least-Squares Problemmath.OC

Paper proposes a pre-conditioning technique to speed up gradient-descent convergence in distributed linear least-squares problems.

problem Expediting convergence of gradient-descent method for ill-conditioned distributed linear least-squares problems.

method Iterative pre-conditioning technique to improve convergence rate of gradient-descent method.

result Pre-conditioned gradient-descent achieves superlinear convergence for unique solutions and improved linear convergence otherwise.

gradient-descent pre-conditioning distributed learning linear least-squares convergence rate

2020-08-06abs ↗pdf ↗

Anytime Acceleration of Gradient Descentcs.LG

This work accelerates gradient descent with anytime convergence guarantees.

problem Improving the convergence rate of gradient descent methods.

method Proposes a stepsize schedule for gradient descent that achieves anytime convergence rates.

result Gradient descent can achieve convergence rates of

O(T^{-1.119})

for any stopping time

T

gradient descent acceleration anytime convergence COLT open problem smooth convex optimization

2024-11-26abs ↗pdf ↗

On the Global Convergence Rates of Softmax Policy Gradient Methodscs.LG

Softmax policy gradient methods converge at $O(1/t)$ rate with constants depending on problem and initialization.

problem Understanding convergence rates of softmax policy gradient methods in tabular settings.

method Analysis of softmax policy gradient and entropy regularized policy gradient methods, using Łojasiewicz inequality and lower bounds.

result Entropy regularization improves convergence rate from

O(1/t)

O(e^{-c \cdot t})

policy gradient softmax convergence rate Łojasiewicz inequality entropy regularization

2020-05-13abs ↗pdf ↗

Stochastic Gradients under Nuisancesstat.ML

New convergence guarantees for learning with unknown nuisance parameters.

problem Learning problems with unknown nuisance parameters.

method Stochastic gradient optimization with Neyman orthogonality and approximately orthogonalized updates.

result Stochastic gradient algorithms can converge under conditions of nuisance parameters.

stochastic gradient convergence guarantees nuisance parameters Neyman orthogonality approximate orthogonality

2025-08-28abs ↗pdf ↗

Predictive Local Smoothness for Stochastic Gradient Methodscs.LG

Stochastic gradient methods are dominant in nonconvex optimization especially for deep models but have low asymptotical convergence due to the fixed smoothness. To address this problem, we propose a simple yet effective method for improving stochastic gradient methods named predictive local smoothness (PLS). First, we …

2018-05-23abs ↗pdf ↗

Global Convergence of Four-Layer Matrix Factorization under Random Initializationmath.OC

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.

matrix factorization gradient descent global convergence four-layer saddle-avoidance

2025-11-13abs ↗pdf ↗

Policy Gradient Methods Find the Nash Equilibrium in N-player General-sum Linear-quadratic Gamesmath.OC

Policy gradient methods find Nash equilibrium in noisy games.

problem Finding Nash equilibrium in noisy games.

method Policy gradient methods with noise added.

result Policy gradient methods converge to Nash equilibrium in noisy games.

policy gradient Nash equilibrium general-sum games linear-quadratic convergence

2021-07-27abs ↗pdf ↗

Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Datamath.OC

Improved convergence for nonconvex optimization with dependent data.

problem Constrained smooth nonconvex optimization with dependent data.

method Stochastic projected gradient methods under a general dependent data sampling scheme.

result Achieved worst-case rate of convergence

ilde{O}(t^{-1/4})

and complexity

ilde{O}(\varepsilon^{-4})

nonconvex optimization dependent data stochastic gradient constrained optimization convergence rate

2022-03-29abs ↗pdf ↗

Understanding Stochastic Natural Gradient Variational Inferencecs.LG

Improves understanding of stochastic NGVI convergence rates.

problem Lack of knowledge about non-asymptotic convergence rates in stochastic NGVI.

method Proved non-asymptotic convergence rates for conjugate likelihoods and showed implicit optimization for non-conjugate likelihoods.

result First

\mathcal{O}(\frac{1}{T})

non-asymptotic convergence rate for stochastic NGVI in conjugate likelihoods.

stochastic natural gradient variational inference convergence rate non-asymptotic stochastic gradient descent

2024-06-04abs ↗pdf ↗

General Proximal Incremental Aggregated Gradient Algorithms: Better and Novel Results under General Schememath.OC

The incremental aggregated gradient algorithm is popular in network optimization and machine learning research. However, the current convergence results require the objective function to be strongly convex. And the existing convergence rates are also limited to linear convergence. Due to the mathematical techniques, th…

2019-10-11abs ↗pdf ↗

On the Convergence of SGD with Biased Gradientscs.LG

Analyze SGD with biased gradients, improving convergence rates and accuracy.

problem Analyzing the convergence of SGD with biased gradients.

method Derive convergence results for smooth non-convex functions and quantify the impact of bias magnitude.

result Improved rates under the Polyak-Lojasiewicz condition and insights into how bias magnitude affects accuracy and convergence.

SGD Biased Gradients Convergence Polyak-Lojasiewicz Accuracy

2020-07-31abs ↗pdf ↗

Convergence Acceleration via Chebyshev Step: Plausible Interpretation of Deep-Unfolded Gradient Descentcs.LG

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.

Chebyshev steps Convergence acceleration Deep-unfolded gradient descent Gradient descent Iterative algorithms

2020-10-26abs ↗pdf ↗

In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noisemath.OC

Stochastic gradient methods can converge in expectation under heavy-tailed noise.

problem Convergence of stochastic gradient methods under heavy-tailed noise.

method Comprehensive study of stochastic optimization under heavy-tailed noise for

extsf{SGD}

extsf{SMD}

extsf{ASMD}

extsf{SGDM}

in convex and nonconvex optimization.

result Established in-expectation convergence results for various stochastic gradient methods.

stochastic gradient methods heavy-tailed noise convergence stochastic optimization convex optimization

2026-05-30abs ↗pdf ↗

Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecs.LG

Policy gradient methods with actor-critic schemes demonstrate tremendous empirical successes, especially when the actors and critics are parameterized by neural networks. However, it remains less clear whether such "neural" policy gradient methods converge to globally optimal policies and whether they even converge at …

2019-08-29abs ↗pdf ↗

Non-convergence of stochastic gradient descent in the training of deep neural networkscs.LG

SGD fails to converge for deep ReLU networks with limited random initializations.

problem SGD convergence in deep neural networks with limited random initializations.

method Analysis of four discretization parameters: network architecture, training data, gradient steps, and random initializations.

result SGD fails to converge for ReLU networks with depth much larger than width.

stochastic gradient descent deep neural networks ReLU networks convergence failure random initializations

2020-06-12abs ↗pdf ↗

Understanding Gradient Clipping in Private SGD: A Geometric Perspectivecs.LG

Gradient clipping helps private SGD converge despite potential bias.

problem Gradient clipping in private SGD can bias convergence.

method Theoretical analysis and empirical evaluation of gradient clipping effects.

result Gradient clipping can prevent convergence to stationary points and introduces bias.

private SGD gradient clipping differential privacy convergence bias geometric perspective

2020-06-27abs ↗pdf ↗

Unregularized limit of stochastic gradient method for Wasserstein distributionally robust optimizationmath.OC

Study shows convergence of stochastic gradient method for unregularized Wasserstein optimization.

problem Wasserstein distributionally robust optimization under potential distribution shifts.

method Regularized approximation with stochastic gradient methods, convergence analysis.

result Stochastic gradient method converges to subgradients of unregularized objective as regularization vanishes.

Wasserstein optimization distributionally robust stochastic gradient convergence analysis regularization

2025-06-05abs ↗pdf ↗

Exponential Convergence of Gradient Methods in Concave Network Zero-sum Gamescs.LG

Gradient methods converge exponentially in concave network games.

problem Finding Nash equilibria in concave network zero-sum games.

method Gradient Ascent and Optimistic Gradient Ascent analyses.

result Exponential convergence rates in various game settings.

Gradient methods Nash equilibrium Concave games Zero-sum games Convergence rates

2020-07-10abs ↗pdf ↗

Convergence of continuous-time stochastic gradient descent with applications to deep neural networkscs.LG

Continuous-time SGD converges under certain conditions, useful for deep learning.

problem Minimizing population expected loss in learning problems.

method Continuous-time approximation of stochastic gradient descent.

result Establishes sufficient conditions for convergence, applicable to overparametrized neural networks.

continuous-time approximation stochastic gradient descent population expected loss convergence deep learning

2024-09-11abs ↗pdf ↗

Adaptive Non-reversible Stochastic Gradient Langevin Dynamicscs.LG

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.

Langevin dynamics stochastic gradient non-reversible adaptive convergence rate

2020-09-26abs ↗pdf ↗

Gradient Descent-Type Methods: Background and Simple Unified Convergence Analysismath.OC

Explains gradient descent methods and their convergence, focusing on simple analysis.

problem Understanding and analyzing gradient descent methods and their variants.

method Elementary mathematical analysis focusing on structures and assumptions of objective functions.

result Unified convergence analysis of various gradient descent methods and variants.

gradient descent convergence analysis stochastic gradient variance reduction

2022-12-19abs ↗pdf ↗

Linear Convergence of Variance-Reduced Stochastic Gradient without Strong Convexitymath.NA

Stochastic gradient algorithms estimate the gradient based on only one or a few samples and enjoy low computational cost per iteration. They have been widely used in large-scale optimization problems. However, stochastic gradient algorithms are usually slow to converge and achieve sub-linear convergence rates, due to t…

2014-06-04abs ↗pdf ↗

On the Last-Iterate Convergence of Shuffling Gradient Methodscs.LG

New convergence rates for shuffling gradient methods without strong convexity.

problem Theoretical gap between shuffling gradient methods' empirical success and established convergence rates.

method Proved last-iterate convergence rates for shuffling gradient methods using function value gap.

result First last-iterate convergence rates for shuffling gradient methods without strong convexity.

shuffling gradient methods last-iterate convergence function value gap empirical success theoretical guarantee

2024-03-12abs ↗pdf ↗

Bubble-Tree Convergence and Local Diffeomorphism Finiteness for Gradient Ricci Shrinkersmath.DG

Proves convergence of gradient Ricci shrinkers with uniform bounds.

problem Compactness and energy concentration in gradient Ricci shrinkers.

method Bubble-tree convergence and local energy analysis.

result No energy concentrates in neck regions, leading to a local diffeomorphism finiteness theorem.

Gradient Ricci shrinkers Bubble-tree convergence Local diffeomorphism finiteness Uniform entropy bounds

2022-06-14abs ↗pdf ↗

Dual Stochastic Natural Gradient Descent and convergence of interior half-space gradient approximationsmath.OC

Proposes a new stochastic optimization method for MLR models.

problem Slow convergence of SGD in big data scenarios.

method Dual Stochastic Natural Gradient Descent (DNSGD) based on manifold optimization.

result DNSGD converges and has linear computational complexity.

stochastic optimization manifold optimization natural gradient multinomial logistic regression convergence

2020-01-19abs ↗pdf ↗

A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergencecs.GT

Policy gradient method proves convergence in imperfect-information games.

problem Policy gradient methods in imperfect-information games (EFGs).

method Policy gradient approach with best-iterate convergence.

result Policy gradient leads to provable best-iterate convergence in self-play EFGs.

policy gradient reinforcement learning imperfect-information games Nash equilibrium best-iterate convergence

2024-08-01abs ↗pdf ↗

The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancestat.ML

AdaGrad-Norm achieves optimal convergence rates for non-convex objectives without tuning.

problem Optimal convergence rates for non-convex, smooth objectives with adaptive step sizes.

method Adaptive SGD (AdaGrad-Norm) with self-tuning step sizes, analyzing under unbounded gradients and affine variance scaling.

result AdaGrad-Norm achieves order optimal convergence rate of $\mathcal{O}\left(\frac{\mathrm{poly}\log(T)}{\sqrt{T}} ight)$ under optimal assumptions.

AdaGrad SGD Adaptive Optimization Convergence Rates Non-Convex Optimization

2022-02-11abs ↗pdf ↗

Clip21: Error Feedback for Gradient Clippingcs.LG

Clip21 improves convergence of gradient-clipped methods in DP settings.

problem Gradient clipping introduces bias in distributed training, causing convergence issues.

method Clip21 designs an error feedback mechanism to mitigate bias in gradient-clipped methods.

result Clip21 converges at the same rate as distributed gradient descent, improving from previous $\mathcal{O}\left(\frac{1}{\sqrt{K}} ight)$ to $\mathcal{O}\left(\frac{1}{K} ight)$.

gradient clipping differential privacy error feedback distributed training convergence rate

2023-05-30abs ↗pdf ↗

On the Linear Convergence of Policy Gradient under Hadamard Parameterizationmath.OC

Policy gradient converges linearly with Hadamard parameterization in tabular settings.

problem Convergence of policy gradient methods under Hadamard parameterization.

method Studied convergence rate and established linear convergence after

k_0

iterations.

result Algorithm converges linearly with rate $O(rac{1}{k})$ and faster locally after

k_0

policy gradient Hadamard parameterization linear convergence tabular settings local linear convergence

2023-05-31abs ↗pdf ↗

Convergence of Policy Gradient for Entropy Regularized MDPs with Neural Network Approximation in the Mean-Field Regimemath.OC

Study shows policy gradient convergence for entropy-regularized MDPs with neural nets in mean-field regime.

problem Global convergence of policy gradient for entropy-regularized MDPs with neural network approximation.

method Softmax policy with neural network approximation in mean-field regime, gradient flow in 2-Wasserstein metric, exponential convergence under sufficient regularization.

result Gradient flow converges exponentially fast to the unique stationary solution under sufficient regularization.

policy gradient entropy regularization Markov decision processes mean-field regime neural networks

2022-01-18abs ↗pdf ↗

Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Networkcs.LG

Adaptive gradient methods like AdaGrad are widely used in optimizing neural networks. Yet, existing convergence guarantees for adaptive gradient methods require either convexity or smoothness, and, in the smooth setting, only guarantee convergence to a stationary point. We propose an adaptive gradient method and show t…

2019-02-19abs ↗pdf ↗

Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuroncs.LG

Gradient descent slows significantly in over-parameterized single neuron learning.

problem Learning a single neuron with over-parameterization and square loss.

method Analysis of gradient descent dynamics, proving convergence rates and lower bounds.

result Over-parameterization can exponentially slow down the convergence rate of gradient descent.

gradient descent neuron learning over-parameterization ReLU activation global convergence

2023-02-20abs ↗pdf ↗