# Streaming Solutions for Time-Varying Optimization Problems

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2021.

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

- [Understanding the Curse of Unrolling](https://mlsanity.com/paper/2602.19733/) (2026)

## Abstract (arXiv)

This paper studies streaming optimization problems that have objectives of the form  sumt=1Tf(xt-1,xt). In particular, we are interested in how the solution hatx t|T for the tth frame of variables changes as T increases. While incrementing T and adding a new functional and a new set of variables does in general change the solution everywhere, we give conditions under which hatx t|T converges to a limit point x^*t at a linear rate as Trightarrow∞. As a consequence, we are able to derive theoretical guarantees for algorithms with limited memory, showing that limiting the solution updates to only a small number of frames in the past sacrifices almost nothing in accuracy. We also present a new efficient Newton online algorithm (NOA), inspired by these results, that updates the solution with fixed complexity of  O( 3Bn3), independent of T, where B corresponds to how far in the past the variables are updated, and n is the size of a single block-vector. Two streaming optimization examples, online reconstruction from non-uniform samples and non-homogeneous Poisson intensity estimation, support the theoretical results and show how the algorithm can be used in practice.