REVIEW 39 cited by
Handbook of Convergence Theorems for (Stochastic) Gradient Methods
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Handbook of Convergence Theorems for (Stochastic) Gradient Methods
read the original abstract
This is a handbook of simple proofs of the convergence of gradient and stochastic gradient descent type methods. We consider functions that are Lipschitz, smooth, convex, strongly convex, and/or Polyak-{\L}ojasiewicz functions. Our focus is on ``good proofs'' that are also simple. Each section can be consulted separately. We start with proofs of gradient descent, then on stochastic variants, including minibatching and momentum. Then move on to nonsmooth problems with the subgradient method, the proximal gradient descent and their stochastic variants. Our focus is on global convergence rates and complexity rates. Some slightly less common proofs found here include that of SGD (Stochastic gradient descent) with a proximal step, with momentum, and with mini-batching without replacement.
Forward citations
Cited by 39 Pith papers
-
Random Reshuffling Dominates Stochastic Gradient Descent
RR dominates SGD in smooth convex optimization under any reasonable stepsize after any finite number of epochs.
-
Unified convergence analysis for gradient descent optimization methods in the training of deep neural networks
Bounded trajectories of a broad class of GD optimizers (Adam, RMSprop, NAG, Adan, etc.) converge with polynomial rates to critical points of KL objectives with locally Lipschitz gradients, covering analytic-activation...
-
Effective dynamics of the Sinkhorn algorithm in the regime of low entropy regularization
Derives the cold Sinkhorn limiting dynamics as tau approaches zero, proving finite-time convergence to unregularized OT and improved O(tau^{-1}) iteration complexity for dual suboptimality.
-
Sharp $O(1/k)$ convergence rate for the Sinkhorn algorithm via a local analysis
Proves sharp O(1/k) rate for Sinkhorn via local bipartite graph analysis of positive-mass edges, bootstrapped from prior almost-sharp global bound.
-
Stochastic Krasnoselskii-Mann Iterations: Convergence without Uniformly Bounded Variance
Stochastic Krasnoselskii-Mann iterations converge almost surely and with rates under finite variance at a single fixed point rather than uniform variance bounds, recovering optimal complexity and providing first such ...
-
Stochastic Krasnoselskii-Mann Iterations: Convergence without Uniformly Bounded Variance
Stochastic Krasnoselskii-Mann iterations converge almost surely weakly with finite variance only at a single fixed point, recovering best-known rates without uniform variance bounds.
-
Stochastic Gradient Variational Inference with Price's Gradient Estimator from Bures-Wasserstein to Parameter Space
Price's gradient estimator enables black-box VI to achieve the same state-of-the-art iteration complexity as Wasserstein VI, with experiments confirming it as the main performance driver.
-
Convergence Rates for Distribution Matching with Sliced Optimal Transport
For Gaussian distributions, slice-matching to an isotropic target with decaying step sizes converges at rate O(k^{-(2α-1)}) in expectation.
-
On the Convergence Rate of LoRA Gradient Descent
LoRA gradient descent converges to a stationary point at rate O(1/log T).
-
SketchGuard: Scaling Byzantine-Robust Decentralized Federated Learning via Sketch-Based Screening
SketchGuard decouples Byzantine filtering from aggregation in decentralized federated learning by exchanging k-dimensional Count Sketches for screening and full models only from accepted neighbors, achieving up to 50-...
-
How does the optimizer implicitly bias the model merging loss landscape?
Effective noise scale non-monotonically governs model merging success with an optimum, unifying effects of learning rate, weight decay, batch size, and augmentation on the loss landscape.
-
Highly Data Parallelizable Estimation of the Sliced-Wasserstein Distance Using Cumulative Distribution Functions
New class of CDF-based estimators for sliced Wasserstein distance avoids sorting, enables massive parallelism, and suits federated learning and Gaussian mixture models.
-
Stochastic Gradient Optimization with Model-Assisted Sampling
Model-assisted sampling applies survey sampling variance reduction with auxiliary predictors to stochastic gradients, yielding empirical gains on benchmarks and faster generalization with AdamW.
-
Randomized conjugate gradient least squares
RCGLS replaces the gradient in CGLS with a randomized coordinate version via a constraint correction view, proving linear convergence in expectation better than randomized coordinate descent, plus sparse implementatio...
-
Factor Augmented High-Dimensional SGD
Proposes Factor-Augmented SGD that runs on streaming high-dimensional data and supplies the first convergence analysis explicitly accounting for latent-factor estimation error.
-
Distributed Learning with Adversarial Gradient Perturbations
Tight feasibility thresholds are derived for the minimal sub-optimality gap in convex L-smooth distributed optimization under bounded adversarial gradient perturbations, together with algorithms attaining them at matc...
-
One Coordinate at a Time: Convergence Guarantees for Rotosolve in Variational Quantum Algorithms
Rotosolve converges to ε-stationary points for smooth non-convex objectives and ε-suboptimal points under PL, with explicit worst-case rates in the finite-shot regime, outperforming or matching RCD in nuanced ways.
-
Mini-Batch Stochastic Krasnosel'ski\u\i-Mann Algorithm for Nonexpansive Fixed Point Problems
A mini-batch stochastic Krasnosel'skiĭ-Mann algorithm converges almost surely to fixed points of nonexpansive mappings when batch sizes increase appropriately.
-
Step-Size Stability in Stochastic Optimization: A Theoretical Perspective
The stability index δ_t, the variance term in a two-term suboptimality bound, is provably smaller and saturates in the step-size cap for SPS, NGN, and proximal point, explaining their observed learning-rate robustness...
-
Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participation
D-Byz-SGDM aggregates cached momentum from non-sampled clients together with fresh momentum from sampled clients, preserving Byzantine robustness under partial participation and achieving an optimal O(cδζ²/p) stationa...
-
A Sketch-and-Project Analysis of Subsampled Natural Gradient Algorithms
For linear least squares, SNGD and SPRING are proved equivalent to accelerated regularized Kaczmarz methods, yielding the first fast rates and first SPRING guarantee; the general quadratic analysis holds under strong ...
-
Constrained free energy minimization for the design of thermal states and stabilizer thermodynamic systems
Benchmarks gradient-ascent algorithms for constrained free energy minimization on quantum Heisenberg models and stabilizer codes, with applications to thermal state design and fixed-temperature quantum encoding.
-
On subspace-constrained preconditioning for randomized iterative methods
Refines subspace preconditioning for randomized linear solvers via QR-like factorization, enabling implicit use and proving expected linear convergence while reducing to a smaller system with good singular values.
-
Accelerated Dynamic Importance Weighting with Versatile Divergence-Minimizing Estimators
ADIW accelerates dynamic importance weighting for joint distribution shift by using a few lightweight projected gradient descent updates with warm-starting from prior weights and generalizes it to support multiple div...
-
COOPO: Cyclic Offline-Online Policy Optimization Algorithm
COOPO is a cyclic offline-online RL algorithm that repeatedly anchors the policy to a dataset via KL-regularized updates then fine-tunes online, claiming better sample efficiency and monotonic improvement under covera...
-
Optimal Asymptotic Rates for (Stochastic) Gradient Descent under the Local PL-Condition: A Geometric Approach
Under the local PL condition with multiplicative noise for C² functions, (S)GD asymptotic rates match those of strongly convex quadratics via a geometric argument.
-
Complex Stochastic Gradient Descent and Directional Bias in Reproducing Kernel Hilbert Spaces
Complex SGD using Wirtinger calculus achieves convergence guarantees paralleling the real-valued setting without analyticity assumptions, and directional bias results extend to complex kernel regression.
-
Complex Stochastic Gradient Descent and Directional Bias in Reproducing Kernel Hilbert Spaces
Complex SGD converges without analyticity constraints and extends real-valued directional bias results to complex RKHS, with demonstrations on Fock and Hardy spaces.
-
HTMuon: Improving Muon via Heavy-Tailed Spectral Correction
HTMuon modifies Muon to produce heavier-tailed updates and weight spectra via HT-SR theory, yielding up to 0.98 lower perplexity on LLaMA pretraining and serving as a plug-in for other Muon variants.
-
Accelerated optimization of measured relative entropies
Measured relative entropies can be computed by Nesterov accelerated gradient descent/ascent because their variational objective functions are smooth and strongly convex/concave.
-
Balancing Utility and Privacy: Dynamically Private SGD with Random Projection
D2P2-SGD combines time-decreasing privacy noise with random projection to improve the accuracy of differentially private SGD, with convergence rates matching ordinary SGD.
-
Stochastic versus Deterministic in Stochastic Gradient Descent
Treating stochastic and deterministic gradients separately in mini-batch SGD yields faster convergence and smaller error radius than uniform treatment, with further gains under strong convexity.
-
On the Convergence Analysis of Muon
Convergence analysis shows Muon outperforms gradient descent by exploiting low-rank structure in neural network Hessians.
-
FOAM: Frequency and Operator Error-Based Adaptive Damping Method for Reducing Staleness-Oriented Error for Shampoo
FOAM adaptively controls damping and update frequency in Shampoo based on staleness-oriented error approximation to cut wall-clock time while preserving convergence.
-
Accelerated Gradient Descent for Faster Convergence with Minimal Overhead
CT-AGD accelerates first-order optimization in deep learning by using finite-difference curvature estimates and noise-mitigation heuristics, achieving equivalent accuracy with 33% fewer training epochs and overhead co...
-
Efficient Stochastic Optimisation via Sequential Monte Carlo
Sequential Monte Carlo samplers can approximate intractable gradients inside a first-order optimizer, yielding a general SOSMC framework that speeds up reward tuning of energy-based models in the reported settings.
-
How AI settled the complexity of the oldest SGD algorithm
AI models discovered the worst-case complexity of the Kaczmarz algorithm for solving linear systems.
-
Design Criteria for SGD Preconditioners: Local Conditioning, Noise Floors, and Basin Stability
The late-stage noise floor of preconditioned SGD is the product of the M-metric condition number and the preconditioned noise level, so the design goal is to improve conditioning while dampening noise.
-
Introduction to optimization methods for training SciML models
A tutorial review of optimization for SciML that explains PDE-induced stiffness through the NTK/Hessian spectrum and surveys adaptive sampling, second-order, and preconditioning methods.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.