Projected Gradient Descent Consider the primal SVM problem:
$$ \frac12||w||^2 +\frac Cm \sum_{i=1}^m \max(0,1-y_iw\cdot x_i) $$
We want to find a solution with a bounded norm, by using SGD with a projection onto the convex set: $ K=\{x | ||x|| \le R \} $
Concretely, the update step would be $w_{i+1}=\Pi_K(x_i-\eta_i \nabla f(x_i))$, where $\Pi_K(x):=\arg \min_{z\in K}||z-x||$.
I'm trying to figure a way to actually calculate the projection.
Is there a simple algorithm to do this?
(My first thought here, is that this is another optimization problem, which maybe can be solved with another SGD...)
 A: This is a simple Lagrange multiplier optimization. The equivalent formulation is to minimize $\|z-x\|^2_2$ subject to $\|z\|_2^2\leq R^2$. This gives:
$$(z_i-x_i)=\lambda z_i \longrightarrow (\lambda-1)^2z^2_i=x^2_i,$$
so summing gives $(\lambda-1)^2R^2\geq \|x\|_2^2$, or $\lambda\geq \frac{1}{R}\|x\|_2+1$. Notice that $\|z-x\|_2^2=\lambda^2\|z\|_2,$ so that the minimum occurs when $\lambda=\frac{1}{R}\|x\|_2+1$, so now solve for $z_i$. 
A: The gradient of the loss function is:
$$\nabla L = \begin{cases}
 w - \frac{C}{m}y_i\cdot x_i && y_iw\cdot x_i < 1 \\
w && \text{else}
\end{cases}
$$
So, the regular SGD step would be (step 1): 
$$w_{t+1} = \begin{cases}(1-\eta_t)w_t + \frac{C}{m}y_ix_i &&y_iw_t\cdot x_i < 1 \\
(1-\eta_t)w_t && \text{else}
\end{cases}
$$
There are 2 possibilities - either $w_{t+1}$ is already in $K$, or it isn't. Because $K$ is a sphere, the way to project $w_{t+1}$ into it is by multiplying it by $\frac{R}{||w_{t+1}||}$ (step 2):
$$w_{t+1} = \begin{cases}
w_{t+1} && ||w_{t+1}|| < R \\
\frac{R}{||w_{t+1}||}w_{t+1} && \text{else}
\end{cases}
$$
