  This paper studies streaming optimization problems that have objectives of
the form $ \sum_{t=1}^Tf(\mathbf{x}_{t-1},\mathbf{x}_t)$. In particular, we are
interested in how the solution $\hat{\mathbf{x} }_{t|T}$ for the $t$th 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 $\hat{\mathbf{x} }_{t|T}$ converges
to a limit point $\mathbf{x}^*_t$ at a linear rate as $T\rightarrow\infty$. 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 $ \mathcal{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 non-homogeneous Poisson intensity estimation, support the theoretical
results and show how the algorithm can be used in practice.
