A Stronger Convergence Result on the Proximal Incremental Aggregated Gradient Method

arXiv1611.08022MaRDI QIDQ6280102FDOQ6280102

Authors: Nuri Denizcan Vanli, Mert Gürbüzbalaban, Asu Ozdaglar 

Publication date: 23 November 2016

Abstract: We study the convergence rate of the proximal incremental aggregated gradient (PIAG) method for minimizing the sum of a large number of smooth component functions (where the sum is strongly convex) and a non-smooth convex function. At each iteration, the PIAG method moves along an aggregated gradient formed by incrementally updating gradients of component functions at least once in the last $K$ iterations and takes a proximal step with respect to the non-smooth function. We show that the PIAG algorithm attains an iteration complexity that grows linear in the condition number of the problem and the delay parameter $K$. This improves upon the previously best known global linear convergence rate of the PIAG algorithm in the literature which has a quadratic dependence on $K$.

This page was built for publication: A Stronger Convergence Result on the Proximal Incremental Aggregated Gradient Method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6280102)