Our theoretical analysis and empirical validations demonstrate the statistical benefits of spectral regularization for learning pseudo-Boolean functions. Future works involve analyzing the algorithms that can achieve such statistical performance. It would be tempting to ask under what conditions stochastic gradient descend achieves stationary points with restricted secant and quadratic growth conditions (for which we have clear empirical evidences). Further, the statistical analysis of the computationally-efficient optimization algorithms for spectral regularization is still poorly understood. On the algorithmic side, spectral algorithms for pseudo-Boolean functions can be extended to generalized Fourier transform to accommodate a larger class of data-frugal combinatorial problems. Overall, our work provides a concrete framework to connect combinatorial algorithms with strong theoretical guarantees and nonlinear machine learning models with strong generalization power.

Additional Empirical Validations
Visualization of real-world functions in WHT
In this subsection, we visualize the combinatorial function evaluations and the WHT of the evaluation vector, that is, the left and right hand sides of the equation below:
\(\begin{bmatrix} f(x) : x \in \lbrace  \pm 1 \rbrace ^d \end{bmatrix}^T = \mathbf {H}\begin{bmatrix} \alpha _z : z \in \lbrace  \pm 1 \rbrace ^d \end{bmatrix}^T,\) 

for the experimental data obtained from the fluorescence protein [1]}. In addition to these plots, we have attached videos as supplemental materials where we visualize the learning trajectory of a DNN initialized using Xavier initialization under data-scarce (red) and data-sufficient (blue) regimes. DNNs start from a local minima that does not have a well-structured WHT representation, and then gets sparser with training. However, if a sufficient amount of data is not available for training, the network does not converge to a good solution. Spectral regularisation enable DNN converge to the sparse solution in the data-scarce regime.
<FIGURE>
Convergence: training and validation
In this subsection, we include additional empirical results which focus on the convergence properties of spectral regularization for training DNNs. The first objective we study is in validating whether stochastic gradient descent (SGD) indeed converges to approximate first order stationary interpolators (def:afosi). The goal of these experiments are to see whether, upon running SGD, the MSE loss gets sufficiently small even when the training loss, against which stochastic gradients are computed, is augmented with spectral regularization. In Fig. REF , we plot the empirical training and validation loss of DNNs trained both with the MSE loss and the additional spectral regularization. We use a depth-4 fully connected network (learning rate\(=1\times 10^{-1}\) ) to train on the fluorescence protein [1]} dataset (also used in the main paper).
<FIGURE><FIGURE>
Validating assumption 1(b): additional plots
In this subsection, we include additional plots on empirical experiments on validating Assumption 1(b). The goal of this experiment is to also provide more details about the new weight initialization method discussed in the Empirical Studies section of the main paper. Note that A1 requires showing that for any \(\theta \) ,
\(\mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ \left( f_{ (x) - f_{*} (x) ^2  \ge C^*_{n,\delta } \Vert   * \Vert _2^2.}However, since it is prohibitively expensive to check this for all choices of \right.\right.\theta , and moreover since the models we consider exhibit some smoothness, we resort to checking this condition only for randomly sampled  around the reference *. In particular, we collect a set of training data points (x^i,y^i)_{i=1}^{n=1000} from an arbitrary sparse polynomial, f(x) : \lbrace  \pm 1 \rbrace ^{13} \rightarrow \mathbb {R}, defined as 3 x_1 + 4 x_2 x_3 + 5 x_4 x_5 + x_{12}.\) 
First we train a DNN using SGD on the unregularized MSE, and define this as \({\theta }^{\ast }\) . Then, we repeatedly perturb the weights \(K\)  times independently with Gaussian noise to generate \({\theta }^{\text{pert},k} = {\theta }^{\ast }+W_k\) , where \(W \sim \mathcal {N} (0,\sigma ^2 I)\)  is independent and normally distributed, for \(k=1,\cdots ,K\) . By concentration of measure, under the Gaussian perturbations, note that \(\Vert  {\text{pert},k} - * \Vert _2^2\)  concentrates around \(M \sigma ^2\) , where \(M\)  is the number of parameters in the network. Therefore, instead of computing the ratio,
\(C_{n,\delta }^* \min _{ \frac{\mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ \left( f_{ (x) - f_{*} (x) ^2 }{\Vert   * \Vert _2^2}\right.we instead approximate it by the ratio (up to scaling by \right.M),{\begin{@align}{1}{-1} \min _{k \in [K]} \frac{\sum _{i=1}^n \left[ (f_{\theta ^{\text{pert},k}}(x^i)-f_{\theta ^*}(x^i))^2 \right]}{\sigma ^2}\end{@align}}as an approximate proxy for perturbations at the scale of \sigma  around * in L_\infty  distance, which is more accurate, as K grows larger. In Fig.~\ref {fig:val_assump}, we plot the ratio in {eq:lkklll} as a function of \sigma .}{W}e repeat this experiment when * is trained starting from weight initialization, and plot the estimated ratio in Fig.~\ref {fig:assumption4}.}\begin{definition}[Weight initialization]  Weight initialization, refers to initialization of the network by first running 100 epochs of SGD against the \textit {unregularized MSE}. From this starting point, subsequently we ``turn on^{\prime \prime } the regularization and run SGD against the MSE with spectral regularization.\end{definition}\) 
Each subplot shows the estimated QG ratio (eq:lkklll) for models initialized with weight initialization, at the 100, 200, 300 and 400 epochs mark respectively. The plots demonstrate that our weight initialization method significantly improves the QG constant \(C_{n,\delta }^*\)  along sample trajectory encountered by the SGD, compared to models trained with spectral regularization starting from a random Xavier initialization.
<FIGURE>
Comparison to other regularization schemes
In this subsection, we compare the performance of neural network under SP regularization with other regularization schemes which directly penalize the \(\ell _1\)  and \(\ell _2\)  norm of the weights of the neural network. The goal of these experiments is to show that promoting sparsity among the weights does not have the same effect as promoting sparsity in the spectral representation of neural networks. We test the generalization power of these networks using the datasets in Fig. REF  under the same experimental conditions. In Fig. REF  we demonstrate that while direct weight-regularization schemes such as \(\ell _1\)  and \(\ell _2\)  norm improve the generalization gap of neural networks, the generalization gap is significantly larger for SP regularization.
<FIGURE>
Statistical performance under QG condition - Proof of theorem:111
In this section we discuss the proof of theorem:111. This result is a consequence of a more general result which characterizes the performance of stationary points of the MSE with spectral regularization when the regularization parameter, \(\lambda \) , is chosen arbitrarily.
2Theorem  
Define \(\Delta = \frac{C^*_{n,\delta }}{2 \mu } - \frac{(2d+1) \lambda }{2} - \frac{3}{2} \lambda \sqrt{k}\)  and assume \(\Delta > 0\) . Suppose the regularization factor \(\lambda \)  satisfies eq:lambda-asmp, namely,
\(\lambda \ge 4 C_0 \sigma \sqrt{ \frac{d + \log (1/\delta )}{n}} \) 
Consider a learner which returns a \(\Delta ^2\) -approximate first order stationary interpolator (def:afosi) of the loss \(\mathcal {L}_n ( + R(\) . Then, under Assumptions REF , REF  and , with probability \(\ge 1 - 2\delta \) ,
\(\Vert  \hat{- * \Vert _2 \le \frac{3 \lambda L \sqrt{k}}{C_{n,\delta }^*}.}\) 
12Lemma  
Under A2, for any \(\mathbb {R}^m\)  and any subgradient \(G \in (\nabla R) (\) ,
\(&\Big \langle  * , \nabla \mathcal {L}_n ( + G \Big \rangle + 2 \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ \left( g_{*} (x) - y(x)) \right) \left( g_{*} (x) - g_{ (x)   \\&\ge 2 \mathrm {Err}_{n} (*)+ R( - R(*) - \left( (2d+1) \lambda \mu + 2 \mu \sqrt{\mathcal {L}_n (} \right) \Vert   * \Vert _2^2}\right.\begin{proof}The proof of this result builds on the analysis in {lemma:cow0}. Observe that,{\begin{@align}{1}{-1}\left\langle  *, \nabla \mathcal {L}_n ( \right\rangle = \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ 2 (g_{ (x) - y(x)) \left\langle  *, \nabla g_{ (x) }\right.For each x \in [2^d] and each  and *, there exists a x \in \textsf {conv} (\lbrace *\rbrace ) such that g_{ (x) - g_{*} (x) = \left\langle \nabla g_{ (x),  * - ( *)^T \nabla ^2 g_{x} (x) ( *). Plugging this in, and using the assumption that -\mu I \preceq \nabla ^2 g_{ (x) \preceq \mu I,{\begin{@align}{1}{-1}&\left\langle  *, \nabla \mathcal {L}_n ( \right\rangle - 2 \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ \left( g_{*} (x) - y(x)) \right) \left( g_{ (x) - g_{*} (x)   \\&= \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ 2 (g_{ (x) - y(x)) \langle  *, \nabla g_{ (x) \rangle - 2 (g_{*} (x) - y(x)) (g_{ (x) - g_{*} (x))  \\&\ge \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ 2 (g_{ (x) - y(x)) (g_{ (x) - g_{*} (x)) - 2 (g_{*} (x) - y(x)) (g_{ (x) - g_{*} (x))  \\&\qquad \qquad -2 \mu \Vert   * \Vert _2^2 \left( \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ | g_{ (x) - y (x) |   \\&\ge 2 \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ ( g_{ (x) - g_{*} (x))^2  -2 \mu \Vert   * \Vert _2^2 \left( \sqrt{\mathcal {L}_n (} \right) }\right.where the last inequality follows by Jensen^{\prime }s inequality.}\right.\right.}Putting together {lemma:reglemma} and {eq:1232220}, for any subgradient G \in (\nabla R) (, we have,{\begin{@align}{1}{-1}&\langle  *, \nabla \mathcal {L}_n ( + G \rangle - 2 \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ \left( g_{*} (x) - y(x)) \right) \left( g_{ (x) - g_{*} (x)   \\&\ge 2 \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ ( g_{ (x) - g_{*} (x))^2  + \frac{\lambda }{\sqrt{2^d}} \left( \Vert  \mathbf {H}g_{ (\mathbf {X}) \Vert _1 - \Vert  \mathbf {H}g_{*} (\mathbf {X}) \Vert _1  \\&\qquad \qquad - \left( (2d+1) \lambda \mu + 2 \mu \sqrt{\mathcal {L}_n (} \right) \Vert   * \Vert _2^2}\right.This completes the proof.}\right.Plugging in  \hat{ into {lemma:cow}, and noting that the learner returns a first order stationary point of the regularized loss, 0 \in \nabla \mathcal {L}_n (\hat{) + (\nabla R) (\hat{), choosing G appropriately,{\begin{@align}{1}{-1} &2 \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ \left( g_{*} (x) - y(x)) \right) \left( g_{*} (x) - g_{\hat{} (x)   \\&\ge 2 \mathrm {Err}_{n} (\hat{,*)+ R(\hat{) - R(*) - \left( (2d+1) \lambda \mu + 2 \mu \sqrt{\mathcal {L}_n (\hat{)}  \Vert  \hat{- * \Vert _2^2 }}Under assumption (A1), recall that we assume that \right.\hat{ is a sufficiently good interpolator in that, \mathcal {L}_n (\hat{) \le \left( \frac{C_{n,\delta }^*}{2\mu } - \frac{(2d+1) \lambda }{2} - \frac{3}{2} \sqrt{k} \lambda \right)^2. Simplifying {eq:prefinal1} under this assumption gives,{\begin{@align}{1}{-1}&2 \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ \left( g_{*} (x) - y(x)) \right) \left( g_{*} (x) - g_{\hat{} (x)   \nonumber \\&\ge 2 \mathrm {Err}_{n} (\hat{,*)+ R(\hat{) - R(*) - \left( C_{n , \delta }^* - 3\mu \lambda \sqrt{k} \right) \Vert  \hat{- * \Vert _2^2 }}}Next we bound the LHS of {eq:final1}.}\right.\begin{lemma} Recall the assumption {eq:lambda-asmp:rep} lower bounding \lambda . Under this condition, define \mathcal {E}_4 as the event that for all \mathbb {R}^m,{\begin{@align}{1}{-1}\mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ \left( g_{*} (x) - y(x)) \right) \left( g_{*} (x) - g_{ (x)   \le \frac{\lambda }{2} \sqrt{\frac{1}{2^d}} \left\Vert  \mathbf {H}\left( g_{*} (\mathbf {X}) - g_{ (\mathbf {X})  _1}\right.Then, \right.\Pr (\mathcal {E}_2) \ge 1-\delta .}\begin{proof}The proof of this result is similar to that of {lemma:31}, and we include the details for completeness. For each sample x^{\prime } \in D_n, define the noise in the sample as z(x^{\prime }) = g_{*} (x^{\prime }) - y (x).Likewise, define the noise vector \mathbf {z}_{D_n} = \lbrace  \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} [z(x^{\prime }) \mathbb {I} (x^{\prime }=x)] : x \in [2^d] \rbrace . Then, by an application of Holder^{\prime }s inequality, we have,{\begin{@align}{1}{-1}\mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ \left( g_{*} (x) - y(x)) \right) \left( g_{*} (x) - g_{\hat{} (x)  &\le \left\Vert  \mathbf {H}\mathbf {z}_{D_n} \right\Vert _\infty \left\Vert  \mathbf {H}\left( g_{*} (\mathbf {X}) - g_{\hat{} (\mathbf {X})  _1.}\right.Note that for each fixed row \right.i \in [2^d], \langle \mathbf {H}_i, \mathbf {z}_{D_n} \rangle = \sum _{j \in 2^d} \mathbf {H}_{ij} \mathbf {z}_{D_n} (j). Note that the coordinates of \mathbf {z}_{D_n} are independently distributed and subgaussian. Therefore, by Hoeffding^{\prime }s inequality, for some constant C_0,\begin{equation}\mathrm {Pr} \left( \langle \mathbf {H}_i, \mathbf {z}_{D_n} \rangle \ge C_0 \sqrt{\frac{\left(\sum _{j \in [2^d]} \mathrm {Var} (\mathbf {z}_{D_n} (j)) \right) \log (1/\delta )}{2^d}} \right) \le \delta \end{equation}Note that the coordinate of \mathbf {z}_{D_n} labelled by x \in \lbrace  \pm 1 \rbrace ^d, \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} [z(x^{\prime }) \mathbb {I} (x^{\prime }=x)], is the sum of D_n (x) independent \mathcal {N} (0,\sigma ^2) Gaussians scaled by 1/n, where D_n (x), defined as the number of times x is sampled in D_n. Therefore, \mathrm {Var} (\mathbf {z}_{D_n} (i)) = \frac{\sigma ^2 D_n (x)}{n^2}.By union bounding over the 2^d rows of \mathbf {H}, with probability \ge 1 - \delta ,\begin{equation}\mathrm {Pr} \left( \Vert  \mathbf {H}\mathbf {z}_{D_n} \Vert _\infty \ge C_0 \sqrt{\frac{ \left(\sum _{x \in [2^d]} \frac{\sigma ^2 D_n (x)}{n^2} \right) \log (2^d/\delta )}{2^d}} \right) \le \delta .\end{equation}Note that \sum _{x \in [2^d]} D_n (x) = n, and therefore, with probability \ge 1 - \delta ,{\begin{@align}{1}{-1}\Vert  \mathbf {H}\mathbf {z}_{D_n} \Vert _\infty \le C_0 \sigma \sqrt{\frac{1}{2^d}} \sqrt{\frac{d + \log (1/\delta )}{n}} \le \frac{\lambda }{4\sqrt{2^d}}.\end{@align}}where the last inequality follows by the assumption on \lambda . This implies that with probability \ge 1 - \delta ,{\begin{@align}{1}{-1}\mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ \left( g_{*} (x) - y(x)) \right) \left( g_{*} (x) - g_{\hat{} (x)   \le \frac{\lambda }{2} \sqrt{\frac{1}{2^d}} \left\Vert  \mathbf {H}\left( g_{*} (\mathbf {X}) - g_{\hat{} (\mathbf {X})  _1}\right.\right.}\right.\right.\end{@align}}}\right.\right.\end{@align}}\end{proof}\right.\right.\end{@align}}\end{lemma}Plugging {lemma:3} into (\ref {eq:final1}) and rearranging both sides, under the event \right.\mathcal {E}_4,{\begin{@align}{1}{-1}&2 \mathrm {Err}_{n} (\hat{,*)- \left( C^*_{n,\delta } - 3 \lambda \mu \sqrt{k} \right) \Vert  \hat{- * \Vert _2^2 \nonumber \\&\overset{(i)}{\le } \frac{\lambda }{\sqrt{2^d}} \left\Vert  \mathbf {H}g_{*} (\mathbf {X}) \right\Vert _1 - \frac{\lambda }{\sqrt{2^d}} \left\Vert  \mathbf {H}g_{\hat{} (\mathbf {X}) _1 + \frac{\lambda }{2\sqrt{2^d}} \left\Vert  \mathbf {H}\left( g_{*} (\mathbf {X}) - g_{\hat{} (\mathbf {X})  _1 \\&\overset{(ii)}{\le } \frac{\lambda }{\sqrt{2^d}} \left( \left\Vert  \mathbf {H}g_{*} (\mathbf {X}) \right\Vert _1 - \left\Vert  \mathbf {H}g_{\hat{} (\mathbf {X}) _1 + \frac{1}{2} \left\Vert  \mathbf {H}g_{*} (\mathbf {X}) \right\Vert _1 + \frac{1}{2} \left\Vert  \mathbf {H}g_{\hat{} (\mathbf {X}) _1  \\&= \frac{\lambda }{2\sqrt{2^d}} \left( 3 \left\Vert  \mathbf {H}g_{*} (\mathbf {X}) \right\Vert _1 - \left\Vert  \mathbf {H}g_{\hat{} (\mathbf {X}) _1  }\right.where \right.(i) follows from the definition of the regularization term, R ( = \frac{\lambda }{\sqrt{2^d}} \left\Vert  \mathbf {H}g_{ (\mathbf {X}) _1. On the other hand, (ii) follows by triangle inequality of the norm \Vert  \cdot \Vert _1.Next we focus on the LHS of the above expression and simplify it further. By the quadratic growth condition in {A1}, under the event \mathcal {E}_3, which is assumed to happen with probability \ge 1 - \delta , \mathrm {Err}_{n} (\hat{,*)\ge C_{n,\delta }^* \Vert  \hat{- * \Vert _2^2. Therefore, under \mathcal {E}_3 and \mathcal {E}_4,{\begin{@align}{1}{-1}&2 \mathrm {Err}_{n} (\hat{,*)- \left( C_{n,\delta }^* - 3 \lambda \mu \sqrt{k} \right) \Vert  \hat{- * \Vert _2^2 \\&\ge \Vert  \hat{- * \Vert _2^2 \left( C_{n,\delta }^* + 3 \lambda \mu \sqrt{k} \right) \\&\ge 0. }}Plugging this into {eq:24} results in the inequality,{\begin{@align}{1}{-1} \frac{\lambda }{2\sqrt{2^d}} \left( 3 \left\Vert  \mathbf {H}g_{*} (\mathbf {X}) \right\Vert _1 - \left\Vert  \mathbf {H}g_{\hat{} (\mathbf {X}) _1  \ge 0.}\right.Under the events \right.\mathcal {E}_3 and \mathcal {E}_4.\end{@align}Next, we apply \cite [Lemma 5]{loh2015regularized} to the function \rho _\lambda (\cdot ) = \Vert  \cdot \Vert _1 , and note that by assumption \mathbf {H}g_{*} (\mathbf {X}) is k-sparse. By defining \nu = \mathbf {H} (g_{*} (\mathbf {X}) - g_{\hat{} (\mathbf {X})) and A as the set of k largest indices of \nu  in absolute value.{\begin{@align}{1}{-1}\frac{\lambda }{2\sqrt{2^d}} \left( 3 \left\Vert  \mathbf {H}g_{*} (\mathbf {X}) \right\Vert _1 - \left\Vert  \mathbf {H}g_{\hat{} (\mathbf {X}) _1  &\overset{(i)}{\le } \frac{\lambda }{\sqrt{2^d}} \left( 3 \Vert  \nu _A \Vert _1 - \Vert  \nu _{A^c} \Vert _1 \right) \\&\le \frac{3\lambda \sqrt{k}}{2 \sqrt{2^d}} \Vert  \nu _A \Vert _2 \\&\le \frac{3\lambda \sqrt{k}}{2 \sqrt{2^d}} \Vert  \nu \Vert _2. }\right.here, \right.(i) uses the fact that 3 \left\Vert  \mathbf {H}g_{*} (\mathbf {X}) \right\Vert _1 - \left\Vert  \mathbf {H}g_{\hat{} (\mathbf {X}) _1 \ge 0 from {eq:25}.}\right.\end{@align}Finally, we plug the relation between \Vert  v \Vert _2 = \Vert  g_{*} (\mathbf {X}) - g_{\hat{} (\mathbf {X}) \Vert _2 to \Vert  \hat{- * \Vert _2 proved in {lemma:00300} into {eq:b12}. This results in the inequality,{\begin{@align}{1}{-1}\frac{\lambda }{2\sqrt{2^d}} \left( 3 \left\Vert  \mathbf {H}g_{*} (\mathbf {X}) \right\Vert _1 - \left\Vert  \mathbf {H}g_{\hat{} (\mathbf {X}) _1  \le 3 \mu \lambda \sqrt{k} \Vert  \hat{- * \Vert _2^2 + 3 \lambda L \sqrt{k} \Vert  \hat{- * \Vert _2}}Plugging this back into {eq:24}, under \mathcal {E}_3 and \mathcal {E}_4,{\begin{@align}{1}{-1}2 \mathrm {Err}_{n} (\hat{,*)- \left( C^*_{n , \delta } - 3 \lambda \mu \sqrt{k} \right) \Vert  \hat{- * \Vert _2^2 \le 3 \mu \lambda \sqrt{k} \Vert  \hat{- * \Vert _2^2 + 3 \lambda L \sqrt{k} \Vert  \hat{- * \Vert _2.}}Resulting in the bound,{\begin{@align}{1}{-1}2 \mathrm {Err}_{n} (\hat{,*)\le 3 \lambda L \sqrt{k} \Vert  \hat{- * \Vert _2 + C^*_{n , \delta } \Vert  \hat{- * \Vert _2^2.}}Under the quadratic growth condition, by the event \mathcal {E}_3 in {A1}, \mathrm {Err}_{n} (\hat{,*)\ge C_{n,\delta }^* \Vert  \hat{- * \Vert _2^2. Therefore, under the events \mathcal {E}_3 and \mathcal {E}_4 which jointly occur with probability \ge 1 - 2 \delta ,{\begin{@align}{1}{-1}\Vert  \hat{- * \Vert _2 \le \frac{3 \lambda L \sqrt{k}}{C_{n,\delta }^*}.}\end{@align}}{theorem:111} follows by choosing \lambda  appropriately according to {eq:lambda-asmp:rep} and showing that when the size of the dataset n grows to be sufficiently large, the conditions in {theorem:1} are satisfied.\subsection {Proof of {theorem:lb}}In this section, we prove a lower bound on the statistical error of parameter estimation. The objective is to show that for every learner \hat{,{\begin{@align}{1}{-1}\sup _{*} \mathbb {E} \left[ \Vert  \hat{- * \Vert _2  \gtrsim \sigma \sqrt{\frac{kd}{n}}.}\right.We first introduce an auxiliary result related to packing binary vectors with bounded Hamming weight.\end{@align}\begin{lemma} Assume that d \ge 3 and k \le 2^d/4. Then, there exists a set of 2^{(d-1) \lfloor k/2 \rfloor } binary vectors of length 2^d, denoted \mathcal {C}_k, each having at most k ones, such that: the hamming distance between any pair of vectors is at least \lfloor \frac{k}{2} \rfloor .\end{lemma}\begin{proof}The number of vectors within hamming distance \kappa = \lfloor k/2 \rfloor  of any vector is \binom{2^d}{\kappa }. Note that k - \kappa \ge \kappa .\end{proof}We can greedily construct a packing of size at least \binom{2^d}{k} / \binom{2^d}{\kappa } \ge \frac{(2^d-\kappa )!}{(2^d-k)!} \ge 2^{d (k-\kappa )} \left( \frac{3}{4} \right)^{k-\kappa } \ge 2^{d \kappa } \left( \frac{3}{4} \right)^{\kappa } \ge 2^{(d-1)\kappa } vectors before running out of binary vectors to choose. By construction, every pair of vectors has Hamming distance at least \kappa .}}}}Define the function space \mathcal {G} = \lbrace  g_{ (\cdot ) : \mathbb {R}^{2^d} \rbrace , where g_{ (x) is defined as the polynomial with coefficients specified by . Namely, g_{ (x) = \sum _{S \subseteq [d]} \theta _S \prod _{i \in S} x_i, where we index the 2^d coefficients of \theta  by the 2^d subsets of [d]. In an alternate notation, we may represent,{\begin{@align}{1}{-1} g_{ (x) = \left\langle \theta , 2^{[x]} \right\rangle }\end{@align}where 2^{[x]} denotes the 2^d length vector whose element indexed by some subset S \subseteq [d] is \prod _{i \in S} x_i.}Furthermore, we assume that the data generating distribution independently samples n pairs (x_i,y_i) where x_i \sim \mathrm {Unif} (\lbrace  \pm 1 \rbrace ^d) and y_i = g_{*} (x_i) + Z_i where Z_i \sim \mathcal {N} (0,\sigma ^2). Denote D_n = \lbrace  x_1,\cdots , x_n\rbrace .}By {lemma:packing}, the binary vectors belonging to \mathcal {C}_k can be used to construct a subset of the function space \mathcal {G}, defined as \mathcal {S}_k,{\begin{@align}{1}{-1}\mathcal {S}_k = \left\lbrace  g_{ (\cdot ) : \Delta \mathcal {C}_k .}\right.where \Delta > 0 is a scaling factor and \Delta \mathcal {C}_k = \lbrace  \Delta  \mathcal {C}_k \rbrace .\end{@align}Henceforth, we will consider ourselves with learning functions (resp. parameters) in the class \mathcal {S}_k (resp. \Delta \mathcal {C}_k).}First we show the properties on \mathrm {Err}_{n} (*) and \mathcal {G} in the statement of {theorem:lb}. Note that \mathcal {G} is a linear family by the representation in {eq:linrep}, and therefore \mu = 0.}In addition, note that,{\begin{@align}{1}{-1}\mathrm {Err}_{n} (*)&= \mathbb {E}_{x \sim D_n} \left[ ( g_{ (x) - g_{*} (x))^2  \\&= \mathbb {E}_{x \sim D_n} \left[ \left\langle  *, 2^{[x]} \right\rangle ^2 \right] \\&= ( *)^T \mathbb {E}_{x \sim D_n} \left[ 2^{[x]} (2^{[x]})^T \right] ( *) }\right.Note that A_x = 2^{[x]} (2^{[x]})^T is a matrix whose entries (indexed by pairs of subsets of [d]) can be described as A_x (S,T) = \prod _{i \in S} x_i \prod _{j \in S} x_j. Note that in expectation over x \sim \mathrm {Unif} (\mathbf {X}), we have that,{\begin{@align}{1}{-1}\mathbb {E}_{x \sim \mathrm {Unif} (\mathbf {X})} \left[ A_x (S,T) \right] = \mathbb {I} (S=T)\end{@align}}This is because if S \ne T, there exists an element i \in (S \setminus T) \cup (T \setminus S) (i.e. the symmetric difference of the two sets) and since \mathbb {E}_{x \sim \mathrm {Unif} (\mathbf {X})} [x_i] = 0, we get the required statement. Therefore,{\begin{@align}{1}{-1} \mathbb {E}_{x \sim \mathrm {Unif} (\mathbf {X})} [A_x] = I\end{@align}}Now, given n samples from the uniform distribution, \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} [A_x] is expected to concentrate around its expectation \mathbb {E}_{x \sim \mathrm {Unif} (\mathbf {X})} [A_x]. In particular, by invoking the matrix Bernstein inequality \cite {tropp}, we have that,{\begin{@align}{1}{-1}\mathrm {Pr} \left( \left\Vert  \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} [A_x] - \mathbb {E}_{x \sim \mathrm {Unif} (\mathbf {X})} [A_x] \right\Vert _{\mathrm {op}} \ge t \right) \le 2(2^d) \exp \left( -nt^2 / 2L^2 \right)\end{@align}}where L is an almost sure upper bound on \Vert  A_x \Vert _{\mathrm {op}}. Note that \Vert  A_x \Vert _{\mathrm {op}} = \Vert  2^{[x]} \Vert _2 = \sqrt{2^d} and therefore we may choose L = \sqrt{2^d}. This results in the bound,{\begin{@align}{1}{-1}\mathrm {Pr} \left( \left\Vert  \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} [A_x] - I \right\Vert _{\mathrm {op}} \ge \frac{1}{2} \right) \le 2(2^d) \exp \left( -n / 2^{d+3} \right)\end{@align}}Therefore, if n \gtrsim (d + \log (1/\delta ) ) 2^{d+3}, with probability \ge 1-\delta ,{\begin{@align}{1}{-1}\frac{1}{2} I \preceq \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} [A_x] \preceq \frac{3}{2} I.\end{@align}}In {eq:332}, this implies that, with probability \ge 1 - \delta ,{\begin{@align}{1}{-1}\mathrm {Err}_{n} (*)\ge \frac{1}{2} \Vert   * \Vert _2^2\end{@align}}And likewise, from the linear representation in {eq:linrep},{\begin{@align}{1}{-1}\mathbb {E}_{x \sim \mathrm {Unif} (\mathbf {X})} \left[ \nabla g_{*} (x) (\nabla g_{*} (x))^T \right] = \mathbb {E}_{x \sim \mathrm {Unif} (\mathbf {X})} \left[ 2^{[x]} (2^{[x]})^T \right] = I\end{@align}}where the last equation follows from {eq:Axexp}.\end{@align}}To generate the lower bound instance, suppose the ground truth parameter * is sampled uniformly from \Delta \mathcal {C}_k. Suppose the learner outputs a candidate parameter \hat{. The population level mean squared error of the learner is lower bounded by the testing error,{\begin{@align}{1}{-1}\sup _{* \in \mathbb {R}^{2^d}} \mathbb {E} \left[ \Vert  \hat{- * \Vert _2  &\ge \mathbb {E}_{* \sim \mathrm {Unif} (\Delta \mathcal {C}_k)} \left[ \mathbb {E} \left[ \left\Vert  \hat{- * _2   \\&\ge \frac{1}{4} \sqrt{\lfloor k/2 \rfloor } \Delta \inf _{\Psi } \mathbb {E}_{* \sim \mathrm {Unif} (\mathcal {C}_k)} \left[ \mathbb {I} (\Psi (D_n) ) \ne *) \right] }\right.where the infimum is over all tests functions which return a function in \right.\right.\mathcal {C}_k. This uses the fact that any estimator \hat{ induces a testing function for * by returning the \Delta \mathcal {C}_k such that \Vert   \hat{\Vert _2 is smallest. If this test makes a mistake, then \hat{ must have predicted > \frac{1}{2}\sqrt{\lfloor k/2 \rfloor } entries of * as < \Delta /2 instead of \Delta  or > \Delta /2 instead of 0 (making an error of at least \Delta /2 on these coordinates).}The optimal hypothesis testing error can be lower bounded by Fano^{\prime }s inequality as follows,{\begin{@align}{1}{-1}\inf _{\Psi } \mathbb {E}_{* \sim \mathrm {Unif} (\Delta \mathcal {C}_k)} \left[ \mathbb {I} (\Psi (D_n) ) \ne *) \right] \ge 1 - \frac{I (*;D_n) + \log (2)}{\log |\Delta \mathcal {C}_k|} \end{@align}}For each parameter \Delta \mathcal {C}_k, define the distribution,{\begin{@align}{1}{-1}P_{ (D_n) = \prod _{i=1}^n \frac{1}{\sqrt{2\pi }} \exp \left( - \frac{1}{2 \sigma ^2} (y_i - g_{ (x_i))^2  \times \left( \frac{1}{2^d} \right). }\right.which captures the data distribution when the underlying ground truth parameter is . Note that D_n \sim P_{*}; marginally x_i is uniformly distributed on the hypercube and conditionally y_i is normally distributed with mean g_{*} (x_i) and variance \sigma ^2.Note that the mutual information can be bounded as,{\begin{@align}{1}{-1}I(*,D_n) &= \inf _{Q} \mathbb {E}_{* \sim \mathrm {Unif} (\Delta \mathcal {C}_k)} \left[ \textsf {KL} (P_{*} \Vert  Q) \right] \\&\le \mathbb {E}_{* \sim \mathrm {Unif} (\Delta \mathcal {C}_k)} \left[ \textsf {KL} (P_{*} \Vert  P_0) \right] \end{@align}}where P_0 is the distribution of D_n when the ground truth function g_{ in {eq:ldddk} is chosen as 0 everywhere. Then,{\begin{@align}{1}{-1}\textsf {KL} (P_{*} \Vert  P_0) &= \frac{1}{2\sigma ^2} \mathbb {E}_{D_n \sim P_{*}} \left[ \sum _{i=1}^n 2 y_i g_{*} (x_i) - (g^*_{ (x_i))^2  \\&= \frac{1}{2\sigma ^2} \mathbb {E}_{D_n \sim P_{*}} \left[ \sum _{i=1}^n (g_{*} (x_i))^2\right] \\&= \frac{n}{2\sigma ^2} \mathbb {E}_{x_i \sim \mathrm {Unif} (\lbrace  \pm 1 \rbrace ^d)} \left[ (g_{*} (x_i))^2 \right] }\right.where the last equation just uses the fact that in P_{*}, the marginal distribution of x_i is uniform. For each *, by Parseval^{\prime }s theorem, \mathbb {E}_{x_i \sim \mathrm {Unif} (\lbrace  \pm 1 \rbrace ^d)} \left[ (g_{*} (x_i))^2\right] = k \Delta ^2. Overall, plugging into {eq:oasoa} and subsequently into {eq:oasoa1},{\begin{@align}{1}{-1}I(*,D_n) \le \mathbb {E}_{* \sim \mathrm {Unif} (\Delta \mathcal {C}_k)} \left[ \textsf {KL} (P_{*} \Vert  P_0) \right] = \frac{n k \Delta ^2}{2 \sigma ^2}\end{@align}}Putting these bounds into {eq:oasoa2} and subsequently into {eq:oasoa3} results in,{\begin{@align}{1}{-1}\mathbb {E}_{* \sim \mathrm {Unif} (\Delta \mathcal {C}_k)} \left[ \mathbb {E} \left[ \left\Vert  \hat{- * _2   &\ge \frac{1}{4} \sqrt{\lfloor k/2 \rfloor } \Delta \left( 1 - \frac{n k \Delta ^2/2\sigma ^2 + \log (2)}{\log 2^{(d-1)\lfloor k/2\rfloor }}\right) \\&\ge \frac{1}{4} \sqrt{\lfloor k/2 \rfloor } \Delta \left( 1 - 10\frac{(n k \Delta ^2/\sigma ^2 + 1)}{(d-1) \lfloor k/2 \rfloor }\right)}\right.Choosing \right.\right.\Delta = 8\epsilon /\sqrt{\lfloor k/2 \rfloor }, for a sufficiently large constant C, we get that for any learner, if n \le C \frac{\sigma ^2 d}{\Delta ^2} \asymp \frac{ \sigma ^2 kd}{\epsilon ^2},{\begin{@align}{1}{-1}\mathbb {E}_{* \sim \mathrm {Unif} (\Delta \mathcal {C}_k)} \left[ \mathbb {E} \left[ \left\Vert  \hat{- * _2   &\ge \epsilon \asymp \sigma \sqrt{\frac{kd}{n}}.}\right. \section {Proof of auxiliary lemmas}\right.\right.\end{@align}\subsection {Proof of {lemma:00300}}}By the Lagrange form of the Taylor series expansion, for any x, there exists a x such that,{\begin{@align}{1}{-1}g_{\hat{} (x) - g_{*} (x) &= (\hat{- *)^T \left( \nabla ^2 g_{x} (x) \right) (\hat{- *) + \left\langle \nabla g_{*} (x), \hat{- * }\right.Then, for each x \in \mathbf {X},{\begin{@align}{1}{-1}\left( g_{\hat{} (x) - g_{*} (x) ^2 &\le 2\mu \Vert  \hat{- *\Vert _2^4 + 2 \left\langle \nabla g_{\theta ^*} (x) , \hat{- * ^2}\right.Summing over x \in \mathbf {X} results in,{\begin{@align}{1}{-1} \Vert  \nu \Vert _2^2 = \Vert  g_{\hat{} (\mathbf {X}) - g_{*} (\mathbf {X}) \Vert _2^2 \le 2 \mu ^2 2^d \Vert  \hat{- *\Vert _2^4 + L^2 2^d \Vert  \hat{- * \Vert _2.}}where recall the assumption, \frac{1}{2^d} \sum _{x \in \mathbf {X}} \nabla g_{\theta ^*} (x) (\nabla g_{\theta ^*} (x))^T \preceq L^2.}\subsection {Proof of {lemma:2121}} \end{@align}Note that \max _{v : \Vert  v \Vert _\infty \le 1} \Vert  \mathbf {H}v \Vert _1 = \max _{v \in \lbrace  -1,+1\rbrace ^{2^d}} \Vert  \mathbf {H}v \Vert _1, by \cite [Proposition 1]{RJ00}. Therefore, it suffices to maximize over v \in \lbrace  -1,+1\rbrace ^{2^d}. It is known from \cite {figula2015numerical} that \hat{\varrho }^{(d)} \le d 2^d where \hat{\varrho }^{(d)} \triangleq \max _{m \in [2^d]} \sqrt{2^d} \Vert  \Phi \mathbf {H}\mathbf {1}_m \Vert _1 where \Phi  is an arbitrary set of vectors from the unit \Vert  \cdot \Vert _1 ball in \mathbb {R}^{2^d}, \mathbf {1}_m is the vector with the first m entries 1 and the remaining entries 0. Since \Phi  can be chosen as any permutation matrix, this result implies that \max _{v \in \lbrace  0,1 \rbrace ^{2^d}} \Vert  \mathbf {H}v \Vert _1 \le d 2^d. To compare with the previous statement, note that the number of non-zeros in v here equals m in the optimization problem defining \hat{\varrho }^{(d)}. Then, we have that,{\begin{@align}{1}{-1}\max _{v \in \lbrace  -1,+1\rbrace ^{2^d}} \Vert  \mathbf {H}v \Vert _1 &= \max _{v \in \lbrace  0,1\rbrace ^{2^d}} \Vert  \mathbf {H}(2v - \mathbf {1}) \Vert _1 \\&\overset{(i)}{\le } 2 \Vert  \mathbf {H}v \Vert _1 + \Vert  \mathbf {H}\mathbf {1} \Vert _1 \\&\le 2d \sqrt{2^d} + \sqrt{2^d},\end{@align}}where (i) follows by triangle inequality.}\section {Statistical performance under RSI - Proof of {theorem:000}} }In this section we discuss the proof of {theorem:000}. We prove a slightly more general result which characterizes the performance of stationary points of the MSE with spectral regularization under the RSI, when the regularization parameter is chosen arbitrarily.}\begin{theorem} For a sufficiently large absolute constant C_0 > 0, suppose the regularization parameter \lambda  satisfies,\begin{equation}\lambda \ge 4 C_0 \sigma \sqrt{ \frac{d + \log (1/\delta )}{n}} \end{equation}Consider a learner which returns any first order stationary point of the loss \mathcal {L}_n ( + R(. Under Assumptions~\ref {A0}, \ref {A2} and \ref {A3}, if \frac{C^*_{n,\delta }}{2} - \frac{5}{4}(2d+1) \lambda \mu - 3 \lambda L \sqrt{k} > 0, with probability \ge 1 - 2\delta ,{\begin{@align}{1}{-1}\Vert  \hat{- * \Vert _2 \le \frac{6 \lambda L \sqrt{k}}{C_{n,\delta }^*}}\end{@align}}\end{theorem}The subgradient of the regularizer \right.R ( = \Vert  \mathbf {H}f_{ (\mathbf {X}) \Vert _1 is characterized below.\begin{proposition} The subgradient of the regularization R( = \Vert  \mathbf {H}f_{ (\mathbf {X}) \Vert _1 is,{\begin{@align}{1}{-1}(\nabla R) ( = \left\lbrace  \frac{\lambda }{\sqrt{2^d}} \left( \nabla f_{ (\mathbf {X})  \mathbf {H}z : z \in \textsf {sgn} ( \mathbf {H}f_{ (\mathbf {X}) ) }}Here, for \right.\right.z \in \mathbb {R}, \textsf {sgn} (z) = {\left\lbrace \begin{array}{ll} \lbrace  +1 \rbrace  \qquad &\text{if } z > 0 \\ \lbrace  -1 \rbrace  &\text{if } z < 0 \\ [-1,+1] &\text{otherwise} \end{array}\right.} and applied on a vector z = (z_1,\cdots ,z_n) is the Cartesian product of the sets \textsf {sgn} (z_1) \times \cdots \times \textsf {sgn} (z_n).\end{@align}}\begin{lemma} Under the Lipschitz gradient condition, {A2}, consider any \mathbb {R}^d and any subgradient G \in (\nabla R) (. Then,{\begin{@align}{1}{-1}\langle  * , G \rangle \ge R(  - R(*) - (2d+1) \lambda \mu \Vert   * \Vert _2^2.\end{@align}}\end{lemma}\begin{proof}\end{proof}Recall that the regularization function R( is defined as \frac{\lambda }{\sqrt{2^d}} \Vert  \mathbf {H} f_{ (\mathbf {X}) \Vert _1. Consider any subgradient G \in (\nabla R) ( of the regularization function R(. By {prop:reg}, this is of the form \frac{\lambda }{\sqrt{2^d}} (\nabla f_{ (\mathbf {X})) \mathbf {H}z, where z \in \textsf {sgn} (\mathbf {H}f_{ (\mathbf {X})). In particular, using this representation, we have the equation,{\begin{@align}{1}{-1}\langle  *, G \rangle = \frac{\lambda }{\sqrt{2^d}} ( *)^T (\nabla f_{ (\mathbf {X})) \mathbf {H}z.}\end{@align}Since f_{ (x) is in general non-linear in , we can relate ( *)^T \nabla f_{ (x) to f_{ (x) - f_{*} (x) by using a Taylor series expansion. In particular, for each x \in [2^d] and each  and *, by the Lagrange form of the Taylor series expansion, there exists a x \in \textsf {conv} (\lbrace *\rbrace ) such that f_{*} (x) - f_{ (x) = \left\langle \nabla f_{ (x), * - \rangle + (* - ^T \nabla ^2 f_{x} (x) (* - . In addition, note from {A2} that -\mu I \preceq \nabla ^2 f_{ (x) \preceq \mu I. This results in the following set of inequalities,{\begin{@align}{1}{-1}\langle  *, G \rangle &= \frac{\lambda }{\sqrt{2^d}} \begin{bmatrix} f_{ (x) - f_{*} (x) + ( *)^T \nabla ^2 f_{x} (x) ( *) \\\vdots }_{x \in [2^d]} \mathbf {H}z \\&\ge \frac{\lambda }{\sqrt{2^d}} (f_{ (\mathbf {X}) - f_{*} (\mathbf {X}))^T \mathbf {H}z - \frac{\lambda }{\sqrt{2^d}} \mu \Vert   * \Vert _2^2 \Vert  \mathbf {H}z \Vert _1 \\&\ge \frac{\lambda }{\sqrt{2^d}} (\mathbf {H}f_{ (\mathbf {X}) - \mathbf {H}f_{*} (\mathbf {X}))^T z - (2d+1) \lambda \mu \Vert   * \Vert _2^2 }}where the last inequality follows from {lemma:2121}, where we show that for any vector v : \Vert  v \Vert _\infty \le 1 (a condition which is satisfied by the sign vector z), \Vert  \mathbf {H}v \Vert _1 \le (2d+1) \sqrt{2^d}.\end{bmatrix}A naive attempt to prove such a bound turns out to result in a loose bound. Indeed, \Vert  \mathbf {H}v \Vert _1 \le \sqrt{2^d} \Vert  \mathbf {H}v \Vert _2 = \sqrt{2^d} \Vert  v \Vert _2 \le \sqrt{2^d} \sqrt{2^d} = 2^d. The improvement of one of the \sqrt{2^d} factors to (2d+1) turns to be quite a deep mathematical fact, and we invoke a result of \cite {figula2015numerical} to prove this result in {proof:lemma:2121}.\end{@align}\begin{lemma} \max _{v : \Vert  v \Vert _\infty \le 1} \Vert  \mathbf {H}v \Vert _1 \le (2d + 1) \sqrt{2^d}.\end{lemma}}Finally, using the convexity of \Vert  \cdot \Vert _1, for any z \in \textsf {sgn} (\mathbf {H}f_{ (\mathbf {X})),{\begin{@align}{1}{-1}(\mathbf {H}f_{ (\mathbf {X}) - \mathbf {H}f_{*} (\mathbf {X}))^T z &= \Vert  \mathbf {H}f_{ (\mathbf {X}) \Vert _1 - (\mathbf {H}f_{*} (\mathbf {X}))^T z \\&\ge \Vert  \mathbf {H}f_{ (\mathbf {X}) \Vert _1 - \sup _{v : \Vert  v \Vert _\infty \le 1} \langle v , \mathbf {H}f_{*} (\mathbf {X}) \rangle \\&\ge \Vert  \mathbf {H}f_{ (\mathbf {X}) \Vert _1 - \Vert  \mathbf {H}f_{*} (\mathbf {X}) \Vert _1 }}Combining this with {eq:12312111} and using the definition of R( completes the proof.}}\begin{lemma} Under Assumptions~\ref {A0} and \ref {A2}, for any \mathbb {R}^d and any subgradient G \in (\nabla R) (, under the event \mathcal {E}_1,{\begin{@align}{1}{-1}&\Big \langle  * , \nabla \mathcal {L}_n ( + G \Big \rangle - 2 \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ \left( f_{*} (x) - y(x)) \right) \left\langle  * , \nabla f_{ (x)  \\&\ge \left( \frac{C_{n,\delta }^*}{2} - (2d+1) \lambda \mu \right) \Vert   * \Vert _2^2 + R( - R(*)}\right.\right.\begin{proof}Observe that,{\begin{@align}{1}{-1}\left\langle  *, \nabla \mathcal {L}_n ( \right\rangle = 2 \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ (f_{ (x) - y(x)) \left\langle  *, \nabla f_{ (x) }\right.Plugging this in below,{\begin{@align}{1}{-1}&\left\langle  *, \nabla \mathcal {L}_n ( \right\rangle - 2 \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ \left( f_{*} (x) - y(x)) \right) \left\langle  * , \nabla f_{ (x)  \\&= 2\mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ (f_{ (x) - y(x)) \langle  *, \nabla f_{ (x) \rangle - (f_{*} (x) - y(x)) \left\langle  * , \nabla f_{ (x)  \\&= 2 \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ ( f_{ (x) - f_{*} (x)) \left\langle  * , \nabla f_{ (x)  \\&= \left\langle  *, \nabla \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ ( f_{ (x) - f_{*} (x))^2  \\&\ge C_{n,\delta }^* \Vert   * \Vert _2^2}\right.where the last inequality follows by the restricted secant condition imposed on \right.\mathrm {Err}_{n} (*) in {A0}. Putting together {eq:1232220lpppl} with {lemma:reglemma},{\begin{@align}{1}{-1}&\left\langle  *, \nabla \mathcal {L}_n ( + G \right\rangle - 2 \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ \left( f_{*} (x) - y(x)) \right) \left\langle  * , \nabla f_{ (x) \\&\qquad \ge C_{n,\delta }^* \Vert   * \Vert _2^2 + R( - R(*) - (2d+1) \lambda \mu \Vert   * \Vert _2^2}\right.This completes the proof.\right.\end{@align}Plugging in  \hat{ into {lemma:cow0}, and noting that 0 \in \nabla \mathcal {L}_n (\hat{) + (\nabla R) (\hat{), choosing G appropriately,{\begin{@align}{1}{-1}&2 \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ \left( f_{*} (x) - y(x)) \right) \left\langle * - \hat{, \nabla f_{\hat{} (x)  \nonumber \\&\qquad \ge R(\hat{) - R(*) + \left( C^*_{n,\delta } - (2d+1) \lambda \mu \right) \Vert  \hat{- * \Vert _2^2 }}Now, we upper bound the LHS of {lemma:cow0}.}}\right.\right.\end{@align}\begin{lemma} Recall the assumption {eq:lambda-asmp} lower bounding \lambda . Under this assumption, define \mathcal {E}_2 as the event that, for all \mathbb {R}^d,{\begin{@align}{1}{-1}&\mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ \left( f_{*} (x) - y(x)) \right) \left\langle * -  \nabla f_{ (x)  \\&\qquad \le \frac{\lambda }{4} \sqrt{\frac{1}{2^d}} \left\Vert  \mathbf {H}\left( f_{*} (\mathbf {X}) - f_{ (\mathbf {X})  _1 + \frac{\lambda \mu (2d+1)}{4} \Vert   * \Vert _2^2.}\right.Then, \right.\Pr (\mathcal {E}_2) \ge 1-\delta .}\begin{proof}For each sample x^{\prime } \in D_n, define the noise in the sample as z(x^{\prime }) = f_{*} (x^{\prime }) - y (x^{\prime }).Likewise, define the noise vector \mathbf {z}_{D_n} = \lbrace  \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} [z(x^{\prime }) \mathbb {I} (x^{\prime }=x)] : x \in [2^d] \rbrace . Note that the coordinates of \mathbf {z}_{D_n} corresponding to inputs unobserved in the dataset D_n are 0.\end{proof}By Taylor series expanding, \right.\right.f_{*} (x) - f_{ (x) = \langle * -  \nabla f_{ (x) \rangle + ( * - ^T \left( \nabla ^2 f_{x} (x) \right) (* -  for some x \in \textsf {conv} ( \lbrace * \rbrace ). Therefore,{\begin{@align}{1}{-1}&\mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ \left( f_{*} (x) - y(x)) \right) \left\langle * -  \nabla f_{ (x)  \\&= \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ \left( f_{*} (x) - y(x)) \right) \left( f_{*} (x) - f_{ (x) - (  * )^T \left( \nabla ^2 f_{x} (x) \right) ( *)   \\&= \left\langle \mathbf {z}_{D_n}, f_{*} (\mathbf {X}) - f_{ (\mathbf {X}) - \mathbf {A} (*) ,}\right.where \mathbf {A} ( *) denotes the vector \left\lbrace  (* - ^T \nabla ^2 f_{x} (x) (* -  : x \in [2^d] \right\rbrace .}By an application of Holder^{\prime }s inequality and triangle inequality of the \right.\right.L_1-norm, we have,{\begin{@align}{1}{-1}&\mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ \left( f_{*} (x) - y(x)) \right) \left\langle * -  \nabla f_{ (x)  \\&\qquad \le \left\Vert  \mathbf {H}\mathbf {z}_{D_n} \right\Vert _\infty \left\Vert  \mathbf {H}\left( f_{*} (\mathbf {X}) - f_{\hat{} (\mathbf {X})  _1 + \left\Vert  \mathbf {H}\mathbf {z}_{D_n} \right\Vert _\infty \Vert  \mathbf {H} \mathbf {A} (*) \Vert _1 }\right.Note that for each fixed row \right.i \in [2^d], \langle \mathbf {H}_i, \mathbf {z}_{D_n} \rangle = \sum _{j \in 2^d} \mathbf {H}_{ij} \mathbf {z}_{D_n} (j). Note that the coordinates of \mathbf {z}_{D_n} are independently distributed and subgaussian. Therefore, by Hoeffding^{\prime }s inequality, for some constant C_0,\begin{equation}\mathrm {Pr} \left( \langle \mathbf {H}_i, \mathbf {z}_{D_n} \rangle \ge C_0 \sqrt{\frac{\left(\sum _{j \in [2^d]} \mathrm {Var} (\mathbf {z}_{D_n} (j)) \right) \log (1/\delta )}{2^d}} \right) \le \delta \end{equation}Note that the coordinate of \mathbf {z}_{D_n} labelled by x \in \lbrace  \pm 1 \rbrace ^d, \mathbb {E}_{x \sim \mathrm {Unif} (D_n)} [z(x^{\prime }) \mathbb {I} (x^{\prime }=x)], is the sum of D_n (x) independent \mathcal {N} (0,\sigma ^2) Gaussians scaled by 1/n, where D_n (x), defined as the number of times x is sampled in D_n. Therefore, \mathrm {Var} (\mathbf {z}_{D_n} (i)) = \frac{\sigma ^2 D_n (x)}{n^2}.By union bounding over the 2^d rows of \mathbf {H}, with probability \ge 1 - \delta ,\begin{equation}\mathrm {Pr} \left( \Vert  \mathbf {H}\mathbf {z}_{D_n} \Vert _\infty \ge C_0 \sqrt{\frac{ \left(\sum _{x \in [2^d]} \frac{\sigma ^2 D_n (x)}{n^2} \right) \log (2^d/\delta )}{2^d}} \right) \le \delta .\end{equation}Note that \sum _{x \in [2^d]} D_n (x) = n, and therefore, with probability \ge 1 - \delta ,{\begin{@align}{1}{-1} \Vert  \mathbf {H}\mathbf {z}_{D_n} \Vert _\infty \le C_0 \sigma \sqrt{\frac{1}{2^d}} \sqrt{\frac{d + \log (1/\delta )}{n}} \le \frac{\lambda }{4\sqrt{2^d}}.\end{@align}}where the last inequality follows by the assumption on \lambda  in {eq:lambda-asmp}.}Note that \right.\right.\Vert  \mathbf {A} ( *) \Vert _\infty \le \mu \Vert   * \Vert _2^2. Thus, the term \Vert  \mathbf {H} \mathbf {A} (*) \Vert _1 can be upper bounded by \sup _{v : \Vert  v \Vert _\infty \le \mu \Vert   * \Vert _2^2} \Vert  \mathbf {H}v \Vert _1. This itself can be further upper bounded using {lemma:2121} by \mu \Vert   * \Vert _2^2 (2d+1) \sqrt{2^d}.\end{@align}All in all, combining this argument and {eq:wee} with {eq:zerg}, under the events \mathcal {E}_1 and \mathcal {E}_2, with probability \ge 1-\delta ,{\begin{@align}{1}{-1}&\mathbb {E}_{x \sim \mathrm {Unif} (D_n)} \left[ \left( f_{*} (x) - y(x)) \right) \left\langle * -  \nabla f_{ (x)  \\&\qquad \le \frac{\lambda }{4} \sqrt{\frac{1}{2^d}} \left\Vert  \mathbf {H}\left( f_{*} (\mathbf {X}) - f_{\hat{} (\mathbf {X})  _1 + \frac{\lambda \mu (2d+1)}{4} \Vert   * \Vert _2^2.}\right.\right.}Plugging {lemma:31} into {eq:prefinal} with the choice of \right.\right. \hat{, and rearranging both sides, under the events \mathcal {E}_1 and \mathcal {E}_2 which jointly occur with probability \ge 1 - 2 \delta ,{\begin{@align}{1}{-1}&\left( C^*_{n,\delta } - \frac{3}{2}(2d+1) \lambda \mu \right) \Vert  \hat{- * \Vert _2^2 \nonumber \\&\overset{(i)}{\le } \frac{\lambda }{\sqrt{2^d}} \left\Vert  \mathbf {H}f_{*} (\mathbf {X}) \right\Vert _1 - \frac{\lambda }{\sqrt{2^d}} \left\Vert  \mathbf {H}f_{\hat{} (\mathbf {X}) _1 + \frac{\lambda }{2\sqrt{2^d}} \left\Vert  \mathbf {H}\left( f_{*} (\mathbf {X}) - f_{\hat{} (\mathbf {X})  _1 \\&\overset{(ii)}{\le } \frac{\lambda }{\sqrt{2^d}} \left( \left\Vert  \mathbf {H}f_{*} (\mathbf {X}) \right\Vert _1 - \left\Vert  \mathbf {H}f_{\hat{} (\mathbf {X}) _1 + \frac{1}{2} \left\Vert  \mathbf {H}f_{*} (\mathbf {X}) \right\Vert _1 + \frac{1}{2} \left\Vert  \mathbf {H}f_{\hat{} (\mathbf {X}) _1  \\&= \frac{\lambda }{2\sqrt{2^d}} \left( 3 \left\Vert  \mathbf {H}f_{*} (\mathbf {X}) \right\Vert _1 - \left\Vert  \mathbf {H}f_{\hat{} (\mathbf {X}) _1  }\right.where \right.(i) follows from the definition of the regularization term, R ( = \frac{\lambda }{\sqrt{2^d}} \left\Vert  \mathbf {H}f_{ (\mathbf {X}) _1. On the other hand, (ii) follows by triangle inequality of the norm \Vert  \cdot \Vert _1. By the assumption \frac{1}{2} C^*_{n,\delta } \ge \frac{3}{2} (2d+1) \lambda \mu + 3 \lambda L \sqrt{k}, the LHS is non-negative under the event \mathcal {E}_1.Plugging this into {eq:241} results in the inequality,{\begin{@align}{1}{-1} \frac{\lambda }{2\sqrt{2^d}} \left( 3 \left\Vert  \mathbf {H}f_{*} (\mathbf {X}) \right\Vert _1 - \left\Vert  \mathbf {H}f_{\hat{} (\mathbf {X}) _1  \ge 0.}\right.Conditioned on the event \right.\mathcal {E}_1.\end{@align}Next, we apply \cite [Lemma 5]{loh2015regularized} to the function \rho _\lambda (\cdot ) = \Vert  \cdot \Vert _1 , and note that by assumption \mathbf {H}f_{*} (\mathbf {X}) is k-sparse. Define \nu = \mathbf {H} (f_{*} (\mathbf {X}) - f_{\hat{} (\mathbf {X})) and A as the set of k largest indices of \nu  in absolute value. Using the fact that 3 \left\Vert  \mathbf {H}f_{*} (\mathbf {X}) \right\Vert _1 - \left\Vert  \mathbf {H}f_{\hat{} (\mathbf {X}) _1 \ge 0,{\begin{@align}{1}{-1}\frac{\lambda }{2\sqrt{2^d}} \left( 3 \left\Vert  \mathbf {H}f_{*} (\mathbf {X}) \right\Vert _1 - \left\Vert  \mathbf {H}f_{\hat{} (\mathbf {X}) _1  &\overset{(i)}{\le } \frac{\lambda }{\sqrt{2^d}} \left( 3 \Vert  \nu _A \Vert _1 - \Vert  \nu _{A^c} \Vert _1 \right) \\&\le \frac{3\lambda \sqrt{k}}{2 \sqrt{2^d}} \Vert  \nu _A \Vert _2 \\&\le \frac{3\lambda \sqrt{k}}{2 \sqrt{2^d}} \Vert  \nu \Vert _2. }\right.Plugging this back into {eq:241} results in the following inequality, conditioned on the events \right.\mathcal {E}_1 and \mathcal {E}_2,{\begin{@align}{1}{-1}\left( C^*_{n,\delta } - \frac{3}{2}(2d+1) \lambda \mu \right) \Vert  \hat{- * \Vert _2^2 \le \frac{3\lambda \sqrt{k}}{2 \sqrt{2^d}} \Vert  f_{*} (\mathbf {X}) - f_{\hat{} (\mathbf {X}) \Vert _2 }}\end{@align}Finally, we relate \Vert  f_{*} (\mathbf {X}) - f_{\hat{} (\mathbf {X}) \Vert _2 to \Vert  \hat{- * \Vert _2.}\begin{lemma} \Vert  f_{*} (\mathbf {X}) - f_{\hat{} (\mathbf {X}) \Vert _2 \le 2 \mu \sqrt{2^d} \Vert  \hat{- * \Vert _2^2 + 2 L \sqrt{2^d} \Vert  \hat{- * \Vert _2.}}Plugging the bound in {lemma:00300} into {eq:goober} results in the following inequality, conditioned on \mathcal {E}_1 and \mathcal {E}_2,{\begin{@align}{1}{-1}\left( C^*_{n,\delta } - \frac{3}{2}(2d+1) \lambda \mu \right) \Vert  \hat{- * \Vert _2^2 \le 3 \mu \lambda \sqrt{k} \Vert  \hat{- * \Vert _2^2 + 3\lambda L \sqrt{k} \Vert  \hat{- * \Vert _2.}}Furthermore, recalling the assumption that \frac{C^*_{n,\delta }}{2} - \frac{3}{2}(2d+1) \lambda \mu - 3 \mu \lambda \sqrt{k} \ge 0, this results in the overall bound,{\begin{@align}{1}{-1}\Vert  \hat{- * \Vert _2 \le \frac{3 \lambda L \sqrt{k}}{ C^*_{n,\delta } - \frac{3}{2}(2d+1) \lambda \mu - 3 \mu \lambda \sqrt{k}} \le \frac{6 \lambda L \sqrt{k}}{C^*_{n,\delta }},}\end{@align}under the events \mathcal {E}_1 and \mathcal {E}_2 which jointly occur with probability \ge 1 - 2 \delta .}{theorem:000} follows by choosing \lambda  appropriately according to {eq:lambda-asmp} and showing that when the size of the dataset n is sufficiently large, the conditions in {theorem:0} are satisfied.}\end{@align}}}\end{lemma}}}\end{@align}}}\right.}}}\right.}\right.}\right.\right.}\right.\right.}\right.}\end{@align}}}\end{@align}}}}\right.\right.\end{@align}}}}\end{@align}}\end{lemma}}}}}}}\right.}\right.}\right.}}\right.}\right.\right.\end{@align}}}\right.\end{@align}}\end{proof}\end{@align}}\end{lemma}\end{@align}}}}}\right.}}}}}}}}}\end{proposition}}\end{@align}}}}}\end{@align}}\end{@align}}\end{@align}}}}\end{@align}}}}}\right.\end{@align}}}}}\end{@align}}}}\end{@align}}}\right.\right.\end{@align}}}}}}}}\end{@align}}}}}\right.}\right.}\right.\right.}\right.\right.}\right.}}\end{@align}}\end{@align}}}}}}}\right.\right.\end{@align}}}}}}\right.\right.\end{@align}}}}\right.}}}\right.}\right.\right.\end{@align}}}}\right.}}\right.\end{@align}}\end{proof}\right.\) 
