Spectral Regularization Allows Data-frugal Learning over Combinatorial Spaces
Authors: Amirali Aghazadeh
Nived Rajaraman
Tony Tu
Kannan Ramchandran
Venue: Accepted by TMLR ()

Abstract: Data-driven machine learning models are being increasingly employed in several important inference problems in biology, chemistry, and physics, which require learning over combinatorial spaces. Recent empirical evidence (see, e.g., ~\cite{tseng2020fourier,aghazadeh2021epistatic,ha2021adaptive}) suggests that regularizing the spectral representation of such models improves their generalization power when labeled data is scarce. However, despite these empirical studies, the theoretical underpinning of when and how spectral regularization enables improved generalization is poorly understood. In this paper, we focus on learning pseudo-Boolean functions and demonstrate that regularizing the empirical mean squared error by the $L_1$ norm of the spectral transform of the learned function reshapes the loss landscape and allows for data-frugal learning under a restricted secant condition on the learner's empirical error measured against the ground truth function. Under a weaker quadratic growth condition, we show that stationary points, which also approximately interpolate the training data points achieve statistically optimal generalization performance. Complementing our theory, we empirically demonstrate that running gradient descent on the regularized loss results in a better generalization performance compared to baseline algorithms in several data-scarce real-world problems.

Published in Transactions on Machine Learning Research (April/2023)
Spectral Regularization Allows Data-frugal Learning over Combinatorial Spaces
Amirali Aghazadeh
amiralia edu
School of Electrical and Computer Engineering Georgia Institute of Technology
Nived Rajaraman
winee..ajjeummanneeerreee
Department Electrical Engineering Computer Science University of California, Berkeley
Tony Tu
tuu32 edu
School of Computer Science Georgia Institute of Technology
Kennan Ramchandran
kannanr@@ecs. edu
Department of Electrical Engineering & Computer Sciences Universily of California, Berkeley
Reviewed on OpenReview: https: // openreview. foru?? iew.gSSsFFCeellhhootrra4222../.0
Abstract
Data-driven machine learning models are being increasingly employed in several important inference problems in biology, chemistry, and physics, which require learning over combina- torial spaces. Recent empirical evidence (see, e.g., [Tseng et al. (2020) Aghazadeh al. (2021 Ha et al. (2021)) suggests that regularizing the spectral representation of such models improves their generalization power when labeled data is scarce. However, despite these em- pirical studics, the thcoretical underpinning of when and how spectral regularization enables improved generalization is poorly understood. In this paper, we focus on learning pseudo- Boolean functions and demonstrate that regularizing the empirical mean squared error by the L norm of the spectral transform the learned function reshapes the loss landscape and allows for data-frugal learning under a restricted secant condition on the learner's 's em- pirical measured against the ground truth function. Under a weaker quadratic growth condition, we show that stationary points, which also approximately interpolate the training data points achieve statistically optimal generalization performance. Complementing our theory, we empirically demonstrate that running gradient descent on the regularized loss results in a better generalization performance compared to baseline algorithms in several data-scarce real-world problems.
1 Introduction
Machine learning (ML) models have become increasingly commonplace in learning Eseudo-Booleds functions f(), which map d-dimensional binary vector {+1]d to real number f(x) R. In biology, ML models are used to infer the functional propertics of macro-molccules (c.g., protcins) from small set of mutations (Riesselman et al. 2018 Gelman et al. 2021]. In physics, ML models are being used to infer the thermodynamic properties of combinatorial systems systems defined over a set of binary (Ising) state variables (Carleo ct al. 2019 Noć et al. 2019). These highly nonlincar and complex ML models are trained using modern techniques in continuous optimization. Yet they inherit the elegant properties of pseudo-Boolean functions the discrete binary hypercube [+1]d. In particular, it. known that the spectral representation of

---

Published in Transactions on Machine Learning Research (April/2023)
pseudo-Boolean function is defined as the Walsha- transform (WHT) of the resulting vector of combinatorial function evaluations, that is, H)) where H is a 24 x 2 Walsh mairix and the function evaluation vector f(X) = [f(x)= : I E x]" is sorted in the lexicographic ordering of all the length-d binary strings in X. The WHT enables writing the pscudo-Boodd Boolcan function f(x) as a multi-lincar polynomial [(x) = Esgiag as Iles Fss where [d] = f1,2,....d .d. and as E R is the WHT coefficient corresponding to the monomial lhes 2i (Boros & Hammer 2002)
Recent studies in biology (e.g,, protein function prediction) have measured the output of several of these real-world functions f() to all the 2d cnumcrations of the input x and analyzed their spectral representation. These costly high-throughout experiments on combinatorially complete datasets demonstrate a curious phe- nomenon: such pseudo-Boolean
Boolean functions often have low dimensional structures that manifest in the form of approximately-sparse polynomial representation (i.e., approximately-spars. WHT) with the top-k coeffi-
cients corresponding to
interactions (Poelwijk et al., 2019 Eble et al. 2020 Brookes
et al. 2022)
(see Appendix A for empirical evidence on protein functions).
The problem of learning psoudo-Boolean Boolcan functions with sparse polynomial representations has a rich history from theoretical and empirical viewpoints. In particular, since the Seeudo-Boolcan functions being learned in their polynomial representations are linear functions in their coefficients, one may think about this problem as special instance of sporse linear regression in dimension 24, There are many algorithms for sparse linear regression, such LARS (Efron et al. 2004), OMP (Topp & Gilbert 2007 AMP (Donoho et al. 2009). and FISTA (Beck & Teboulle, 2009]. In particular, one may apply LASSO to get stalistical guaranlees for this problem which only scale linearly in the sparsity of the underlying ground truth polynomial h and logarithmically in the problem dimension log(24) (Candes et al. 2006). Likewise, from another perspective, one may view the polynomial instead as a vector of 2d outcomes f(X); the objective of the learner is to approximate f(X), when the learner can observe any chosen set of a few entries of this vector (corrupted by noise), under the assumption that f(X) itself has a sparse WHT. In the litcrature,, this problem has been referred to by several names, and we refer to it as the sparse WHT problem. There are many computationally and statistically efficient algorithms for solving this problem, such as SPRIGHT (Li & Ramchandran 2015 and Sparsc-FFT (Amrollahi et al. 2019), among others.
A common issue with these alternate views of the problem, such as sparse linear regression or sparse WHT is that the resulting algorithms are not suited for function approzimation. In particular, real-world physical and biological functions often have additional structurcs which are either unknown a priori or cannot be described succinetly, and which nonlinear function classes are often implicitly biased towards learning. Indeed, several deep neural networks (DNNs) have been shown to exhibit strong generalization performance in biological and physical problems (Gelman et al. 2021 Ching et al. 2018 Sarrisyan et al., [0016). This leads to a fundamental disconnect between algorithms for which strong theoretical guarantees are known (e.g., LASSO) and practical MT. models based on nonlinear and complex function classes which are well-suited for function approximation.
Another issue is specific to algorithms for solving the sparse WHT problem: some of these approaches require observing f() at any chosen input (Li & Ramchandran 2015 Li et al. 2015). In many practical applications, where data is prohibitively expensive to collect, one often forced to work with a handful of random samples. For example, in the case of proteins, common approach to measure biological functions is through a procedure called random mutagenesis, which allows only random sampling of the combinatorial sequence space Sarkisyan et al.] (2016). This constraint renders several algorithms for the sparse WHT problem ill-suited for learning, even though they admit near-optimal computational and sample complexity guarantees.
From a more practical point of view, several recent approaches for learning over combinatorial spaces (see, e.g.: (Tseng et al.) 2020 Aghazadeh et al. 2021 Ha et al. 2021 Li et al. 2020 follow similar ideas for improving empirical generalization. Instead of directly Tearning the diddimensin polynomial, they have converged on explicitly promoting sparsity in the spectral representation of the learned compactly- represented nonlinear function also known as spectral regularization. These empirical studies motivate several important theoretical questions regarding the underlying mechanism of spectral regularization in
We use these terms interchangesbly for pseudo-Roolean Roolean functions: spectral, Fourier, and Walsh- Hadamard.
2

---

Published in Transactions on Machine Learning Research (April/2023)
improving generalization in practice. This paper focuses on the question: When and how does spectral regularization improve generalization? The answer to this question is important from theoretical and practical perspectives. Theoretically, it helps us understand how the loss landscape is reshaped as the result of spectral regularization in favor of data-frugal learning. Practically, it tells us when and how to use spectral regularization learning real-world combinatorial functions.
Contributions. In this paper, we theoretically analyze spectral regularization of the empirical risk from the perspective of learning psendo-Boolean functions. We demonstrate that regularizing with the L norm of the spectrum of the learned function improves the generalization performance of the learner. In particular, under particular Restricted Secant Incquality (RST) condition on the learner's empirical error, mcasured against the ground truth, stationary points of the regularized loss admit optimal generalization performance. We re- lax this to a weaker quadratic growth (QG) condition and show that, under an additional intappiteroonntion condition, stationary points of the regularized loss also admit statistical optimality. We empirically demon- strate that these conditions are satisfied for wide class of nonlincar functions. Our analysis provides a new generalization bound when the underlying learned functions are sparse in the spectral domain. Empirical demonstrations on several real-world data sets complement our theoretical findings.
2 Learning Pseudo-Boolean Functions
Problem statement. We consider the problem of learning structured pseudo-Boolens Boolean functions on the binary hypercube (=1]d. In the finite sample setting, we assumee that the learner has access to a dataset D, comprised of n labeled data points (x', ) where E {+1]4 are drawn from an input distribution D and the real-valued output y E is a noisy realization of an unknown pscudo-Bool Boolean function of the input D Consider a rich nonlinear function class F (Je 0 E RT) parameterized by 0, where Se [+1]d R.. We study the realizable setting, where the ground-truth labels are generated as y = (x*) + 2 for an unknown parameter 0" E RTh where Z' is the noise in the measurement for input z², assumed to be independent and
normally distributed ~ (000 2²) 3
The objective of the learner is to learn 0-.
Multi-linear polynomial representation. Any pseudo- pseudo-Boolean function f(-) can be uniquely represented as a multi-linear polynomial, f(x) = Exe az I1 Fi, where the scalar a₂ E is the coefficient corre- sponding to the monomial I1: Hi, with order Σ 1(z; = +1) BBoros & Hammer 2002). The problem of learning a pseudo-Boolean function f(-) is equivalent to finding the 2 unknown coefficients ag. In par- ticular, the evaluations of f on all vertices of the binary hypercube {+1]22 results in a linear system of equations over the ag variables,
[f(x) : aE (+1]-²² =H [a, [aa :2E (=1)a²²
where the variables x and a enumerate the vertices of the binary hypercube {+1]" in lexicographic order, and H = Hz denotes the 2d x 2d scaled Hadamard matrix defined recursively as,
H H2
H
H
(2)
V2
H2d
where H2 = [+1]. Thus the vector of function evaluations can be obtained by taking the WHT of the vector of coefficients in the polynomial representation of f. Furthermore, by inverting the above linear system (note that H is an orthonormal matrix), the vector of polynomial coefficients [az 2 E [=1]#] can, in turn, be obtained by taking the WHT of the vector [f(x): : x E {+1]"? For brevily of notation, for function J. we define f(X) as [f(x): x E {+1] where in the LHS the binary strings are emumerated in lexicographic order. The coefficients in the polynomial representation of f(.) can be collected in the vector ( For functions, we use "sparsity in WHT" and "sparsc polynomial represcntation" interchangeably.
We the subscript &; refer to the 8th digit the binary string 12,,22,".. a.)).
In fact, our results only require the noise be independent subgaussian random variables with variance parameter o?, but for ease of exposition, we impose the Ganssian noise condition.
3

---

Published in Transactions on Machine Learning Research (April/2023)
Sparsity in real-world functions. Even in the noiscless setting, to perfectly learn general pscudo-Boolean function f()), its evaluations on all binary input vectors E [+1]2 are required, which may be very expensive. In the presence of additional structures, this significant statistical and computational cost can be mitigated. One such structure that has been observed in real-world biological and physical functions is sparsity in WHT (Poelwijk et al., 2019 Fble et al. 2020 Brookes el al. 2022). In particular, the theoretical analysis of this paper, we assume that the ground-truth function fo- has sparse polynomial representation composed of at most k monomials. Namely, ||H (X)llo - k, where < 2d is typically unknown.
Spectral regularization. In attempting to learn BeeuooBooleann functions with sparse polynomial rep- resentation, a natural question to ask is: how can one encourage the learned functions also to have sparse polynomial representations. One solution is to regularize the training loss with an additional functional which promotes sparsity in the polynomial representation of the learned function f. Denoting the polynomial rep- resentation of f by (=) ā I 11:2,111 Zi, a natural regularization functional would be ||ō'lo = [X)ll which is also the sparsity of f in WHT.
However, since || llo is not continuous function, we proxy the || llo by the L1 norm. The resulting regularization functional is, [|HÍ(X)]] When learning over a parameterized function family, f = fo, the resulting regularized ERM we consider in this paper is,
min (0) + R(0), where R(0) A 0
(OBJ)
where (0) A n EL= ((o(w')-))) is the empirical mean squared error (MSE). Regularizing by R(0) of the above form is known as spectral regulorization (SP).
Remark 1. The scaling of the regularization parameter, V221 is motivated from the lincarly parameterized
setting of F ((, 0 RR). An explicit computation gives, /22 H)f = A|001,, which is the scaling of the regulorization parameter as used in LASSO.
The regularization weight À > 0 strikes balance between the empirical MSF and the spectral regularization, and is set empirically using cross validation. Since the aggregate loss (0) + R(O) is subdifferentiable with respect to the model parameters 0, we can apply stochastic (sub~)gradienl met mothods on the aggregate loss. Note however that, in general, as function of the parameter 0, both the MSE, as well as the SP regularization are non-convex functions.
3 Related Works
A recent line of thcoretical works on learning pseudo-Boolean functions demonstrate a staircase-like property of gradient descent learning DNNs in that the WHT coefficients corresponding to higher order monomials (e.g., x112243) are reachable from lower order ones along increasing chains (i.e., Z142 and æ1), and are thus learnable in polynomial time and sample cost (Abbe et al.) 2021p. Other works have shown that under certain distributions, low order parity functions are learnable by means of gradient decent depth-2 2 networks, while they cannot. be learned efficiently using linear mots (Daniely & Malach 2020). These analyses are limited to certain DNN architectures or assumee (linear) approximations to DNNs (e.g., neural tangent kernels) which entirely disallows the analysis of spectral regularization as they manifest only in nonlincar function classes.
Spectral bias of DNNs have been the subject of several other empirical and theoretical works Yang & Salman 2019). Approximations to the Fourier transform of two-layer (Zhang et al. (2099) and multi-layer (Rahaman et al.) 2019) ReLU networks show that these networks have learning bias towards low frequency func- tions [Xu et al. 2019). To improve the limitations of DNNs in learning high frequency components, empir- ical works use Fourier features explicitly as part of the input (Tancik et al. 2020). A paramctrization of polynomial DNNs has also been shown to speed up the learning of higher frequency components in two-layer networks (Choraria et al., 2022). Different notions of spectral priors have also been empirically investigated in graph neural networks (Li et al. 2020) and elsewhere (Yoshida & Miyato 2017). These results support the implicit bias of DNNs towards dense and low-freqyency spectral representation and only motivate our analysis of sparsity as explicit spectral prior.
4

---

Published in Transactions on Machine Learning Research (April/202)
4 Theoretical Analysis
To develop some intuition about the general problem, consider the special case of learning over the set of linear functions. Namely, F= = {(0.-) : R*). The polynomial representation of any linear function Jo (z) (0.z) is simply Eieig 6.I; where only the order-1 coefficients are non-zero. Thus, the assumption that the polynomial representation of fe is composed of at most & monomials is equivalent to saying that is k-sparse. Thus in the linear setting, the problem boils down to sparse linear regression (Candes et al, 2006). Furthermore, in the linear setting, spectral regularization has an explicit representation in terms of paramcter 0. In particular, here R(0)= X
/2z (X)] \||0|11. Thus, the proposod objective function, " 1 y²)² +
OBJ,, when specialized to the linear setting boils down to the LASSO objective, 1 I| which can be efficiently solved by gradient descent, and is known to be statistically optimal in the finite sample regime (Raskutti et al. 2011
4.1 Going beyond the linear setting Restricted Secant Inequality
In the linear setting, a sufficient condition for the fimite sample statistical optimality of LASSO is the restricted eigenvalue condition on the empirical covariance matrix Σn 1 cigenvalue condition is automatically satisfied if the smallest eigenvalue of Σ,, is bounded away from 0. The condition induces a particular sense of curvature around the true paramcter 0* of the loss (0,,00 that is the MSE of the learned function compared to the ground truth,
" E - x'z'". The restricted
1 (fo(z*) - So- (xx))).
Err, (0,0") = 72
(3)
In contrast, when F is a non-linear function family, we circumvent these sufficient conditions, and directly study assumptions which induce curvature in the loss Err, (0,0"). These assumptions, however, do not concern the structure of the spectral regularizer, which unlike the lincar case, can no longer be represented as a closed-form function of 0. A major technical challenge the analysis relates to circumventing the use of this explicit representation, which we expand upon later.
Definition 1 (Restricted secant inequality (RSI) Zhang & Yin 2013 The set of functions satisfying the restricted secant inequality with parameter C, denoted RSI(C) defined as follows. A function g R + R belongs to RST(C) iff for some 2x E arg min g(2) and for all E Rm
[o(()),==)) 2 Cl|= == =1.
(4)
In other words, the restricted secant inoquality implics that the gradient of the loss at a point is well correlated with the --2" =", the line joining the current point to the minimizer of g-
Remark 2. The RSI is known to generalize several eatensions of converity, such as quasar-star converity (Hinder al., 2020) and strong star-conwezity (Tee & Valiani, 2015). Refer to Karimi et al. (2016) for a comparison with other constraints such as the condition which we study in Section 4.2 In general, the RSI is significantly weaker condition than global strong converity.
(PL) inequality, and the quodratic growth
The first main assumption we study is when the (0r,,0,00 0*) satisfics the RSI. This assumption captures a notion of curvature, in which the gradients of Err, (0, 0*) are informative about (i.e., positively correlated with) the error in the parameter space 0 0-
From this behavior, it may be expected that all stationary points of functions which satisfy the RSI are global minima, which is indeed true (Karimi et al.) 2016). However, note that we impose the RSI condition on Err,, (0, 0*) (which cannot be computed by the learner) and not the empirical risk (0). Even under the RSI condition on (0,0,0,0') it not trivial to find global minima of the training objective, (,) + R(0) which is composed of two non-convex (in 0) functions and is non-smooth. Thus, we restrict our attention the analysis of first-order stalionary points of this objective.
5

---

Published in Transactions on Machine Learning Research (April/2023)
Assumption (a). Assume the function Err, (0,00) satisfies the RSI with high probability over the datoset. Namely, there is a constant C > O such that with probabilily at least 1 - 8, for every 0 E Rm
0 0" VO 2 C 1 -0
Remark 3. The RSI is true for linear families F (0, (0. E ] as long as with probability at least 1, the dala covariance salisfies Eg>Uuni((.) [xx=) z In,s,, i.e,, well conditioned. The quadratic growth condition in Section 4.2 also holds under the same conditions with parometer C%,6'
In addition to the RSI, we make some mild regularity assumptions on the function classes we study. Wo emphasize that none of these assumptions imply convexity or smoothness of the training objective (.) + R(0) or Err, (0,0*). First, we assume that the function class FF is sufficiently smooth, having Lipschitz continuous gradients (Cisse al. 2017). Note that we study the case when the function class F is smooth, and do not impose this condition on the empirical risk, (0), as is often assumed (Jin et al. 2018).
A Assumption (Lipschitz continuous gradients on F). For each a X and conslunt μ4, assume that fo(x) is twice differentiable in 0 and the Hessian of fz)z) satisfies -pI 3 f2fo()) pl.
The final assumption we impose assumes that the ground truth function l has well behaved gradicnts in that certain covariance matrix induced by the gradients the matrix is bounded.
Assumption 3 (Bounded average gradient norm at 0*). Under this assumption,
EX-Unif(X)
[ (o- (z)) IZI.
(6)
Assumption 3 can be interpreted as one-point Lipschitzness condition, showing that on average across the inputs x E X, the gradients of fe (z) are well behaved at the singular point 0 = 0 Under the previous assumptions, we prove a bound on the error in the parameter space made by the learner. This theorem is a
consequence a more general result we prove in Appendix C for an arbitrary regularization scale À >>> O.
Theorem 1. Suppose Assumptions (aa and of the dalasel is sufficienlly lurge, namely n nio defined as,
satisfied, x is chosen as 120g
d+ d+1og(1/8) and the size
n
0² (d2 2 + L2k) (d+ log(1/0)) (O,,g)
no - C
for a large conslant C1 < 1000 Consider learner which relarns a first order stationary poinl, 0, of the loss C, + R()). Then, with probability 2 1 -22,
k(d + log(1/8)) 1|0 01 S aT.
(8)
C
n
Note that in the dependence on d and k the sample size threshold no scales asymptotically as de + dk.
4.2 Going beyond the RSI The Quadratic Growth condition
While RST much weaker condition than convexity, at a high level, it assumes that the gradients of (rr, (0)0") are informative about the crror in the parameter space 0-0 0- We can further relax this assump- tion. In this section, we consider a weakening of this assumption which only supposes that Err, (0,6 0 grows at least quadratically in ||0 -- This is known as the quadratic growth (QG) condition (Anitescu 2000). This condition no longer characterizes the behavior of the gradients of the function Err,,(8 (0, much less those of the empirical loss C,- Stationary points of a function satisfying the QG condition are no longer global minima, in contrast with the behavior under the RST (Definition
Note that we did not optimize the value of this constant. With a more careful analysis, its value be brought down.

---

Published in Transactions on Machine Learning Research (April/2023)
Definition 2 (Quadratic Growth (QG) condition (Anitescu 2000 ). The set of functions satisfying the QG
condition with parameter C, denoted (G(C) is defined by the inclusion, IR - R belongs to QG(C) i0 for some z" E arg min g(2) and for all 2 E Rm
s(2) -(=0) -
(9)
For C > O, functions in QG(C) have a unique global minimizer.
As the name suggests, the quadratic growth condition implies that the function g has local curvature around z². However, it is important note that this does not discount the possibility that g has many spurious local minima. In this section, go beyond the RSI assumption on Err, (0) and discuss the case where it satisfies the quadratic growth condition.
Assumption (bb (Quadratic Growth (QG) condition (Anitescu 2000 ). The function family F = {fo
E ] the dataset Dn,
} is assumed to satisfy the QG condition with parameter Cū,6: if with probability at least - ō over
v0 E RT, (0,0") 2 Ch, 10 1-.
(10)
Remark 4. { [Aniteser, 2000, Theorem 2) Restricting to functions f which have I.-Läpschitz continuous gradients, if E RSI(C), then it implies that E QG(2C/L). This implies that up to the value of the parameter, the QG condition is weaker than RSI, under a smoothness constroint on the considered functions.
longer constrained to be positively cor- related with the - In fact, the absence of this feature proves to be a significant barrier for first-order methods to generalize well. To circumvent this issuc, we motivate and introduce the notion of approzimate firs--oder stationary interpolators in the next section, and characterize their statistical performance. This imposes a stronger requirement on the algorithm than just returning an arbitrary stationary point of the training objective (()) + R(().
Note that under the QG condition, gradients of Err, (0,0")
Approximate First-order Interpolators. When F is an expressive family of nonlinear models, it has been observed empirically that standard stochastic gradient methods can be run until the model begins to perfectly interpolate the training data, without hurting test-(ime performance. This phenomenon has been referred to in the literature as benign overfitting (Bartlett et al.) 2020), and has been seen to hold frequently in the training of DNNs in practice, when stochastic gradient descent is run for sufficiently many epochs. In fact, in all our experiments (sce Figs. and 6 in Appendix A we observe that upon running stochastic gradient descent for sufficiently long on the aggregate loss (0)+ + RR(),, the parameter Ô eventually converges
to solution which interpolates the labelled ezamples well, i.c., the mean square error (0) is upper bounded by a sufficiently small A > 0. Note that we do not assume that A is so small that the condition essentially imposes that is an approximate global minimizer of the training loss. In theory, our rcsults also hold under the stronger condition that (.)()) + R(O) is upper bounded by A, which the loss function being optimized by (stochastic) gradient descent. This phenomenon motivates the following definition of approximate first order stationary interpolators.
Definition 3 (A-approximate first order stationary interpolator). A point 0 is defined to be A A-approrimate first-order stationary interpolator if,
1. 0 is first order stationary point of the aggregate loss (0) + R(O). Namely,
O (V).))() + (V)
(1I)
2. fg approzimately interpolates the observed training data. Namely, the empirical mean squared error of 0 evaluated on the training dataset satisfies,
C. (. SA.
(12)
Note that our results hold under the stronger condition C,, (0) + R(0) < A, the training loss function being minimized by the (stochastic) gradient methods in our experiments.
7

---

Published in Transactions on Machine Learning Research (April/2023)
We are ready to establish guarantee on the statistical performance of approximate first-order stationary interpolators.
Theorem 2. Suppose À is chosen- 120 d+Hog(2/6) Assume that the size of the dalaset is sufficienlly 15
large, namely, > no (as defined in Equation ). Consider a learner returns @ which is a A-approzimate first order stationary interpolator, where A C (C n1)) for sufficiently large constant C1. Then, with probability 2 11--8. 28,
100 10 ØL k(d + log(1//))))
(13)
C7,6"
71
Remark 5. For peeuo-BBoleent functions, the log-covering number in any norm up log factors is log (2)) = kd. Therefore, an algorithm which returns a function which is an exact minimizer of the mean squared error among all functions with o, k-sporse polynomial representation, g admits the guaranlee ||0] 5 Vkd/n up to scaling constants, with high probability, up to log factors. However, when A is large, the learner considered in Theorem 2
is not constrained to return the exact minimizer of the squared error (subject to the sparsity constraint). Thus, under the additional condition of first-order stationarity, Theorem imposes much weaker condition, (0) S A malher than f arg min C.. (0).
Finally, in the context of the previous two results, we prove a lower bound showing statistical optimality under the imposed assumptions.
Theorem 3. Suppose d 2 3 and h S 24/4. Then, there enists a parameter class O, and an associated function class F (Jo 0 θ} such that for any learner 0, there erists a ground truth function So- {+1]" + R having k-sporse polynomial representation, such that given a sufficiently large dataset of n samples,
1. Assumptions 1(a) probability at least 8.
1(b and are satisfied with constants L = 1, fa ===0 and Cn,5- E [ 22 with
31
2. E 10- 1100-112
80112]
2 ov
Ad where 0² denotes the noise variance in the observed labels.
Extensions to the case of non-unique minima. While we focus on general parametric function classes in Theorems [ and 2 for the specific case of DNNs, the issue of "permutation invariance" can appear. In particular, permutation (i.e., relabeling) of the neurons in the same layer of a network can result in a different network with the same functional relationship between the input and the output. In this case, Assumptions [(a) and [(b] cannot hold globally for all 0 E R" the loss (0,,00,0*) and its gradient become 0 at any parameter 0% where 0 denotes the weight matrices corresponding to functionally invariant permutation of the neurons of the base network with parameter 0", However, even in this case, we can extract guarantee from Theorem I and Theorem by modifying the underlying assumptions slightly.
In particular, let 3 C Rm denote the set of parameters that are functionally equivalent to 0", in that so- = So for all 0 E @* These parameters are local minimizers of Err,(0,0*)) In particular, we define a modified RSI and QG condition, as below,
0 - 0 proj: V Errr,,,0,0 (0,0") 2 C 0
0 proj l
(Modified Assumption 1(a)
Err,, (0,00 2 C e
0 prej llā.
(Modified Assumption 1(b)
where 0: proj = arg mingee. |10 00 is the projection of 0 onto O' in some metric || I]. In particular, for each 0 E θ let Ke denote the subset R" such that for all 8' E KGp 0 arg min ||0 - 0l) In other words, Ke are the set of parameters which are closest to among all the functionally equivalent parameters 0r Then, modified Assumptions [(a) and 1(b) impose the RSI and QG conditions in local neighborhood (KG) of each 0 E O
Corresponding to the new modified assumptions, a learner which returns any θ which stationary point under modified Assumption [[a] (resp. approximate first order stationary interpolator, under modified As- sumption ((b). guarantees to approximate 0 prop, the nearest local minimizer to 0 in O The proofs of these
8

---

Published in Transactions on Machine Learning Research (April/2023)
X, X,X
X
XX xxx+xpa+ x
X x,txx
monomial
power law
staircase
WHT
WHIT
WHT
order of interactions
MSE
power law coeffiiient
power coefficient
3
1.5
3/4
1
1/2
1
S
2
MSE+SP
MSE+SP
3
1.5
1/4
2
5
50
100
150
200
50
100
150
200
50
100
150
200
number of samples
Figure 1: The plots demonstrate the gencralization power of a depth-4 feed-forward neural network learning classes sparse pseudo-Boolean functions f(x) {+1]18 + R using the mean squared error (MSE) loss before (first row) and after (second row) adding the spectral (SP) regularizer, as function of the number of training samples. MONOMIAL are 1-sparse functions in Walsh-Hadamard transform (WHT) with increasing order of interactions (1 to 5). POWER LAW 10-sparse functions in WHT with second order interactions and coefficients set using power law function. STAIRCASE are 18-sparse functions in WHT with 3 first order, 6 second order, and 9 third order interactions, each with an equal coefficients and set using a power law function. The heat maps show the fraction of times (among 5 random independent trials) the models generalize on unseen data with the coefficient of determination larger than R² > 0.45 on the test data points.
results follow identically to Theorem and Theorem In particular, replacing 0 by the parameter Proj and following the same argument completes the proof of the result showing that proj (which is functionally equivalent 0*) can be recovered approximately.
In summary, rather than assuming that the loss (rr,,0,0*)) is globally bowl shaped as in Assumption I(b) assumption which cannot hold globally for example in neural networks because of permutation invariance, it suffices to assume that the loss function is locally bowl shaped around functionally invariant permutations E O the ground truth parameter * This line of reasoning can be extended to incorporate other symmetries the function class which prevent exact parameter recovery, as the case of permutation invariance of neural networks. The corresponding parameter recovery guarantee is also modified to be up this symmetry.
4.3 Computational complexity of minimizing the regularized loss OB.
In this section we discuss the computational complexity of finding stationary points of the regularized loss (0) + R()) in (OBJ.. Note that Aghazadeh et al. (2021) propose an algorithm for minimizing the regu- larized loss (BJ]) based on an alternating minimization based approach and sparse WHT algorithms. this section, we provide different insights on how first-order methods can be used minimize the regularized Joss, based on computing sparse WHTs.
To begin with, the cost of computing the gradient of (0) for many function classes scales O(n poly(m)), where dim(O). Note that we can also compute a stochastic gradient in time which scales O(poly(m) by simply computing the gradient of (fe(z') - y² for single (x", y²) pair. The variance of this stochastic gradient estimate largely depends on the nature of fe. as well as the training data.
On the other hand, consider the regularization term R(0) = A (X)][) In general, the complexity of exactly computing the gradient of R is exponential in d without any further assumptions, as it involves the summation 2d terms. While this might prove to be a challenge, empirically we observe that a two-step training process can help alleviate this issue. We first carry out weight initialization. running a few iterations of gradient descent on the unregularized loss, (,) which generalizes moderately well, and is therefore somewhat. sparse in the spectral domain. Warm-starting from this initialization and running
/

---

Published in Transactions on Machine Learning Research (April/2023)
FCN-1
FCN-2
CNN
(f - fo "x0l
10
10
spech
2 spoch spoch
400 spoch
10
10"
10
10²
10
Depech
apadds
10'
10
wpoch
sppcch
10²
10" -2
10 -1
10'
0
10
10"
0 o²
10
d²
Figure 2: We estimate the empirical lower bound C in the quadratic growth (QG) condition by finding the minimum change in the network's output as result of perturbations to the weights with noise drawn from the normal distribution W ~ (O) Experiments on 2 fully connected networks (FCNs) and a convolutional neural network (CNN) reveals empirical lower bounds.
is empirically observed that the iterates of gradient descent remain sparse throughout the training trajectory. The key implication of this result. is that one can now use sparse WHT based techniques, such as Li et al. (2015) now compute an approdmation of the gradient of the regularizer time t, R(es)) at computational cost scaling polynomially in m, and lincarly in the sparsity of fe. in the spectral domain, which is small at each time & in the second phase.
gradient descent on the regularized loss in [BJ),
5 Empirical Studies
We design our experiments in way to address these questions:
Does SP improve generalization accuracy in learning sparse polynomials?
When does QG hold for common DNN architectures? what is the empirical lower bound C
Does SP improve generalization accuracy in real-world problems?
How does Zı-regularization compare to SP-regularization in practice in terms of generalization!
Sparse polynomials. We compare the generalization performance of a depth-4 fully connected network with and without the SP regularization on 3 classes of sparse polynomials in Fig. 1 1) MONOMIAL are randomly-drawn 1-sparse functions in WHT with increasing order of interactions from to 5. 2) POWER LAW are randomly-drawn 10-sparse functions in WHT all with order-2 interactions and coefficients set based on a power law function with decreasing exponent. 3) STAIRCASE are randomly-drawn 18-sparse functions in the WHT with 3 first order, 6 second order, and 9 third order interactions, cach with equal coefficients and set based on a power law function. These synthetic sparse polynomials are inspired by physical models for real-world aseudo-Booleas functions (e.g., protein functions (Brookes et al., 2022. Qian et al. 2001 Qin & Colwell 2018 ). We observe clear transitions in gencralization power: it is harder in terms of sample cost to learn nonlinear models with higher order interactions and lower sparsity exponent (i.e., denser functions in WHT). This analysis adds new axis to the secracy-vs-samplee
phase transition curves in compressed sensing (Donoho et al., 2011). SP regularization consistently improves the transition curves for generalization power as a function of order and sample cost.
QG condition. To empirically estimate the lower bound Či, we follow this procedure. We collect a set of training data points (x', "f,,"") 1===000, initialize a DNN at 0* (see below for more detail), and repeatedly perturb the weights with Gaussian noise to generate gpert,h = 0* + Wt. where W ~ ~N(00021) is independent and normally distributed, for k = 1,... K. For each k, we compute the ratio >" (Sovas, (x*) fo- (x )22 / and report the minimum value across & [K] as function of o² in Fig. 2 Next, we train the DNN with SP regularization for certain number of epochs to arrive at new 0² and repeat the same procedure
10

---

Published in Transactions on Machine Learning Research (April/2023)
Protein
T cell
Cancer
0.22
0.64
0.60
0.20
0.56
RMSE
0.54
0.18
0.48
0,48
0.16
0.42
0.40
MSE+SP MSE
RF
XGB LASSO SVM
MSE+SP MSE
RF
XGB LASSO SVM
MSE+SP MSE
RF
XGB LASSO SVM
Figure 3: The plot demonstrates the generalization error of depth-4 neural networks with the mcan squared error (MSE) loss before and after adding the spectral (SP) regularizer compared to Random Forest, XGBoost, LASSO, and SVM. SP drastically improves the generalization error of neural network (reduced mean and variance) and allows for a superior performance over LASSO with Lı norm regularization over the polynomial representation directly.
again to observe how the lower bound changes with training, The outputs y are generated from binary vectors x E [+1]13 using the (randomly-drawn) sparse polynomial f(z) = 3x, + 4x223 + 5x4 + 212- We choose sufficienlly small architectures compared to the number of perturbations to ensure reliable empirical estimate for Čr,s. Fig.
2 shows the results for iavier-initializod, depth-2 FCNs with 222 paramcters, perturbed K = 100 (FCN-1) and K = 500 (FCN-2) times, with different ranges a² (learning rate = 10- Fig. also shows the result for depth-4 CNN with 1551 parameters, initialized by a trained network using MSE loss and perturbed K 6000 times (learning rate 10 10-3). The plots demonstrate that the QG condition is satisfied for these instances with empirical lower bounds 6.02 and 19.5, respectively. The bound also improves drastically with training; morcover, initializing the networks with trained models consistently improves the lower bound. See Appendix A for more detailed empirical studies and discussions of these results.
Real world experiments. We compare the gencralization error with and without the SP rogularization to standard baseline algorithms for data-scarce learning in the real-world (Fig 3). PROTEIN is a dataset which measures the fluorescence level of 23 protein sequences that link two variants of the Entacmaea quadricolor proteins different at exactly 13 amino acids (Poclwijk et al. 2019) T CELL. is dataset which measures the DNA repair outcome of T cells (average length of deletions)
1521 sites human genome after applying double-strand breaks (DSBs) using CRISPR (Leenay et al. 2019). CANCER is a similar dataset. on 287 sites on cancer genome (Leenay et al.) 2019). In the two latter datasets, a one-hot--ncooeee context sequence of size 20 around the DSB is used as the input to predict the DNA repair outcome. Following the low-n experimental setting in (Biswas el al., 2021). : we use subset of 30 sequences drawn uniformly random for training and validation and use the rest for testing. We repeat each experiments 10x with independent random splits of the data and report the RMSE in predicting the phenotype. We initialize DNNs using Xavier (equal seeds). We use the default hyperparamters in scikit-learn for the baselines. Despite minimal hyperparameter tuning and no architecture search, SP allows for competitive performance. In particular, the SP re-ueaulr model outperforms LASSO which applies the L1 norm penalty on the coefficients in the polynomial representation (Fig. 8 in Appendix compares SP with different regularizers).
6 Summary, Discussion, and Future Vision
In the paper, we focused on learning sparse pscudo-Boolcan functions with explicit regularization the spec- tral domain and established the conditions on general nonlinear functions under which the stationary points which approximately interpolate the training data achieve statistically optimal generalization performance.
11

---

Published in Transactions on Machine Learning Research (April/2023)
We demonstrated how the assumptions can be extended to nonlinear functions with multiple local minimas. Real-world experiments with neural networks demonstrated the utility of these assumptions. Naturally, some of the bounds might result in larger constants for very deep neural network (due to higher Lipschitz constants). Future works involve analyzing the algorithms that can achieve such statistical performance. It would be lempling 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 computationalll--ffiieen optimization algorithms for spectral regularization is still poorly understood. On the algorithmic side, spectral algorithms for pseudo-Boolean functions be extended to generalized Fourier transform to accommodate larger class of data--rugal 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.
Broader Impact Statement
We do not anticipate this work to have any potential negative impact on user of this research.
References
E. Abbe, E. Boix Adsera, M. Brennan, G. Bresler, and D. Nagaraj. The staircase property: How hierarchical structure can guide deep learning. Advances in Neural Informalion Processing Systems, 34, 2021.
A. Aghazadeh, H. Nisonoff, O. Ocal, D. Brookes, Y. Huang, O. Koyluoglu, J. Listgarten, and K. Ramchan- dran. Epistatic net allows the sparse spectral regularization of deep neural networks for inferring fitness functions. Nature Communications, 12(1):1-11 10, 2021.
A. Amrollahi, A. Zandich, M. Kapralov, and A. Krause. Efficiently learning Fourier sparse set functions. Advances in Neural Information Processing Systems, 32, 2019.
M. Anitescu. Degenerate nonlinear programming with a quadratic growth condition. SIAM Journal on Optimization, 10(4):1116 1135, 2000.
P. Bartlett, P. Long, G. Lugosi, and A. Tsigler. Benign overfitting in linear regression. Proceedings of the (1044)))0003300000 2020.
National Academy of Sciences,
A. Beck and M. Teboulle. A fast iterative shrinkage- thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 211):183-202, 2009.
S. Biswas, G. Khimulya, E. Alley K. Esvelt, and G. Church. Low-N protein engineering with data-efficient deep learning. Nature Methods, 18(4):389-38) 396, 2021.
E. Boros and P. Hammer. Pseudo-Boolear optimization. Discrete Applied Mathematics, (1333)) 225, 2002.
D. Brookes, A. Aghazadeh, and J. Listgarten. On the sparsity of fitness functions and implications for learning. Proceedings of the National Academy of Sciences, 119(1), 2022.
E. Candes, J. Romberg, and T. Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Math- ematical Sciences, 59(8):1207-122
2006.
G. Carleo, 1. Cirac, K. Cranmer, L. Daudet, M. Schuld, N. Tishby, L. Mart-Maranto, and L. Zdeborová. Machine lcarning and the physical sciences. Revieus of Modern Physics, (14::04550,, 2019.
T. Ching, D. Himmelstein, B. Beaulieu-Jones, A. Kalinin, B. Do, G. Way, E. Ferrero, Agapow, M. Zietz, M. Hoffman, et al. Opportunities and obstacles for deep learning in biology and medicine. Journal of The Royal Sociely Interface, 15(141):01170387, 2018.
M. Choraria, L. Dadi, G. Chrysos, J. Mairal, and V. Cevher, The spectral bias of polynomial neural networks. Xiviv preprint or 22o: 13478, 2022.
12

---

Published in Transactions on Machine Learning Research (April/2023)
M. Cisse, P. Bojanowski, E. Grave, Y. Dauphin, and N. Usunier. Parseval networks: Improving robustness to adversarial examples. In International Conference on Machine Learning, pp. 854-863. PMIR, 2017.
Daniely and E. Malach. Learning parities with neural networks. Advances in Neural Information Pro- cessing Systems, 13:20356-20366 2020.
D. Donoho, A. Maleki, and A. Montanari. Message-psssng algorithms for compressed sensing. Proceedings of the National Academy of Sciences, 106(45):18914 18919, 2009.
D. Donoho, A. Malcki, and A. Montanari. The noise-sonsitivity phase transition in compressod scnsing. IEEE Transactions on Information Theory, 57(0)):6920 6941, 2011.
H. Eble, M. Joswig, L. Lamberti, and W. Ludington. Higher-order interactions in fitness landscapes are sparse. arXiv preprinl Xr0: 12277, 2020.
Bradley Efron, Trevor Hastie, Tain Johnstone, and Robert Tibshirani. Least angle regression. 2004.
Á. Figula. and V. Kvaratskhelia. Some numerical characteristics of Sylvester and Hadamard matrices, 2015.
S. Gelman, S. Fahlberg, P. Heinzelman, P. Romero, and A. Gitter. Neural networks to learn protein se- quence
quence-function function relationships from deep mutational scanning data. Proceedings of the National Academy of Sciences, 118(48), 2021. doi: 10.1073/pmaz htt////aa...1488111111 2104878118.
W. Ha, C. Singh, F. Lanusse, S. Upadhyayula, and B. Yu. Adaptive wavelet distillation from neural networks through interpretations. Advances in Neural Information Processing Systems, 34, 2021.
O. Hinder, A. Sidford, and N. Sohoni. Near-optimal methods for minimizing star-convex functions and beyond. In Conference on learning theory, pp. 1894-1938. PMLR, 2020.
C. Jin, L. Liu, R. Ge, and M. Jordan. On the local minima of the empirical risk. In Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and proximal-gradient methods under the polyak-tojasiewice condition. In Joint European conference on machine learning and knowledge discovery in databases, pp. 795-8 811. Springer, 2016.
J. Lee and P. Valiant. Optimizing star-convex functions, 2015.
R. Leenay, A. Aghazadeh, J. Hiatt, D. Tse, T. Roth, R. Apathy, E. Shifrut, J. Hultquist, N. Krogan, Z. Wu, et al. Large dataset enables prediction of repair after CRISPR- Cas9 editing in primary cells. Nature Biotechnology, 3719)11034 1037, 2019.
M. Li, Z. Ma, Y. Wang, and X. Zhuang. Fast Haar transforms for graph neural networks. Neural Networks, 128:188 198, 2020.
X. Li and K. Ramchandran. An active learning framework using sparse-graph codes for sparse polynomials and graph sketching. Advances Neural Information Processing Systems, 28, 2015.
X. Li, J. Bradley, S. Pawar, and K. Ramchandran. SPRIGHT: A fast and robust framework for sparse Hadamard transform. arXio preprint arXiv: 06336, 2015.
P. Loh and M. Wainwright. Regularized m-estimators with nonconvexity: Statistical and algorithmic theory for local optima, 2015.
F. Noé, S. Olsson, J. Köhler, and H. Wu. Boltzmann generators: Sampling cquilibrium states of many-body systems with deep learning. Science, 365(6457), 2019.
F. Poclwijk, M. Socolich, and R. Ranganathan. Learning the pattern of epistasis linking genotype and phenotype in protein. Nature Communications, 10(1):1-11, 2019.
13

---

Published in Transactions on Machine Learning Research (April/202)
J. Qian, N. Luscombe, and M. Gerstein. Protein family and fold occurrence in genomes: power-law behaviour and evolutionary model. Journal of Molecular Biology, (13(4):673-685) 2001.
C. Qin and L. Colwell. Power law tails in phylogenetic systems. Proceedings of the National Academy of Sciences, 115(4):690-695 2018.
N. Rahaman, A. Baratin, D. Arpit, Draxler, M. Lin, F. Hamprecht, Y. Bengio, and A. Courville. On the spectral bias of neural networks. In International Conference Machine Learning, pp. 5301 5310. PMLR, 2019.
G. Raskuuti, M. Wainwright, and B. Yu. Minimax rates of estimation for high-dimensional linear regression over by -balls. IEEE Transactions on Information Theory, 57(10):6976 6994, 2011. doi: 10.1109/TTII 2011.2165799.
Riesselman, J. Ingraham, and D. Marks. Deep generative models genetic variation capture the effects of mutations. Nature Methods, 15(10)8816-22) 2018.
J. Rohn. Computing the norm | is NP-hard. Linear and Mullilinear Algebru, 47:195 204, 05 2000.
K. Sarkisyan, D. Bolotin, M. Meer, D. Usmanova, A. Mishin, G. Sharonov, D. Ivankov, N. Bozhanova, M. Baranov, O. Soylemez, et al. Local fitness landscape of the green fluorescent protein. Nature, 533 (7903):397 401, 2016.
M. Tancik, P. Srinivasan, B. Mildenhall, S. Fridovich-Keil, N. Raghavan, U. Singhal, R. Ramamoorthi, J. Barron, and R. Ng. Fourier features let networks learn high frequency functions in low dimensional domains, Advances in Newral Information Processing Systems, 33:7537-7547, 2020.
J. Tropp and A. Gilbert. Signal recovery from random measurements via orthogonal matching pursuit. 1EEE Transactions on Information Theory, 53(12):4655-466 2007.
J. A Tropp et al. An introduction matrix concentration inequalities. Foundations and Trends0 in Machine Learning, (11-)): 2015.
Tseng, Shrikumar, and A. Kundaje. Fourier-trannne sraiiir-rransfoom-bbseeld attribution priors improve the inter- pretability and stability of deep learning models for genomics. Advances in Neural Information Processing Systems, 33:1913 1923, 2020.
Z. Xu, Y. Zhang, T. Luo, Y. Xiao, and Z. Ma. Frequency principle: Fourier analysis sheds light on deep neural networks. arXiv preprint wxXx:1991.0662.. 2019.
arXiv preprint G. Yang and H. Salman. fino-grained spectral perspoctive on neural networks. 1rXiv:1907.10599, 2019.
Y. Yoshida and T. Miyato. Spectral norm regularization for improving the generalizability of deep learning. arXiv preprint 1 10941, 2017.
H. Zhang and W. Yin. Gradient methods for convex minimization: better rates under weaker conditions. arXiv preprint ar 4645, 2013.
Y. Zhang, Z. Xu, T. Luo, and Z. Ma. Explicitizing an implicit bias of the frequency principle in two-layer neural networks. arXe preprint arXiv: 10264, 2019.
14

---

Published in Transactions on Machine Learning Research (April/2023)
A Additional Empirical Validations
A.1 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:
[s()) : x (+1) H [a= = [
(14)
for the experimental data obtained from the fluorescence protein (Poelwijk et al. 2019). In addition these plots, we have attached videos supplemental materials where visualize the learning trajectory of 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 good solution. Spectral regularisation enable DNN converge to the sparse solution in the data-scarce regime.
function value
1.5
brightness
1.0
0.5
0
2000
4000 protein index
6000
8000
spectrum
0.8
coefficient
0.4
0.0
0
2000
4000
6000
8000
WHT index
Figure Combinatorial visualization of the brightness 2 proteins (top) and their Walsh-Hadamane transform (bottom) linking two variants of a fluorescence protein that are different 13 locations on their amino acid chain (Poclwijk al. 2019 The brightness pscudo-Boolcan function which maps from ʃ {=1) R. The sparse spectrum reveals low and high order interactions among amino acid sites on the protein.
A.2 Convergence: training and validation
In this subsoction, we include additional empirical results which focus on the convergence properties of spectral regularization for training DNNs. The first objective we study in validating whether stochastic gradient descent (SGD) indeed converges to approximate first. order stationary interpolators (Definition 3
15

---

Published in Transactions on Machine Learning Research (April/2023)
The goal of these experiments even when the training loss, against which stochastic gradients are computed, is augmented with spectral regularization. In Fig, 5 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 rale= 10-1) to train on the fluorescence protein (Poelwijk et al. 2019 dataset (also used in the main paper).
whether, upon running SGD, the MSE loss gets sufficiently small
0.45
MSE+SP SP
MSE
0.24
validation loss (MSE)
training loss (MSE)
0.16
0.30
0.08
0.15
0.00
200
400
600
800
1000
0
200
400
600
800
1000
epoch
epoch
Figure 5: We plot the training and validation error in terms of the empirical mean squared error (MSE) in predicting the brightness of a fluorescence protein (Poelwijk et. al.) 2019) using DNNs trained with and without the spectral regularization. We use a depth-4 fully connected neural network with Xavier initializa- tion both cases. The plots demonstrate that 1) the training MSE eventually gets sufficiently small, even when the original loss function on which SGD is run is augmented with spectral regularization, even when network uses random initialization and 2) spectral regularization consistently allows for significantly better generalization gap all along the trajectory of training process.
MSE+ SP
MSE
0.24
training loss (MSE)
validation loss (MSE)
0.4
0.16
0.3
0.08
0.2
0.00
200
400
600
800
1000
0
200
400
600
800
1000
epoch
epoch
Figure 6: We repeat the experiment above with the only difference that instead of a Xavier initialization, we carry out what is known as "weight initialization" (Definition 4 Here, we train the DNN with spectral regularization (blue curve) in comparison with a DNN without spectral regularization (orange curve), but with weight initialization. The plots demonstrate that even with weight intialization, spectral regularization does not result in an increase training, and results in decrease in validation MSE. Weight initialization has the advantage that the QG constant encountered along the training trajectory of SGD are higher (Figure 7 compared to with Xavier initialization
16

---

Published in Transactions on Machine Learning Research (April/2023)
Training after 100 epochs with regularization
Training after 200 epochs with regularization
Weights inttalizee Xavier
10
Weights inibalized
10
X
Weights inihalized with 100 apochs training without regularization
X
Weights inihalized with 100 training without regular zation
min - fo- (xx)1//0
10
10'
10²
10
10
10
8
10
X
10
X
10
8
10
10
8
10
10²
8
-
10
10
10
10'
10-9
10
10 o²
10
10'
o²
Training after epochs regularization
Training after epochs regularization
Weights initialized with Xaviar
O Weights initializad with Xavier
10
X
Weights intiaaizeed with 100 epochs training without regulariatonn
10
X
Weights inttalizzd with 100 epochs training without regular zalion
ff - fo (xill/00
10"
10
10
10
X
10
10
83
10
10
130
25
10
10
38
8
102
8
10
X
10
10
10" d²
10
10
10
10" 2
10 σ²
10"
10'
Figure 7: We plot the minimum ratio minke(k) Er= (Joven (x*) models trained initialized from (i) Xavier initialization, and (ii) weight initialization, with a learning rate of 10-3, Similar the experiments plotted in Fig. we perturb 0", 6000 times generate Opert.k
So- (x=)))/
against o² for 4-layer CNN
A.3 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 Assumption I(b) requires showing that for any 0,
En--Uii((.))
(fo(z) for (x))
Ch
0
(15)
However, since it is prohibitively expensive check this for all choices of 9 and morcover since the models we consider exhibit. some smoothness, resort to checking this condition only for randomly sampled 0 around
17

---

Published in Transactions on Machine Learning Research (April/2023) 2023)
Protein
T cell
Cancer
0.22
0.64
0.60
0.20
0.56
RMSE
0.54
0.18
0.48
0.48
0.16
0.42
0.40
MSE+SP
MSE
MSE+L2
MSE+L1
MSE+SP
MSE
MSE+12
MSE+L1
MSE+SP
MSE
MSE+L2
MSE+L1
Figure 8: Comparison of the generalization error of different regularization schemes: spectral (SP), L1, and L2 norm regularization.
the reference 0r In particular, collect set of training data points (æ', y') from an arbitrary sparse polynomial, f(x): {+1)13 + IR, defined as 3z, + 4xg22 + 504I5 T12-
First. we train a DNN using SGD on the unregularized MSE, and define this as 0" Then, we repeatedly perturb the weights K times independently with Gaussian noise to generate Opert,k = 0 + We, where o2) is independent and normally distributed, for = I,..., ,. under the Gaussian perturbations, note that ||@pert. 1 concentrates around Mo?, where M is the number of parameters in the network. Therefore, instead of computing the ratio,
K. By concentration of measure,
Ea>Uni((D.) (Jo fo- (x)))
C min
(16)
0
0 1
we instead approximate it by the ratio (up to scaling by M),
E [[Soport (xt) so (xt))²
min RE[K]
(17)
g²
as an approximate proxy for perturbations at the scale of a around 0* Too distance, which more accurate, K grows larger. In Fig. 2 we plot the ratio in eq. (17 as function of a.
We repeat this experiment when 0* is trained starting from weight initialization, and plot the estimated ratio in Fig.
Definition 4 (Weight initialization). Weight initialization, refers to initialization of the network by first running 100 epochs of SGD against the unregularized MSE. From this starting point, subsequently we "turn on" the regularization and run SGD against the MSE with spectral regularization.
Each subplot shows the estimated QG ratio (eq. 17)) for models initialized with weight initialization, at the 100, 200, 300 and 400 epochs mark respectively. The plots demonstrate that weight initialization method significantly improves the QG constant Ci,ss along sample trajectory encountered by the SGD, compared to models trained with spectral regularization starting from a random Xavier initialization.
Remark 6. The guarantees hold for a specific choice of regularization parameter X, which may also be adap- lively changed over the course of oplimization the compulation of gradients. In praclice, the regularization parameter X is chosen by cross-volidation.
A.4 Comparison other regularization schemes
In this subsection, we compare the performance of neural network under SP regularization with other regu- larization schemes which directly penalize the & and lg norm of the weights of the neural network. The goal
18

---

Published in Transactions on Machine Learning Research AArri/2223)
X, X,X
X
XX xxx+xpa+ x
x
monomial
power law
staircase
WHT
WHIT
WHT
order of interactions
MSE
power waw cpefiicient
MSE
power coefficient
3
1.5
3/4
5
1
1/2
1
MSE+SP
2
MSE+SP
MSE+SP
3
1.5
1/4
5
50
100
150
200
50
100
150
200
50
100
150
200
number samples
Figure 9: The plots demonstrate the gencralization power of a depth-4 feed-forward neural network learning classes sparse pseudo-Boolean functions f(x) {+1]18 + R using the mean squared error (MSE) loss before (first row) and after (second row) adding the spectral (SP) regularizer, as function of the number of training samples. MONOMIAL are 1-sparse functions in Walsh-Hadamard transform (WHT) with increasing order of interactions (1 to 5). POWER LAW 10-sparse functions in WHT with second order interactions and coefficients set using power law function. STAIRCASE are 18-sparse functions in WHT with 3 first order, 6 second order, and 9 third order interactions, each with an equal coefficients and set using a power law function. The heat maps show the average of the coefficient of determination among random independent trials on unseen data.
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. 3 the same experimental conditions. In Fig, 3 we demonstrate that while direct weight-reguulrtiztion schemes such as l and & norm improve the generalization gap of neural networks, the generalization gap is significantly larger for SP regularization.
B Technical lemmas
In this section outline and prove the lemmas used for the proof of the main theorems. We first state the subgradient of the regularizer R(0)
-
H
(X))l.
Proposition 1. The subgradient of the regularizer R(()) V2c
H.fo
is,
(VR)
(V)(())) Ha : (ggn(H(((
(18)
(+1}
if > 0
Here, for E R, sgn(z)=
(-1}
<<0
and applied on a vector z (z)) the Cartesian
+11
otherwise
product of the sets sgn(21)
... sgn( (n)),, and (X) matriz with columns fe(x)) for each x X.
Proof. The proof follows by direct computation. Observe that, ()]Hf(())ll: D Vile, Hfo()))
D 4 (V fo Hz where the last equation uses the symmetry of H.
Lemma 1. [l (X) (x) 2 < 2 0 2L Ø 0-
Proof. By the Lagrange form of the Taylor series expansion, for any x, there exists O,, such that,
fa( fo (x) -0- (z)) @ 0r) (x) 0-)
(19)
19

---

Published in Transactions on Machine Learning Research (April/202)
Then, for each E X,
(f)(z) - So. (x)) S 21²110 -0'1 + 2 (V fo (x). 0- -x))
(20)
Summing over x E X results in;
|| llf fo. (X)1 $ 22 110 0 + L 2 -0
(21)
where recall the assumption, 1 EzEx viG- (z) I.?
Lemma |axx:] $1 [Hul 1 S (2d + 1)v2d.
Proof. Note that max 1 He|| max w (- [Hellı. by (Rohn 2000 Proposition 1). Therefore, it suffices to maximize over V E (-1, +11²". It is known from Figula. & Kvaratskhelia, (2015) that gld) I d2d where gl4) A maxme(24) / HH1 || where & is an arbitrary set of vectors from the unit || || ball in R²", 1m is the vector with the first m entries and the remaining entries O. Since & can be chosen as any permutation matrix, this result implics that max (e0,)j= [Hujla I d2d. To compare with the previous statement, note that the number non-zeros in here equals m the optimization problem defining g(d) Then, we have that,
max WE (-1++11))
Hullı
H(2v 1)1l1
(22)
vE(0,1) 2
2 2||Hl|1 + H1|||
(23)
< 2dv 2d + V
(24)
where (i) follows by triangle inequality.
Lemma Under Assumptions
((a) and for any E Rd and any subgradient G E (VR)(0), under the
event Eyst
8r, Err, (0,0 C
0 112 which happens with probability 2 1 5,
0", VL, (0) + G) - -2E [[fo (x) - --(()())))))))))>)>>)(())) (0 - 0r, VzV
(25)
2 (Oh.5 (2d + 1) |00 0- 11 R(0) -(()))
(26)
Proof. Observe that,
0 0-00, VC)( 2E u ((o
v(x)) (0 8-, Vfo(2))
(27)
Plugging this in below,
0 0-, VL. Unit [ff- --
(28)
2E Do.tt((( [ff(x) - u(z)) 0- ff(=)) - (z) - v(z)) (0 - 0- vf(()))
(29)
2E. [(f((z) - fo (x)) (0 0", fo(x)))
(30)
= (0 10-0 0r, VlL [(fo(z) - fo- (x))
(31)
> C 1 0 11
(32)
where the last inequality follows by the RSI condition imposed on Err,(0,0") 0") in Assumption ( Putting
together eq. (32) with Lemma 5 uner the event Eysh.
0 V., (0) + G) 2FanUni((D.) ((o-- (x) y(x))) 0", Vie(2)))
(33)
2 C 0 R(0) R((0) - (2d + 1)Am1l0
00
(34)
This completes the proof.
20

---

Published in Transactions on Machine Learning Research (April/2023)
In the remaining proofs, will assume lower bound on the regularization parameter to ensure that the regularization actually plays role. In particular, Condition 1. Assume that the regularization parameter X satisfies,
d + log(1/6)
x2 12
(35)
Lemma 4. Suppose X satisfies the lower bound in Condition
Define Eg as the event that, for all Rd
Ln)Uni((D.)) (x) y(x))) (0 - 0, V (x)o))
(36)
A2d2d + 1)
H (fo (X) (x))l) +
110 1
(37)
2d
4
Then, Pr(E2) 2 6.
Proof. For each sample x' Dn, define the noise in the sample as z(x') = (x)) Likewise, define the
noise vector zD., (EE)) [xxx z)] x E [2 Note that the coordinates of zp, corresponding to inputs unobserved in the dataset Dn 0.
By Taylor series expanding, fo- (x) fe(x) (0' O. vfo()) + (0) (V* (x)) (0- -0) for some 0, E conv((0,0*)) Therefore,
En-Uni((D,) (ffo (x) v(x))) (0 - 0, fo(x)))
(38)
Uniutt(D..) [fo- (x) y(x))) (Jo- (x) fo(x) - (0 -0- (V2 So. (x)) 0²)
(39)
(ZD,, So- (X) (X) A0 ))
(40)
where A0) denotes the vector { 0² fa. (0) - 0) x [24]]
By an application of Holder's inequality and triangle inequality the Lo-nor,, we have,
Ez>Uni((D.) [[fo (x) - v(x))) (0- - 0, V.(
(41)
HzD, loc H (Jo- (X) - (x)) 11, + HZD. Il. (A
(42)
Note that for each fixed row [2"], (H, DD.) = Ex HIJZD, ()) Note that the coordinates of zp. are independently distributed and subgaussian. Therefore, by Bernstein's 's incquality,
Eveley Var(zD,,()) (i) log(1/0) 2d
Pr (H,.D. 2 231
5 8
(43)
Note that the coordinate of zp., labelled by x E {+1]d, Ez- E independent ((0 o²) Gaussians scaled by 1/n, where Dz(x), defined as the number times æ is sampled in DR, Therefore, Var(zn, (i)) r²D,(z) By union bounding over the 2d rows of H, with probability 2 1 6,
x)]. is the sum of (z,
)DD,( Exeep4
log(24/0) n²
Pr
HzD, 1l0 231
S.
(44)
2d
Note that Evelo Dx(z) = n, and therefore, with probability > 1 1-5, the event Ei, defined below, is satisfied,
1
d + log (1/8
A
& : Hzp, ao S $30
(45)
2d
n
4v/2d
21

---

Published in Transactions on Machine Learning Research (April/202)
where the last inequality follows by the assumption on À in Condition 1
Note that || I1 I p/|0 1- Thus, the term [0 can be upper bounded by
suP S0 a- [Hull This itself can be further upper bounded using Lemma 2 by (
All in all, combining this argument and eq. 45 with eq.
under the event E₁, with probability 2 1- 8,
Un-Uti((D,,) [(fo (x) - v(z))) 10 - fo())M
(46)
(fo (X) fx)x) + Ay(2d + +) 10 ---
4 V 2d
(47)
Lemma 5. Under the Lipschitz gradient condition, Assumption consider any 0 Rd and any subgradient G C (VR)().. Then,
0-00 0'' 2 R(0) R((0) - (2d + 1)Am(10 - 1-
(48)
Proof. Recall that the regularization function R(()) is defined as V2d (X)]ll Consider any subgradient G E (VR)(0) of the regularization function R(0). By Proposition this of the form A V2n
(X))
where E (x))H In particular, using this representation, we have the equation,
A 2d
0-00 G)
0 0
(49)
Since fo(x) is in general non-linear in O, we can relate (0 V') to fo(x) fo-(x) by using a Taylor
series expansion. In particular, for each x E [24] and each 0 and 0r, by the Lagrange form of the Taylor series expansion, there exists a 0₂ E conv((0,0)) (0,0*) such that fo- (x) fo(x) = =VVolz)) - 0) + (0" 0'" fe_ (0) - 0). In addition, note from Assumption 2 that -ul = fo(x)) I ul. This results in the following set of incqualities.
fo(z) fo- (2) + (0
(0) 0*)
A
0 1--0'
0 G)
Hz
(50)
22d
xE(24)
X (fo fo- (X)) H A
V22 120 111 00
(51)
/2d
(H
H (X)) - (2d + 1)Au 00
(52)
V2d
where the last inequality follows from Lemma 2 where show that for any vector v ||o|| condition which is satisfied by the sign vector z), [H S (2d + 12
A naive attempt to prove such a bound turns out to result in a loose bound. Indeed, |Hul] S 12 < 2dd = 2d. The improvement of one of the v factors to (2d + 1) turns to be quite deep mathematical fact, and we invoke a result of Figula. & Kvaratskhelia (2015) to prove this result in Lemma
Finally, using the convexity of || ||I, for any z E sgn (g)(Ho(X)))
(X) H (x))
(H) (Hfo- (X))²²
(53)
H (X) [l
sup
(v, H (X))
(54)
v:||e|| 51
z H X |H (X)ll1
(55)
Combining this with eq. 52 and using the definition of R(0) completes the proof.
7
22

---

Published in Transactions on Machine Learning Research (April/2023)
Lemma 6. Under Assumption 2 for any 0 E Rm and any subgradient G E (VR)(0),
0 0", VL, + G) + 2E p.uili((( [1So (x) v(x)))) (fo- (x) fo()))
(56)
(Err,(0,00) R R(0') (2d 1) 2p C, (0) |0 1
(57)
Proof. The proof of this result builds on the analysis in Lemma Observe that,
0 0 (.)
(nir(()) (2(f((x) vx)) (0 0", Vfo(=))]
(58)
For each x E [24] and each 0 and 0", there exists 02 E conv( 0*)) such that fo(x) fo (x) =
2 for (0 8*). Plugging this in, and using the assumption that -pl = (o) 0 -0) (0 8)
2 fo(r) 3 nl,
0 0-, VL, (0)) - 2I pnit [ (x) v(x))) (fo(z) - fo (x)) EzwUnif((D) (D.) (2( v(x)) 0¹, Vfolz)) 2(So (x) - ((=)) - for (x))
(59)
(60)
(xUini((D.) (2(f((z) v(z))(
2(S0- (x) - v(x))) -o (x))
(61)
17 2 2F goUni((D..) [[) - Se- (x)) 2p| - 0013 (x)
- -2410 1-012 Ez~Uni((D.) [[f((z) - y(z)]
(62)
(63)
where the last inequality follows by Jensen's inequality.
Putting together Lemma and eq. 63 for any subgradient (V) we have,
0 0 VL, ( G) 2E Unir(() [(fo- (x) y(x))) (fo(z) - fo- (x))
(64)
A
2 zmUi((( [(o(1)) - Sa (z)) + 222 ([ X - H- (X)
(65)
- -(22d+ + 2pV (n)
110
0 1
(66)
This completes the proof.
Lemma 7. Suppose the regularization parameter satisfies the lower bound in Condition event that for all RTm
Define Eg as the
Ex-Unit(Da) ((fe- (x) v(x))) (fo (x) fo(x))) <
H (fo- (X) fo(X))
(67)
2\ 2d
Then, Pr(Es) 2 8.
Proof. The proof of this result is similar to that of Lemma and we include the details for completeness. For each sample x' E Dn, define the noise in the sample as x(x)) = fo (x') - y(x) Likewise, define the noise vector ZD. (Es= (=<(')0((2 x) [24]]. Then, by application of Holder's incquality, have,
En-UUi((Da) [(fo (x) -(xx)))))))))))) (fo- fx))) S HZD lbo H (fo (X) fo (x)
(68)
Note that for each fixed row i [24], (H; 2n.) Eee2 Hij2n, (i). Note that the coordinates of zn, are independently distributed and subgaussian. Therefore, by Bernstein's inequality,
Eje(pn Var(zD. (i) log(1/6) 2d
Pr H, zD.) 2 31
<
(69)
23

---

Published in Transactions on Machine Learning Research (April/2023)
Note that the coordinate of zp, labelled by {+1}", Ex x)). is the sum of (n)
independent o0) Gaussians scaled by 1/n, where (x( defined as the number of times æ is sampled in Dn Therefore, Var(zp, (1)) = o² (2)) By union bounding over the 2 rows of H, with probability 2 1-16. 6,
ExeRu
(aD, n
log(24/6)
Pr
|Hzp, 231
S 8.
(70)
2d
Note that En (2(x) n, and therefore, with probability
21-60
+ log(1/6)
Hzp, oo I 3 2d
(71)
n
4v2
where the last inequality follows by the assumption on X. This implies that with probability 2 6,
A
En-Unit(DD)) [Ifo- (x) y(x))) (fe (x) - fo(x))] S
H (fo- (X) fx))]l
(72)
2 2d
Lemma 8. Assume that d 2 3 and k S /4. Then, there erists set of (dd1))(/2 binary vectors of length
24, denoted Ck, each having at most k ones, such that: the hamming distance between any pair of vectors is at least k|
Proof. The number of vectors within hamming distance x [k/2] of any vector is (*)). Note that k K 2
We can greedily construct packing of size least (1)) (2d-x))
(24 2d()=-) (2) (2)0m 2du (2)
2(d-1)s vectors before running out of binary vectors to choose. By construction, every pair of vectors has Hamming distance at least K.
C Proof of Theorem
1 Statistical performance under RSI
In this section discuss the proof of Theorem I
We prove 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.
Theorem 4. Suppose the regularization parameter À satisfies Condition Namely,
X 120 d + log(1/8)
(73)
Consider learner which returns any first order stationary point of the loss (.) + R(0). Under Assump- - [2d + 1)Au - 3XLV / > 0, with probability 2 1 26,
tions ((a)
2
and
3
if
6ALVk Ci
1@0 0'112 <
(74)
Proof. Plugging in 0 = θ into Lemma 3 and noting that 0 VL,, (VR)()), choosing G appropriately
we obtain, conditioned on Ersh:
2n (fo (()))))))))) (0- 0, (z)
R(0) R(0") + (C (2d + 1) 1) 110 0'
(75)
24

---

Published in Transactions on Machine Learning Research (April/2023)
Now, we upper bound the LHS of this equation using Lemma 4 choice of 0 = 0, and rearranging both sides, under the event Ersi and &g which jointly occur with probability 2 1 2
Plugging Lemma into eq. 75 with the
3
C
2 (2d + 1)
10 00
A
(Iffo((X)l)
V2d H (X) ||, 2v2d
H (fo- (X) (x))
(76)
V2d
(88)
X
(X) || - H (X) + 1
HH (X)Il1
HH
(77)
V2d
X
(3 H. (X)I1 (x)]))
(78)
2d
where (1) follows from the definition of the regularization term, R(()- = - [|) On the other hand,
(ii) follows by triangle inequality of the norm || ||- By the assumption - 2 (2d + 1) 3ALV,, the LHS of eq. 78 is non-negative. Plugging this into eq- (78 results in the inequality,
(3 H (x) (x)(())))) 2 O.
(79)
2 2
Conditioned on Eg and Ens.
Lemma 5) to the function px(-) = |l,, and note that by assumption H.fe (X) is k-sparse. Define v H(fe- (X) - fe (X)) and A as the set of k largest indices of y in absolute value. Using the fact that H (X)Il Hf [x)
Next, we apply Loh & Wainwright/ 2015
|| 2 0,
A
H (X)I1
HJ 11))
(31|vAll (14
(80)
2
22d
3\Vk
||Al|
(81)
2
3
||/||2-
(82)
2v2d
Plugging this back into eq-
78
results in the following inequality, conditioned the event & and E
3 (2d + 1))m)) |10 13
3\vK
Ch
fo (X) - la(
(83)
2
2v2d
Finally, we relate Il (X)
(x) to ||0 110-0-12.
Plugging the bound in Lemma into eq. 83 results in the following incquality, conditioned on Eg and E
3 22d + 1)2zz)
C
||@ 0 3 0- 3-3 A 1-
(84)
2
Furthermore, recalling the assumption that C. 3(dd 1)Ap 3μAVK 2 0, this results in the overall bound,
3ALVE
6XLVE
1|@ - 00-0-1 -
Ch,8 (2d + 1)Ap - 3pAVK S
(85)
C
under the events Eg and Ens which jointly occur with probability 21-26 25.
7
25

---

Published in Transactions on Machine Learning Research (April/2023)
Proof of Theorem 1 Theorem D follows from Theorem 4 by choosing À as its lower bound in Condition 1 It easily verified (hat when the size of the dataset, n, is larger than the quantity defined in the statement of Theorem the condition G (2d + 1) 3AL & > 0 as required in Theorem is satisfied.
equal to 12o d+ d+-log(1/8) a
Notes on the constants. We did not choose to optimize the constants in the theorem statements to keep the proofs simple. With more careful analysis they can be brought down further.
D Proof of Theorem 2 Statistical performance under QG condition
In this section we discuss the proof of Theorem 2 This result is a consequence of more general result which characterizes the performance of stationary points of the MSE with spectral regularization when the regularization parameter, X, is chosen arbitrarily.
Theorem 5. Define A C. (2d+1)A
3 AvV and assume A > 0. Suppose the regularization parameter
2n
satisfies Condition 1 Nomely,
d + log(1/8)
2 12
(86)
Consider learner which returns a A approozimat first order stationary interpolator (Definition 3 of the loss (0) + R(O). Then, under Assumptions
I(b) 2 and with probability 2 1 - 22,
3ALVK
||0 12 S
(87)
CH,6
Proof. Plugging in 0 = into Lemma 6 and noting that the learner returns a first order stationary point of the regularized loss, 0 E C. (0) + (V (0), choosing G appropriately we have, that under the event Eggs
2 (lL [(fe- (x) v()))) (fo- (x) (x)--((x)))
(88)
2ET,, (0,60) R() R(0") (2d 1)Ax (2dd+))Ap+ + 2n (n(0) 1|0 0 0²
(89)
Under assumption (A1), recall that we assume that 0 sufficiently good interpolator in that, (,) s Simplifying eq. (89) under this assumption gives,
Ci. 2p
(2d+1)A
VkX
2E Unif((D.) [(fe (x) y(z))) (fo- (x) - fo(z))]
> 2Err, (Err,(0,0') (0.0") + R(0) R((0) (C7,6 3udvk) 110 -0
(90)
Next bound the LHS of eq.
90
using Lemma
Plugging Lemma into 90 and rearranging both sides, under the event Es.
2Err, (0.00) - (Cr,5 - 3)4VKk 0 0
A
H V2d Híg (x) |1
H (X) (X) So (x)
(91)
/2d
2/2d
(1))
X
[|H.So- (X)Il (x)] + H (x)
1 |||x(X)|||)
(92)
/
(3 H (X) H(*())] ||
(93)
2v
where (1) follows from the definition of the regularization term, R()) = X
v [X)o On the other hand.
(ii) follows by triangle inequality of the norm || ||. Next we focus the LHS of the above expression and
26

---

Published in Transactions on Machine Learning Research (April/2023)
simplify it further. By the quadratic growth condition in assumption [(bb under the event Egg ErT, Err, (0.0") 2 Cū,5l 00 12, which assumed to happen with probability 2 - Therefore, under & and Exg.
,rrr,, 0- - -Cri.s - 32pvk) 110 1
(94)
2 10 - 10-0-1 002 122 Ch, + 3.22k
(95)
0.
(96)
Plugging this into eq.
93
results in the inequality,
(3 H (X)II, ||//())|l| 0.
(97)
2v2d
Under the events &g and Eqg-
Next, we apply (Loh & Wainwright, 2015 Lemma 5) to the function px(+) = || 11,, and note that by assumption He (X) k-sparse. By defining v H(fo- (X) fx)) and as the set of le largest indices of in absolute value.
À
( A
H (X)IIi |
(3]|vAl1 - -1MA-=11)
(98)
2 2 2d
V2d
3
|ual2
(99)
2v
3\v
||/122
(100)
2v2d
here, (i) uses the fact that 3 Hof (X)Il - f (X) 2 from eq.
97
Finally, plug the relation between ||0||2 llfo- (X) fo (x)
110
00 proved in Lemma into
eq. 100 This results in the inequality,
H (X)
3yAvTT r" 00 3AL 1
(101)
2 2d
Plugging this back into eq.
93 under Eg and Egg.
2rrr, - (C 32pvk) <3 -0 3ALV - 0-
(102)
Resulting in the bound,
2E,r, 3ALVRII0 0- Ch @|0 1-1
(103)
Under the quadratic growth condition, by the event &a in Assumption 1(b) Err, (0.0') 2 C 10 -0"1l3 Therefore, under the events &g and Egg which jointly occur with probability 1 1 1-2
3ALVK Ci
||0 00 S
(104)
Proof of Theorem 2 Theorem 2 follows from Theorem 5 by choosing as its lower bound in Condition
d+log(1/6) It is easily verified that when n no, as defined in the statement Theorem
equal to 12o
the condition A C [2d 1)Ay ALL > O required in Theorem is satisfied.
27

---

Published in Transactions on Machine Learning Research (April/202))
E Proof of Theorem 3
In this scction, prove lower bound the statistical error of parameter estimation. the objective is to show that for every learner 0,
Loosely speaking,
sup E 100-01122 2 ov kd 8-
(105)
Proof. We first introduce auxiliary result related to packing binary vectors with bounded Hamminn weight in Lemma 8 Now define the function space (.f(.)) R²² }, where fa()) defined the polynomial with coefficients specified by 0. Namely, fo fo( Esgia Os Ilis 2i, where we index the 2 coefficients of 0 by the 24 subsets [d]. In an alternate notation, we may represent,
fo(x) (0 201
(106)
where 2|x) denotes the 2d length vector whose element indexed by some subset S S [d] is HiEs
Furthermore, we assume that the data generating distribution independently samples n pairs (II.3) where 24 ~ Un) and y; = fo- (x;) + Zi where Z; ~ -N,00 Denote D. = {.1, ... ,.n)
By Lemma 8 the binary vectors belonging to Cs can be used to construct a subset of the function space G, defined as Sk,
S₁ = (fo(-) :0 E ACk),
(107)
where A > O is scaling factor and AC₁ (20 0 E Cx).
Henceforth, we will consider ourselves with learning functions (resp. parameters) in the class S₃ (resp, ACk).
First we show the properties on Err, (0.0*) and G in the statement of Theorem 3 Note that G is a linear family by the representation in eq. 106 and therefore = O.
In addition, note that,
Err,, (0,0") = FrnD, [fo(x) - so (z)))
(108)
(0 - 0- 2/ }
LxnD.
(109)
(0 - 0-0 (2(e()))) (0-0")
(110)
Note that A, 22 is matrix whose entries (indexed by pairs of subsets of [d] can be described (S,T) = Ilis Iz IlyEs Ty. Note that in expectation over ~ Unif(X), we have that,
Ex-Unif(X) (A,(S, 0(S T)
(111)
This is because S + T, there exists an element i E () S) (i.e the symmetric difference of the two sets) and since Un)-Un))(() [2,]] 0, we get the required statement. Therefore,
En-
(112)
Now, given samples from the uniform distribution, EgsuUit(( [A)) is expected to concentrate around its expectation Ex>Unif(x)(AA] [Ar]. In particular, by invoking the matrix Bernstein inequality Tropp et al. (2015) we have that.
Pr Unit,))nit Uni [Awlllo 2t) 2(2") exp (-nt?/2L2)
(113)
28

---

Published in Transactions on Machine Learning Research (April/2023)
where L is an almost sure upper bound on ||A Note that ||Aello ||2101112 v2d and therefore we may choose L. v2d. This results the bound,
1 - 22("") exp (-n/24+3)
Pr [|E [4p] -1lopp 2 2
(114)
Therefore, if n Z (d + log log(1/0))2ats with probability 2 1 -
2 I Es-unit((D.) (D.)) [Ax] 1 I.
(115)
In eq. 110 this implies that, with probability 2 - 6,
Err,(0,0") 2 2 100 00
(116)
And likewise, from the linear representation in eq. (106).
V fe- (z) (z))²] Unif(
(2()()
(117)
where the last equation follows from eq. 112
To generate the lower bound instance, suppose the ground truth parameter sampled uniformly from AC₁. Suppose the learner outputs candidate parameter 0. The population level mean squared error of the
learner is lower bounded by the testing error,
sup RRRd
[10 0 l12] 2 Eg Eg-~Uni((ACa)
E fll- 0- 1111
(118)
4 Lk/2| inf Uuit(cc) (V(V((,)) + 0*)]
(119)
where the infirmum is over all tests functions which return a function in Cs. This uses the fact that any estimator 0 induces a testing function for 0 by returning the E AC₁ such that |10 10-0l12 is smallest. If this test makes mistake, then 0 must have predicted > V [k/2] entries of 0' as A/2 instead of A or > A/2 instead of (making an error of at least A/2 on these coordinates).
The optimal hypothesis testing error can be lower bounded by Fano's inequality as follows,
inf E Unif((AC.) [I()(D.)) * #0))21- T(0"; Dr,) + log(2) log AC+]
(120)
For each parameter 0 E AC,, define the distribution,
Po(D,) II
n
exp
(- 20 (v: fo(2)))²
(
1
(121)
2
2d
which captures the data distribution when the underlying ground truth parameter is 0. Note that D, ~ Po- marginally H, is uniformly distributed on the hypercube and conditionally is normally distributed with mcan fo- (x;) and variance o². Note that the mutual information can be bounded as,
T(0", Da) inf Fnf -.) [KL [[Q)]
(122)
Unif KL [[Pb)]
(123)
where Po is the distribution of Dn when the ground truth function fe in eq. 121 is chosen as 0 everywhere. Then,
KL(Po-IIPA (Po)
En Pa.
2w:So- (ax) (gb(
(124)
20
1
ED,~Pa Pa-
Σ (fo- (x::))
(125)
20
Eng~
E
[[Tor (xx)))
(126)
2g
29

---

Published in Transactions on Machine Learning Research (April/2023)
where the last equation just uses the fact that in Po-, the marginal distribution of is uniform. For each 0", by Parseval's theorem, F (2,-Uoi(((++1))) [[So (x:))²] kA?. Overall, plugging into eq. (12)) and subsequently into eq. 123)
nk
1(0", D.)) S (g)-Uni((ACs) [KL(Po- Poo]
(127)
2n²
Putting these bounds into eq. 120 and subsequently into eq. (119 results in,
F UnC((A
F 0 0-
[
[2/2
nk 222222222222 log(2)
(128)
log 2(d-1)[k/2]
(nk-22/02 +
4//2
1 10
(129)
(d - 1)[k/2]
Choosing A Se/ / for sufficiently large constant C, we get that for any learner, if S C
d²
A
[E [||0 0-
[b1l
kd
[ UnifUA)((
2 2exa
(130)
7
30


Reviews:
[{"review_id": "WhfpRCk8Wz", "reviewer": "Reviewer_BvRF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strength\n- topic of interest for TMLR audience\n- results on par with the existing literature on the Lasso (though a more in depth comparison of the constants would be useful); the dependency on the number of samples, dimension and true sparsity makes sense and is proven to be a lower bound.\n\n## Weaknesses\n- see requested changes for experiments below\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the learning of pseudo-boolean functions (functions from $\\{-1, 1\\}^d$ to $\\mathbb{R}$)/\nSuch functions can be written $f(x) = \\sum_{\\mathcal{S} \\subset [d]} \\alpha_{\\mathcal{S}} \\prod_{i \\in \\mathcal{S}} x_i$.\nWhen learning such a function through empirical mean minimization, the paper proposes to $\\ell_1$-regularize the spectral transform of the learned function.\nThis approach is motivated by the observation that the spectral transforms of several real-world pseudo-Boolean functions have a sparse structure.\nTraditional sparsity approach may fail, as the number of spectral coefficients in the decomposition is $2^d$.\n\nWhen the true empirical loss, $\\sum_i (f_\\theta(x^i) - f_{\\theta^*}(x^i))^2$ satisfies a restricted secant condition (RSI, def 1), any critical point of the regularized objective is, w.h.p., close enough to the true parameter, with error bounds similar to that of the Lasso (Eq 8, 9) ($\\sqrt{kd / n}$)\nWithout the RSI condition, an analysis under quadratic growth is provided, for \"almost interpolating\" critical points (and not just any critical point).", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "\n\n## Experiments\n- In figure 1, the generalization is considered a success if \"the models generalize on unseen data with the coefficient of determination larger than R2 ≥ 0.45 on the test data points.\". Why this value of 0.45? Can you directly plot the left-out error or the R2? rather than thresholding?\n- The experiment on QG conditions seems flawed to me: why would a random sampling provide a good estimate of the direction in which the growth is minimal? If it were performed on a simple quadratic function, you'd need to sample in the direction of the eigenvector associated with the smallest eigenvalue; any isotropic sampling will vastly overestimate the smallest eigenvalue, and instead yield the average eigenvalue. Can the authors clarify?\n- In the real world experiments, what does \"Lasso\" correspond to? What does \"L1 norm penalty on the coefficients in the\npolynomial representation\" mean here; what are the polynomials?\nHow is $\\lambda$ chosen for SP in this experiment? It seems that it is not tuned for other methods, so it should be clear that it's a vanilla choice here too.\n- The labels of some plots are of low quality (Fig 7 ylabel and xlabel for example). matplotlib can be configured to use latex.\n\n## Literature\nThe paper puts on the same level the Lasso (a statistical estimator) and FISTA (an optimization algorithm, suited amongst others to solving the Lasso minimization problem).\nSimilarly, suggesting that the Lasso objective \"can be efficiently solved by gradient descent\" is inexact, to say the least: 1) Gradient descent cannot be used, because of the non-differentiability of the L1 norm along the axes. 2) *sub*gradient descent could be used, but it performs very poorly and cannot be called \"efficient\", with a convergence rate in $1 / \\sqrt{k}$.\n\n## Typos\n- In equation 19 $\\mu$ should be $\\mu^2$\n- In equation 20 $\\Vert \\theta - \\theta^* \\Vert$ should be squared\n- There are multiple useless parentheses that make the reading harder than it should, eg around the sqrt in 62, around the gradient in 48, and others.\n\n\n## Formulations\n- Some sentences/formulations seem somehow off, e.g. \"ML models are being used\" > ML models are used?\nRunning Grammarly on the paper may easily fix a lot of these.\n- I couldn't understand \"and which nonlinear function classes are often implicitly biased towards learning.\"\n- positively correlated with the $\\theta - \\theta^*$\n- each with an equal coefficients\n- The authors use $(\\nabla) R$ to denote the subgradient; using $\\partial R$ (and without parenthesis) is more standard in the optimization literature. In proposition 1, this is not the subgradient, this is the subdifferential.\n- Before eq 52, \"Finally, using the convexity of\": I see the dual representation of the L1 norm rather than its convexity.\n", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "hJ4gMlE0AH", "reviewer": "Reviewer_QbBF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nI believe the paper is technically sound and, despite the strong claim of the title with respect to the actual results, provide an interesting perspective on learning boolean functions under a sparse hypothesis.\n\n**Strenghts**\n\n- The proofs seem correct.\n- The theoretical analysis under QG is interesting.\n\n**Weaknesses**\n\n- The paper does not a very good job at comparing the guarantees obtained for spectral regularizatin w.r.t for instance the Lasso.\n- The authors recognize themselves that the bounds might not be really practical, but I would say that this is not the first paper in this type of work having this shortcoming...", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper show that $\\ell^1$-regularizing the so-called spectral representation helps to to learn (pseudo)-Boolean functions.\nMore precisely, the authors provide some theoretical results indicating that under the quadratic growth, this allows to find an (approximate) stationary point with $\\sqrt{kd/n}$ error with high probability. This is also shown empirically on examples.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please use \\citep and \\citet properly.\n- The condition on $\\lambda$ (big enough) is sound, but don't you risk to have for instance a solution reduced to 0 in the linear case if you do not control how big $\\lambda$ (or $C_0$) grows?\n- I would like to see a discussion on a the computational cost of MSE+SP w.r.t. to using for instance the Lasso.\n- What do you mean by \"empirical lower bound\" in the description of Fig 2? Do you meant the minimal value achieved in the expriments? It is not perfectly clear for me how to use this information to derive a \"true\" lower bound.\n- I don't undertand \"specific path of regularization parameter \\lambda\". In my mind, the regularization path is the map $\\lambda \\mapsto argmin (OBJ)$ (where argmin should be better defined). Do you mean a particular trajectory of this potential multivalued map?\n- In your source code, you should check if the directory are created, I had to manually use mkdir to be able to run your experiments.\n- Assumption 2 should read $-\\mu I \\preceq \\nabla^2 f_{\\theta(x)} \\preceq \\mu I$.\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "B1Lng5l2Cy", "reviewer": "Reviewer_HJac", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- The paper is globally clear and well written\n- The topic is of interest to the TMLR community\n\n\n**Weaknesses**\n- It is not entirely clear to me how the presented analysis (especially that of Theorem 1) differs from that of LASSO, or already known techniques. In particular, it seems that Assumption 1(a) somehow allows to shortcut the difficulty of considering models beyond the linear setting. Further, the authors do not present any other setting in which the assumption is satisfied. I feel it would be necessary to come up with other examples of interest to showcase that the presented analysis truly goes beyond the linear setting.\n- I read the discussion in Appendix C but really do not appreciate the wording \"for a sufficiently large $C_{0/1}$\". If they can be set explicitly to 10, I feel it should be done. In the current version, it is not clear whether these constants are the same or not from one proposition to the other. More importantly, it suggests that we can take $\\lambda$ in Theorem 1 as big as we wish and the result would still hold, which I assume is wrong. This inaccuracy is easy to clarify by expliciting the values.\n- Regarding Theorem 2, could the authors provide some examples of algorithms satisfying Definition 3 with the required $\\Delta$? Also, how come $\\Delta$ does not play any role in the bound (13)? I feel constants should be handled more carefully here to highlight the dependencies. Also, (13) does not depend on the confidence level $\\delta$ nor the variance $\\sigma$, is it expected? The $1/2$ seems not necessary if authors use $\\lesssim$. I encourage the authors to proof read the statement of Theorem 2.\n- The lower bound (Theorem 3) is in expectation. Also, it could be beneficial if the authors could provide some intuition about its construction.\n- Have the authors tried to empirically test the lower bound?\n- In the Appendix, the authors refer many times to some event $\\cal{E}_1$, which I could not find defined/introduced. Please clarify this.\n\n\n**Minor comments**\n- use \\citep to put references between parenthesis when it is not part of the sentence\n- p.3 paragraph \"Problem statement\": instead of assuming the existence of $\\cal{F}$, let $\\cal{F}$ and assume the existence of some $\\theta^* \\in \\mathbb{R}^m$ such that labels are generated...\n- use \"with probability greater / at least $1-\\delta$\" instead of \"probability $\\ge$\"\n- $f_\\theta$ instead of $g_\\theta$ in Lemma 1?\n- $\\mu^2$ and not $\\mu$ in eq. (19)\n- $2L^2 2^d \\\\|\\hat{\\theta} - \\theta^*\\\\|_2^2$ in eq. (20)\n- Hoeffding's inequality if for bounded r.v., what is used for eq. (42) is more the concentration of subGaussian r.v.\n- Between eq. (73) and (74), $\\lambda / \\sqrt{2^d}$ is missing twice in the definition of $R(\\theta)$\n- Proposition 1: **in** the Cartesian product", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors analyze the learning of pseudo-Boolean functions, i.e., decision functions from $\\\\{-1, 1\\\\}^d\\rightarrow \\mathbb{R}$. The latter are known to admit a polynomial representation, whose associated coefficients have been empirically shown to be sparse. The authors thus analyze the statistical properties of the minimizers of the empirical mean squared error, penalized with the $\\ell_1$ norm of the coefficients. Under some curvature (Assumption 1(a)) and smoothness (Assumptions 2, 3) conditions, the authors show that for a suitably chosen regularization parameter any first order stationary point of the regularized objective is close to the ground truth one (Theorem 1). The authors then relax the curvature assumption into Assumption 1.(b), but consider the more demanding $\\Delta$ first order stationary interpolators (Definition 3). The latter have similar guarantees in this relaxed setting (Theorem 2). A lower bound in expectation is also presented (Theorem 3), and experiments carried out in Section 5.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses above", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "hKOUwhabhw", "reviewer": "Reviewer_hciS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n\n- The theoretical analysis shows that the stationary point of the regularized objective is closed to the groundtruth. An interesting property is that the upper bound depends on the sparsity parameter $k$, which shows the effect of spectral regularization to capture sparsity.\n\n- Lower bounds are also given, which match the upper bounds and therefore show the optimality of the analysis.\n\n- The paper is well written. The analysis seems to be rigorous. The experimental analysis is comprehensive.\n\n**Weakness**\n\n- Both the restricted secant inequality and the quadratic growth (QG) condition are stated for the reference point $\\theta^*$, which is the groundtruth. It seems that these assumptions are stronger than the assumptions in the literature. For example, in [1], the QG assumption says $f(x)-\\inf_xf(x)\\geq \\mu\\|x-x_p\\|^2$ , where $x_p$ is the projection of $x$ to the set of optimal solutions. That is, the QG assumption in [1] requires the distance to the optimal solution set is bounded by the excess function value. This paper instead considers the distance to $\\theta^*$, which is a stronger assumption. Furthermore, the paper does not give a specific example which satisfies these assumptions.\n\n- $n_0$  in Thm 1 scales as $(d^3+dk)/C_{n,\\delta}^*$. This assumption can be restrictive in high-dimensional settings. This is especially the case if $C_{n,\\delta}^*$ is small.\n\n- In the proof of Theorem 3, the authors assume $n\\geq d2^{d+3}$. It seems this is a restrictive assumption is $d$ is moderate.\n\n[1]  Karimi, Hamed, Julie Nutini, and Mark Schmidt. \"Linear convergence of gradient and proximal-gradient methods under the polyak-lojasiewicz condition.\" ECML 2016", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the problem of learning pseudo-Boolean functions via spectral regularization. While most studies on this topic consider algorithm design and applications, the paper considers theoretical analysis to show the accuracy gain of spectral regularization in learning pseudo-Boolean functions. Under a restricted secant inequality on the empirical error, the paper shows that stationary points approximate the global model as measured by the Euclidean distance. The paper further extends this result to an approximate first-order stationary interpolator under a weaker quadratic growth condition. Experimental results are also given to verify the effectiveness of spectral regularization and the theoretical statements.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- I would request the authors to give more discussion on the restricted secant inequality and QG condition to justify these assumptions in the setting of learning pseudo-Boolean functions.\n\n- Definition 1: it seems that $\\langle \\nabla g(z),z^*-z\\rangle$ should be $\\langle \\nabla g(z),z-z^*\\rangle$\n\n- The authors should use *\\\\citep* instead of *\\\\citet* when the reference is not a part of the sentence\n\n- Section 1: \"a new generalization bounds\"\n\n- Section 1: \"demonstrations on ... complements\"\n\n- Below Thm 3: \"a permutations\"\n\n- End of section 4: \"is also be\"\n\n- In the proof of Lemma 1 and Lemma 6, the authors use $g_\\theta$. It seems that they should be $f_\\theta$\n\n- Eq (19): $2\\mu$ should be $2\\mu^2$\n\n- Eq (20): $\\|\\hat{\\theta}  -\\theta^\\star\\|_2$ should be    $\\| \\hat{\\theta} - \\theta^\\star\\|_2^2$\n\n- Eq (25): $C^*_{n,\\delta}/2$ should be $C^*_{n,\\delta}$\n\n- Below eq (57): \"Plugging this in,\"\n\n- It would be nice if the authors can give a reference for Proposition 1\n\n- Eq (107): \".\" should be \",\" ", "broader_impact_concerns": "I do not see any concern on broader impacts", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "yjaKzjOBBf", "reviewer": "Reviewer_EH8r", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Here are the strengths and weaknesses that I assessed; I added a paragraph with additional remarks that I have for the authors at the end.\n\nStrengths:\n\n- The presentation of the paper is good, the research questions are clearly stated in the introduction as well as in the experiments section.\n- The mathematical details are sound.\n- The theoretical contributions shed light on an open problem: generalization properties of the spectral regularization scheme for learning pseudo-boolean functions.\n- The theoretical assumptions are not only there to provide some bounds, they are numerically checked, especially the critical quantity $C_{n,\\delta}^\\star$. Related to this, the discussion in the paragraph \"Extensions to cases with multiple local minima\" is invaluable and shows that a special care was given to this aspect of the work (having realistic assumptions).\n- The experiments section is convincing.\n- Some python code is provided.\n\nWeaknesses:\n- The influence of some of the quantities in the bounds is not discussed, especially $C_0$ and $C_1$ in Theorem 1. I could not understand where the $C_1$ quantity was coming from in the proofs.\n- The guarantees hold for a specific path of regularization parameter $\\lambda$ that depends on the (unknown) level of noise in the statistical model. This is classical in Lasso-related papers, but could have been discussed.\n\nAdditional remarks:\n\n- QG is presented as weaker than RSI, and while I agree that this holds true for functions with Lipschitz continuous gradients, given that the loss function used is the square loss, one can say that the Lipschitz constant of the gradient of $\\mathrm{Err}_n(\\theta, \\theta^\\star)$ scales as the Lipschitz constant of the overall neural network. Lipschitz constants associated to neural networks are known to explode quite fast, so that in practice even if a function is RSI(C), the quantity 2C/L might be very small. Could the authors comment on that ? \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a theoretical analysis of a Lasso-like type of regularization aiming at finding sparse representations of pseudo-boolean functions learned through empirical risk minimization. This so called spectral regularization is computed via the Walsh-Hadamard transform, and coincides in the linear model setting with the classical Lasso regularization term.\n\nThe statistical analysis of the resulting estimator is mainly divided in two parts corresponding to two different assumptions on the behavior of the MSE of the learned function compared to the ground truth, denoted by $\\mathrm{Err}_n(\\theta, \\theta^\\star)$, in addition to regularity assumptions on the model class $\\mathcal{F}$ (namely Lipschitz continuous gradients of the evaluations w.r.t. the parameter, and bounded average gradient norm at $\\theta^\\star$).\n\n- In the first part of the analysis, $\\mathrm{Err}_n(\\theta, \\theta^\\star)$ is assumed to satisfy a restricted secant inequality (RSI, extended notion of convexity), and Theorem 1 ensures that with high probability the estimated parameter converges in 2-norm to the ground truth parameter in the class. The proposed convergence rate scales as $\\mathcal{O}(\\frac{1}{\\sqrt{n}})$ in terms of the number of samples, with constants involving information about the problem.\n\n- In the second part, the RSI assumption is traded against a quadratic growth condition (QGC) on $\\mathrm{Err}_n(\\theta, \\theta^\\star)$, which does not inform about the correlation between the gradients of $\\mathrm{Err}_n(\\theta, \\theta^\\star)$ and $\\theta - \\theta^\\star$ anymore. To alleviate this difficulty the concept of first-order interpolators is introduced, and under these new assumptions Theorem 2 proposes again a convergence rate in high probability scaling as $\\mathcal{O}(\\frac{1}{\\sqrt{n}})$.\n\nTo complete this analysis, a lower bound result under the aforementioned assumptions is derived, showing statistical optimality with respect to the $\\mathcal{O}(\\frac{1}{\\sqrt{n}})$ scaling.\n\nA coherent empirical study is proposed, illustrating the interest of the spectral regularization scheme on both simulated and real data. The study goes beyond showing improvements in generalization accuracy, by exploring numerically the assumptions used in the theoretical derivations.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Below are a few suggestions for adjustments, decreasingly ordered in terms of criticality.\n\n- Plots in Figure 2 and 7 need to be extracted in better quality. The labels are barely readable.\n\n- In assumption 2, it may be of interest to introduce the constant $\\mu$ at the beginning of the sentence, as this constant should exist independently of all $x \\in \\mathbf{X}$. Here this does not cause real issues as $\\mathbf{X}$ is discrete, but it would be cleaner.\n\n- The proofs section organisation could be improved. Section B is supposed to be dedicated to proving Theorem 2, yet section B.1 presents the proof of Theorem 3. A suggestion would be: B) Technical lemmas C) Proof of Theorem 1 (through Theorem 5) D) Proof of Theorem 2 (through Theorem 4) E) Proof of Theorem 3. Generally speaking, it is better to not refer to some unannonced Lemma presented further down in another section as it makes the reading difficult. Also, for completion, the proof of Lemma 8 is missing.\n\n- The proofs often suggest to \"plug something into Lemma Y\", it would be better if the equations were refered to instead of the lemmas. Example: the LHS of Lemma 6 is Eq (97). Proposition 1 could also be made a lemma to unify the environments used.\n\n- I would have prefered having access to the related work section higher in the paper, between sections 2 and 3 - although I do not know how much it speaks of my personal tastes rather than some objective efficiency.", "broader_impact_concerns": "Does not apply here.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the learnability of pseudo-boolean functions under a structural assumption that its Fourier transform is sparse. The resulting regularized empirical objective is shown to have tractable properties under mild assumptions, both theoretically and through experiments. 
Reviewers agreed that this paper is technically sound and provides an appealing perspective on the benefits of spectral regularisation via sparsity-inducing norms. They also acknowledge that the authors have taken the reviewers feedback into account to produce a much improved version. 
Decision: Accept (poster)