Research map / Optimization / Implicit bias and generalization
Controlling the Flow: Stability and Convergence for Stochastic Gradient Descent with Decaying Regularization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes SGD with decaying Tikhonov regularization (reg-SGD) for convex L-smooth functions on Hilbert spaces, proving strong L2 and almost sure convergence to the minimum-norm solution under an ABC-type noise condition, with polynomial-schedule rates and experiments on tomography and ODE inverse problems.
Problem
Standard SGD on convex problems with infinitely many minimizers may converge to an arbitrary solution rather than the minimum-norm one, and its iterates can explode; the paper targets stable convergence to the minimum-norm solution.
Approach
Adds a vanishing Tikhonov term lambda_k X_k to the SGD update; the regularization both pulls iterates toward the minimum-norm solution and keeps iterates almost surely bounded, with step-size and regularization schedules balanced via a Lyapunov energy E_k = f_{lambda_{k+1}}(X_k) - f_{lambda_{k+1}}(x_{lambda_{k+1}}).
Key results
- Reg-SGD with alpha_k=0.1k^{-q}, lambda_k=k^{-p} converges to the minimum-norm solution in L2 and a.s. on the toy example, whereas vanilla SGD does not, though SGD attains a faster optimality gap decay.
- Theoretical L2 rate for polynomial schedules: E[f(X_k)-f(x*)] in O(k^{-min(p,q-p)}); with lambda_k=C k^{-q/2} and alpha_k=C k^{-q}, q in (0,2/3], gives O(k^{-q/2}).
- Under Polyak-Lojasiewicz (xi=1/4), optimal choice p=1/(4xi+3), q=(1+p)/2 gives E||X_k-x*||^2 = O(k^{-2xi/(4xi+3)}).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use reg-SGD with the theoretically optimal schedules (p=1/3, q=2/3) instead of the more aggressive schedules (p=q=2/3) (ablation) | reg-SGD · X-ray tomography | convergence to the minimum-norm solution | Helped |
| Use vanilla SGD instead of reg-SGD with the theoretically optimal schedules | X-ray tomography reconstruction · X-ray tomography | reconstruction feasibility | Hurt |
| Use vanilla SGD instead of reg-SGD | X-ray tomography reconstruction · X-ray tomography | optimality gap | Mixed |
| Use vanilla SGD instead of reg-SGD | ODE-based inverse problem · ODE-based inverse problem | minimum-norm solution error | Hurt |
| Use reg-SGD instead of vanilla SGD | ODE-based inverse problem · ODE-based inverse problem | optimality gap | Mixed |
| Use reg-SGD instead of vanilla SGD | Toy example · Toy example | minimum-norm solution error | Helped |
| Set regularization decay to p=0 instead of p=0.111, with q=0.667 (ablation) | reg-SGD · Toy example | convergence to the minimum-norm solution | Hurt |
| Set regularization decay to p=0.67 instead of p=0.111, with q=0.5 (ablation) | reg-SGD · Toy example | convergence to the minimum-norm solution | Hurt |
| Use schedule (p=0.111, q=0.29) instead of the theory-suggested schedule (p=0.111, q=0.667) (ablation) | reg-SGD · Toy example | variance of minimum-norm solution error | Hurt |
Surprising findings
- Vanilla SGD fails to converge to the minimum-norm solution in the tomography and ODE experiments even though its optimality gap converges faster.
- Iterates of reg-SGD are almost surely bounded without any a priori boundedness assumption on the iterates.
Limitations
- Analysis restricted to smooth convex unconstrained problems
- Rates for general schedules depend on known convergence rate of x_lambda to x_* (source or Lojasiewicz condition)
- Noise assumed to satisfy ABC-type condition with only two constants
Experimental setup
Datasets: synthetic Radon transform image reconstruction (128x128, 32 angles) toy quadratic f(x1,x2)=0.5(x1+x2-1)^2 ODE-based inverse problem (1D elliptic BVP, K=64)
Benchmarks: Radon transform image reconstruction toy quadratic example ODE-based inverse problem
Metrics: expected optimality gap pathwise optimality gap L2 error to minimum-norm solution pathwise squared error to minimum-norm solution
Baselines: vanilla SGD reg-SGD with aggressive schedule
Builds on: stochastic gradient descent Tikhonov regularization ABC noise condition Robbins-Siegmund theorem
Closest papers by meaning
- Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descent (ICML 2022 · similarity 0.91)
- The Implicit Regularization of Dynamical Stability in Stochastic Gradient Descent (ICML 2023 · similarity 0.91)
- Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime (NeurIPS 2025 · similarity 0.89)
- Convergence of Clipped SGD on Convex $(L_0,L_1)$-Smooth Functions (NeurIPS 2025 · similarity 0.89)
- Statistical Guarantees for High-Dimensional Stochastic Gradient Descent (NeurIPS 2025 · similarity 0.89)
- The Global Convergence Time of Stochastic Gradient Descent in Non-Convex Landscapes: Sharp Estimates via Large Deviations (ICML 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.