Research map / Optimization / Nonconvex and smooth optimization
Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions
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 SMAG, a single-loop stochastic Moreau-envelope gradient method for difference-of-max-structured weakly convex problems, achieving O(eps^-4) complexity and unifying DWC and non-smooth WCSC min-max optimization.
Problem
Stochastic non-smooth non-convex optimization of differences of max-structured weakly convex functions (DMax), which covers difference-of-weakly-convex and weakly-convex-strongly-concave min-max problems; prior stochastic methods for these are double-loop.
Approach
Smooth the difference via Moreau envelopes of each max-component and approximate the envelope gradient by performing only one stochastic gradient step on the proximal-point variables and the inner dual variables per iteration, removing inner loops.
Key results
- SMAG achieves O(eps^-4) non-asymptotic complexity with a single loop for DMax, DWC and non-smooth WCSC min-max problems, matching the best double-loop rate.
- On CelebA (Attractive, Male), SMAG attains pAUC 0.8605 with EOD 0.1900, EOP 0.1648, DP 0.4116, the best fairness metrics among compared methods.
- Experiments show SMAG's training loss curves surpass the SGD, SDCA, SSDC and SBCD baselines on PU learning across all four datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SMAG instead of EGDA | pAUC optimization with adversarial fairness regularization · CelebA test, Attractive/Male | pAUC: 0.8546 -> 0.8605 | Helped |
| Use SMAG instead of EGDA | pAUC optimization with adversarial fairness regularization · CelebA test, Attractive/Male | EOD: 0.2290 -> 0.1900 | Helped |
| Use SMAG instead of EGDA | pAUC optimization with adversarial fairness regularization · CelebA test, Attractive/Male | EOP: 0.1735 -> 0.1648 | Helped |
| Use SMAG instead of EGDA | pAUC optimization with adversarial fairness regularization · CelebA test, Attractive/Male | DP: 0.4305 -> 0.4116 | Helped |
| Use SMAG instead of SMAG$^*$ (no fairness regularization) | pAUC optimization with adversarial fairness regularization · CelebA test, Attractive/Male | pAUC: 0.8606 -> 0.8605 | No clear effect |
| Use SMAG instead of SMAG$^*$ (no fairness regularization) | pAUC optimization with adversarial fairness regularization · CelebA test, Attractive/Male | EOD: 0.2192 -> 0.1900 | Helped |
| Use SMAG instead of EGDA | pAUC optimization with adversarial fairness regularization · CelebA test, Big Nose/Male | pAUC: 0.8023 -> 0.8058 | Mixed |
| Use SMAG instead of EGDA | pAUC optimization with adversarial fairness regularization · CelebA test, Big Nose/Male | EOD: 0.3293 -> 0.2708 | Helped |
| Use SMAG instead of EGDA | pAUC optimization with adversarial fairness regularization · CelebA test, Big Nose/Male | EOP: 0.3076 -> 0.2148 | Helped |
| Use SMAG instead of EGDA | pAUC optimization with adversarial fairness regularization · CelebA test, Big Nose/Male | DP: 0.4620 -> 0.4333 | Helped |
| Use SMAG instead of the strongest listed baseline | pAUC optimization with adversarial fairness regularization · CelebA test, Bags Under Eyes/Male | pAUC: 0.8307 -> 0.8278 | Hurt |
| Use SMAG instead of EGDA | pAUC optimization with adversarial fairness regularization · CelebA test, Bags Under Eyes/Male | EOD: 0.2223 -> 0.1642 | Helped |
Limitations
- Requires strong concavity of phi(x,.) and psi(x,.), which may limit applicability.
- Relies on Lipschitz continuity of argmax solutions and bounded stochastic gradients (Assumption M).
Experimental setup
Datasets: Fashion-MNIST MNIST CIFAR10 FER2013 CelebA
Benchmarks: Fashion-MNIST MNIST CIFAR10 FER2013 CelebA
Metrics: training loss pAUC EOD EOP DP
Baselines: SGD SDCA SSDC-SPG SSDC-Adagrad SBCD SOPA SGDA Epoch-GDA
Builds on: Moreau envelope smoothing for weakly convex optimization stochastic DC algorithm (SDCA) Epoch-GDA SOPA
Closest papers by meaning
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.91)
- Stochastic Bias-Reduced Gradient Methods (NeurIPS 2021 · similarity 0.90)
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.89)
- Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods (ICLR 2024 · similarity 0.89)
- Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints (ICML 2025 · similarity 0.89)
- Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints (NeurIPS 2024 · 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.