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 $C\log(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?

  • 1
    $\begingroup$ This formula appears in almost every online learning lecture notes $\endgroup$
    – Raba Poco
    Commented Apr 19, 2015 at 19:38

1 Answer 1

  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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.