.png){kind=icon}
.png){kind=icon}
Return
Optimal Prediction-Correction Algorithm Using Sparse Linear Extrapolation for Time-Varying Optimization
.png){kind=icon}
PRE
AI
DOI：10.1109/tsp.2026.3703622.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\boldsymbol{\ell}_{1}$</tex-math></inline-formula>-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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\boldsymbol{\ell}_{1}$</tex-math></inline-formula>-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
Journal
I
IF:
5.8
Papers:
276
Citations:
0