Section 4.5.1 Non-convex Min-Max Optimization

Assumption 4.8

Regarding the problem (\(\ref{eqn:mm}\)), the following conditions hold:

1. \(f(\mathbf{w}, \mathbf{u})\) is \(\mu\)-strongly concave in terms of \(\mathbf{u}\), and \(\mathbf{u}^*(\mathbf{w})=\arg\max_{\mathbf{u}\in\mathcal U}f(\mathbf{w}, \mathbf{u})\) exists for any \(\mathbf{w}\).

2. \(\nabla_1 f(\mathbf{w}, \mathbf{u})\) is \(L_1\)-Lipschitz continuous such that

\[\begin{align} \|\nabla_1 f(\mathbf{w}, \mathbf{u}) - \nabla_1 f(\mathbf{w}', \mathbf{u}')\|_2 \leq L_1(\|\mathbf{w} - \mathbf{w}'\|_2 + \|\mathbf{u} - \mathbf{u}'\|_2). \end{align}\]

3. \(\nabla_2 f(\mathbf{w}, \mathbf{u})\) is \(L_{21}\)-Lipschitz continuous with respect to the first variable and is \(L_{22}\)-Lipschitz continuous with respect to the second variable

\[\begin{align} &\|\nabla_2 f(\mathbf{w}, \mathbf{u}) - \nabla_2 f(\mathbf{w}', \mathbf{u}')\|_2\leq L_{21} \|\mathbf{w} - \mathbf{w}'\|_2 +L_{22} \|\mathbf{u} - \mathbf{u}'\|_2. \end{align}\]

4. there exist \(\sigma_1,\sigma_2\) such that

\[\begin{align} &\mathbb{E}[\|\nabla_1f(\mathbf{w}, \mathbf{u}; \xi)- \nabla_1 f(\mathbf{w}, \mathbf{u})\|_2^2]\leq \sigma_1^2,\\ &\mathbb{E}[\|\nabla_2f(\mathbf{w}, \mathbf{u}; \xi)- \nabla_2 f(\mathbf{w}, \mathbf{u})\|_2^2]\leq \sigma_2^2. \end{align}\]

22. \(F_*=\min\limits_{\mathbf{w}} F(\mathbf{w})\geq -\infty\).

Lemma 4.17

Let \(\mathbf{u}^*(\mathbf{w})=\arg\max_{\mathbf{u}\in\mathcal U}f(\mathbf{w}, \mathbf{u})\). Under Assumption 4.8(i), (iii), \(\mathbf{u}^*(\cdot)\) is \(\kappa\)-Lipschitz continuous with \(\kappa=\frac{L_{21}}{\mu}\).

Lemma 4.18

Under Assumption 4.8(i) and (ii), \(\nabla F(\mathbf{w})=\nabla_1 f(\mathbf{w}, \mathbf{u}^*(\mathbf{w}))\), and it is \(L_F\)-Lipschitz continuous with \(L_F=L_1(1+\kappa)\).

Lemma 4.19

It holds that \[\begin{align*} &\mathbb{E}_{\xi_t}\left[\|\mathbf{v}_{t} - \nabla F(\mathbf{w}_t)\|^2_2\right] \leq (1-\beta_t)\|\mathbf{v}_{t-1} - \nabla F(\mathbf{w}_{t-1})\|_2^2 + \frac{2L_F^2}{\beta_t}\|\mathbf{w}_{t-1}-\mathbf{w}_t\|_2^2 \\ & + 4L_1^2\beta_t\|\mathbf{u}_{t} - \mathbf{u}^*(\mathbf{w}_t)\|_2^2 + \beta_t^2\sigma_1^2. \end{align*}\]

Lemma 4.20

Suppose Assumption 4.8(i), (iii), (iv) hold. Consider the update \(\mathbf{u}_{t} = \Pi_{\mathcal U} [\mathbf{u}_t + \gamma_t \nabla_2 f(\mathbf{w}_t, \mathbf{u}_t; \zeta_t)]\). If \(\gamma_t<1/L_{22}<1/\mu\), we have \[\begin{equation*} \begin{split} \mathbb{E}_t[\|\mathbf{u}_{t+1} - \mathbf{u}^*(\mathbf{w}_{t+1})\|_2^2] & \leq (1-\frac{\gamma_t \mu}{2}) \|\mathbf{u}_t - \mathbf{u}^*(\mathbf{w}_t)\|_2^2 + \frac{3\kappa^2}{\gamma_t \mu} \mathbb{E}_t[\|\mathbf{w}_t - \mathbf{w}_{t+1}\|_2^2]\\ & + 2\gamma_t^2 \sigma_2^2. \end{split} \end{equation*}\]

Theorem 4.5

Suppose Assumption 4.8 holds. By setting \(\beta_t=\beta= \epsilon^2/(3\sigma_1^2)\), \(\gamma_t=\gamma=\mu\epsilon^2/(96L_1^2\sigma_2^2)\) and \(\eta_t=\eta= \min(\frac{\beta}{\sqrt{8}L_F},\frac{\gamma\mu}{16\sqrt{3}L_1\kappa},\frac{1}{2L_F})\) in SMDA, then the following holds

\[\begin{align} \label{eqn:smda-c} \mathbb E\left[\frac{1}{T}\sum_{t=0}^{T-1}\left\{\frac{1}{4}\|\mathbf{v}_{t}\|_2^2 + \|\nabla F(\mathbf{w}_t)\|_2^2\right\}\right]\leq \epsilon^2, \end{align}\]

with an iteration complexity of

\[\begin{align} \label{eqn:smda-t} T&=O\left(\max\left\{\frac{C_\Upsilon L_F}{\epsilon^2}, \frac{C_\Upsilon\sigma_1^2L_F}{\epsilon^4}, \frac{C_\Upsilon L_1^3\kappa\sigma_2^2}{\epsilon^4\mu^2}\right\}\right), \end{align}\]

where \(C_\Upsilon= 2(F(\mathbf{w}_0) - F_*) + \frac{1}{\sqrt{8}L_F}\|\mathbf{v}_0 - \nabla F(\mathbf{w}_0)\|_2^2 + \frac{L_1}{\sqrt{3}\kappa}\|\mathbf{u}_0 - \mathbf{u}^*(\mathbf{w}_0)\|_2^2\).

💡 Why it matters
The MA gradient estimator in SMDA is critical to obtaining a complexity of \(O(1/\epsilon^4)\). If we simply update the primal variable by SGD, the algorithm becomes SGDA. The convergence analysis of SGDA for non-convex minimax problems will suffer from a large batch size issue or slow convergence. In particular, SGDA with a batch size of \(O(1/\epsilon^2)\) can find an \(\epsilon\)-stationary solution in \(O(1/\epsilon^2)\) iterations when the problem is smooth in terms of primal and dual variables and strongly-concave in terms of dual variable, yielding a sample complexity of \(O(1/\epsilon^4)\). If using a constant batch size \(O(1)\), SGDA may need \(O(1/\epsilon^8)\) iterations for finding an \(\epsilon\)-stationary solution (Lin et al. 2020).

It is worth mentioning that an improved complexity of \(O(1/\epsilon^3)\) can be achieved by employing the STORM gradient estimator for both the primal and dual variables under the mean-square smooth condition of the objective.