Research map / Optimization / Nonconvex and smooth optimization
Delving into the Convergence of Generalized Smooth Minimax 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.
Shows that Lipschitz-smoothness-based minimax methods can diverge, and proves that normalized-stepsize variants of GDA, SGDA, GDmax and SGDmax converge under a generalized (lx-ly) smoothness condition for nonconvex-strongly-concave problems.
Problem
Convergence of minimax optimization algorithms (GDA, SGDA, GDmax, SGDmax) fails when the Lipschitz smoothness assumption does not hold, as in distributionally robust optimization and phase retrieval; the paper targets nonconvex-strongly-concave problems under generalized smoothness.
Approach
Introduces lx-ly-smoothness (a generalization of l-smoothness to minimax) and adds adaptive stepsize normalization (dividing the x-step by a gradient-norm-based scale S_t) to GDA, SGDA, GDmax and SGDmax, proving they converge with the same gradient/SFO complexity as their Lipschitz counterparts.
Key results
- Proves generalized GDA/SGDA/GDmax/SGDmax converge under lx-ly-smoothness with gradient complexity matching Lipschitz counterparts (e.g., GDA O(κ²ϵ⁻²), SGDA SFO O(κ³ϵ⁻⁴)).
- On nine LIBSVM datasets, generalized SGDA with gradient-normalized stepsize improves convergence speed or stability over constant-stepsize SGDA on all datasets (qualitative, Figure 1).
- Gives a counterexample (yx² − 0.5y²) where plain gradient descent diverges, since |x_t| ≥ 2^t|x_0|.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the suitable stepsize strategy with gradient normalization | SGDA · Robust logistic regression on a9a, covtype, diabetes, german, gisette, ijcnn1, mushrooms, phishing, and w8a | convergence speed or stability | Helped |
| Use average historical gradient norm for St instead of current gradient norm, exponential average, or a constant (ablation) | Generalized GDA/SGDA · Generalized smooth minimax | SFO complexity: O(κ3ϵ−4) -> ˜O(κ3ϵ−4) | Hurt |
| Use average historical gradient norm for St instead of current gradient norm, exponential average, or a constant (ablation) | Generalized GDmax/SGDmax · Generalized smooth minimax | SFO complexity: O(κ3ϵ−4) -> ˜O(κ3ϵ−4) | Hurt |
| Use gradient normalization, a constant St, or exponential averaging for St (ablation) | Generalized GDA/SGDA · Generalized smooth minimax | SFO complexity: O(κ3ϵ−4) | No clear effect |
| Use gradient normalization, a constant St, or exponential averaging for St (ablation) | Generalized GDmax/SGDmax · Generalized smooth minimax | SFO complexity: O(κ3ϵ−4) | No clear effect |
Surprising findings
- Constant-stepsize GDA-type methods diverge on a simple two-scalar minimax example even though the objective is smooth in the classical sense for bounded regions.
Limitations
- Analysis restricted to nonconvex-strongly-concave problems
- Experiments limited to a single robust logistic regression task with SGDA only
- Some stepsize options incur an extra logarithmic factor in complexity
Experimental setup
Datasets: a9a covtype diabetes german gisette ijcnn1 mushrooms phishing w8a
Benchmarks: robust logistic regression on LIBSVM datasets
Metrics: primal objective value Φ(x) vs iterations
Baselines: SGDA with constant stepsize
Builds on: GDA SGDA GDmax SGDmax l-smoothness (L0, L1)-smoothness
Closest papers by meaning
- Generalized Smooth Variational Inequalities: Methods with Adaptive Stepsizes (ICML 2024 · similarity 0.89)
- Gradient-Variation Online Learning under Generalized Smoothness (NeurIPS 2024 · similarity 0.89)
- Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity (NeurIPS 2025 · similarity 0.88)
- Trust Region Methods for Nonconvex Stochastic Optimization beyond Lipschitz Smoothness (AAAI 2024 · similarity 0.88)
- Nonlinearly Preconditioned Gradient Methods under Generalized Smoothness (ICML 2025 · similarity 0.88)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.88)
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.