Timezone: »

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

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.

Author Information

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

More from the Same Authors