Timezone: »

 
Poster
Stochastic Gradient Descent with Only One Projection
Mehrdad Mahdavi · Tianbao Yang · Rong Jin · Shenghuo Zhu

Tue Dec 04 07:00 PM -- 12:00 AM (PST) @ Harrah’s Special Events Center 2nd Floor
in Poster Session »
Although many variants of stochastic gradient descent have been proposed for large-scale convex optimization, most of them require projecting the solution at {\it each} iteration to ensure that the obtained solution stays within the feasible domain. For complex domains (e.g., positive semidefinite cone), the projection step can be computationally expensive, making stochastic gradient descent unattractive for large-scale optimization problems. We address this limitation by developing a novel stochastic gradient descent algorithm that does not need intermediate projections. Instead, only one projection at the last iteration is needed to obtain a feasible solution in the given domain. Our theoretical 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 optimization under mild conditions about the domain and the objective function.
[ PDF] 

Author Information

Mehrdad Mahdavi (Michigan State University (MSU))
Tianbao Yang (NEC Labs America)
Rong Jin (Michigan State University (MSU))
Shenghuo Zhu (NEC Laboratories America)

More from the Same Authors