Material Detail

This video was recorded at 24th Annual Conference on Learning Theory (COLT), Budapest 2011. We give a novel algorithm for stochastic strongly-convex optimization in the gradient oracle model which returns an O(1/T)-approximate solution after T gradient updates. This rate of convergence is optimal in the gradient oracle model. This improves upon the previously known best rate of O(log(T)/T), which was obtained by applying an online strongly-convex optimization algorithm with regret O(log(T)) to the batch setting. We complement this result by proving that any algorithm has expected regret of Ω(log(T)) in the online stochastic strongly-convex optimization setting. This lower bound holds even in the full-information setting which reveals more information to the algorithm than just gradients. This shows that any online-to-batch conversion is inherently suboptimal for stochastic strongly-convex optimization. This is the first formal evidence that online convex optimization is strictly more difficult than batch stochastic convex optimization.

This will delete the comment from the database. This operation is not reversible. Are you sure you want to do it?

Thank you for reporting a broken "Go to Material" link in MERLOT to help us maintain a collection of valuable learning materials.

Would you like to be notified when it's fixed?

Your email address

Do you know the correct URL for the link?

Suggested URL

Your broken link report has been sent to the MERLOT Team. Thank you for helping MERLOT maintain a current collection of valuable learning materials!

Your broken link report failed to be sent. Please try reloading the page and reporting it again. Thank you! Sorry for the trouble.

If you feel this material is inappropriate for the MERLOT Collection, please click SEND REPORT, and the MERLOT Team will investigate. Thank you!

Your inappropriate material report has been sent to the MERLOT Team. Thank you for helping MERLOT maintain a valuable collection of learning materials.

Your inappropriate material report failed to be sent. Please try reloading the page and reporting it again. Thank you! Sorry for the trouble.

Your inappropriate comment report has been sent to the MERLOT Team. Thank you for helping MERLOT maintain a valuable collection of learning materials.

You are being taken to the material on another site. This will open a new window.

You just viewed Beyond the regret minimization.... Please take a moment to rate this material.