Linear Coupling of Gradient and Mirror Descent for First-Order Optimization

Linear Coupling of Gradient and Mirror Descent for First-Order Optimization is a primal-dual first-order algorithmic design and analysis framework introduced by Allen-Zhu and Orecchia (2014, 2017) that unifies and reconstructs Nesterov's accelerated gradient method (and extends acceleration to arbitrary norms, non-Euclidean Bregman divergences, positive linear programs, and coordinate/stochastic settings) by linearly coupling a primal gradient descent sequence {y_k} with a dual mirror descent sequence {z_k}. Observing that gradient descent y_{k+1} = Grad(x_{k+1}) = argmin_{y in Q} {(L/2)||y - x_{k+1}||^2 + <grad f(x_{k+1}), y - x_{k+1}>} achieves primal objective decrease Prog(x_{k+1}) (>= ||grad f(x_{k+1})||_*^2 / (2L) in R^n) proportional to the squared dual gradient norm while mirror descent z_{k+1} = Mirr_{z_k}(alpha_{k+1} grad f(x_{k+1})) = argmin_{z in Q} {V_{z_k}(z) + <alpha_{k+1} grad f(x_{k+1}), z - z_k>} (with 1-strongly convex distance generating function w and Bregman divergence V_x(y)) incurs a dual regret error (alpha_{k+1}^2 / 2)||grad f(x_{k+1})||_*^2 proportional to the same quantity (Lemma 3.1, Lemma 4.2), Algorithm 1 (AGM) queries the gradient at the convex combination x_{k+1} = tau_k z_k + (1 - tau_k) y_k with alpha_{k+1} = (k + 2) / (2L) and tau_k = 1 / (alpha_{k+1} L) = 2 / (k + 2). This exact coupling ratio cancels the mirror descent regret error against the primal gradient descent progress to yield the telescoping inequality (alpha_{k+1}^2 L) f(y_{k+1}) - (alpha_{k+1}^2 L - alpha_{k+1}) f(y_k) + (V_{z_{k+1}}(u) - V_{z_k}(u)) <= alpha_{k+1} f(u) (Lemma 4.3), proving f(y_T) - f(x^*) <= 4 Theta L / (T + 1)^2 for any L-smooth convex objective over Q with V_{x_0}(x^*) <= Theta (Theorem 4.1).