A unifying prediction-correction framework for online convex optimization

Abstract

There is a growing interest for online optimization, motivated by the need for efficient algorithms that solve streaming optimization problems. Modeling the online problem as a sequence of static problems for which a solver is available, we propose a unified prediction-correction framework. The prediction step employs past information to approximate future problems, and the correction step, warm-started by the prediction, solves newly observed problems. The proposed framework is compatible with broad classes of solvers, e.g. ADMM, and prediction schemes, like those employed in online learning.