Convergence Rate of Incremental Gradient and Incremental Newton Methods

摘要

The incremental gradient method is a prominent algorithm for minimizing afinite sum of smooth convex functions, used in many contexts includinglarge-scale data processing applications and distributed optimization overnetworks. It is a first-order method that processes the functions one at a timebased on their gradient information. The incremental Newton method, on theother hand, is a second-order variant which exploits additionally the curvatureinformation of the underlying functions and can therefore be faster. In thispaper, we focus on the case when the objective function is strongly convex andpresent fast convergence results for the incremental gradient and incrementalNewton methods under the constant and diminishing stepsizes. For a decayingstepsize rule $lpha_k = Theta(1/k^s)$ with $s in (0,1]$, we show that thedistance of the IG iterates to the optimal solution converges at rate ${calO}(1/k^{s})$ (which translates into ${cal O}(1/k^{2s})$ rate in thesuboptimality of the objective value). For $s>1/2$, this improves the previous${cal O}(1/sqrt{k})$ results in distances obtained for the case whenfunctions are non-smooth. We show that to achieve the fastest ${cal O}(1/k)$rate, incremental gradient needs a stepsize that requires tuning to the strongconvexity parameter whereas the incremental Newton method does not. The resultsare based on viewing the incremental gradient method as a gradient descentmethod with gradient errors, devising efficient upper bounds for the gradienterror to derive inequalities that relate distances of the consecutive iteratesto the optimal solution and finally applying Chung's lemmas from the stochasticapproximation literature to these inequalities to determine their asymptoticbehavior. In addition, we construct examples to show tightness of our rateresults.