A Double-Inertial Variance-Reduced Proximal Alternating Method for Block-Structured Nonconvex Minimax Optimization

Technical Summary: A Double-Inertial Variance-Reduced Proximal Alternating Method for Block-Structured Nonconvex Minimax Optimization

Problem Statement
The paper addresses the finite-sum nonconvex–nonconcave minimax optimization problem:
$$\min_{x \in \mathbb{R}^{m_1}} \max_{y \in \mathbb{R}^{m_2}} \Psi(x, y) = H(x, y) + f(x) - g(y),$$
where $H(x, y) = \frac{1}{N} \sum_{i=1}^N H_i(x, y)$ is a smooth finite sum, and $f, g$ are proper, lower semicontinuous convex functions (potentially indicator functions of convex sets). The problem arises in applications such as adversarial training, generative adversarial networks (GANs), and robust tensor decomposition.

The analysis is conducted under the Minty Variational Inequality (MVI) condition. This condition posits the existence of a point $z^* = (x^*, y^*)$ such that for all $z = (x, y)$ in the domain and subgradients $u, v$, the inequality $\langle \nabla_x H(x, y) + u, x - x^* \rangle + \langle -\nabla_y H(x, y) + v, y - y^* \rangle \geq 0$ holds. This condition is weaker than convex-concavity but excludes cycling and legitimizes the proximal gradient residual as a stationarity measure.

Methodology: IiSminimaxPALM
The authors propose IiSminimaxPALM (Inertial, Inertial, Stochastic, Minimax Proximal Alternating Linearized Minimization), a double-inertial variance-reduced proximal alternating method.

• Double-Inertial Mechanism: The algorithm employs two types of inertia:
  1. Query Inertia ($\beta$): Used to extrapolate the query point for gradient evaluation.
  2. Post-Update Inertia ($\gamma$): Used to extrapolate the updated iterate before the next step.
     Unlike prior works, the analysis imposes no lower bound on the post-update inertia $\gamma$ beyond $[0, 1)$, explicitly covering the case $\gamma = 0$.
• Variance Reduction: The method utilizes the SAGA estimator for single-loop updates and an epoch-based SARAH variant.
• Proximal Alternating Updates: The algorithm alternates between minimizing with respect to $x$ (using a proximal operator for $f$) and maximizing with respect to $y$ (using a proximal operator for $g$), incorporating stochastic gradients and inertial terms.
• Anchored Analysis: The convergence analysis relies on an "anchor" at the Minty point $z^*$. A critical technical constraint is that the prox-center parameter (inertia applied to the anchor point) is set to zero ($\alpha = 0$) for the main stochastic complexity results. The case $\alpha > 0$ is identified as an open problem within the anchored framework.

Key Contributions and Results

1. Complexity Bounds:

   • SAGA Variant: The method achieves an evaluation complexity of $N + O(N^2 L^2 D^2 / \varepsilon^2)$, where $N$ is the number of components, $L$ is the Lipschitz constant, $D$ is the domain diameter around the Minty point, and $\varepsilon$ is the stationarity tolerance.
   • SARAH Variant: An epoch-based SARAH variant achieves $O(\sqrt{N} L^4 D^2 / \varepsilon^2)$.
   • Optimality of $N^2$: The paper proves that the $N^2$ scaling for single-loop unbiased estimators is information-theoretically optimal within the class of anchor-type analyses. Specifically, any unbiased table-based estimator refreshing $b$ entries per iteration contracts at a rate no faster than $1 - b/N$. Consequently, no such estimator can achieve a complexity better than $\Omega(N^2)$ for this class.
   • Optimality of $\varepsilon^{-2}$: The $\varepsilon^{-2}$ scaling is shown to be class-optimal at $N=1$ via an explicit star-monotone nonconvex hard instance.
   • Conjecture: The authors conjecture that a tighter $\sqrt{N} L \Delta / \varepsilon^2$ lower bound exists for the Minty class, providing a construction program in the appendix, though the strongest available bound of this form currently applies to a non-Minty nonconvex zero-chain.

2. Linear Convergence:

   • Under strong monotonicity of the saddle operator (covering strongly convex–strongly concave composite problems), the deterministic non-inertial variant converges R-linearly with a certified rate of $(1 + \eta \mu)^{-1}$.
   • For the inertial variant, linear convergence is preserved for sufficiently small inertia parameters ($\alpha \leq \eta \mu / 50$).
   • For quadratic games with small coupling, the full practical range of inertia is certified to preserve linear convergence and provide acceleration (rate $1 - \Theta(\kappa^{-1/2})$), verified via exact spectral computation.

3. Adaptive Steps:

   • An adaptive step-size selection algorithm (backtracking) is proposed that determines a constant step size satisfying the theoretical requirements without prior knowledge of problem constants, retaining the complexity guarantees.

4. Numerical Experiments:

   • Experiments are conducted on a provably-Minty benchmark (a nonconvex–nonconcave game where the Minty condition is analytically proven, not just sampled).
   • Scalability: The stochastic variant (IiSminimaxPALM) outperforms the deterministic PALM baseline by a factor of 9.6 to 14.1 in oracle evaluations for large $N$, due to the independence of per-iteration cost from $N$.
   • Inertia: The experiments confirm convergence for every tested inertial configuration, including $\gamma = 0$ (which was previously excluded by non-zero inertia hypotheses in related literature) and $\alpha > 0$ (beyond the current theoretical scope). On the tested instances, double inertia did not yield measurable acceleration over the non-inertial case, suggesting its primary value is the relaxation of restrictive hypotheses.

Significance and Claims
The paper claims to fill a gap in the literature by developing a variance-reduced inertial block-coordinate proximal alternating method under the Minty MVI condition with matching lower-bound certificates.

• Theoretical Rigor: It provides the first complexity analysis for such methods under Minty conditions, establishing that the $N^2$ dependence for single-loop unbiased methods is not an artifact of the analysis but an information-theoretic barrier for that specific estimator class.
• Hypothesis Relaxation: By proving convergence for $\gamma = 0$ and $\alpha = 0$, the method removes restrictive assumptions found in previous inertial proximal alternating literature.
• Open Problems: The authors modestly state that several questions remain open, including:
  • The stochastic linear convergence rate for the inertial proximal variant under the two-sided Polyak-Łojasiewicz (PL) condition.
  • The inertial prox-center case ($\alpha > 0$) in the main stochastic complexity theorem.
  • Proving the conjectured $\sqrt{N}$ lower bound for the Minty class.
  • Developing non-monotone adaptive safeguards that detect variance instability.

The work concludes that while single-loop unbiased variance reduction under Minty conditions is limited to $N^2$ complexity, epoch-based biased methods (SARAH) achieve the superior $\sqrt{N}$ scaling, and the proposed method offers a robust, theoretically grounded framework for nonconvex–nonconcave minimax optimization.