Global Convergence Rate of Proximal Incremental Aggregated Gradient\n Methods

We focus on the problem of minimizing the sum of smooth component functions\n(where the sum is strongly convex) and a non-smooth convex function, which\narises in regularized empirical risk minimization in machine learning and\ndistributed constrained optimization in wireless sensor networks and smart\ngrids. We consider solving this problem using the proximal incremental\naggregated gradient (PIAG) method, which at each iteration moves along an\naggregated gradient (formed by incrementally updating gradients of component\nfunctions according to a deterministic order) and taking a proximal step with\nrespect to the non-smooth function. While the convergence properties of this\nmethod with randomized orders (in updating gradients of component functions)\nhave been investigated, this paper, to the best of our knowledge, is the first\nstudy that establishes the convergence rate properties of the PIAG method for\nany deterministic order. In particular, we show that the PIAG algorithm is\nglobally convergent with a linear rate provided that the step size is\nsufficiently small. We explicitly identify the rate of convergence and the\ncorresponding step size to achieve this convergence rate. Our results improve\nupon the best known condition number dependence of the convergence rate of the\nincremental aggregated gradient methods used for minimizing a sum of smooth\nfunctions.\n