## Block Stochastic Gradient Iteration for Convex and Nonconvex OptimizationYangyang Xu and Wotao Yin Published in SIAM Journal on Optimization Slides (by Yangyang Xu)
## OverviewThe This paper proposes a The convergence of BSG is established for both convex and nonconvex cases. In the convex case, BSG has the same order of convergence rate as SG. In the nonconvex case, its convergence is established in terms of the expected violation of a first-order optimality condition. In both cases our analysis is nontrivial since the typical unbiasedness assumption no longer holds. BSG is numerically evaluated on the following problems: (convex) stochastic least squares, (convex) logistic regression, (nonconvex) low-rank tensor recovery, (nonconvex) bilinear logistic regression.
On the convex problems, BSG performed significantly better than SG. On the nonconvex problems, BSG significantly outperformed the deterministic BCD method because the latter tends to early stagnate near local minimizers. Overall, BSG inherits the benefits of both stochastic gradient approximation and block-coordinate updates and is especially useful for solving large-scale nonconvex problems. ## Citation
« Back |