Timezone: »

 
Poster
Stochastic Composite Mirror Descent: Optimal Bounds with High Probabilities
Yunwen Lei · Ke Tang

Wed Dec 05 07:45 AM -- 09:45 AM (PST) @ Room 210 #97
in Wed Poster Session A »

We study stochastic composite mirror descent, a class of scalable algorithms able to exploit the geometry and composite structure of a problem. We consider both convex and strongly convex objectives with non-smooth loss functions, for each of which we establish high-probability convergence rates optimal up to a logarithmic factor. We apply the derived computational error bounds to study the generalization performance of multi-pass stochastic gradient descent (SGD) in a non-parametric setting. Our high-probability generalization bounds enjoy a logarithmical dependency on the number of passes provided that the step size sequence is square-summable, which improves the existing bounds in expectation with a polynomial dependency and therefore gives a strong justification on the ability of multi-pass SGD to overcome overfitting. Our analysis removes boundedness assumptions on subgradients often imposed in the literature. Numerical results are reported to support our theoretical findings.

Keywords: Kernel Methods · Learning Theory · Convex Optimization · Stochastic Methods
[ Paper]  [ Poster] 

Author Information

Yunwen Lei (Southern University of Science and Technology)
Ke Tang (Southern University of Science and Technology)

More from the Same Authors