4
$\begingroup$

Given a strong (not only strict) convex function $f: \mathbb{R}^n\to\mathbb{R}$. On such problems, stochastic gradient decent (SGD) has a convergence rate of $O(1/T)$, where $T$ is the number of iterations [1]. How is the convergence rate affected if a constrained is added to the problem and the projected subgradient method is used to solve it?

E.g. \begin{align} \text{minimize } &f(x) \text{ subject to } \\ &x\in C, \end{align} where $C$ is a convex set? The projected subgradient method uses the iteration

$x^{(k+1)} = P \left(x^{(k)} - \alpha_k g^{(k)} \right)$

where $P$ is projection on $C$ and $g^{(k)}$ is any subgradient of $f$ at $x^{(k)}$. Is the convergence rate affected by the projection? If yes, are there better approaches to keep the convergence rate of $O(1/T)$?

$\endgroup$
2
  • $\begingroup$ Strong convexity implies strict convexity; Also, the convergence rate is unchanged (it is still O(1/t) ) --- that is, "stochastic projected subgradient" will have O(1/t) convergence rate for strongly convex problems (on a true stochastic optimization problem) $\endgroup$
    – Suvrit
    Jul 16, 2014 at 18:29
  • $\begingroup$ Thanks! If you answer the question I can mark is as correct. Do you have a source or hint how to prove it? $\endgroup$ Jul 16, 2014 at 19:44

1 Answer 1

2
$\begingroup$

See here for a convergence analysis. As mentioned in the comments, the rate is still $O(\frac{1}{T})$ if the additional constraint keeps the feasible set $C$ convex and the algorithm used is projected stochastic subgradient descent with a suitable step size rule.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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