# Convergence rate of stochastic gradient decent with projections

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)$?

• 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) Jul 16, 2014 at 18:29
• Thanks! If you answer the question I can mark is as correct. Do you have a source or hint how to prove it? Jul 16, 2014 at 19:44

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.