## 4 Applying ADMM to the Ordered Ridge Regression  
In order to apply ADMM to the problem in Equation (5), we first transform it into an equivalent form of the problem in Equation (1) by introducing an auxiliary variable \(z\). \[\underset{x,z\in\mathbb{R}^{p}}{\min}\frac{1}{2}\|Ax-b\|_{2}^{2}+\frac{1}{2}J _{\lambda}(z)\quad s.t.\quad x-z=0 \tag{6}\]  
We can see that Equation (6) has two blocks of variables (i.e., \(x\) and \(z\)). Its objective function is separable in the form of Equation (1) since \(f(x)=\frac{1}{2}\|Ax-b\|_{2}^{2}\) and \(g(z)=\frac{1}{2}J_{\lambda}(z)=\frac{1}{2}\lambda\|z\|_{2}^{2}=\frac{1}{2} \underset{k=1}{\overset{p}{\sum}}\lambda_{k}|x_{(k)}|^{2}\), where \(A=I\) and \(B=-I\). Therefore, ADMM is applicable to Equation (6). An augmented Lagrangian form of Equation (6) can be defined as follows:  
\[ \begin{split}\mathcal{L}_{p}(x,z,y)&=\frac{1}{2} \|Ax-b\|_{2}^{2}+\frac{1}{2}\lambda\|z\|_{2}^{2}+y^{T}(x-z)\\ &+\frac{\rho}{2}\|x-z\|_{2}^{2}\end{split}  \tag{7}\] \begin{table}
\begin{tabular}{l l l l} \hline \hline
**Notations** & **Explanations** & **Notations** & **Explanations** \\ \hline Matrix & denoted by uppercase letter & f & loss convex function \\ Vector & denoted by lowercase letter & g & Regularizer part (\(\ell_{1}\) or \(\ell_{2}\) etc.) \\ \(\|.\|_{1}\) & \(\ell_{1}\) norm & \(\hat{\partial}f(x)\) & subdifferential of convex function f at x \\ \(\|.\|_{2}\) & \(\ell_{2}\) norm & \(\hat{\partial}g(z)\) & subdifferential of convex function g at z \\ \(\|x\|_{1}=\frac{\underset{k=1}{\overset{p}{\sum}}}{k\|x_{k}}|\) & \(\ell_{1}\) norm & L1 & the \(\ell_{1}\) norm or the lasso \\ \(\|x\|_{2}=\sqrt{\underset{k=1}{\overset{p}{\sum}}}|x_{k}|^{2}\) & \(\ell_{2}\) norm & OL1 & ordered \(\ell_{1}\) norm or ordered lasso \\ \(\|x\|_{2}^{2}=\frac{\underset{k=1}{\overset{p}{\sum}}}{k\|x_{k}}|^{2}\) & square of \(\ell_{2}\) norm & OL2 & ordered \(\ell_{2}\) norm or ordered ridge regression \\ \(J_{\lambda}(.)\) & the ordered norm & Eq. & equation \\ \hline \hline \end{tabular}  
**Note:** We often use the ordered \(\ell_{2}\) norm/regularization, OL2, and ADMM-O\(\ell_{2}\) interchangeably.  
\end{table} 
Table 2: Notations and explanations. where \(y\in\mathbb{R}^{p}\) is a Lagrangian multiplier and \(\rho>0\) denotes a penalty parameter. Next, we apply ADMM to the augmented Lagrangian equation of Equation (7) (Reference [9], Section 3.1), which renders ADMM iterations as follows:  
\[ \begin{split} x^{k+1}&:=\mathop{\vphantom{\sum} \smash{\mathop{\vphantom{\sum}\smash{\mathop{\vphantom{\sum}\smash{\mathop{ \vphantom{\sum}\smash{\mathop{\vphantom{\sum}\smash{\mathop{\vphantom{\sum}\smash{ \mathop{\vphantom{\sum}\smash{\mathop{\vphantom{\sum}\smash{\mathop{\vphantom{\smash{ \vphantom{\smash{\vphantom{\vphantom{\vphantom{\vphantom{\vphantomvphantom{\vphantomvphantomvphantom{\vphantomvphantomvphantom{  }}}}}}}}}}}}}}}}}}_{x\in \mathbb{R}^{p}}\mathcal{L}_{p}(x,z^{k},y^{k})\\ z^{k+1}&:=\mathop{\vphantom{\sum}\smash{ \mathop{\vphantom{\sum}\smash{\mathop{\vphantom{\sum}\smash{\mathop{\vphantom{ \sum}\smash{\mathop{\vphantom{\sum}\smash{\mathop{\vphantom{\sum}\smash{\mathop{ \vphantom{\sum}\smash{\mathop{\vphantom{\sum}\smash{\mathop{\vphantom{\sum}\smash{ \mathop{\vphantom{\leftleft\{\vphantom{\left\left\{\left\{\left\{\left\{\left\{\left\{ \left\{\left\{\left\{\left\{\left\left\{\left\{\left\{\left\{{ \left\{\left\left\{{ \left\{{ \leftleft}}}}}}} \right}\right}}}}}}}}_{x\in\mathbb{R}^{p}}\mathcal{L}_{p}(x^{k+1},z,y^{k})\\ y^{k+1}&:=y^{k}+\rho\big{(}x^{k+1}-z^{k+1}\big{)} \end{split} } \tag{8}\]  
Proximal gradient methods are well known for solving convex optimization problems for which the objective function is the sum of a smooth loss function and a non-smooth penalty function [9; 29; 30]. A well-studied example is \(\ell_{1}\) regularized least squares [1; 5]. It should be noted that an ordered \(\ell_{1}\) norm is convex but not smooth. Therefore, these researchers used a proximal gradient method.