Research map / Optimization / Nonconvex and smooth optimization
Shuffling Gradient-Based Methods for Nonconvex-Concave 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.
Proposes shuffling gradient methods for nonconvex-linear and nonconvex-strongly-concave minimax problems via a bilevel reformulation, using new shuffling hyper-gradient estimators, with oracle complexity matching shuffling nonconvex optimization and comparable numerical performance to SGD.
Problem
Stochastic nonconvex-concave minimax optimization with finite-sum objectives, where shuffling (sampling without replacement) strategies are not yet well understood, and hyper-gradient estimators for the bilevel reformulation are unclear.
Approach
Reformulates the minimax problem as bilevel (lower-level maximization, upper-level minimization) and builds shuffling estimators for the hyper-gradient of the (smoothed) value function, including a semi-shuffling and a full-shuffling scheme for the nonconvex-strongly-concave setting.
Key results
- Nonconvex-linear shuffling method (SGM) achieves O(n eps^-3) oracle complexity under strongly convex h and O(n eps^-7/2) without it; random shuffling improves by sqrt(n).
- Nonconvex-strongly-concave semi-shuffling variant requires O(n eps^-3) evaluations of both gradient blocks; full-shuffling needs O(n eps^-3) or O(n eps^-4) evaluations of grad_u depending on assumptions.
- Numerically, SGM variants perform comparably with SGD and Prox-Linear on w8a and rcv1 after 200 epochs.
Limitations
- Nonconvex-linear complexity without strong convexity of h is worse (eps^-7/2), and the sqrt(n) improvement requires random permutations and extra assumptions.
- Full-shuffling with S=1 requires additional assumptions (gradient-mapping error bound and smoothness of f).
- Numerical experiments are limited to two LIBSVM datasets and show only comparable, not superior, performance.
Experimental setup
Datasets: w8a rcv1
Benchmarks: w8a rcv1
Metrics: objective value vs epochs
Baselines: SGD Prox-Linear
Builds on: shuffling SGD for nonconvex optimization smoothing of convex conjugate (Nesterov smoothing) bilevel optimization approach to minimax
Closest papers by meaning
- Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization (ICML 2025 · similarity 0.92)
- SGD with shuffling: optimal rates without component convexity and large epoch requirements (NeurIPS 2020 · similarity 0.91)
- Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements (NeurIPS 2024 · similarity 0.91)
- Nesterov Accelerated Shuffling Gradient Method for Convex Optimization (ICML 2022 · similarity 0.90)
- Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness (ICML 2025 · similarity 0.89)
- On the Last-Iterate Convergence of Shuffling Gradient Methods (ICML 2024 · 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.