# A Class of Prediction-Correction Methods for Time-Varying Convex Optimization

arXiv: https://arxiv.org/abs/1509.05196 · HTML: https://mlsanity.com/paper/1509.05196/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Sep 2015.

## Built on by (most cited first, 16 of 16)

- [A Single-Timescale Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2102.04671/) (2021)
- [Learning Time-Varying Graphs from Online Data](https://mlsanity.com/paper/2110.11017/) (2021)
- [Online Filtering over Expanding Graphs](https://mlsanity.com/paper/2301.06898/) (2023)
- [First-Order Dynamic Optimization for Streaming Convex Costs](https://mlsanity.com/paper/2310.07925/) (2023)
- [Time-Varying Graph Learning for Data with Heavy-Tailed Distribution](https://mlsanity.com/paper/2501.00606/) (2024)
- [Time-Varying Optimization for Streaming Data Via Temporal Weighting](https://mlsanity.com/paper/2510.13052/) (2025)
- [Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution](https://mlsanity.com/paper/2302.03933/) (2023)
- [A Novel Theoretical Framework for Exponential Smoothing](https://mlsanity.com/paper/2403.04345/) (2024)
- [Prediction techniques for dynamic imaging with online primal-dual methods](https://mlsanity.com/paper/2405.02497/) (2024)
- [Decentralized Time-Varying Optimization for Streaming Data via Temporal Weighting](https://mlsanity.com/paper/2605.06971/) (2026)
- [Distributed Unconstrained Optimization with Time-varying Cost Functions](https://mlsanity.com/paper/2212.09472/) (2022)
- [MUSIC: Accelerated Convergence for Distributed Optimization With Inexact and Exact Methods](https://mlsanity.com/paper/2403.02589/) (2024)
- [Time-Varying Convex Optimization with O(n) Computational Complexity](https://mlsanity.com/paper/2410.15009/) (2024)
- [Optimal Resource Allocation for ML Model Training and Deployment under Concept Drift](https://mlsanity.com/paper/2512.12816/) (2025)
- [Higher-Order Equilibrium Tracking for EM-Compressible Online Estimation](https://mlsanity.com/paper/2605.08864/) (2026)
- [Distributed Optimization with Streaming Data: A Temporal Weighting Perspective](https://mlsanity.com/paper/2608.09565/) (2026)

## Abstract (arXiv)

This paper considers unconstrained convex optimization problems with time-varying objective functions. We propose algorithms with a discrete time-sampling scheme to find and track the solution trajectory based on prediction and correction steps, while sampling the problem data at a constant rate of 1/h, where h is the length of the sampling interval. The prediction step is derived by analyzing the iso-residual dynamics of the optimality conditions. The correction step adjusts for the distance between the current prediction and the optimizer at each time step, and consists either of one or multiple gradient steps or Newton steps, which respectively correspond to the gradient trajectory tracking (GTT) or Newton trajectory tracking (NTT) algorithms. Under suitable conditions, we establish that the asymptotic error incurred by both proposed methods behaves as O(h2), and in some cases as O(h4), which outperforms the state-of-the-art error bound of O(h) for correction-only methods in the gradient-correction step. Moreover, when the characteristics of the objective function variation are not available, we propose approximate gradient and Newton tracking algorithms (AGT and ANT, respectively) that still attain these asymptotical error bounds. Numerical simulations demonstrate the practical utility of the proposed methods and that they improve upon existing techniques by several orders of magnitude.