Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization

Feihu HuangShangqian GaoJian PeiHeng Huang

article2022JMLR73 citations

Develops momentum-based accelerated zeroth-order and first-order algorithms for nonconvex minimization and minimax problems that achieve state-of-the-art query and gradient complexities without relying on large batch sizes.

Listen

Modern machine learning applications increasingly rely on complex optimization, ranging from training models against adversarial attacks to solving multi-agent decision problems. However, calculating exact mathematical gradients is often impractical or impossible, especially in black-box systems where practitioners can only observe model outputs rather than internal calculations. While gradient-free and minimax optimization techniques exist, standard approaches suffer from high computational noise and typically require impractically large data batches at every iteration, leading to excessive evaluation costs and slow processing.

The article aims to resolve these computational bottlenecks by introducing a family of accelerated momentum-based algorithms for both single-objective minimization and two-player minimax optimization. Specifically, the authors evaluate whether combining momentum-based noise reduction with uniform smoothing techniques can achieve provably faster convergence and lower query costs in both gradient-free and gradient-accessible settings, with and without variable constraints.

To demonstrate this, the authors develop theoretical proofs establishing query and gradient complexity bounds for both constrained and unconstrained problems. They also validate their theoretical guarantees through practical computational experiments, including generating black-box adversarial attacks against deep neural networks across standard image benchmarks (MNIST, FashionMNIST, CIFAR-10, and SVHN) and simulating data poisoning attacks on logistic regression models.

The findings show that the proposed gradient-free minimization method reduces function query complexity while operating efficiently with a single data sample per step, eliminating the need for large batch updates required by existing baseline methods. For black-box minimax problems, the accelerated method matches or improves upon existing convergence rates without large batches. For transparent minimax problems where gradients can be calculated directly, the proposed first-order algorithm achieves state-of-the-art computational efficiency. In empirical testing, these algorithms consistently required substantially fewer function evaluations to successfully compromise target models compared to previous techniques.

These results demonstrate that organizations conducting security audits, adversarial robustness testing, and complex optimization can significantly cut computing time and infrastructure expenses. Removing the requirement for massive batch sizes enables real-world deployment in resource-constrained environments where querying a black-box model is computationally expensive or rate-limited.

Technical leaders and engineering teams should consider adopting these momentum-based variance-reduction methods when auditing machine learning models for adversarial vulnerabilities or solving saddle-point games. Practitioners should evaluate these techniques in pilot benchmarking workflows to optimize hyperparameter selection across their specific domain tasks before wide-scale deployment.

Readers should note that the theoretical guarantees rely on component smoothness and strong concavity in the minimax sub-problems, which may not hold uniformly across every non-standard architecture. Nevertheless, given the consistent performance across both mathematical proofs and empirical benchmarks, confidence in the algorithms' computational advantages remains high.

Simon Fraser University University of Pittsburgh optimization zeroth-order momentum descent first-order momentum methods minimax optimization

arXiv: 2008.08170

Paper: Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming, Saeed Ghadimi et al. (2013). Establishes foundational convergence analysis and randomized smoothing frameworks for stochastic first-order and zeroth-order nonconvex optimization.
Paper: ZOO: Zeroth Order Optimization Based Black-box Attacks to Deep Neural Networks without Training Substitute Models, Pin-Yu Chen et al. (2017). Introduces the formulation and practical application of zeroth-order optimization for black-box adversarial attacks on deep neural networks.
Paper: Towards Deep Learning Models Resistant to Adversarial Attacks, Aleksander Madry et al. (2017). Frames adversarial machine learning as a robust minimax optimization problem, motivating the descent-ascent algorithms studied in the source.

Paper: Fine-Tuning Language Models with Just Forward Passes, Sadhika Malladi et al. (2023). Applies memory-efficient zeroth-order optimization principles to large-scale deep learning by fine-tuning massive language models purely via forward passes.
Paper: Lower Bounds and Accelerated Algorithms for Bilevel Optimization, Kaiyi Ji et al. (2023). Extends accelerated first-order optimization principles and lower-bound complexity analysis from minimax problems to structured bilevel optimization.

Cover for Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization

Abstract

In the paper, we propose a class of accelerated zeroth-order and first-order momentum methods for both nonconvex mini-optimization and minimax-optimization. Specifically, we propose a new accelerated zeroth-order momentum (Acc-ZOM) method for black-box mini-optimization where only function values can be obtained. Moreover, we prove that our Acc-ZOM method achieves a lower query complexity of Õ(d3/4ϵ−3) for finding an ϵ-stationary point, which improves the best known result by a factor of O(d1/4) where d denotes the variable dimension. In particular, our Acc-ZOM does not need large batches required in the existing zeroth-order stochastic algorithms. Meanwhile, we propose an accelerated zeroth-order momentum descent ascent (Acc-ZOMDA) method for black-box minimax optimization, where only function values can be obtained. Our Acc-ZOMDA obtains a low query complexity of Õ((d1 + d2)3/4κ4.5y ϵ−3) without requiring large batches for finding an ϵ-stationary point, where d1 and d2 denote variable dimensions and κy is condition number. Moreover, we propose an accelerated first-order momentum descent ascent (Acc-MDA) method for minimax optimization, whose explicit gradients are accessible. Our Acc-MDA achieves a low gradient complexity of Õ(κ4.5y ϵ−3) without requiring large batches for finding an ϵ-stationary point. In particular, our Acc-MDA can obtain a lower gradient complexity of Õ(κ2.5y ϵ−3) with a batch size O(κ4y), which improves the best known result by a factor of O(κ1/2y ). Extensive experimental results on black-box adversarial attack to deep neural networks and poisoning attack to logistic regression demonstrate efficiency of our algorithms.

Topics

optimization

Keywords

zeroth-order momentum descent first-order momentum methods minimax optimization nonconvex-concave minimax problems momentum descent ascent momentum-based variance reduction zeroth-order stochastic algorithms gradient descent ascent methods hybrid variance-reduced SGD

1. Introduction
2. Related Works
2.1 Zeroth-Order Mini-Optimization
2.2 Zeroth-Order Minimax Optimization
2.3 First-Order Minimax Optimization
3. Preliminaries
3.1 Notations
3.2 Preliminaries for Mini-Optimization
3.3 Preliminaries for Minimax-Optimization
4. Accelerated Zeroth-Order Momentum Method for Mini-Optimization
5. Accelerated Zeroth-Order Momentum Descent Ascent Method for Minimax Optimization
6. Accelerated First-Order Momentum Descent Ascent Method for Minimax Optimization
7. Convergence Analysis
7.1 Convergence Analysis of the Acc-ZOM Algorithm
7.1.1 Convergence Analysis of the Acc-ZOM Algorithm for Constrained Mini-Optimization
7.1.2 Convergence Analysis of Acc-ZOM Algorithm for Unconstrained Mini-Optimization
7.2 Convergence Analysis of the Acc-ZOMDA Algorithm
7.2.1 Convergence Analysis of the Acc-ZOMDA Algorithm for Constrained Minimax Optimization
7.2.2 Convergence Analysis of the Acc-ZOMDA Algorithm for Unconstrained Minimax Optimization
7.3 Convergence Analysis of the Acc-MDA Algorithm
7.3.1 Convergence Analysis of the Acc-MDA Algorithm for Constrained Minimax Optimization
7.3.2 Convergence Analysis of Acc-MDA Algorithm for Unconstrained Minimax Optimization
8. Numerical Experiments
8.1 Black-Box Adversarial Attack to DNNs
8.2 Poisoning Attack to Logistic Regression
9. Conclusions
Acknowledgments
Appendix A. Detailed Convergence Analysis
A.1 Convergence Analysis of Acc-ZOM Algorithm for Constrained Mini-Optimization
A.2 Convergence Analysis of Acc-ZOM Algorithm for Unconstrained Mini-Optimization
A.3 Convergence Analysis of the Acc-ZOMDA Algorithm for Constrained Minimax Optimization
A.4 Convergence Analysis of Acc-ZOMDA Algorithm for Unconstrained Minimax Optimization
A.5 Convergence Analysis of Acc-MDA Algorithm for Constrained Minimax Optimization
A.6 Convergence Analysis of Acc-MDA Algorithm for Unconstrained Minimax Optimization
Appendix B. Comparison of Assumptions Used in Zeroth-Order Methods
Appendix C. Query Complexity of ZO-Min-Max Method in (Liu et al., 2019b)
References

Knowls

Knowl 1 — Accelerated Zeroth-Order Momentum Algorithm for Mini-Optimization
algorithm
Accelerated Zeroth-Order Momentum (Acc-ZOM) is a stochastic gradient-free optimization algorithm for solving constrained or unconstrained nonconvex stochastic mini-optimization problems: $\min_{x \in \mathcal{X}} f(x) = \mathbb{E}_{\xi \sim \mathcal{D}}[f(x; \xi)]$ where $\mathcal{X} \subseteq \mathbb{R}^d$ is a closed convex set and only stochastic function evaluations $f(x; \xi)$ are accessible. The method applies a momentum-based variance-reduction estimator inspired by STORM and extends it to constrained domains via projected momentum steps.

At step $t$ , the algorithm updates an adaptive learning rate $\eta_t = \frac{k}{(m+t)^{1/3}}$ and momentum parameter $\alpha_{t+1} = c\eta_t^2$ . In the unconstrained setting ( $\mathcal{X} = \mathbb{R}^d$ ), the update is $x_{t+1} = x_t - \gamma \eta_t v_t$ . In the constrained setting ( $\mathcal{X} \subset \mathbb{R}^d$ ), it computes an auxiliary projected point $\tilde{x}_{t+1} = \mathcal{P}_{\mathcal{X}}(x_t - \gamma v_t) = \arg\min_{x \in \mathcal{X}} \langle v_t, x - x_t \rangle + \frac{1}{2\gamma}\|x - x_t\|^2$ and sets $x_{t+1} = x_t + \eta_t(\tilde{x}_{t+1} - x_t)$ . The variance-reduced zeroth-order gradient estimate $v_{t+1}$ is updated recursively using a random vector $u \in \mathbb{R}^d$ drawn from the uniform distribution over the unit sphere $\mathbb{S}^{d-1}$ : $v_{t+1} = \hat{\nabla} f(x_{t+1}; \xi_{t+1}) + (1 - \alpha_{t+1})\big(v_t - \hat{\nabla} f(x_t; \xi_{t+1})\big)$ where $\hat{\nabla} f(x; \xi) = \frac{f(x + \mu u; \xi) - f(x; \xi)}{\mu / d} u$ is the uniform smoothing gradient estimator with smoothing parameter $\mu > 0$ .
Input: Total iterations $T$ , parameters { $\gamma, k, m, c$ }, smoothing radius $\mu$ , initial point $x_1 \in \mathcal{X}$
Sample $\xi_1 \sim \mathcal{D}$ and $u \sim \text{Uniform}(\mathbb{S}^{d-1})$
Compute $v_1 = \frac{f(x_1 + \mu u; \xi_1) - f(x_1; \xi_1)}{\mu / d} u$
for $t = 1, 2, \dots, T$ do
     $\eta_t = \frac{k}{(m+t)^{1/3}}$
    if $\mathcal{X} = \mathbb{R}^d$ then
         $x_{t+1} = x_t - \gamma \eta_t v_t$
    else
         $\tilde{x}_{t+1} = \mathcal{P}_{\mathcal{X}}(x_t - \gamma v_t)$
         $x_{t+1} = x_t + \eta_t(\tilde{x}_{t+1} - x_t)$
    end if
     $\alpha_{t+1} = c \eta_t^2$
    Sample $\xi_{t+1} \sim \mathcal{D}$ and $u \sim \text{Uniform}(\mathbb{S}^{d-1})$
     $\hat{\nabla} f(x_{t+1}; \xi_{t+1}) = \frac{f(x_{t+1} + \mu u; \xi_{t+1}) - f(x_{t+1}; \xi_{t+1})}{\mu / d} u$
     $\hat{\nabla} f(x_t; \xi_{t+1}) = \frac{f(x_t + \mu u; \xi_{t+1}) - f(x_t; \xi_{t+1})}{\mu / d} u$
     $v_{t+1} = \hat{\nabla} f(x_{t+1}; \xi_{t+1}) + (1 - \alpha_{t+1})(v_t - \hat{\nabla} f(x_t; \xi_{t+1}))$
end for
Output: $x_\zeta$ chosen uniformly at random from $\{x_t\}_{t=1}^T$ (theoretical), or $x_T$ (practical)
Knowl 2 — Convergence and Query Complexity of Acc-ZOM for Mini-Optimization
theoretical result
Let $f(x) = \mathbb{E}_{\xi \sim \mathcal{D}}[f(x; \xi)]$ defined on a closed convex set $\mathcal{X} \subseteq \mathbb{R}^d$ satisfy:
1. Bounded zeroth-order gradient variance: $\mathbb{E}_{u, \xi}[\|\hat{\nabla} f(x; \xi) - \nabla f_\mu(x)\|^2] \le \sigma^2$ for all $x \in \mathcal{X}$ , where $f_\mu(x) = \mathbb{E}_{u \sim \mathcal{U}_B}[f(x + \mu u)]$ is the uniform ball-smoothed function.
2. Component $L$ -smoothness: $\|\nabla f(x; \xi) - \nabla f(x'; \xi)\| \le L \|x - x'\|$ for all $x, x' \in \mathcal{X}$ .
3. Lower boundedness: $f^* = \inf_{x \in \mathcal{X}} f(x) > -\infty$ .
Set parameters $\eta_t = \frac{k}{(m+t)^{1/3}}$ , $\alpha_{t+1} = c\eta_t^2$ , $c \ge \frac{2}{3k^3} + \frac{5}{4}$ , $k > 0$ , $m \ge \max(2, k^3, (ck)^3)$ , step size $0 < \gamma \le \min\left(\frac{m^{1/3}}{2Lk}, \frac{1}{2\sqrt{6d}L}\right)$ , and smoothing parameter $0 < \mu \le \frac{1}{d(m+T)^{2/3}}$ .
1. Constrained Setting ( $\mathcal{X} \subset \mathbb{R}^d$ ): $\frac{1}{T}\sum_{t=1}^T \mathbb{E}[\|G_{\mathcal{X}}(x_t, \nabla f(x_t), \gamma)\|] \le \frac{1}{T}\sum_{t=1}^T \mathbb{E}[G_t] \le \frac{\sqrt{2M}m^{1/6}}{T^{1/2}} + \frac{\sqrt{2M}}{T^{1/3}} + \frac{L}{2(m+T)^{2/3}}$ where $G_t = \frac{1}{\gamma}\|\tilde{x}_{t+1} - x_t\| + \|\nabla f(x_t) - v_t\|$ , $G_{\mathcal{X}}(x_t, \nabla f(x_t), \gamma) = \frac{1}{\gamma}(x_t - \mathcal{P}_{\mathcal{X}}(x_t - \gamma \nabla f(x_t)))$ , and $M = \frac{f_\mu(x_1) - f^*}{k\gamma} + \frac{m^{1/3}\sigma^2}{k^2} + \frac{9L^2}{4k^2} + 2k^2 c^2 \sigma^2 \ln(m+T) = \tilde{\mathcal{O}}(\sqrt{d}).$
2. Unconstrained Setting ( $\mathcal{X} = \mathbb{R}^d$ ): $\frac{1}{T}\sum_{t=1}^T \mathbb{E}[\|\nabla f(x_t)\|] \le \frac{\sqrt{2M}m^{1/6}}{T^{1/2}} + \frac{\sqrt{2M}}{T^{1/3}} + \frac{L}{2(m+T)^{2/3}}.$
Because $\gamma = \mathcal{O}(d^{-1/2})$ and $M = \tilde{\mathcal{O}}(d^{1/2})$ , the algorithm achieves an $\tilde{\mathcal{O}}(d^{1/4} T^{-1/3})$ convergence rate. For an $\epsilon$ -stationary point ( $\mathbb{E}[G_\zeta] \le \epsilon$ or $\mathbb{E}[\|\nabla f(x_\zeta)\|] \le \epsilon$ ), Acc-ZOM requires $T = \tilde{\mathcal{O}}(d^{3/4}\epsilon^{-3})$ iterations. Since each iteration queries exactly 4 function evaluations (batch size $\mathcal{O}(1)$ ), the total query complexity is $\tilde{\mathcal{O}}(d^{3/4}\epsilon^{-3})$ , improving upon coordinate-smoothing SPIDER zeroth-order methods by a factor of $\mathcal{O}(d^{1/4})$ .
Knowl 3 — Accelerated Zeroth-Order Momentum Descent Ascent Algorithm
algorithm
Accelerated Zeroth-Order Momentum Descent Ascent (Acc-ZOMDA) is a single-loop stochastic zeroth-order method for solving black-box nonconvex-strongly-concave minimax optimization problems: $\min_{x \in \mathcal{X}} \max_{y \in \mathcal{Y}} f(x, y) = \mathbb{E}_{\xi \sim \mathcal{D}'}[f(x, y; \xi)]$ where $\mathcal{X} \subseteq \mathbb{R}^{d_1}$ and $\mathcal{Y} \subseteq \mathbb{R}^{d_2}$ are compact convex sets, and explicit gradients are inaccessible.

Acc-ZOMDA generates stochastic partial gradient approximations using mini-batches $\mathcal{B}_{t+1} = \{\xi_{t+1}^i\}_{i=1}^b$ and uniform sphere random vectors $\hat{u}_i \in \mathbb{S}^{d_1-1}$ , $\tilde{u}_i \in \mathbb{S}^{d_2-1}$ via: $\hat{\nabla}_x f(x, y; \mathcal{B}) = \frac{1}{b}\sum_{i=1}^b \frac{f(x + \mu_1 \hat{u}_i, y; \xi^i) - f(x, y; \xi^i)}{\mu_1 / d_1} \hat{u}_i$ $\hat{\nabla}_y f(x, y; \mathcal{B}) = \frac{1}{b}\sum_{i=1}^b \frac{f(x, y + \mu_2 \tilde{u}_i; \xi^i) - f(x, y; \xi^i)}{\mu_2 / d_2} \tilde{u}_i$
Input: Iterations $T$ , parameters { $\gamma, \lambda, k, m, c_1, c_2, b$ }, smoothing radii $\mu_1, \mu_2$ , initial $x_1 \in \mathcal{X}, y_1 \in \mathcal{Y}$
Draw mini-batch $\mathcal{B}_1 = \{\xi_1^i\}_{i=1}^b$ and vectors $\{\hat{u}_i \in \mathbb{S}^{d_1-1}\}_{i=1}^b$ , $\{\tilde{u}_i \in \mathbb{S}^{d_2-1}\}_{i=1}^b$
Compute $v_1 = \hat{\nabla}_x f(x_1, y_1; \mathcal{B}_1)$ and $w_1 = \hat{\nabla}_y f(x_1, y_1; \mathcal{B}_1)$
for $t = 1, 2, \dots, T$ do
     $\eta_t = \frac{k}{(m+t)^{1/3}}$
    if $\mathcal{X} = \mathbb{R}^{d_1}$ then
         $x_{t+1} = x_t - \gamma \eta_t v_t$
    else
         $\tilde{x}_{t+1} = \mathcal{P}_{\mathcal{X}}(x_t - \gamma v_t)$
         $x_{t+1} = x_t + \eta_t(\tilde{x}_{t+1} - x_t)$
    end if
     $\tilde{y}_{t+1} = \mathcal{P}_{\mathcal{Y}}(y_t + \lambda w_t)$
     $y_{t+1} = y_t + \eta_t(\tilde{y}_{t+1} - y_t)$
     $\alpha_{t+1} = c_1 \eta_t^2$
     $\beta_{t+1} = c_2 \eta_t^2$
    Draw mini-batch $\mathcal{B}_{t+1} = \{\xi_{t+1}^i\}_{i=1}^b$ and vectors $\{\hat{u}_i \in \mathbb{S}^{d_1-1}\}_{i=1}^b$ , $\{\tilde{u}_i \in \mathbb{S}^{d_2-1}\}_{i=1}^b$
     $v_{t+1} = \hat{\nabla}_x f(x_{t+1}, y_{t+1}; \mathcal{B}_{t+1}) + (1 - \alpha_{t+1})(v_t - \hat{\nabla}_x f(x_t, y_t; \mathcal{B}_{t+1}))$
     $w_{t+1} = \hat{\nabla}_y f(x_{t+1}, y_{t+1}; \mathcal{B}_{t+1}) + (1 - \beta_{t+1})(w_t - \hat{\nabla}_y f(x_t, y_t; \mathcal{B}_{t+1}))$
end for
Output: $(x_\zeta, y_\zeta)$ sampled uniformly from $\{x_t, y_t\}_{t=1}^T$ (theoretical), or $(x_T, y_T)$ (practical)
Knowl 4 — Convergence and Query Complexity of Acc-ZOMDA
theoretical result
Let $f(x, y) = \mathbb{E}_{\xi \sim \mathcal{D}'}[f(x, y; \xi)]$ defined on compact convex sets $\mathcal{X} \subseteq \mathbb{R}^{d_1}$ and $\mathcal{Y} \subseteq \mathbb{R}^{d_2}$ satisfy:
1. $L_f$ -Lipschitz gradient: $\|\nabla f(x, y; \xi) - \nabla f(x', y'; \xi)\| \le L_f \|(x, y) - (x', y')\|$ for all $x, x' \in \mathcal{X}$ and $y, y' \in \mathcal{Y}$ .
2. $\tau$ -strong concavity in $y$ : $\|\nabla_y f(x, y) - \nabla_y f(x, y')\| \ge \tau \|y - y'\|$ , with condition number $\kappa_y = L_f / \tau$ .
3. Bounded zeroth-order partial gradient variance: $\mathbb{E}[\|\hat{\nabla}_x f(x, y; \xi) - \nabla_x f_{\mu_1}(x, y)\|^2] \le \delta_1^2$ and $\mathbb{E}[\|\hat{\nabla}_y f(x, y; \xi) - \nabla_y f_{\mu_2}(x, y)\|^2] \le \delta_1^2$ .
4. Lower bounded primal function: $F^* = \inf_{x \in \mathcal{X}} F(x) > -\infty$ , where $F(x) = \max_{y \in \mathcal{Y}} f(x, y)$ .
Let $\tilde{d} = d_1 + d_2$ , $L_g = L_f + L_f^2 / \tau$ , and choose parameters:
- $\eta_t = \frac{k}{(m+t)^{1/3}}$ , $c_1 \ge \frac{2}{3k^3} + \frac{9\tau^2}{4}$ , $c_2 \ge \frac{2}{3k^3} + \frac{625\tilde{d}L_f^2}{3b}$ , $k > 0$ , $1 \le b \le \tilde{d}$
- $m \ge \max(2, k^3, (c_1 k)^3, (c_2 k)^3)$ , $0 < \lambda \le \min\left(\frac{1}{6L_f}, \frac{75\tau}{24}\right)$
- $0 < \gamma \le \min\left(\frac{\lambda \tau}{2L_f}\sqrt{\frac{6b / \tilde{d}}{36\lambda^2 + 625\kappa_y^2}}, \frac{m^{1/3}}{2L_g k}\right)$
- $0 < \mu_1 \le \frac{1}{d_1(m+T)^{2/3}}$ and $0 < \mu_2 \le \frac{1}{\tilde{d}^{1/2} d_2(m+T)^{2/3}}$
Convergence Rate: $\frac{1}{T}\sum_{t=1}^T \mathbb{E}[\|G_{\mathcal{X}}(x_t, \nabla F(x_t), \gamma)\|] \le \frac{1}{T}\sum_{t=1}^T \mathbb{E}[H_t] \le \frac{2\sqrt{3M'}m^{1/6}}{T^{1/2}} + \frac{2\sqrt{3M'}}{T^{1/3}} + \frac{L_f}{2(m+T)^{2/3}}$ where $H_t = \frac{1}{\gamma}\|\tilde{x}_{t+1} - x_t\| + \|\nabla_x f(x_t, y_t) - v_t\| + L_f \|y_t - y^*(x_t)\|$ , $\Delta_1 = \|y_1 - y^*(x_1)\|^2$ , and $M' = \frac{F_{\mu_1}(x_1) - F^*}{\gamma k} + \frac{25\tilde{d}L_f^2 \Delta_1}{k\lambda \tau b} + \frac{2m^{1/3}\delta^2}{b\tau^2 k^2} + \frac{36\tau^2 L_f^2 + 625L_f^4}{8b\tau^2}(m+T)^{-2/3} + \frac{9L_f^2}{4b\tau^2 k^2} + \frac{2(c_1^2 + c_2^2)\delta^2 k^2}{b\tau^2}\ln(m+T).$

Query Complexity: For batch size $b = 1$ , $M' = \tilde{\mathcal{O}}(\sqrt{\tilde{d}\kappa_y^3 + \tilde{d}^2 \kappa_y^2})$ . When $\kappa_y \ge \tilde{d}^{3/2}$ , the convergence rate is $\tilde{\mathcal{O}}\left(\frac{\kappa_y^{3/2}\tilde{d}^{1/4}}{T^{1/3}}\right)$ , resulting in a total query complexity of: $8T = \tilde{\mathcal{O}}\big((d_1 + d_2)^{3/4} \kappa_y^{4.5} \epsilon^{-3}\big)$ for finding an $\epsilon$ -stationary point without requiring large batches.
Knowl 5 — Accelerated First-Order Momentum Descent Ascent Algorithm
algorithm
Accelerated First-Order Momentum Descent Ascent (Acc-MDA) is a single-loop stochastic first-order algorithm for solving transparent nonconvex-strongly-concave minimax optimization problems: $\min_{x \in \mathcal{X}} \max_{y \in \mathcal{Y}} f(x, y) = \mathbb{E}_{\xi \sim \mathcal{D}'}[f(x, y; \xi)]$ where stochastic partial gradients $\nabla_x f(x, y; \xi)$ and $\nabla_y f(x, y; \xi)$ are explicitly accessible.

Acc-MDA tracks both partial gradients using STORM-style momentum estimators $v_t$ and $w_t$ and applies projected gradient updates with step size $\eta_t = \frac{k}{(m+t)^{1/3}}$ .
Input: Iterations $T$ , parameters { $\gamma, \lambda, k, m, c_1, c_2$ }, batch size $b$ , initial $x_1 \in \mathcal{X}, y_1 \in \mathcal{Y}$
Draw mini-batch $\mathcal{B}_1 = \{\xi_1^i\}_{i=1}^b$
Compute $v_1 = \frac{1}{b}\sum_{i=1}^b \nabla_x f(x_1, y_1; \xi_1^i)$ and $w_1 = \frac{1}{b}\sum_{i=1}^b \nabla_y f(x_1, y_1; \xi_1^i)$
for $t = 1, 2, \dots, T$ do
     $\eta_t = \frac{k}{(m+t)^{1/3}}$
    if $\mathcal{X} = \mathbb{R}^{d_1}$ then
         $x_{t+1} = x_t - \gamma \eta_t v_t$
    else
         $\tilde{x}_{t+1} = \mathcal{P}_{\mathcal{X}}(x_t - \gamma v_t)$
         $x_{t+1} = x_t + \eta_t(\tilde{x}_{t+1} - x_t)$
    end if
     $\tilde{y}_{t+1} = \mathcal{P}_{\mathcal{Y}}(y_t + \lambda w_t)$
     $y_{t+1} = y_t + \eta_t(\tilde{y}_{t+1} - y_t)$
     $\alpha_{t+1} = c_1 \eta_t^2$
     $\beta_{t+1} = c_2 \eta_t^2$
    Draw mini-batch $\mathcal{B}_{t+1} = \{\xi_{t+1}^i\}_{i=1}^b$
     $v_{t+1} = \frac{1}{b}\sum_{i=1}^b \nabla_x f(x_{t+1}, y_{t+1}; \xi_{t+1}^i) + (1 - \alpha_{t+1})\left(v_t - \frac{1}{b}\sum_{i=1}^b \nabla_x f(x_t, y_t; \xi_{t+1}^i)\right)$
     $w_{t+1} = \frac{1}{b}\sum_{i=1}^b \nabla_y f(x_{t+1}, y_{t+1}; \xi_{t+1}^i) + (1 - \beta_{t+1})\left(w_t - \frac{1}{b}\sum_{i=1}^b \nabla_y f(x_t, y_t; \xi_{t+1}^i)\right)$
end for
Output: $(x_\zeta, y_\zeta)$ chosen uniformly from $\{x_t, y_t\}_{t=1}^T$ (theoretical), or $(x_T, y_T)$ (practical)
Knowl 6 — Convergence and Gradient Complexity of Acc-MDA
theoretical result
Let $f(x, y) = \mathbb{E}_{\xi \sim \mathcal{D}'}[f(x, y; \xi)]$ have $L_f$ -Lipschitz gradient, $\tau$ -strong concavity in $y$ (condition number $\kappa_y = L_f / \tau$ ), bounded partial gradient variance $\mathbb{E}[\|\nabla_x f(x, y; \xi) - \nabla_x f(x, y)\|^2] \le \delta_2^2$ and $\mathbb{E}[\|\nabla_y f(x, y; \xi) - \nabla_y f(x, y)\|^2] \le \delta_2^2$ , and lower-bounded envelope $F^* = \inf_{x \in \mathcal{X}} \max_{y \in \mathcal{Y}} f(x, y) > -\infty$ .

Hyperparameters are chosen as $\eta_t = \frac{k}{(m+t)^{1/3}}$ , $c_1 \ge \frac{2}{3k^3} + \frac{9\tau^2}{4}$ , $c_2 \ge \frac{2}{3k^3} + \frac{75L_f^2}{2}$ , $m \ge \max(2, k^3, (c_1 k)^3, (c_2 k)^3)$ , $0 < \lambda \le \min\left(\frac{1}{6L_f}, \frac{27b\tau}{16}\right)$ , and $0 < \gamma \le \min\left(\frac{\lambda \tau}{2L_f}\sqrt{\frac{2b}{8\lambda^2 + 75\kappa_y^2 b}}, \frac{m^{1/3}}{2L_g k}\right)$ .

Convergence Bound: $\frac{1}{T}\sum_{t=1}^T \mathbb{E}[\|G_{\mathcal{X}}(x_t, \nabla F(x_t), \gamma)\|] \le \frac{1}{T}\sum_{t=1}^T \mathbb{E}[H_t] \le \frac{2\sqrt{3M''}m^{1/6}}{T^{1/2}} + \frac{2\sqrt{3M''}}{T^{1/3}}$ where $\Delta_1 = \|y_1 - y^*(x_1)\|^2$ and $M'' = \frac{F(x_1) - F^*}{\gamma k} + \frac{9L_f^2 \Delta_1}{k\lambda \tau} + \frac{2m^{1/3}\delta^2}{b\tau^2 k^2} + \frac{2(c_1^2 + c_2^2)\delta^2 k^2}{b\tau^2}\ln(m+T).$

Gradient Complexities:
- Batch size $b = 1$ : $M'' = \mathcal{O}(\kappa_y^3)$ , yielding a gradient complexity of $4T = \tilde{\mathcal{O}}(\kappa_y^{4.5}\epsilon^{-3})$ for finding an $\epsilon$ -stationary point without large batches.
- Batch size $b = \mathcal{O}(\kappa_y^\nu)$ $b = O (κ_{y}^{ν})$ with $\nu > 0$ $ν > 0$ and $\kappa_y^\nu \le \frac{8}{81L_f \tau}$ $κ_{y}^{ν} \leq \frac{8}{81 L _{f} τ}$ : Acc-MDA achieves a gradient complexity of: $4bT = \tilde{\mathcal{O}}\big(\kappa_y^{4.5 - \nu/2}\epsilon^{-3}\big).$ $4 b T = \tilde{O} (κ_{y}^{4.5 - ν /2} ϵ^{- 3}) .$
  - For $b = \mathcal{O}(\kappa_y^3)$ ( $\nu = 3$ ), the complexity is $\tilde{\mathcal{O}}(\kappa_y^3 \epsilon^{-3})$ .
  - For $b = \mathcal{O}(\kappa_y^4)$ ( $\nu = 4$ ), the complexity is $\tilde{\mathcal{O}}(\kappa_y^{2.5} \epsilon^{-3})$ , improving the best known rate by a factor of $\mathcal{O}(\kappa_y^{1/2})$ .
Knowl 7 — Stationarity Metrics for Constrained Stochastic Momentum Optimization
definition
For stochastic momentum algorithms over closed convex constraint sets, convergence is characterized using metrics tailored to momentum estimators $v_t$ and projected auxiliary iterates $\tilde{x}_{t+1} = \mathcal{P}_{\mathcal{X}}(x_t - \gamma v_t) = \arg\min_{x \in \mathcal{X}} \langle v_t, x - x_t \rangle + \frac{1}{2\gamma}\|x - x_t\|^2$ .
1. Mini-Optimization Stationarity Metric $G_t$ : For $\min_{x \in \mathcal{X}} f(x)$ with $\mathcal{X} \subset \mathbb{R}^d$ : $G_t = \frac{1}{\gamma}\|\tilde{x}_{t+1} - x_t\| + \|\nabla f(x_t) - v_t\|.$ $G_t$ upper-bounds the gradient mapping metric $\|G_{\mathcal{X}}(x_t, \nabla f(x_t), \gamma)\| = \frac{1}{\gamma}\|x_t - \mathcal{P}_{\mathcal{X}}(x_t - \gamma \nabla f(x_t))\|$ , since: $\|G_{\mathcal{X}}(x_t, \nabla f(x_t), \gamma)\| \le \|\nabla f(x_t) - v_t\| + \frac{1}{\gamma}\|\tilde{x}_{t+1} - x_t\| = G_t.$
2. Minimax Optimization Stationarity Metric $H_t$ : For $\min_{x \in \mathcal{X}} \max_{y \in \mathcal{Y}} f(x, y)$ with primal envelope $F(x) = \max_{y \in \mathcal{Y}} f(x, y)$ and unique maximizer $y^*(x) = \arg\max_{y \in \mathcal{Y}} f(x, y)$ : $H_t = \frac{1}{\gamma}\|\tilde{x}_{t+1} - x_t\| + \|\nabla_x f(x_t, y_t) - v_t\| + L_f \|y_t - y^*(x_t)\|$ where $L_f$ is the Lipschitz constant of $\nabla f(x, y)$ . $H_t$ upper-bounds the primal gradient mapping $\|G_{\mathcal{X}}(x_t, \nabla F(x_t), \gamma)\| \le H_t$ .
Knowl 8 — Uniform Smoothing Gradient Estimator Formulation and Bounds
model/method
The Uniform Smoothing Gradient Estimator (UniGE) constructs a gradient estimate from randomized function evaluations over the unit Euclidean sphere $\mathbb{S}^{d-1} = \{u \in \mathbb{R}^d : \|u\| = 1\}$ .

For a scalar function $f(x; \xi): \mathbb{R}^d \to \mathbb{R}$ with smoothing parameter $\mu > 0$ : $\hat{\nabla} f(x; \xi) = \frac{f(x + \mu u; \xi) - f(x; \xi)}{\mu / d} u, \quad u \sim \text{Uniform}(\mathbb{S}^{d-1}).$

Properties:
1. Let $f_\mu(x; \xi) = \mathbb{E}_{u \sim \mathcal{U}_B}[f(x + \mu u; \xi)]$ where $\mathcal{U}_B$ is the uniform distribution on the $d$ -dimensional unit Euclidean ball $\mathcal{B} = \{u \in \mathbb{R}^d : \|u\| \le 1\}$ . Then $\mathbb{E}_{u, \xi}[\hat{\nabla} f(x; \xi)] = \nabla f_\mu(x) = \mathbb{E}_\xi[\nabla f_\mu(x; \xi)]$ .
2. If $f(x)$ has $L$ -Lipschitz continuous gradient, then $f_\mu(x)$ also has $L$ -Lipschitz continuous gradient, and: $|f_\mu(x) - f(x)| \le \frac{\mu^2 L}{2}, \quad \|\nabla f_\mu(x) - \nabla f(x)\| \le \frac{\mu L d}{2}, \quad \forall x \in \mathbb{R}^d.$
3. The estimation difference satisfies: $\mathbb{E}_u\big[\|\hat{\nabla} f(x; \xi) - \hat{\nabla} f(x'; \xi)\|^2\big] \le 3dL^2 \|x - x'\|^2 + \frac{3L^2 d^2 \mu^2}{2}, \quad \forall x, x' \in \mathbb{R}^d.$
In minimax optimization $f(x, y; \xi)$ , separate estimators with smoothing parameters $\mu_1, \mu_2$ are used for partial derivatives: $\hat{\nabla}_x f(x, y; \mathcal{B}) = \frac{1}{b}\sum_{i=1}^b \frac{f(x + \mu_1 \hat{u}_i, y; \xi_i) - f(x, y; \xi_i)}{\mu_1 / d_1}\hat{u}_i, \quad \hat{u}_i \sim \text{Uniform}(\mathbb{S}^{d_1-1})$ $\hat{\nabla}_y f(x, y; \mathcal{B}) = \frac{1}{b}\sum_{i=1}^b \frac{f(x, y + \mu_2 \tilde{u}_i; \xi_i) - f(x, y; \xi_i)}{\mu_2 / d_2}\tilde{u}_i, \quad \tilde{u}_i \sim \text{Uniform}(\mathbb{S}^{d_2-1}).$

Knowl 9 — Complexity Comparison of Nonconvex Zeroth-Order and First-Order Methods

data/table

The theoretical query and gradient complexities for finding an $\epsilon$ -stationary point in stochastic mini-optimization $\min_{x \in \mathcal{X}} f(x)$ and minimax optimization $\min_{x \in \mathcal{X}} \max_{y \in \mathcal{Y}} f(x, y)$ (with $\tau$ -strongly concave $y$ , condition number $\kappa_y = L_f / \tau$ , and dimensions $d, d_1, d_2$ where $\tilde{d} = d_1 + d_2$ ) are compared below.

Algorithm	Problem	Estimator	Batch Size	Complexity
ZO-SGD	Mini	Gaussian	$\mathcal{O}(1)$	$\mathcal{O}(d \epsilon^{-4})$
ZO-AdaMM	Mini	Uniform	$\mathcal{O}(\epsilon^{-2})$	$\mathcal{O}(d^2 \epsilon^{-4})$
ZO-SVRG	Mini	Coordinate	$\mathcal{O}(\epsilon^{-2})$	$\mathcal{O}(d \epsilon^{-10/3})$
ZO-SPIDER-Coord	Mini	Coordinate	$\mathcal{O}(\epsilon^{-2})$	$\mathcal{O}(d \epsilon^{-3})$
SPIDER-SZO	Mini	Coordinate	$\mathcal{O}(\epsilon^{-2})$	$\mathcal{O}(d \epsilon^{-3})$
Acc-ZOM	Mini	Uniform	$\mathcal{O}(1)$	$\tilde{\mathcal{O}}(d^{3/4} \epsilon^{-3})$
ZO-Min-Max	Minimax	Uniform	$\mathcal{O}((d_1+d_2)\kappa_y^2 \epsilon^{-2})$	$\mathcal{O}((d_1+d_2)\kappa_y^6 \epsilon^{-6})$
ZO-SGDA	Minimax	Gaussian	$\mathcal{O}((d_1+d_2)\epsilon^{-2})$	$\mathcal{O}((d_1+d_2)\kappa_y^5 \epsilon^{-4})$
ZO-SGDMSA	Minimax	Gaussian	$\mathcal{O}((d_1+d_2)\epsilon^{-2})$	$\tilde{\mathcal{O}}((d_1+d_2)\kappa_y^2 \epsilon^{-4})$
ZO-SREDA-Boost	Minimax	Coordinate	$\mathcal{O}(\max(\kappa_y \epsilon^{-1}, \tilde{d})\kappa_y \epsilon^{-1})$	$\mathcal{O}((d_1+d_2)\kappa_y^3 \epsilon^{-3})$
Acc-ZOMDA	Minimax	Uniform	$\mathcal{O}(1)$	$\tilde{\mathcal{O}}((d_1+d_2)^{3/4}\kappa_y^{4.5}\epsilon^{-3})$
PGSVRG	Minimax	Explicit	$\mathcal{O}(\epsilon^{-2})$	$\mathcal{O}(\kappa_y^3 \epsilon^{-4})$
SGDA	Minimax	Explicit	$\mathcal{O}(\kappa_y \epsilon^{-2})$	$\mathcal{O}(\kappa_y^3 \epsilon^{-4})$
SREDA	Minimax	Explicit	$\mathcal{O}(\kappa_y^2 \epsilon^{-2})$	$\mathcal{O}(\kappa_y^3 \epsilon^{-3})$
SREDA-Boost	Minimax	Explicit	$\mathcal{O}(\kappa_y^2 \epsilon^{-2})$	$\mathcal{O}(\kappa_y^3 \epsilon^{-3})$
Acc-MDA	Minimax	Explicit	$\mathcal{O}(1)$	$\tilde{\mathcal{O}}(\kappa_y^{4.5}\epsilon^{-3})$
Acc-MDA	Minimax	Explicit	$\mathcal{O}(\kappa_y^3)$	$\tilde{\mathcal{O}}(\kappa_y^3 \epsilon^{-3})$
Acc-MDA	Minimax	Explicit	$\mathcal{O}(\kappa_y^4)$	$\tilde{\mathcal{O}}(\kappa_y^{2.5}\epsilon^{-3})$

The comparison shows that Acc-ZOM reduces the dimensional dependence for mini-optimization from $\mathcal{O}(d)$ to $\mathcal{O}(d^{3/4})$ with $\mathcal{O}(1)$ batch size. For minimax optimization, Acc-ZOMDA is the only zeroth-order method achieving $\mathcal{O}(1)$ batch size with sublinear query complexity $\tilde{\mathcal{O}}(\tilde{d}^{3/4}\kappa_y^{4.5}\epsilon^{-3})$ . In the first-order setting, Acc-MDA achieves $\tilde{\mathcal{O}}(\kappa_y^{2.5}\epsilon^{-3})$ with batch size $\mathcal{O}(\kappa_y^4)$ , improving upon the best existing bound by a factor of $\mathcal{O}(\kappa_y^{1/2})$ .

Knowl 10 — Empirical Performance on Black-Box Adversarial Attacks to DNNs
empirical result
Acc-ZOM was evaluated on designing universal black-box adversarial perturbations against pre-trained deep neural networks across four image classification benchmarks:

Setup:
- Datasets: MNIST (99.4% test accuracy), FashionMNIST (91.8%), CIFAR-10 (93.2%), and SVHN (80.8%).
- Optimization Task: Untargeted perturbation $x \in \mathbb{R}^d$ constrained to $\|x\|_\infty \le \varepsilon$ over $n = 40$ images: $\min_{\|x\|_\infty \le \varepsilon} \frac{1}{n}\sum_{i=1}^n \left( f_{b_i}(x + a_i) - \max_{j \ne b_i} f_j(x + a_i) + \ln\left(1 + \exp\left(\max_{j \ne b_i} f_j(x + a_i) - f_{b_i}(x + a_i)\right)\right) \right)$ where $f_j(x+a_i)$ is the $j$ -th pre-softmax logit, and $\varepsilon$ is set to $0.4$ (MNIST), $0.3$ (FashionMNIST), $0.1$ (CIFAR-10), and $0.2$ (SVHN). Batch size was fixed to 10.
- Acc-ZOM parameters: $\gamma = 0.1$ , $k = 1$ , $m = 3$ , $c = 3$ .
Findings:
1. Query Efficiency: Acc-ZOM reduced attack loss with significantly fewer function queries than baseline zeroth-order methods (ZO-AdaMM, ZO-SPIDER-Coord, SPIDER-SZO, and ZO-SFW) across all four datasets.
2. Batch Size Robustness: When tested across batch sizes of 5, 10, and 20, Acc-ZOM exhibited consistent convergence trajectories and query efficiency, validating its batch-size independence.
Knowl 11 — Empirical Performance on Data Poisoning Attacks to Logistic Regression
empirical result
Acc-ZOMDA (two-sided black-box), Acc-Semi-ZOMDA (one-sided black-box w.r.t. attacker), and Acc-MDA (transparent) were evaluated on data poisoning attacks against $\ell_2$ -regularized binary logistic regression.

Formulation: $\max_{\|x\|_\infty \le \varepsilon} \min_{\|y\|_2^2 \le \lambda_{\text{reg}}} f(x, y) = h(x, y; \mathcal{D}_p) + h(0, y; \mathcal{D}_t)$ where $h(x, y; \mathcal{D}) = -\frac{1}{|\mathcal{D}|}\sum_{(a_i, b_i) \in \mathcal{D}} [b_i \ln g(x, y; a_i) + (1 - b_i) \ln(1 - g(x, y; a_i))]$ with logistic sigmoid $g(x, y; a_i) = (1 + e^{-(x+a_i)^T y})^{-1}$ . Synthetic data consisted of $n = 1000$ samples in $d = 100$ dimensions from $\mathcal{N}(0, 1)$ , corruption rate $|\mathcal{D}_p| / (|\mathcal{D}_t| + |\mathcal{D}_p|) = 0.15$ , $\varepsilon = 2$ , and $\lambda_{\text{reg}} = 0.001$ . Acc-ZOMDA hyperparameters were $\gamma = 0.2$ , $\lambda = 0.08$ , $k = 1$ , $m = 3$ , $c_1 = 3$ , $c_2 = 3$ .

Findings:
1. In the two-side black-box setting, Acc-ZOMDA achieved the fastest convergence and the smallest final stationary gap compared to ZO-Min-Max, ZO-SGDMSA, and ZO-SREDA-Boost.
2. In the one-side black-box setting, Acc-Semi-ZOMDA substantially outperformed ZO-Min-Max in convergence speed and stationary gap reduction.
3. In the transparent setting, Acc-MDA reached a lower stationary gap in fewer iterations than SGDA and SREDA-Boost.
4. Parameter sensitivity visualization across $\gamma \in [0.04, 0.36]$ and $\lambda \in [0.02, 0.18]$ showed that all proposed momentum descent-ascent variants maintain stable convergence across a broad range of step-size pairs.

Coverage note — Intermediate algebraic derivations, supporting Lyapunov decrease inequalities (Lemmas 21, 22, 24, 25, 27, 28, 29, 31, 32, 33, 35, 36, 37, 39, 40, 41), and Appendix C's re-derivation of the ZO-Min-Max query complexity were omitted as supporting proof apparatus.

References

1.Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In International Conference on Machine Learning, pages 699–707, 2016.
2.Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv:1912.02365, 2019.
3.Krishnakumar Balasubramanian and Saeed Ghadimi. Zeroth-order (non)-convex stochastic optimization via conditional gradient and gradient updates. In Advances in Neural Information Processing Systems, pages 3455–3464, 2018.
4.Radu Ioan Boţ and Axel Böhm. Alternating proximal-gradient steps for (stochastic) nonconvex-concave minimax problems. arXiv preprint arXiv:2007.13605, 2020.
5.Jinghui Chen, Dongruo Zhou, Jinfeng Yi, and Quanquan Gu. A frank-wolfe framework for efficient and effective adversarial attacks. arXiv preprint arXiv:1811.10828, 2018.
6.Xiangyi Chen, Sijia Liu, Kaidi Xu, Xingguo Li, Xue Lin, Mingyi Hong, and David Cox. Zo-adamm: Zeroth-order adaptive momentum method for black-box optimization. In Advances in Neural Information Processing Systems, pages 7202–7213, 2019.
7.Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex sgd. In Advances in Neural Information Processing Systems, pages 15210–15219, 2019.
8.John C Duchi, Michael I Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61(5):2788–2806, 2015.
9.Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, pages 689–699, 2018.
10.Xiang Gao, Bo Jiang, and Shuzhong Zhang. On the information-adaptive variants of the admm: an iteration complexity perspective. Journal of Scientific Computing, 76(1):327–363, 2018.
11.Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341–2368, 2013.
12.Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1-2):267–305, 2016.
13.Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural information processing systems, pages 2672–2680, 2014.
14.Chuan Guo, Jacob Gardner, Yurong You, Andrew Gordon Wilson, and Kilian Weinberger. Simple black-box adversarial attacks. In International Conference on Machine Learning, pages 2484–2493, 2019.
15.Feihu Huang, Shangqian Gao, Songcan Chen, and Heng Huang. Zeroth-order stochastic alternating direction method of multipliers for nonconvex nonsmooth optimization. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 2549–2555. AAAI Press, 2019a.
16.Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Nonconvex zeroth-order stochastic admm methods with lower function query complexity. arXiv preprint arXiv:1907.13463, 2019b.
17.Feihu Huang, Bin Gu, Zhouyuan Huo, Songcan Chen, and Heng Huang. Faster gradient-free proximal stochastic methods for nonconvex nonsmooth optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1503–1510, 2019c.
18.Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Momentum-based policy gradient methods. In Proceedings of the 37th International Conference on Machine Learning, pages 3996–4007, 2020a.
19.Feihu Huang, Lue Tao, and Songcan Chen. Accelerated stochastic gradient-free and projection-free methods. In Proceedings of the 37th International Conference on Machine Learning, 2020b.
20.Kaiyi Ji, Zhe Wang, Yi Zhou, and Yingbin Liang. Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization. In International Conference on Machine Learning, pages 3100–3109, 2019.
21.Chi Jin, Praneeth Netrapalli, and Michael I Jordan. What is local optimality in nonconvex-nonconcave minimax optimization? arXiv preprint arXiv:1902.00618, 2019.
22.Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In NIPS, pages 315–323, 2013.
23.Harshat Kumar, Dionysios S Kalogerias, George J Pappas, and Alejandro Ribeiro. Zeroth-order deterministic policy gradient. arXiv preprint arXiv:2006.07314, 2020.
24.Yuh-Jye Lee and Olvi L Mangasarian. Ssvm: A smooth support vector machine for classification. Computational optimization and Applications, 20(1):5–22, 2001.
25.Tianyi Lin, Chi Jin, and Michael I Jordan. On gradient descent ascent for nonconvex-concave minimax problems. arXiv preprint arXiv:1906.00331, 2019.
26.Tianyi Lin, Chi Jin, Michael Jordan, et al. Near-optimal algorithms for minimax optimization. arXiv preprint arXiv:2002.02417, 2020.
27.Mingrui Liu, Youssef Mroueh, Jerret Ross, Wei Zhang, Xiaodong Cui, Payel Das, and Tianbao Yang. Towards better understanding of adaptive gradient algorithms in generative adversarial nets. arXiv preprint arXiv:1912.11940, 2019a.
28.Sijia Liu, Jie Chen, Pin-Yu Chen, and Alfred Hero. Zeroth-order online alternating direction method of multipliers: Convergence analysis and applications. In The Twenty-First International Conference on Artificial Intelligence and Statistics, volume 84, pages 288–297, 2018a.
29.Sijia Liu, Bhavya Kailkhura, Pin-Yu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini. Zeroth-order stochastic variance reduction for nonconvex optimization. In Advances in Neural Information Processing Systems, pages 3727–3737, 2018b.
30.Sijia Liu, Xingguo Li, Pin-Yu Chen, Jarvis Haupt, and Lisa Amini. Zeroth-order stochastic projected gradient descent for nonconvex optimization. In 2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pages 1179–1183. IEEE, 2018c.
31.Sijia Liu, Songtao Lu, Xiangyi Chen, Yao Feng, Kaidi Xu, Abdullah Al-Dujaili, Minyi Hong, and Una-May Obelilly. Min-max optimization without gradients: Convergence and applications to adversarial ml. arXiv preprint arXiv:1909.13806, 2019b.
32.Luo Luo, Haishan Ye, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic nonconvex-strongly-concave minimax problems. arXiv preprint arXiv:2001.03724, 2020.
33.Dhruv Malik, Ashwin Pananjady, Kush Bhatia, Koulik Khamaru, Peter L Bartlett, and Martin J Wainwright. Derivative-free methods for policy optimization: Guarantees for linear quadratic systems. Journal of Machine Learning Research, 21(21):1–51, 2020.
34.Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
35.Yurii Nesterov and Vladimir G. Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17:527–566, 2017.
36.Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving a class of non-convex min-max games using iterative first order methods. In Advances in Neural Information Processing Systems, pages 14934–14942, 2019.
37.Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. Efficient search of first-order nash equilibria in nonconvex-concave smooth min-max problems. arXiv preprint arXiv:2002.07919, 2020.
38.Qi Qi, Zhishuai Guo, Yi Xu, Rong Jin, and Tianbao Yang. A practical online method for distributionally deep robust optimization. arXiv preprint arXiv:2006.10138, 2020.
39.Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max optimization: Provable algorithms and applications in machine learning. arXiv preprint arXiv:1810.02060, 2018.
40.Sashank J Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International conference on machine learning, pages 314–323, 2016.
41.Abhishek Roy, Yifang Chen, Krishnakumar Balasubramanian, and Prasant Mohapatra. Online and bandit algorithms for nonstationary stochastic saddle-point optimization. arXiv preprint arXiv:1912.01698, 2019.
42.Anit Kumar Sahu, Manzil Zaheer, and Soummya Kar. Towards gradient free and projection free stochastic optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3468–3477, 2019.
43.Alexander Shapiro and Anton Kleywegt. Minimax analysis of stochastic problems. Optimization Methods and Software, 17(3):523–542, 2002.
44.Kiran K Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Efficient algorithms for smooth minimax optimization. In Advances in Neural Information Processing Systems, pages 12680–12691, 2019.
45.Quoc Tran-Dinh, Nhan H Pham, Dzung T Phan, and Lam M Nguyen. A hybrid stochastic optimization framework for stochastic composite nonconvex optimization. arXiv preprint arXiv:1907.03793, 2019.
46.Quoc Tran-Dinh, Deyi Liu, and Lam M Nguyen. Hybrid variance-reduced sgd algorithms for nonconvex-concave minimax problems. arXiv preprint arXiv:2006.15266, 2020.
47.Hoi-To Wai, Zhuoran Yang, Zhaoran Wang, and Mingyi Hong. Multi-agent reinforcement learning via double averaging primal-dual optimization. In Advances in Neural Information Processing Systems, pages 9649–9660, 2018.
48.Hoi-To Wai, Mingyi Hong, Zhuoran Yang, Zhaoran Wang, and Kexin Tang. Variance reduced policy evaluation with smooth function approximation. In Advances in Neural Information Processing Systems, pages 5784–5795, 2019.
49.Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost and momentum: Faster variance reduction algorithms. In Advances in Neural Information Processing Systems, pages 2403–2413, 2019.
50.Zhongruo Wang, Krishnakumar Balasubramanian, Shiqian Ma, and Meisam Razaviyayn. Zeroth-order algorithms for nonconvex minimax problems with improved complexities. arXiv preprint arXiv:2001.07819, 2020.
51.Tengyu Xu, Zhe Wang, Yingbin Liang, and H Vincent Poor. Enhanced first and zeroth order variance reduced algorithms for min-max optimization. arXiv preprint arXiv:2006.09361, 2020a.
52.Zi Xu, Huiling Zhang, Yang Xu, and Guanghui Lan. A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems. arXiv preprint arXiv:2006.02032, 2020b.
53.Yan Yan, Yi Xu, Qihang Lin, Wei Liu, and Tianbao Yang. Sharp analysis of epoch stochastic gradient descent ascent methods for min-max optimization. arXiv preprint arXiv:2002.05309, 2020.
54.Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance-reduced optimization for a class of nonconvex-nonconcave minimax problems. arXiv preprint arXiv:2002.09621, 2020.
55.Yiming Ying, Longyin Wen, and Siwei Lyu. Stochastic online auc maximization. In Advances in neural information processing systems, pages 451–459, 2016.
56.Renbo Zhao. A primal dual smoothing framework for max-structured nonconvex optimization. arXiv preprint arXiv:2003.04375, 2020.
57.Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for nonconvex optimization. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 3925–3936. Curran Associates Inc., 2018.

Citation

MLA

Huang, F., et al. “Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization”. Journal of Machine Learning Research, vol. 23, no. 36, 2022, pp. 1–0, https://www.jmlr.org/papers/v23/20-924.html.

APA

Huang, F., Gao, S., Pei, J., & Huang, H. (2022). Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization. Journal of Machine Learning Research, 23(36), 1–70. https://www.jmlr.org/papers/v23/20-924.html

Chicago

Huang, F., S. Gao, J. Pei, and H. Huang. 2022. “Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization”. Journal of Machine Learning Research 23 (36): 1–70. https://www.jmlr.org/papers/v23/20-924.html.

Harvard

Huang, F. et al. (2022) “Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization”, Journal of Machine Learning Research, 23(36), pp. 1–70. Available at: https://www.jmlr.org/papers/v23/20-924.html.

Vancouver

1. Huang F, Gao S, Pei J, Huang H (2022) Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization. Journal of Machine Learning Research 23:1–70

BibTeX

@article{JMLR:v23:20-924,
  author  = {Feihu Huang and Shangqian Gao and Jian Pei and Heng Huang},
  title   = {Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization},
  journal = {Journal of Machine Learning Research},
  year    = {2022},
  volume  = {23},
  number  = {36},
  pages   = {1--70},
  url     = {http://jmlr.org/papers/v23/20-924.html}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Accelerated Zeroth-Order Momentum Algorithm for Mini-Optimization

Knowl 2 — Convergence and Query Complexity of Acc-ZOM for Mini-Optimization

Knowl 3 — Accelerated Zeroth-Order Momentum Descent Ascent Algorithm

Knowl 4 — Convergence and Query Complexity of Acc-ZOMDA

Knowl 5 — Accelerated First-Order Momentum Descent Ascent Algorithm

Knowl 6 — Convergence and Gradient Complexity of Acc-MDA

Knowl 7 — Stationarity Metrics for Constrained Stochastic Momentum Optimization

Knowl 8 — Uniform Smoothing Gradient Estimator Formulation and Bounds

Knowl 9 — Complexity Comparison of Nonconvex Zeroth-Order and First-Order Methods

Knowl 10 — Empirical Performance on Black-Box Adversarial Attacks to DNNs

Knowl 11 — Empirical Performance on Data Poisoning Attacks to Logistic Regression

References

Citation

BibTeX

Access the Paper