Regularized Nonlinear Acceleration of Fixed-Point Iterations

Regularized Nonlinear Acceleration of Fixed-Point Iterations (RNA) is a black-box sequence extrapolation algorithm introduced by Scieur, d'Aspremont, and Bach (2016, 2020) that accelerates any fixed-point iteration x_{i+1} = g(x_i) (such as gradient descent g(x) = x - (1/L) grad f(x)) by forming a linear combination sum_{i=0}^k c_i x_i of k + 1 past iterates with sum_{i=0}^k c_i = 1. Given the residual matrix R = [r_0, ..., r_k] in R^{d x (k+1)} with columns r_i = x_{i+1} - x_i = g(x_i) - x_i, Algorithm 2 solves the Tikhonov-regularized constrained least-squares problem c_lambda^* = argmin_{c^T 1 = 1} (||R c||_2^2 + lambda ||c||_2^2) in closed form via c_lambda^* = (R^T R + lambda I)^{-1} 1 / (1^T (R^T R + lambda I)^{-1} 1) (requiring only an O((k+1)^3 + d(k+1)^2) linear system of small window size k << d). On noiseless linear fixed-point iterations x_{i+1} - x^* = G(x_i - x^*) with symmetric Jacobian G (0 <= G <= sigma I, sigma = 1 - mu/L), Proposition 2.1 and Proposition 2.3 prove that unregularized extrapolation (lambda = 0) reduces to a shifted Chebyshev polynomial in G achieving the optimal Nesterov/Chebyshev rate ||sum_{i=0}^k c_i^* x_i - x^*||_2 <= (1 / (1 - sigma)) * (2 beta^k / (1 + beta^{2k})) ||x_0 - x^*||_2 with beta = (1 - sqrt(1 - sigma)) / (1 + sqrt(1 - sigma)) and reaches exact convergence in k = deg(G) steps by Cayley-Hamilton. Under nonlinear/stochastic perturbations, Proposition 3.2 and Theorem 3.4 prove that Tikhonov regularization lambda > 0 prevents Krylov matrix ill-conditioning by bounding ||c_lambda^*||_2 <= sqrt((lambda + ||tilde{R}||_2^2) / (4 lambda)) and ||c_lambda^* - c_{lambda,clean}^*||_2 <= (||P||_2 / lambda)||c_{lambda,clean}^*||_2, yielding an optimal bias-variance tradeoff at lambda = O(||P||_2).