Catalyst Universal Acceleration for First-Order Optimization

Catalyst Universal Acceleration for First-Order Optimization is a generic outer-loop inexact accelerated proximal point framework introduced by Lin, Mairal, and Harchaoui (2015, 2018) that accelerates a broad class of first-order and incremental finite-sum optimization algorithms M (such as SAG, SAGA, SVRG, SDCA, MISO, and randomized coordinate descent) on composite objectives min_{x in R^p} {F(x) := f(x) + psi(x)} (where f is mu-strongly convex and L-smooth, or convex with mu = 0). At outer step k, Algorithm 1 forms the better-conditioned (mu + kappa)-strongly convex auxiliary proximal subproblem G_k(x) = F(x) + (kappa / 2)||x - y_{k-1}||_2^2 around the extrapolated center y_{k-1}, computes an approximate minimizer x_k approx argmin_x G_k(x) using the inner method M up to tolerance G_k(x_k) - G_k^* <= epsilon_k, updates alpha_k in (0, 1) via the Nesterov quadratic equation alpha_k^2 = (1 - alpha_k) alpha_{k-1}^2 + q alpha_k with q = mu / (mu + kappa), and extrapolates y_k = x_k + beta_k (x_k - x_{k-1}) with beta_k = alpha_{k-1}(1 - alpha_{k-1}) / (alpha_{k-1}^2 + alpha_k). Using canonical quadratic estimate sequences (Lemmas A.6-A.8, Equations 20-28) and a discrete Gronwall-type quadratic sequence inequality (Lemma A.10), Theorem 3.1 proves that when epsilon_k = (2/9)(F(x_0) - F^*)(1 - rho)^k with rho < sqrt(q), the outer loop achieves the accelerated linear rate F(x_k) - F^* <= (8 / (sqrt(q) - rho)^2)(1 - rho)^{k+1}(F(x_0) - F^*); balancing the inner and outer work via kappa = L / (n + 1) - mu reduces total finite-sum gradient complexity from O((n + L/mu) log(1/epsilon)) to tilde{O}((n + sqrt(n L / mu)) log(1/epsilon)).