Speaker:

Rong Jin, Michigan State University

Title: 

Stochastic Gradient Descent with Only One Projection

Abstract:

Stochastic gradient descent (SGD) have been widely used for large-scale convex optimization. Although many variants of stochastic gradient descent have been proposed, most of them require projecting the intermediate solution at each iteration to ensure that the obtained solution stay within the feasible domain. For complex domains (e.g. SDP cone), the projection step can be computationally expensive, making stochastic gradient descent unattractive for large-scale optimization problems. In this talk, I will discuss our work that explicitly addresses this limitation of stochastic gradient descent.

The key feature of the proposed algorithm is that it does not need to project the intermediate solution to the feasible domain. Instead, only one projection at the last iteration is needed to obtain a feasible solution from the given domain. Our analysis shows that with a high probability, the proposed algorithms achieve an O(1/sqrt{T}) convergence rate for general convex optimization, and an O([ln T]/T ) rate for strongly convex functions under mild conditions about the domain and the objective function.

Bio:

Dr. Jin is an associate professor in the Department of Computer Science and Engineering at Michigan State University. His research is focused on statistical machine learning and its application to information retrieval. He has worked on a variety of machine learning algorithms/theories and their application to a wide range of applications, including information retrieval, collaborative filtering, document clustering, and visual object recognition. He has published over 180 conference and journal articles on related topics.

Dr. Jin holds a Ph.D. in Computer Science from Carnegie Mellon University in 2003. He received the NSF Career Award in 2006, and the best student paper of COLT in 2012.