Streaming Solutions for Time-Varying Optimization Problems

This paper studies streaming optimization problems with objectives given by a sum of locally coupled cost terms of the form f(vx(t-1), vx(t)). In particular, we are interested in how the solution (x) over cap (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 (x) over cap (t|T) converges to a limit point x*(t) at a linear rate as T -> infinity. 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 per-iteration complexity of O(3Bn(3)), 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 inhomogeneous Poisson intensity estimation, support the theoretical results and show how the algorithm can be used in practice.

Automated summary

This paper studies streaming optimization problems and proposes conditions for the convergence of solutions at a linear rate. It also presents a new efficient algorithm and provides example applications to support the theoretical results.