# Variational Multiscale Nonparametric Regression: Algorithms and Implementation
## 2 Theoretical Properties of Variational Multiscale Estimation Methods
### Theoretical Guarantees  
Estimators of the form (3) have been analysed from a theoretical viewpoint in a variety of settings. When the dictionary basis functions \(\phi_{\lambda}\) are orthogonal, this becomes particularly simple, as then the evaluation functionals (if the truth equals \(g\)) \(\langle\phi_{\lambda},e\rangle\) become independent in model (3). This is valid for wavelet systems and their statistical analysis is vast (see, e.g., [44; 45; 46; 47; 48; 49; 50; 51; 52] for various forms of adaptation and thresholding techniques). If the dictionary is redundant the analysis becomes more difficult (see, however, [53] for the asymptotic validity of hard and soft thresholding in this case) and only in recent years it could be been shown that suitably constructed MINDs with redundant dictionaries perform optimal in a statistical (minimax) sense over certain function spaces. In the following, we summarise some of these results in an informal way. To this end, the notion of minimax optimality is key, which compares a given estimator with the _best_ possible estimator in terms of their _worst case error_ (see Equation (4) and Definition 3.1 in [13] for a formal definition).  
* _Sobolev spaces_: The authors of [14; 16] analysed the MIND with \(R(g)=|g|_{H^{s}}\) and \(\{\phi_{\lambda}\}\) being a set of indicator functions of rectangles at different locations and scales. They showed that, for the choice \(q_{n}=C\,\sigma\,\sqrt{\log n/n}\) for an explicit constant \(C>0\), the MIND is minimax optimal up to logarithmic factors for estimating functions in the Sobolev space \(H^{s}\). This means that the MIND's expected reconstruction error is of the same order as the error of the best possible estimator, i.e., \[1\leq\frac{\sup_{|f|_{H^{s}}\leq L}\mathbb{E}\|f-\hat{f}_{MIND}\|_{L^{p}}}{ \inf_{\text{all estimators}}\hat{f}\sup_{|f|_{H^{s}}\leq L}\mathbb{E}\|f- \hat{f}\|_{L^{p}}}\leq C\,Polylog(n).\] (4) Besides minimax optimality, [PERSON] et al. [16] also showed that the MIND with \(H^{s}\) regularisation is also optimal for estimating functions in other Sobolev spaces \(H^{t}\) for certain smoothness indices \(t\), a phenomenon known as adaptation.
* _Bounded variation_: In [29], the MIND with bounded variation regularisation \(R(g)=|g|_{BV}\) was considered. It was shown that it is optimal in a minimax sense up to logarithms for estimating functions of bounded variation if \(d=2\). For \(d\geq 3\), the discretisation matters further and this could only be shown in a Gaussian white noise model. Such results hold for a variety of dictionaries \(\{\phi_{\lambda}\}\), such as wavelet bases, mixed wavelet and curvelet dictionaries, as well as suitable systems of indicator functions of rectangles.  
In addition to theoretical guarantees, these results also provide a way of choosing the threshold parameter \(q_{n}\) in (3). Indeed, both for Sobolev and for bounded variation regularisation, it is shown (see again [16; 29]) that the choice \(q_{n}=C\,\sigma\,\sqrt{(\log n)/n}\) for an explicit constant \(C>0\) yields asymptotically optimal performance. The constant \(C\) depends on the dimension \(d\) and smoothness \(s\) of the functions, on whether we consider Sobolev or BV regularisation, and on the dictionary \(\{\phi_{\lambda}\}\) we employ.