Research map / Optimization / Nonconvex and smooth optimization
Robust and Faster Zeroth-Order Minimax Optimization: Complexity and Applications
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 ZO-GDEGA, a single-loop zeroth-order gradient-descent extragradient-ascent algorithm for nonconvex-concave and nonconvex-strongly-concave minimax problems, with improved complexity and looser smoothing-parameter conditions, validated on data poisoning and AUC maximization.
Problem
Black-box nonconvex minimax optimization (nonconvex-concave and nonconvex-strongly-concave, deterministic and stochastic) where only function values are available; existing ZO minimax methods have high complexity and strict smoothing-parameter conditions.
Approach
Applies an extragradient ascent step, motivated by backward-Euler discretization of continuous-time dynamics, only to the dual variable y while using a plain ZO gradient descent step for x, which lowers complexity and allows smoothing parameters of order O(ϵ).
Key results
- ZO-GDEGA achieves overall complexity O((dx+dy)ϵ^-6) for NC-C deterministic and O(dxϵ^-6+dyϵ^-8) for stochastic NC-C (vs O(dxϵ^-8+dyϵ^-10) for ZO-AGP), with smoothing parameters allowed at O(ϵ).
- In the poisoning attack, ZO-GDEGA reduces test accuracy by about 2.1%-7.9% relative to ZO-AGP across settings.
- In AUC maximization at larger smoothing parameters, ZO-GDEGA improves AUC by 0.4-5.4 units over baselines.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ZO-GDEGA instead of the strongest baseline | AUC maximization · MNIST, µ1=µ2=0.001 | AUC: 91.60 vs 92.45 | Hurt |
| Use ZO-GDEGA instead of the strongest baseline | AUC maximization · MNIST, µ1=µ2=0.01 | AUC: 92.58 vs 92.60 | Helped |
| Use ZO-GDEGA instead of the strongest baseline | AUC maximization · MNIST, µ1=µ2=0.05 | AUC: 89.35 vs 89.70 | Helped |
| Use ZO-GDEGA instead of the strongest baseline | AUC maximization · Fashion-MNIST, µ1=µ2=0.001 | AUC: 91.97 vs 92.97 | Hurt |
| Use ZO-GDEGA instead of the strongest baseline | AUC maximization · Fashion-MNIST, µ1=µ2=0.01 | AUC: 91.65 vs 92.23 | Helped |
| Use ZO-GDEGA instead of the strongest baseline | AUC maximization · Fashion-MNIST, µ1=µ2=0.05 | AUC: 87.75 vs 88.66 | Helped |
| Use ZO-GDEGA rather than ZO-AGP to generate poisoned data | Logistic regression data poisoning attack · Synthetic dataset, different poisoning ratios | testing accuracy reduction: 2.1%-7.6% | Helped |
| Use ZO-GDEGA rather than ZO-AGP to generate poisoned data | Logistic regression data poisoning attack · epsilon_test | testing accuracy: about 8.0% | Helped |
Surprising findings
- Robustness to smoothing parameters can matter more than overall complexity in practice for ZO AUC maximization, per the authors.
Limitations
- Stochastic NC-C result relies on Lipschitz continuity (Assumption 5) for the better bound; the continuity-agnostic bound is worse (O(dxϵ^-8+dyϵ^-10)).
- Experiments are small-scale (logistic regression, two-layer MLP) with limited baselines and no compute details.
Experimental setup
Datasets: synthetic Gaussian dataset (2,000 samples, 100 dims) epsilon_test (LIBSVM) MNIST Fashion-MNIST ijcnn1
Benchmarks: synthetic poisoning dataset epsilon_test MNIST AUC Fashion-MNIST AUC ijcnn1 AUC
Metrics: testing accuracy stationary gap objective value AUC CPU time theoretical oracle complexity
Baselines: ZO-AGP ZO-SGDA ZO-Min-Max Acc-ZOMDA FO-AGP
Builds on: extragradient method ZO-GDA ZO-AGP Moreau envelope stationarity (Lin et al. GDA analysis)
Closest papers by meaning
- signSGD via Zeroth-Order Oracle (ICLR 2019 · similarity 0.89)
- Refining Adaptive Zeroth-Order Optimization at Ease (ICML 2025 · similarity 0.88)
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.86)
- Adaptively Incorporating Directional Hints into Zeroth-Order Optimization (NeurIPS 2026 · similarity 0.86)
- Stability and Generalization of Zeroth-Order Decentralized Stochastic Gradient Descent with Changing Topology (AAAI 2025 · similarity 0.86)
- DeepZero: Scaling Up Zeroth-Order Optimization for Deep Model Training (ICLR 2024 · similarity 0.86)
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.