# Variational Multiscale Nonparametric Regression: Algorithms and Implementation
## 3 Computational Methods
### ADMM Method  
The alternating direction methods of multipliers (ADMM) can be seen as a variant of the augmented Lagrangian method (see [58; 59] for classical references). To derive it, we introduce a slack variable \(h\in\mathbb{R}^{\#\Lambda_{n}}\) and rewrite (3) it into the equivalent problem  
\[\operatorname*{argmin}_{v\in\mathbb{R}^{n},w\in\mathbb{R}^{\#\Lambda_{n}}}F(w )+G(v)\ \ \text{subject to}\ Kv=w.\]  
By the convex duality theory, it is equivalent to find the saddle point of the augmented Lagrangian \(L_{\lambda}(v,w;h)\), that is,  
\[\operatorname*{argmin}_{v,w}\ \max_{h\in\mathbb{R}^{\#\Lambda_{n}}}F(w)+G(v)+ \langle h,Kv-w\rangle+\frac{\lambda}{2}\|Kv-w\|^{2}\]  
where \(h\in\mathbb{R}^{\#\Lambda_{n}}\) is the Lagrangian multiplier and \(\lambda>0\). As its name suggests, the ADMM algorithm solves this saddle point problem alternately over \(v,w\) and \(h\) in a Gauss-Seidel fashion (i.e., successive displacement). The details are given in Algorithm 2 below.  
```
0:\(\delta,\tau>0,\theta\in[0,1]\), \(k=0\), \((v_{0},w_{0})\in X\times Y\), stopping criterion
1:while stopping criterion not satisfied do
2:\(w_{k+1}\leftarrow\big{(}I+\delta\,\partial F^{\star}\big{)}^{-1}(w_{k}+\delta \,K\,\widetilde{v}_{k})\)
3:\(v_{k+1}\leftarrow\big{(}I+\tau\,\partial G\big{)}^{-1}(v_{k}-\tau\,K^{\star}\,w _{k+1})\)
4:\(\widetilde{v}_{k+1}\leftarrow v_{N}+\theta\big{(}v_{k+1}-v_{k}\big{)}\)
5:\(k\gets k+1\)
6:endwhile
7:Return \((v_{k},w_{k})\)
```  
**Algorithm 2**Chambolle-Pock algorithm  
The usage of the ADMM for the problem (3) was first proposed by [PERSON] et al. [31]. One central difference compared to the Chambolle-Pock algorithm is that the ADMM splitting avoids the usage of \(F^{\star}\). Instead, it deals with the high-dimensional constraint in an explicit way, which ultimately results in a slower performance.  
From the steps performed by the ADMM in Algorithm 2, the first one (Line 2) involves the proximal operator of \(R\) and can typically be dealt with with a standard algorithm (see the discussion in the Chambolle-Pock algorithm, Section 3.1). The second step (Line 3) is more challenging, as it involves solving the optimisation problem  
\[w_{k}=\underset{w}{\text{argmin}}\ \frac{\lambda}{2}\|w-(Kv_{k}+\lambda^{-1}h_{k-1}) \|^{2}\ \text{ subject to }\max_{\lambda\in\Lambda_{n}}|w_{\lambda}-\langle\phi_{ \lambda},Y\rangle|\leq q_{n}. \tag{11}\]  
In other words, we have to find the orthogonal projection of the point \(Kv_{N}+\lambda^{-1}h_{N-1}\) to the feasible set  
\[\big{\{}w\in\mathbb{R}^{\#\Lambda_{n}}\ |\ \max_{\lambda\in\Lambda_{n}}|w_{ \lambda}-\langle\phi_{\lambda},Y\rangle|\leq q_{n}\big{\}}.\]  
This set is the intersection of \(2\#\Lambda_{n}\) half-spaces, and it is known to be non-empty (as it always contains \(\{\langle Y,\phi_{\lambda}\rangle\ |\ \lambda\in\Lambda_{n}\}\)). The projection problem (11) can be solved by [PERSON]'s algorithm [60; 61], which converges linearly [62] (see [63] for an efficient stopping rule).  
Finally, it follows from Corollary 3.1 in [64] that the ADMM has a linear convergence guarantee for the problem (6).  
```
0: data \(Y\in\mathbb{R}^{n}\), step size \(\lambda>0\), tolerance \(\epsilon>0\), initial values \(v_{0},w_{0},h_{0}\)
1:while\(\max\{\|Kv_{k}-w_{k}\|,\|K(v_{k}-v_{k-1})\}>\epsilon\)do
2:\(v_{k}=\underset{w}{\text{argmin}}v\frac{\lambda}{2}\|Kv-(w_{k-1}-\lambda^{-1 }h_{k-1})\|^{2}+G(v)\)
3:\(w_{k}=\underset{w}{\text{argmin}}w\frac{\lambda}{2}\|w-(Kv_{k}+\lambda^{-1}h_{ k-1})\|^{2}+F(w)\)
4:\(h_{k}=h_{k-1}+\lambda(Kv_{k}-w_{k})\)
5:\(k\gets k+1\)
6:endwhile
7:Return \((v_{k},w_{k})\)
```  
**Algorithm 2**Alternating direction method of multipliers (ADMM)