TransWikia.com

Online gradient descent for strongly convex function

Cross Validated Asked by Raba Poco on November 2, 2021

Given that our loss function is $alpha$ strongly convex function which means

$mbox(nabla f(mathbf{x})-nabla f(mathbf{y}))^{T}(mathbf{x}-mathbf{y})geq alpha||mathbf{x}-mathbf{y}||_{2}^{2}
$

we know the Online gradient descent algorithm can get
$Clog(T))/alpha$ for some const C and T is the number of iterations

My question is what happens when $alpha$ is close to zero( in particular much smaller then 1) , can the algorithm fail in that case?

One Answer

  1. Convergence isn't guaranteed by this analysis when the objective isn't strongly convex.

  2. The required number of iterations grows as $alpha$ gets smaller. You may not be able to wait around long enough for convergence if $alpha$ is really small.

  3. The accumulation of round-off errors might also cause problems in practice.

There are some results on the convergence of stochastic subgradient descent algorithms in Bertsekas's new book on Convex Optimizaton Algorithms. With these results you can get convergence with probability one to a solution with an objective function value within $epsilon$ of the optimal value. However, you may have to use a tiny step size that makes this impractical.

Answered by Brian Borchers on November 2, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP