Incremental Aggregated Proximal and Augmented Lagrangian Algorithms

Understand

We consider minimization of the sum of a large number of convex functions, and we propose an incremental aggregated version of the proximal algorithm, which bears similarity to the incremental aggregated gradient and subgradient methods that have received a lot of recent attention.

• Under cost function differentiability and strong convexity assumptions, we show linear convergence for a sufficiently small constant stepsize.
• This result also applies to distributed asynchronous variants of the method, involving bounded interprocessor communication delays.
• We then consider dual versions of incremental proximal algorithms, which are incremental augmented Lagrangian methods for separable equality-constrained optimization problems.