Cover Image

Bias-Optimal Bounds for SGD: A Computer-Aided Lyapunov Analysis

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cortild, Daniel, Ketels, Lucas, Peypouquet, Juan, Garrigos, Guillaume
Format:	Preprint
Published:	2025
Subjects:	Optimization and Control Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problems
by: Garrigos, Guillaume, et al.
Published: (2025)

Quadratic Objective Perturbation: Curvature-Based Differential Privacy
by: Cortild, Daniel, et al.
Published: (2026)

Global Optimization Algorithm through High-Resolution Sampling
by: Cortild, Daniel, et al.
Published: (2024)

Krasnoselskii-Mann Iterations: Inertia, Perturbations and Approximation
by: Cortild, Daniel, et al.
Published: (2024)

Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity
by: Tyurin, Alexander, et al.
Published: (2024)

The Rich and the Simple: On the Implicit Bias of Adam and SGD
by: Vasudeva, Bhavya, et al.
Published: (2025)

Byzantine-Robust Distributed SGD: A Unified Analysis and Tight Error Bounds
by: Ruan, Boyuan, et al.
Published: (2026)

Online Inventory Problems: Beyond the i.i.d. Setting with Online Convex Optimization
by: Hihat, Massil, et al.
Published: (2023)

Multivariate Online Linear Regression for Hierarchical Forecasting
by: Hihat, Massil, et al.
Published: (2024)

Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies
by: Li, Qiang, et al.
Published: (2024)

A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression
by: Zhang, Yixuan, et al.
Published: (2025)

The Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimization
by: Zhang, Haihan, et al.
Published: (2024)

Optimal Projection-Free Adaptive SGD for Matrix Optimization
by: Kovalev, Dmitry
Published: (2026)

Muon Does Not Converge on Convex Lipschitz Functions
by: Parshakova, Tetiana, et al.
Published: (2026)

Finite-Time Minimax Bounds and an Optimal Lyapunov Policy in Queueing Control
by: Liu, Yujie, et al.
Published: (2025)

Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds
by: Cai, Xufeng, et al.
Published: (2023)

Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD
by: Emmanouilidis, Konstantinos, et al.
Published: (2026)

High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise
by: Kar, Avik, et al.
Published: (2026)

Phases of Muon: When Muon Eclipses SignSGD
by: Paquette, Elliot, et al.
Published: (2026)

Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance
by: Fazla, Arda, et al.
Published: (2026)

A Simplified Analysis of SGD for Linear Regression with Weight Averaging
by: Meterez, Alexandru, et al.
Published: (2025)

ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm
by: Li, Chris Junchi, et al.
Published: (2020)

SGD with Adaptive Preconditioning: Unified Analysis and Momentum Acceleration
by: Kovalev, Dmitry
Published: (2025)

A Minibatch-SGD-Based Learning Meta-Policy for Inventory Systems with Myopic Optimal Policy
by: Lyu, Jiameng, et al.
Published: (2024)

Optimal Growth Schedules for Batch Size and Learning Rate in SGD that Reduce SFO Complexity
by: Umeda, Hikaru, et al.
Published: (2025)

SLowcal-SGD: Slow Query Points Improve Local-SGD for Stochastic Convex Optimization
by: Dahan, Tehila, et al.
Published: (2023)

Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization
by: Jiang, Ruichen, et al.
Published: (2024)

Improved Compression Bounds for Scenario Decision Making
by: Berger, Guillaume O.
Published: (2025)

Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates
by: Kovalev, Dmitry, et al.
Published: (2025)

An Optimal Transport Approach for Computing Adversarial Training Lower Bounds in Multiclass Classification
by: Trillos, Nicolas Garcia, et al.
Published: (2024)

Making SGD Parameter-Free
by: Carmon, Yair, et al.
Published: (2022)

On the Trajectories of SGD Without Replacement
by: Beneventano, Pierfrancesco
Published: (2023)

A Concise Lyapunov Analysis of Nesterov's Accelerated Gradient Method
by: Liu, Jun
Published: (2025)

From PowerSGD to PowerSGD+: Low-Rank Gradient Compression for Distributed Optimization with Convergence Guarantees
by: Xie, Shengping, et al.
Published: (2025)

Dimension-adapted Momentum Outscales SGD
by: Ferbach, Damien, et al.
Published: (2025)

Heavy-Tail Phenomenon in Decentralized SGD
by: Gurbuzbalaban, Mert, et al.
Published: (2022)

Demystifying SGD with Doubly Stochastic Gradients
by: Kim, Kyurae, et al.
Published: (2024)

Verifiable Error Bounds for Physics-Informed Neural Network Solutions of Lyapunov and Hamilton-Jacobi-Bellman Equations
by: Liu, Jun
Published: (2026)

Sign-SGD via Parameter-Free Optimization
by: Medyakov, Daniil, et al.
Published: (2025)

Can SGD Handle Heavy-Tailed Noise?
by: Fatkhullin, Ilyas, et al.
Published: (2025)