MATH Seminar
| Title: Randomized Block Coordinate Gradient Methods for a Class of Structured Nonlinear Programming |
|---|
| Colloquium: N/A |
| Speaker: Zhaosong Lu of Simon Fraser University |
| Contact: James Nagy, nagy@mathcs.emory.edu |
| Date: 2014-02-17 at 4:00PM |
| Venue: MSC W303 |
| Download Flyer |
| Abstract: Nowadays a class of huge-scale structured optimization problems arise in some emerging areas such as machine learning. They can be reformulated as minimizing the sum of a smooth and block separable nonsmooth functions. For these problems, it is prohibitive to evaluate the full gradient of the smooth component of the objective function due to huge dimensionality and hence the usual gradient methods cannot be efficiently applied. Nevertheless, its partial gradients can often be computed much more cheaply. In this talk we study a randomized block coordinate gradient (RBCG) method for solving this class of problems. At each iteration this method randomly picks a block, and solves a proximal gradient subproblem over the subspace defined by the block that only uses a partial gradient and usually has a closed-form solution. We present new iteration complexity results for this method when applied to convex problems. We also propose a nonmonotone RBCG method for solving a class of nonconvex problems with the above structure, and establish their global convergence and iteration complexity. In addition, we present new complexity results for the accelerated RBCG method proposed by Nesterov for solving unconstrained convex optimization problems. Finally, we discuss the application of these methods for solving some support vector machine problems and report some computational results. (This is a joint work with Lin Xiao at Microsoft Research Redmond.) |
See All Seminars