# Compressed Learning of Deep Neural Networks for OpenCL-Capable Embedded Systems
## 2 Method
### Optimization Algorithm  
When the number of training examples \(n\) is not too large, say \(n\sim 10k\), we can solve the training problem with sparse coding (1) using proximal gradient descent [30; 52], which updates the weight vector at the \(k\)th iteration by:  
\[w^{k+1}\leftarrow\operatorname{prox}_{\eta\Psi}\left(w^{k}-\eta G(w^{k}) \right).\]  
Here, \(\eta>0\) is the learning rate and \(G(w^{k})\) is the full gradient involving all training examples,  
\[G(w^{k}):=\frac{1}{n}\sum_{i=1}^{n}\
abla\ell(w^{k};x_{i},y_{i}).\]  
The proximal gradient descent algorithm is capable of solving the regularized training problem (1) with \(\Psi(w)=\lambda\|w\|_{1}\), while optimally fixing irrelevant weights in \(w\in\mathbb{R}^{p}\) to the exact zero value. However, it will be too costly to use the method for large \(n\), since it will require \(n\) back-propagation steps to compute the \(\
abla\ell(w^{k};x_{i},y_{i})\) for all training examples in each update. We suggest to use a minibatch gradient \(g_{B}(w)\) in the proximal operator so that the update will be:  
\[w^{k+1}\leftarrow\mathrm{prox}_{\eta\#}\left(w^{k}-\eta g_{B}(w^{k})\right). \tag{2}\]  
Due to the stochasticity in minibatch gradients, the behavior of the proximal gradient algorithm based on the update (2) will become less predictable, but some convergence results are available for the algorithm [53; 54; 55] (under the assumption that the loss function \(\ell\) is convex and Lipschitz continuous in \(w\), the objective function value converges to the optimal value with the rate \(\mathcal{O}(k^{-1/2})\) in expectation). We further consider the update (2) within the RMSProp [31] and ADAM [32] algorithms, arguably the two most popular methods for training deep neural networks. RMSProp uses adaptive learning rates computed differently on gradient components, while ADAM combines the idea of adaptive learning rates and that of the momentum method [56] to improve convergence and to escape saddle points. We integrate proximal operators with RMSProp and ADAM: the resulting algorithms are called Prox-RMSProp (Algorithm 1) and Prox-ADAM (Algorithm 2). We can conjecture that the search directions produced by Prox-ADAM will be more stable than those of Prox-RMSProp since the former uses compositions of minibatch gradients and momentum directions, not just noisy minibatch gradients as in the latter. We show in experiments that the behavior of Prox-ADAM is indeed more stable than that of Prox-RMSProp. ```
Input: a learning rate \(\eta\), a safeguard parameter \(\epsilon>0\), \(\beta\in[0,1)\): a decay rate  Initialize the weight vector \(w\in\mathbb{R}^{p}\); \(v\gets 0\) (Init. 1 st moment vector); \(t\gets 0\) (Init. timestep); while\(w_{t}\) not convergeddo \(t\gets t+1\);  Compute a minibatch gradient: \(g_{t}\gets g_{B}(w_{t-1})\);  Update grad info: \(v_{t}\leftarrow\beta v_{t-1}+(1-\beta)g_{t}\odot g_{t}\);  Update: \(w_{t}\leftarrow\mathrm{prox}_{\eta\|\cdot\|_{1}}(w_{t-1}-\eta\cdot g_{t}/( \sqrt{v_{t}}+\epsilon))\); return\(w_{t}\);
```  
**Algorithm 1**Prox-RMSProp Algorithm  
```
Input: a learning rate \(\eta\), a safeguard parameter \(\epsilon>0\), \(\beta_{1},\beta_{2}\in[0,1)\): decay rates  Initialize the weight vector \(w\in\mathbb{R}^{p}\); \(m_{0}\gets 0\) (Init. 1 st moment vector); \(v_{0}\gets 0\) (Init. 2 nd moment vector); \(t\gets 0\) (Init.