However, since \(\Vert  \cdot \Vert _0\)  is not a continuous function, we proxy the \(\Vert  \cdot \Vert _0\)  by the \(L_1\)  norm. The resulting regularization functional is, \(\Vert  \mathbf {H}\widehat{f} (\mathbf {X}) \Vert _1\) . When learning over a parameterized function family, \(\widehat{f} = f_{, the resulting regularized ERM we consider in this paper is,\begin{equation} \min _{ \mathcal {L}_n (+R(, \text{ where } R( \triangleq \frac{\lambda }{\sqrt{2^d}} \Vert \mathbf {H}{\bf f}_{\theta }({\bf X})\Vert _1, }where \qquad \mathrm {(OBJ)}\mathcal {L}_n ( \triangleq \frac{1}{n} \sum _{i=1}^n \left[ \left( f_{ (x^i) - y^i ^2  is the empirical mean squared error (MSE). Regularizing by R ( of the above form is known as \textit {spectral regularization (SP)}.}\right.\begin{remark}The scaling of the regularization parameter, \frac{\lambda }{\sqrt{2^d}}, is motivated from the linearly parameterized setting of \mathcal {F} = \lbrace  \langle  x \rangle : \mathbb {R}^d \rbrace . An explicit computation gives, \frac{\lambda }{\sqrt{2^d}}\Vert  \mathbf {H}f_{ (\mathbf {X}) \Vert _1 = \lambda \Vert  _1, which is the scaling of the regularization parameter as used in LASSO. }\end{remark}The regularization weight \right.\lambda > 0 strikes a balance between the empirical MSE and the spectral regularization, and is set empirically using cross validation. Since the aggregate loss \mathcal {L}_n ( + R ( is subdifferentiable with respect to the model parameters {\theta }, we can apply stochastic (sub-)gradient methods on the aggregate loss. Note however that, in general, as a function of the parameter , both the MSE, as well as the SP regularization are non-convex functions.\end{equation}\section {Theoretical Analysis}}To develop some intuition about the general problem, consider the special case of learning over the set of linear functions. Namely, \) F = {  : Rd }\(. The polynomial representation of any linear function \) f (x) =  x \( is simply \) i [d] i xi\( where only the order-\) 1\( coefficients are non-zero. Thus, the assumption that the polynomial representation of \) f\( is composed of at most \) k\( monomials is equivalent to saying that \)  is \(k\) -sparse. Thus in the linear setting, the problem boils down to sparse linear regression [1]}. Furthermore, in the linear setting, spectral regularization has an explicit representation in terms of its parameter \(. In particular, here \) R ( = 2d  Hf (X) 1 =  1\(. Thus, the proposed objective function, (\ref {eq:OBJ}), when specialized to the linear setting boils down to the LASSO objective, \) 1n i=1n ( xi, - yi)2 +  1\(, which can be efficiently solved by gradient descent, and is known to be statistically optimal in the finite sample regime \cite {6034739}.\)
