Research map / Optimization / Nonconvex and smooth optimization
Semi-infinite Nonconvex Constrained Min-Max 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 an inexact dynamic barrier primal-dual method (iDB-PD) for nonconvex min-max problems with nonconvex semi-infinite constraints, proving O(eps^-3), O(eps^-6θ), O(eps^-3θ/(1-θ)) complexities for stationarity, feasibility, and slackness under a Łojasiewicz condition on the squared constraint residual.
Problem
Min-max optimization with infinitely many nonconvex nonlinear constraints (semi-infinite constrained min-max), motivated by adversarial robustness and safety-constrained learning, where existing methods assume convex, easy-to-project constraints or lack the nested max structure.
Approach
Extends the dynamic barrier gradient descent idea to the min-max, semi-infinite setting: the primal step solves a closed-form QP with a barrier-type affine constraint using the estimated worst-case constraint index w_k, and an indicator based on zeta = [psi]_+ ||grad psi|| switches off the dual multiplier when the constraint is treated as inactive, avoiding bounded-dual assumptions; inner maximiza
Key results
- iDB-PD achieves convergence in stationarity, infeasibility, and slackness on Multi-MNIST and CHD49, while adaptive discretization with COOPER fails to reduce infeasibility and diverges in stationarity.
- Theoretical complexities: O(eps^-3) for stationarity, O(eps^-6θ) for feasibility, O(eps^-3θ/(1-θ)) for slackness; reduces to O(eps^-3) for all metrics when θ=1/2.
- Compared with GDMA on the DRO reformulation, iDB-PD converges in feasibility and stationarity, whereas GDMA with small rho fails to reduce infeasibility and large rho is unstable.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use iDB-PD instead of adaptive discretization solved with COOPER | Robust multitask learning with task priority · Multi-MNIST | infeasibility | Helped |
| Use iDB-PD instead of adaptive discretization solved with COOPER | Robust multitask learning with task priority · CHD49 | stationarity | Helped |
| Use iDB-PD instead of GDMA with small ρ | Robust multitask learning with task priority · Multi-MNIST | infeasibility | Helped |
| Use iDB-PD instead of GDMA with large ρ | Robust multitask learning with task priority · CHD49 | stationarity | Helped |
Limitations
- Requires the Łojasiewicz condition on the squared constraint residual, which may fail for nonsmooth networks such as ReLU.
- Assumes smooth objective and constraints with strongly concave or PL dependence on the inner variable.
- Experiments are limited to a single robust multi-task learning setup on small benchmarks.
Experimental setup
Datasets: Multi-MNIST CHD49 Multi-Fashion MNIST Yeast 20NG
Benchmarks: Multi-MNIST CHD49
Metrics: stationarity infeasibility complementarity slackness objective loss
Baselines: Adaptive discretization (Blankenship and Falk) with COOPER GDMA (gradient descent multi-ascent) on DRO reformulation
Builds on: dynamic barrier gradient descent Lojasiewicz inequality gradient descent ascent
Closest papers by meaning
- Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion (ICML 2024 · similarity 0.88)
- Hybrid Variance-Reduced SGD Algorithms For Minimax Problems with Nonconvex-Linear Function (NeurIPS 2020 · similarity 0.88)
- Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization (NeurIPS 2022 · similarity 0.88)
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.88)
- Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity (ICML 2024 · similarity 0.87)
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 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.