Research map / Optimization / Nonconvex and smooth optimization
Dealing With Unbounded Gradients in Stochastic Saddle-point Optimization
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.
Proposes COGDA/COMIDA, stochastic primal-dual gradient methods with a quadratic regularizer anchored at the initial point, giving initialization-dependent duality-gap bounds for unbounded gradients without projections, and applies it to average-reward MDP planning.
Problem
Stochastic first-order saddle-point optimization on unbounded domains where gradients (and multiplicative noise) can grow with the iterates, causing divergence; also planning in average-reward MDPs with unknown value-function scale.
Approach
Augment the min and max players' objectives with regularizers centered at the initial point (ρ-weighted squared distance), which cancels the squared gradient norms in the regret analysis and replaces them with gradient norms at the initialization, yielding bounds that hold without projections or prior knowledge of comparator norms.
Key results
- COGDA achieves expected duality gap bound O((L_M^2 E[||y*||^2+||x*||^2] + L_b^2 + L_c^2)/(L_M sqrt(T))) for bilinear games with stochastic noise scaling with iterates.
- COMIDA under sub-bilinear growth achieves O(L(E[Bregman terms]+1)/sqrt(gamma_x gamma_y T)) without projections.
- COMIDA-MDP achieves O(sqrt(B^4 SA log(SA)/T)) average-reward suboptimality without prior knowledge of bias span B, with query complexity B^4 S^2 A^2 log(SA)/eps^2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add quadratic regularization centered at the initial points | Primal-dual stochastic gradient descent-ascent on unconstrained bilinear games · Unconstrained bilinear games | duality gap: 2\eta_{x}L_{M}^{2} \to 2\eta_{x}L_{M}^{2} (gradient-norm terms at iterates replaced by gradient-norm terms at the initia | Helped |
| Add regularization to the value-function player | Average-reward MDP planning with an unconstrained value-function domain · Average-reward MDPs | policy suboptimality | Helped |
| Set regularization parameters to zero (ablation) | COGDA on unconstrained bilinear games · Unconstrained bilinear games | stability | Hurt |
Surprising findings
- The authors suggest that the quadratic scaling with comparator norm may be unavoidable in this setting, based on a lower bound from a related sub-quadratic-growth OCO result.
Limitations
- Scaling with squared initialization error rather than linear is not improved and may be unavoidable.
- MDP query complexity is suboptimal in S and A dependence.
- Regularization does not guarantee uniform boundedness of iterates.
Experimental setup
Metrics: expected duality gap suboptimality of average reward
Baselines: plain stochastic gradient descent-ascent projection-based primal-dual methods parameter-free OCO methods
Builds on: COMID stabilized online mirror descent Halpern iteration ghost iterate
Closest papers by meaning
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.88)
- Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling (ICML 2025 · similarity 0.88)
- Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry (NeurIPS 2024 · similarity 0.88)
- Second-Order Convergence in Private Stochastic Non-Convex Optimization (NeurIPS 2025 · similarity 0.88)
- Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity (NeurIPS 2025 · similarity 0.87)
- Universal Gradient Methods for Stochastic Convex Optimization (ICML 2024 · similarity 0.87)
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.