Optimal Prediction-Correction Algorithm Using Sparse Linear Extrapolation for Time-Varying Optimization

This paper introduces an optimal prediction-correction algorithm leveraging sparse linear extrapolation for strongly convex, unconstrained time-varying optimization problems, which are prevalent in dynamic systems and online learning. The proposed method constructs the prediction phase as a sparse linear combination of past iterates, with extrapolation coefficients derived by solving an l1-norm minimization problem under tractable constraints. By promoting sparsity in the predictor, the algorithm reduces the frequency of correction steps and the associated computational cost of gradient evaluations. We establish the existence of an l1-optimal sparse predictor and derive closed-form solutions for second- and third-order tracking accuracy cases. Theoretical analysis confirms that the method achieves state-of-the-art tracking accuracy with improved computational efficiency compared to existing prediction-correction approaches. Numerical experiments validate the theoretical results, demonstrating the advantages of the proposed algorithm in reducing computational overhead while maintaining high accuracy.