A Unified Lyapunov-IQC Framework for Uniform Stability of Smooth Quadratic First-Order Accelerated Optimizers

Technical Summary: A Unified Lyapunov-IQC Framework for Uniform Stability of Smooth Quadratic First-Order Accelerated Optimizers

Problem Statement
The paper addresses the challenge of establishing uniform stability for first-order accelerated optimization algorithms, specifically within the regime of $\beta$-smooth and $\gamma$-strongly convex loss functions. Uniform stability is a critical metric for generalization in machine learning, quantifying how much an algorithm's output changes when a single data point in the training set is modified.

While classical analyses for Stochastic Gradient Descent (SGD) (e.g., Hardt, Recht, and Singer, 2016) successfully derive uniform stability bounds using direct coupling arguments and case-by-case tracking of iterate differences, extending these methods to accelerated optimizers like Nesterov Accelerated Gradient (NAG) is non-trivial. Accelerated methods introduce higher-order state dynamics via momentum terms, resulting in multiple coupled update rules (e.g., for both position $w_t$ and velocity $v_t$). This complexity makes the direct tracking of iterate differences ($\Delta w_t$ and $\Delta v_t$) cumbersome and difficult to generalize.

Methodology
The authors propose a unified framework that bridges optimization dynamics and robust control theory to overcome the limitations of direct coupling arguments. The methodology proceeds in two main stages:

1. Direct Lyapunov Construction:
   The authors first extend the classical approach by constructing a specific quadratic Lyapunov function for smooth quadratic NAG. They model the difference between iterates on the original dataset $S$ and a perturbed dataset $S'$ (differing by one point) as a state vector $x_t = [\Delta w_t, \Delta v_t]^T$. By leveraging the properties of the smooth quadratic regime (specifically the integral form of Taylor's theorem and bounds on the Hessian), they derive a matrix inequality condition. They explicitly construct a positive definite matrix $P$ such that the Lyapunov function $V(x_t) = x_t^T P x_t$ satisfies a strict contraction condition $V(x_{t+1}) \leq (1-\rho)V(x_t)$ when the differing sample is not selected, and a bounded growth condition when it is selected. This allows for the derivation of a stability bound via the law of total expectation.

2. Lur'e System and IQC Formulation:
   To generalize the approach and automate the derivation of stability certificates, the authors model first-order optimizers as Lur'e-type feedback interconnections. In this representation:

   • The optimizer's linear dynamics (momentum and update rules) form a linear time-invariant (LTI) system.
   • The gradient operator acts as a non-linear feedback element.
   • The $\beta$-smoothness and $\gamma$-strong convexity of the loss function are encoded as Integral Quadratic Constraints (IQC) (specifically sector inequalities derived from the Baillon-Haddad theorem and gradient monotonicity).

   Under this representation, the existence of a uniform stability bound is certified by the feasibility of a Linear Matrix Inequality (LMI). This LMI is formulated as a Semi-Definite Programming (SDP) problem, which seeks a quadratic Lyapunov function satisfying the contraction condition subject to the IQC constraints. This approach utilizes the S-lemma to ensure the implication holds for all admissible trajectories.

Key Contributions and Results

• Unified Framework: The paper establishes a modular methodology for analyzing the uniform stability of accelerated methods by treating them as dynamical systems subject to IQCs, moving away from ad-hoc, case-specific proofs.
• Explicit Stability Bound for NAG: By instantiating the framework for NAG, the authors derive a uniform stability bound of:
  $$\epsilon \leq O\left(\frac{G \kappa^{1/4}}{\beta \sqrt{n}} \sqrt{1 - (1-\rho)^T}\right)$$
  where $G$ is the gradient bound, $\kappa = \beta/\gamma$ is the condition number, and $n$ is the dataset size.
• Comparison with Prior Work: The derived bound scales as $O(1/\sqrt{n})$ for large $T$. The authors note that this differs from the $O(1/n)$ bound derived by Chen et al. (2018) for NAG. They attribute this difference to the specific nature of their Lyapunov construction and the lack of "early stopping" considerations in their limit analysis, though the framework successfully recovers the structural dependencies on $\kappa$ and $\beta$.
• Numerical Validation: Small-scale experiments on the Wisconsin breast cancer dataset using logistic regression validate the theoretical findings. The results show that empirical stability scales approximately as $1/\sqrt{n}$ with respect to sample size and grows roughly as $\sqrt{T}$ with respect to iterations, consistent with the derived bounds.
• Automated Certification: The paper demonstrates that the stability analysis can be automated via SDP, removing the need for manual construction of Lyapunov functions for new algorithm variants.

Significance and Claims
The paper claims to underscore a structural connection between optimization dynamics and robust control theory. By framing optimization algorithms as Lur'e systems, the authors provide a "modular methodology" for the reliable and reproducible numerical certification of uniform stability and generalization behavior.

The significance lies in the ability to handle higher-order dynamics (momentum) that complicate classical analysis. The framework is presented as adaptable to increasingly complex optimization algorithms. The authors modestly suggest that future work could involve implementing these SDPs in standard software (e.g., CVXPY, MOSEK) and extending the analysis to smooth general convex or non-convex settings, noting that the latter is complicated by the lack of a fixed Hessian over the algorithm's execution. The work does not claim to solve the generalization problem for all non-convex deep learning scenarios but rather provides a rigorous tool for certifying stability in the smooth quadratic regime.