Online gradient descent for strongly convex function

Question

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?

Brian Borchers · Answer

Convergence isn't guaranteed by this analysis when the objective isn't strongly convex.  
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.  
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.

Online gradient descent for strongly convex function

One Answer

Add your own answers!

Ask a Question