# Time-Varying Convex Optimization with O(n) Computational Complexity

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 31 references that are in the map.
- First posted on arXiv 19 Oct 2024.

## Builds on (most cited first, 15 of 15)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [Time-Varying Convex Optimization: Time-Structured Algorithms and Applications](https://mlsanity.com/paper/2006.08500/) (2020)
- [A Class of Prediction-Correction Methods for Time-Varying Convex Optimization](https://mlsanity.com/paper/1509.05196/) (2015)
- [Optimization and Learning with Information Streams: Time-varying Algorithms and Applications](https://mlsanity.com/paper/1910.08123/) (2019)
- [Distributed Convex Optimization for Continuous-Time Dynamics with Time-Varying Cost Function](https://mlsanity.com/paper/1507.04878/) (2015)
- [Prediction-Correction Interior-Point Method for Time-Varying Convex Optimization](https://mlsanity.com/paper/1608.07544/) (2016)
- [Federated Learning Using Variance Reduced Stochastic Gradient for Probabilistically Activated Agents](https://mlsanity.com/paper/2210.14362/) (2022)
- [Contraction and Robustness of Continuous Time Primal-Dual Dynamics](https://mlsanity.com/paper/1803.05975/) (2018)
- [Distributed and time-varying primal-dual dynamics via contraction analysis](https://mlsanity.com/paper/2003.12665/) (2020)
- [Projected Forward Gradient-Guided Frank-Wolfe Algorithm via Variance Reduction](https://mlsanity.com/paper/2403.12511/) (2024)
- [tvopt: A Python Framework for Time-Varying Optimization](https://mlsanity.com/paper/2011.07119/) (2020)
- [Escaping spurious local minimum trajectories in online time-varying nonconvex optimization](https://mlsanity.com/paper/1912.00561/) (2019)
- [First-Order Dynamic Optimization for Streaming Convex Costs](https://mlsanity.com/paper/2310.07925/) (2023)
- [A Framework for Time-Varying Optimization via Derivative Estimation](https://mlsanity.com/paper/2403.19088/) (2024)

## Abstract (arXiv)

In this article, we consider the problem of unconstrained time-varying convex optimization, where the cost function changes with time. We provide an in-depth technical analysis of the problem and argue why freezing the cost at each time step and taking finite steps toward the minimizer is not the best tracking solution for this problem. We propose a set of algorithms that by taking into account the temporal variation of the cost aim to reduce the tracking error of the time-varying minimizer of the problem. The main contribution of our work is that our proposed algorithms only require the first-order derivatives of the cost function with respect to the decision variable. This approach significantly reduces computational cost compared to the existing algorithms, which use the inverse of the Hessian of the cost. Specifically, the proposed algorithms reduce the computational cost from O(n3) to O(n) per timestep, where n is the size of the decision variable. Avoiding the inverse of the Hessian also makes our algorithms applicable to non-convex optimization problems. We refer to these algorithms as O(n)-algorithms. These O(n)-algorithms are designed to solve the problem for different scenarios based on the available temporal information about the cost. We illustrate our results through various examples, including the solution of a model predictive control problem framed as a convex optimization problem with a streaming time-varying cost function.