Timezone: »

 
Poster
A Composite Randomized Incremental Gradient Method
Junyu Zhang · Lin Xiao

Tue Jun 11 06:30 PM -- 09:00 PM (PDT) @ Pacific Ballroom #97
in Posters Tue »

We consider the problem of minimizing the composition of a smooth function (which can be nonconvex) and a smooth vector mapping, where both of them can be express as the average of a large number of components. We propose a composite randomized incremental gradient method by extending the SAGA framework. The gradient sample complexity of our method matches that of several recently developed methods based on SVRG in the general case. However, for structured problems where linear convergence rates can be obtained, our method can be much better for ill-conditioned problems. In addition, when the finite-sum structure only appear for the inner mapping, the sample complexity of our method is the same as that of SAGA for minimizing finite sum of smooth nonconvex functions, despite the additional outer composition and the stochastic composite gradients being biased in our case.

Keywords: Non-convex Optimization

Author Information

Junyu Zhang (University of Minnesota, Twin Cities)
Lin Xiao (Microsoft Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors