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

Zhonghao Lin

doi:10.1109/tsp.2026.3703622

Return

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

2026-06-15

PRE

Zhonghao Lin

Jie Hou

Xianlin Zeng

DOI：10.1109/tsp.2026.3703622

Original

Original request for help

Save

Abstract

En 中文

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 $\boldsymbol{\ell}_{1}$-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 $\boldsymbol{\ell}_{1}$-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.

Keywords:

Time-varying optimization

prediction-correction algorithm

sparse predictor

linear extrapolation

$Q$ -linear convergence