incremental gradient – Optimization Online

An optimal randomized incremental gradient method

Published: 2015/07/07, Updated: 2015/10/18

Convex Optimization complexity, convex optimization, data analysis, incremental gradient, nesterov's method, primal-dual gradient method

In this paper, we consider a class of finite-sum convex optimization problems whose objective function is given by the summation of $m$ ($\ge 1$) smooth components together with some other relatively simple terms. We first introduce a deterministic primal-dual gradient (PDG) method that can achieve the optimal black-box iteration complexity for solving these composite optimization … Read more

Tail bounds for stochastic approximation

Published: 2013/04/19

Michael P. Friedlander

Gabriel Goh

Convex Optimization, Stochastic Programming convex optimization, incremental gradient, sample average approximation, stochastic approximation

Stochastic-approximation gradient methods are attractive for large-scale convex optimization because they offer inexpensive iterations. They are especially popular in data-fitting and machine-learning applications where the data arrives in a continuous stream, or it is necessary to minimize large sums of functions. It is known that by appropriately decreasing the variance of the error at each … Read more