Last Iterate Convergence of Incremental Methods and Applications in
  Continual Learning
Xufeng Cai Jelena Diakonikolas
Incremental gradient methods and incremental proximal methods are a
fundamental class of optimization algorithms used for solving finite sum
problems, broadly studied in the literature. Yet, when it comes to their
convergence guarantees, nonasymptotic (first-order or proximal) oracle
complexity bounds have been obtained fairly recently, almost exclusively
applying to the average iterate. Motivated by applications in continual
learning, we obtain the first convergence guarantees for the last iterate of
both incremental gradient and incremental proximal methods, in general convex
smooth (for both) and convex Lipschitz (for the proximal variants) settings.
Our oracle complexity bounds for the last iterate nearly match (i.e., match up
to a square-root-log or a log factor) the best known oracle complexity bounds
for the average iterate, for both classes of methods. We further obtain
generalizations of our results to weighted averaging of the iterates with
increasing weights, which can be seen as interpolating between the last iterate
and the average iterate guarantees. Additionally, we discuss how our results
can be generalized to variants of studied incremental methods with permuted
ordering of updates. Our results generalize last iterate guarantees for
incremental methods compared to state of the art, as such results were
previously known only for overparameterized linear models, which correspond to
convex quadratic problems with infinitely many solutions.