The Power of Random Features and the Limits of Distribution-Free Gradient Descent
Authors: Ari Karchmer
Eran Malach
Venue: ICML 2025 poster (2025)
Keywords: gradient descent
distribution-free
random features
statistical queries
Primary area: theory->learning_theory
TL;DR: We prove that if a function class is learnable in a distribution-free manner by gradient descent, then most functions in the class must have a relatively simple random feature representation.

Abstract: We study the relationship between gradient-based optimization of parametric models (e.g., neural networks) and optimization of linear combinations of random features. Our main result shows that if a parametric model can be learned using mini-batch stochastic gradient descent (bSGD) without making assumptions about the data distribution, then with high probability, the target function can also be approximated using a polynomial-sized combination of random features. The size of this combination depends on the number of gradient steps and numerical precision used in the bSGD process. This finding reveals fundamental limitations of distribution-free learning in neural networks trained by gradient descent, highlighting why making assumptions about data distributions is often crucial in practice.
Along the way, we also introduce a new theoretical framework called average probabilistic dimension complexity (adc), which extends the probabilistic dimension complexity developed by Kamath et al. (2020). We prove that adc has a polynomial relationship with statistical query dimension, and use this relationship to demonstrate an infinite separation between adc and standard dimension complexity.

The Power of Random Features and the Limits of Distribution-Free Gradient Descent
Ari Karchmer' Eran Malach
Abstract
oretical studies the goal of distribution-fre learning. In distribution-Fie learning, the goal is to design algorithms that can learn target function f from a class JF without making strong assumptions about the distribution of the input examples. Specifically, let be arbitrary distribu- tion over the input domain, and let (z, f()) be an example drawn from p. distribution-free learning algorithm must succeed in approximating f for any choice of p. This stands in contrast to distribution-specciie learning, where the al- gorithm is designed with prior knowledge about the input distribution, often leading more efficient and practical solutions. While distribution-free learning is desirable goal, it is often computationally challenging, as it requires the algorithm to handle worst-case scenarios.
We study the relationship between gradient-based optimization of parametric models (e.g., neural networks) and optimization linear combina- tions of random features. Our main result shows that if parametric model be learned using mini-batch stochastic gradient descent (bSGD) without making assumptions about the data distri- bution, then with high probability, the target func- tion can also be approximated using polynomial- sized combination of random features. The size of this combination depends on the number of gradient steps and numerical precision used in the hSGD process. This finding reveals fundamental limitations of distribution-fii free learning in neural networks trained by gradient descent, highlighting why making assumptions about data distributions is often crucial in practice. Along the way, we also introduce a new theoretical framework called average probabilistic dimension complexity (ade). which extends the probabilistic dimension plexity developed by Kamath et al. (2020). We prove that adc has polynomial relationship with statistical query dimension, and use this relation- ship to demonstrate an infinite separation between ade and standard dimension complexity.
This work, in a nutshell. In this work, we discover a surprising relationship between distribution free learning with gradient descent over differentiable parametric model classes and random feature representations. Informally speaking, show the following implication. Let J be class of target functions. Assume that a differentiable parametric model class can be successfully optimized in a distribution-free manner by mini-batch gradient descent to approximate all f E F. Let μ be a target distribution over F. Then, with high probability over f ~ μu, f can be approximated by linear combination of random features. Importantly, the number of random features necessary to include in this linear combination is upper bounded by polynomial function of the number of optimization steps of gradient descent.
1. Introduction
Theoretically, learning neural networks is computationally hard in the worst case. However, the practice of modern deep learning has demonstrated the remarkable power of gradient-based optimization of neural networks. Why does gradient descent over neural networks work so well in prac- tice, despite theoretical pessimism? A full answer to this question is still missing in the science of deep learning.
This result, as stated, sounds like a very strong positive result: could we now replace SGD on complex networks with optimization of simpler random features model? This the positive interpretation of the result. However, know that random features are limited in their expressive power. So, another (and we believe better) way to understand this result is as a statement on the limitation of distribution-free SGD. Indeed, our result, more formally described on the next page, reveals fundamental limitation of distribution- free learning:
One possible source of the computational hardness in the-
Harvard University, Cambridge, Massachusetts, USA. Corre- spondence to: Ari Karchmer <akarchmero@@ goail.com>>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
a function class is learnable in a distribution- free manner by gradient descent, then most func-

---

The Power of Random Features and the Limits of Distribution-Free Gradient Descent
tions in the class must have a relatively simple random feature representation.
unlabeled data in a domain X, according an unknown
example distribution p. and labels the data with values in
{=1}, according target function f X + {+13.
This limitation has a clear connection to the practice of deep learning, as we discuss next. Specifically, our result provides theoretical foundation for the observation that distributional assumptions are crucial for the success of gradient-based optimization.
Roughly, our main result is the following. Let F be a class of target functions and let A (X) be the set of distributions over domain X. Suppose it is possible to distribution-fres learn an accurate model fw E H. for some unknown source distribution f,, E {D : f F, E A(X)) (with re- spect to squared loss, for any f and p) by mini-batch SGD with parameters T, c,p. Then, given any prior distribution I over F, there exists random feature distribution & such that:
The theoretical value of this result. A common finding in the practice of Machine Learning is that making appropriate distributional assumptions often leads to dramatically better learning outcomes. For example, it has been shown both empirically and theoretically that, when examples are drawn from the uniform distribution, learning parity functions- Boolean functions that compute the parity (XOR) of a subset of input bits cats-canhhe be extremely diffieult for gradient descent on neural networks. However, the same task becomes much easier under biased product distributions over the input do- main (see e.g., Malach & Shalev-Shwartz (2019)).
For random features Φ1 ... Qd ~ E, there exists a weight vector such that
f
under 0/1 loss with respect to p. with probability 99/100 (over μ)).
Parity functions are a comerstone of computational learn- ing theory due to the fact that, despite their simplicity, they exhibit exponential hardness under many learning frame- works (e.g., statistical queries and random features). Parity functions are also useful as informative special cases when studying difficult topics in deep learning theory. For exam- ple. parity functions have been recently used to study length complexity of chain-of-thouu thothugh in autoregressive models (Malach, 2023), hidden progress in gradient descent (Barak al., 2022), and pareto frontiers in width, initialization and computation of gradient descent (Edelman et al., 2023).
It holds that S poly (Tpcc.
Here, T' is the number of clipped mini-batch gradient up- dates, p is the number of parameters in the differentiable model, E (0, 1] controls the granularity of the mini-batch gradient estimates. We note that the batch size must satisfy certain a lower bound roughly polylogarithmic in Tp (for constant c).
At the end of the technical overview (section 3), we state the main theorem in full mathematical formality as Theorem 3.3.
In contrast, our result helps explain the phenomenon, instead of just demonstrating it for the case of learning parity func- tions. We bring to light the fact that distribution-fres learn- ing with gradient descent essentially "collapses" to learning linear combinations of random features, in the average case. To ground this in the specific case of parity functions, we comment that random parities are well known to be compu- tationally hard to learn using linear combinations of random features (even in the average case). Thus, our result provides a consistent explanation for why distribution-ffee learning of parities with gradient descent is hard, in terms of the well- known hardness of learning parities with random features. Again, note that random parities are not hard to learn with gradient descent in the distribution-specife case.
Techniques and further contributions. To prove the main theorem, a series of transformations between different learning paradigms and complexity measures.
First we use transformation from bSGD algorithms (with a certain maximum precision -these can be thought of as noisy gradients) to statistical query (SQ) learning methods, which was proved by Abbe et al. (2021). This allows us to then relate poly(Tp), a polynomial function of the product of parameters and bSGD steps, to the statistical query dimension of the class of target functions that label the source distribu- tion. This is done using the characterization of Blum et al. (1994).
Main theorem in more detail. Let us now describe the main theorem contributed by this work in more detail. We consider a differentiable parametric hypothesis class H. which has p parameters w = (wl wp)) E I²' and a bounded output range. Let fw be the function in H corre-
Following this, we use ideas from communication com- plexity, particularly those related to discrepancy and the 2- 2-party norm of a function, to relate statistical query dimension to the probability of being able to weakly
sponding to parameters set to w. Suppose that data is gener- ated according to a source distribution D Di which samples
2

---

The Power of Random Features and the Limits of Distribution-Free Gradient Descent
approximate a source distribution by sampling a sin- gle random feature (we call this the Random Feature lemma). This step employs new mathematical tech- niques that resemble the circuit learning algorithms of Karchmer (2024a:b).
these parameters effectively changes the weight on the bot- tom layer, Wi, by by tiny amount (Chizat et al., 2019). This means that when gradient descent for small bounded number of steps is used to learn R, essentially, the bottom layers could have remained fixed after random initialization. Thus, in this case, learning the overparameterized network is effectively the same as learning the linear combination of some random features of the form o ((w,, +b,). for which known techniques suffice to prove optimal convergence. All in all, this allows Andoni et al. (2014); Daniely (2017); Du et al. (2018; 2019); Li & Liang (2018); Allen-Zhu et al. (2019) (among others) to derive provable guarantees for learning overparameterized neural networks by analyzing them as one would analyze linear learning with random features (LLRF).
Next, we also introduce new technique that uses boosting techniques, such as Adaboost (Freund & Schapire, 1997: Domingo et al., 2000), as construc- tive proofs of the fact that we can combine these weak approximators into a strong approximator: linear combination of relatively small number of random features.
Along the way, we introduce a new notion of dimension complexity called average probabilistic dimension complex- ity. This notion relaxes both the standard notion (Ben-David et al., 2002), and the probabilistic notion (Kamath et al., 2020). Average probabilistic dimension complexity pre- cisely captures the quantity of interest in this paper: the number of features needed approximate a given function class, with high probability, over some prior distribution over the function class. Thus, as further contribution, we give an "infinite" separation between average probabilistic dimension complexity, and standard dimension complex- ity. Previously, only an exponential separation was known between the intermediate notion, probabilistic dimension complexity, and standard dimension complexity, from Ka- math et al. (2020). Kamath et al. (2020) highlighted as an open problem to resolve whether or not infinite separa- tion exists between probabilistic and standard dimension complexity. Our relaxed notion of average probabilistic dimension complexity is sufficient for an aftirmative reso- lution, but we also show that there may exist complexity- theoretic barriers to demonstrating that our relaxed notion is necessary for the separation.
It is worth mentioning that the Neural Tangent Kernel (NTK, Jacot et al. (2018)) is a bit more subtle. The NTK approach goes beyond considering the features of the top layer. In- stead, NTK constructs a kernel matrix where each entry represents the dot product between the gradients of the net- work output with respect to the parameters, evaluated at two different data points. This kernel matrix effectively encodes the similarity between data points in the high-dimensional gradient feature space (the feature map representation is the gradient of the neural net with respect to the model parameters at a certain training point).
The main difference between this line of work and ours is that we show the collapse of the learning capabilities of distribution frree gradient descent, while the above line work connection to LLRF illustrate how gradient descent can learn.
3. Technical Overview and Theorem Statements
In this section we introduce and formally define the relevant technical settings, and finish with full statements of our main theorem and other results. After that, we provide a bird's eye view of our path to proving the main theorem.
2. Related Work
Many related works analyze the relationship between gra- dient descent on wide neural networks and linear learning with random features (LLRF). Much of this line of work is based on the following idea, which we now illustrate using a simple one-layer neural network:
Let F be a class of target concepts f : X - [=1}. Let D Dj, E Dz= (D, I E F,P E A(X)) be a source distribution which samples unlabeled data in a domain X, according to an example distribution over domain X, and labels the data according to some f feF. F. We consider generally speaking learning functions f: - (+1) over an input space X, with the objective of minimizing the population loss:
d R(x) Σ 1: (io((wa,a) + b:)
(1)
The d neurons are identified by their weights w; and bias by. a is an activation function, and the top layer applies linear combination by weights u,
C (f) & E(r.y)D,,,, [(f(2)) y)]
with respect to source distribution Dj over X x {+1}, where& é: R x {+1} - Rzo is a loss function.
When d is really large and the weights are randomly initial- ized, it can be shown that applying gradient descent over
In this work, we take the loss function to be either the
3

---

The Power of Random Features and the Limits of Distribution-Fres Gradient Descent
squared-loss: ( (Ū. y) - or 0-1 loss: for (ú. v) [ū + v)- We write Con and Lan to denote population loss.
internal randomness and all prior statistical queries o, for < t. The algorithm A ensures distribution-free e-accuracy if for any source distribution Dr,p E Dz, h <- A satisfies E (sup (h)) I e, where the supremum is taken over all valid responses wt to each query Φt, which are those that satisfy | [x, y)] m/l S т. The expectation is taken over the internal randomness of A.
3.1. Learning Paradigms
In this work, we consider learning of differentiable paramet- ric hypothesis classes such feed-forward neural networks. A p-parameter differentiable model w (Wi,-- (.01.".ppp)))) -Up) is function fw X'' + [-1, 1], and for every x E X there is gradient V (x)) on almost every w E RR (not in- cluding sets of measure 0). Note the bounded range of the mode. We say that H. is differentiable parametric hypoth- esis class with p parameters if every H is written as a differentiable model with p parameters.
If statistical query responses have some maximum degree of precision (i.e., 1/2 E [-1,1] is an integer multiple of E (0, 1)), then a statistical query & X + [-1, can be converted into series of t = log( (1/c) statistical queries + ... $, X - {=1} (note the Boolean range). This is done by asking individually for the expected value of each bit in the bit representation, and applying linearity to reconstruct the total expectation.
Mini-batch stochastic gradient descent. We consider learning of differentiable parametric hypothesis classes by mini-batch stochastic gradient descent (bSGD). Our setting is the same as Abbe et al. (2021) and we adopt some of their notation and their definitions.
Complexity of linear learning with random features. Kamath et al. (2020) introduced a probabilistic variant of dimension complexity Ben-David et al. (2002) to in order to study the complexity of optimizing a linear combination over random features to fit source distribution.
For a differentiable fw. an initial distribution W over RP, gradient precision e E (0, mini-batch size b, and stepsize y, the bSGD paradigm iteratively com- putes new parametric models at timestep t defined by ((0) ~ W and w((++1) + -w(() - 79t- For a mini batch B3 ~ p²,the the function Ji is the c-approximate clipped gra- dient (fg,(fw)) _ EE=ilVe (V (fwo))) where [-]1 de- notes the entry-wise clipping over values to the interval 1.. The clipped gradient in [-1, 1]2 is a c-approximate rounding if each entry of the the clipped gradient is an inte- ger multiple of c and ||9. Vlg.(fwo) )o S 3c/4.
Let H be a hypothesis class consisting of functions of the form h X + E. and é be an implicit loss function (to be stated explicitly in context).
Definition 3.1 (Probabilistic dimension complexity). The quantity (7t) is the smallest positive integer d such that there exists a distribution & over feature maps Φb : X - Rd. such that for every P over X, and every h E H.
inf Dt. ((w, .0)) Se WERd
E 3
(2)
We say that a learning algorithm A is bSGD(TT, c, p) method for differentiable parametric hypothesis class with parameters if works by computed bSGD for T updates on the p-parameter differentiable model, with e-approximate gradient clipping and batch size b, and beginning from initialization distribution W. The algorithm A ensures distribution-free e-accuracy if for any source distribution
We use the notation (w, o) to denote the function defined (w, (x) = Σ wio(x);
Clearly. showing an upper bound on the probabilistic dimen- sion complexity d of a hypothesis class is sufficient to reduce learning source distribution to learning the optimal linear combination over the d-dimensional feature map implied by the upper bound.
Dj.e Dy, fwi) < A satisfies E [sup CPr. (Pt.)(wwo)) (f] The expectation is taken over the random initialization of fw))) and the selections of the mini-batches. The supremum is taken over all valid c-approximate gradient clippings.
Complexity of linear learning with random features and prior. We introduce an average-case analogue of prob- abilistic dimension complexity. Let é be an implicit loss function (to be stated explicitly in context).
We refer the reader to section of Abbe et al. (2021) for discussion on some of the modelling/design choices taken in defining the bSGD model.
Definition 3.2 (Average probabilistic dimension complex- ity). The quantity adc,,s given a prior distribution over a hypothesis class H. is the smallest positive integer d such that there exists a distribution E over embeddings & : X + Rd such that
Statistical query learning and SQ dimension. We con- sider statistical query learning. A learning algorithm A is said to be SQ(k, 7) method if in & iterations, it produces a statistical query de X {+1} + [-1, at iteration t, which then gets a response U, from an oracle, and then after & iterations outputs a candidate hypothesis f f + RR. Each successive statistical query di is allowed to depend on
Pr kop
Vp:
E 3ng
inf L (h, (w, Ui) wERRd"
S6 2 1-8
4

---

The Power of Random Features and the Limits of Distribution-Fri Free Gradient Descent
Clearly, showing an upper bound on the average probabiliis- tic dimension complexity d of hypothesis class is sufficient to reduce learning source distribution to learning the linear combination over the d' d-dimensional feature map implied by the upper bound, which is optimal for a large probability mass of H.
borrow from the work of Abbe al. (2021). They show in Theorem 1a of their paper that (distribution-free) PAC- learning algorithms can be simulated by (distribution-free) bSGD algorithmss, when allowed fine enough gradient pre- cision c. Specifically, when c < 1 /8b. Using this theorem, it follows that for b, c such that c < 1/8b, then bSGD can learn parities in the distribution- free case. From here, we can conclude that our transformation from bSGD to random features cannot hold for b, c such that 1/8b, since the size of the implied random feature representation would violate SQ dimension lower bounds for parities.
We discuss at length the motivation of average probabilis- tic dimension complexity in the context of the dimension complexity literature in the Appendix, Section B.
3.2. Main Theorem Statement
We can now state our main theorem, which demonstrates that, with respect to any prior distribution μt, the learnability of a large probability mass of data generating source distri- butions that are efficiently accurately learnable by bSGD, could potentially be analyzed as efficiently accurately learn- able by the LLRF method.
3.3. Technical Tools
Now, we define some technical concepts, theorems, and quantities of interest that are useful in proving our results. Using those, we will then outline the path we will take to prove Theorem 3.3 via modular proof of the theorem.
Let Let p, p E Z. c (0, 1] be such that bc 2 (log Tp/ Let H be differentiable parametric hypothesis class, where each model fw X - [-1, 1] has parameters (w.)... Wp)) Let F be class of target concepts f X -> {+1]. Let Dro E D,= {D : f E F,P& E A(X)) be a source distribution which samples unlabeled data x in a domain X, according to an example distribution p. and labels the data according to some f E F. Let y be a prior distribution over F.
Relation Between SQ-Learning and bSGD. Abbe et al. (2021) show that SQ-learning is as powerful as bSGD meth- ods in the following sense.
Theorem 3.4 (Thm Ic. of Abbe et al. (2021)). Let l(ū. y) 1\ (0 y)². Let T, b, E C. C (0, 1] be such that be Z 2(log Tp/5). For every learning algorithm ALSOD that is bSGD c, b.p) p) method, there exists learning algorithm Asq which is SQ(Tp, c/8)) method, such that for every source distribution Dj,0-
Define (A,,A A inf, E |suph-- (Prw (h)] S sc]. That is, the infimum over e such that the algorithm A ensures distribution-fiee e-accuracy on Dy. where the expectation is over the random initialization of the differentiable model and the mini-batches. distribution-free e-accuracy on Dro measured with respect to some loss function eº Let (2 (ū. v)- (ū 3) Let fbr (ū.v) v) 1 + v). Theorem 3.3 (Main theorem). Suppose there exists learn- ing algorithm ALsGD that is a bSGD e, b, method, and Crr( (AASGD p.p)) I 1/10 for every source distribu- tion DT E Dy with respect to l2g. Then, there exists positive integer d S poly(Tp/e) 2 such that there exists a distribution E over embeddings o X + Rd, such that for arbitrarily small constants c, 6.8%
crr(Asq, Dj.)) S CrT(AD Dr +
In words, this theorem says that when setting batch-size and gradient precision appropriately, mini-batch SGD algo- rithms can be converted into SQ-learning algorithms that suffer only a small additive loss of accuracy, and the number of statistical queries is the product of the number of batch gradient updates and the size of the differentiable model.
SQ-learning Characterized by SQ dimension. The com- plexity of SQ-learning itself can also be captured by simple combinatorial parameter called the SQ dimension (see Blum et al. (1994)). Consider now a function X + {+1} over a finite domain X. A hypothesis class H set of hypotheses h: X + {+1).
Pr Vp: homp
inf Dr ((r oi)) se 3621-0
WERd
In other words, for any prior distribution i over F, adc,,s(u) S popy(T)/c²).
Definition 3.5 (Statistical query dimension). Let p be a distribution over domain X. The statistical query dimension over P of H. denoted sq(H,, p). is the largest number d such that there exists d functions fi. H. that satisfy, for all i } j:
A Note on Gradient Precision. It is worth mentioning that a result analogous to the above theorem, but for gradi- ent descent with arbitrarily fine precision, is not possible. Indeed, our theorem would not hold if there were no restric- tion on the precision of the gradients. To see this, we can
[f( < 'd a~p
E
We define sq(H)= = maxx8q(H4 p).
5

---

The Power of Random Features and the Limits of Distribution-Free Gradient Descent
The relationship between query complexity in the SQ- learning model and SQ dimension proved by Blum et al. (1994) is the following. We state their result using our notation and terminology.
Proef of Theorem 3.3. First, observe that under the condi- tions of Theorem 3.3, Theorem 3.4 implies that for the assumed algorithm ASSGD, which is a bSGD b) method, there exists a learning algorithm Asq which is a (Q(TT,, c/8) method, such that for every source distribu- tion Dspp
Theorem 3.6 (Blum et al. (1994)). Let d = sq(H) and (01 1 + y). If A is a SQ(k,, T) method that is distribution-free 1/2 - T-accurate, then k dr
err(AsQ, Dr,0) I err Dj.p) + 8.
Communication Complexity. Our proofs use as tools many ideas from the theory of communication complexity. We will introduce the necessary notation, definitions and concepts in the Appendix, section D. We refer the reader to Kushilevitz & Nisan (1996) for more of the basics.
Now, by Theorem 3.6, we know that since Asq is a SQ(Tp, e/8) method that distribution-free e + --accuraee then Tp > (dc² (dc2/64 - 1)/2 > 1((d²2,, where sq(F). Rearranging, conclude that d < O(Tp/c²).
We can now invoke Theorem 4.1 to conclude that adc,, (H) S poly(TTp/c²), where adc (p) is with respect to f01.
3.4. Separations Between Dimension Complexities
As a corollary of Theorem 4.1, we make some possible progress towards answering the open question left by Ka- math et al. (2020). We recall their question was whether there exists hypothesis class H. which satisfies for 0/1 loss, and some functions f. N + N. both expressions de(H) E (m)( and (H)) E ((1
Remark. The explicit conclusion of Theorem 3.3 is that with high probability over 14, the source distribution can be e-approximated with respect to 2/ by a linear combination of poly(Tp/c) random features (w, o). This implies that the corresponding learned parametric model fw can also be (c))- aprr)xippp with respect to 2 by a linear combination of (T/y(T random features. This follows from the fact that we are considering source distributions that have a deterministic labelling function and because the learned parametric model fw : X - [-1, has a bounded range, which means that per-sample squared loss is at most 2.
Our result, shows that the answer is yes, if we take ade instead of deç
Corollary 3.7 (Infinite Separation between add and de"). There exists a hypothesis class H. with domain 11 and range {+1], which satisfies for 0/1 loss and any prior dis- tribution over H. and arbitrarily small constant ō > 0:
dc(H)) 20(42)
5. Outline of Proof of Theorem 4.1
(H) E O(1/e).
We present outline of our proof of Theorem 4.1, which we defer in full to the appendix.
This separation follows immediately from Theorem 4.1 and theorem of Sherstov (2008a), which is concerned with the family of Zarankiewicz matrices. We refer to the Appendix section A and B for the details and definition of dc(H)).
(Step 1; Section A.1). We will apply a theorem of Sherstov (2008b), to conclude that statistical query dimension of a function class F controls the reciprocal of the correlation of A (the sign matrix representation of F) and 2-bit 2-party deterministic communication protocols. Here, correlation measure with respect to a product distribution over the rows and columns of A. This induces prior μs over the hypothesis class and distribution p over unlabeled inputs.
4. Modular Proof of Theorem 3.3
To prove Theorem 3.3, we use the relationships introduced in the previous section to reduce our goal proving the following standalone theorem.
Theorem 4.1.
Let FF be a function class, μ a distribution over F, and let consider loi loss. We have:
(Step 2: Section A.2). We will use the results of step I and an analysis inspired by Karchmer (2024b) to show Random Feature lemma. Our Random Feature lemma essentially says that, for every prior μ4, with high probability over target function f ~~ μ., then for every example distribution p. there exists a feature distribu- tion /ffaat over features, such that 1 samples weak approximators for the target function f (with respect
adc,, (M) S (1q(())2101)
where e, 8. are arbitrarily small constants.
We will prove Theorem 4.1 in the next section. For now, we prove Theorem 3.3 assuming Theorem 4.1.
6

---

The Power of Random Features and the Limits of Distribution-Fre Gradient Descent
to p). The predictive accuracy of the weak approxima- tor is 1/2 7 where y is polynomial function of [/s
two layers. Advances in neural information processing systems, 32, 2019.
Alman, and Williams, R. Probabilistic rank and matrix
rigidity, In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 64 641-460166 1-652 2017,
(Step 3; Section A.3). We will employ a new analysis technique, which uses boosting theorems such as Ad- aboost as constructive proofs of the fact that a relatively small linear combination of weakly predictive random features approximate given concept under the prior μ.
Andoni, A., Panigrahy, R., Valiant, G., and Zhang, L. Learn- ing polynomials with neural networks. In International conference on machine learning, pp. 1908-1916. PMLR, 2014.
Arora, S. and Barak, Computational complexity: a mod- ern approach. Cambridge University Press, 2009.
6. Conclusion
Our results show that distribution-fiee gradient-based learn- ing of parametric models collapses optimization of linear combinations of random features, in the average case. This indicates limits the capabilities of neural networks with- out distributional assumptions and explains why tasks such as parity learning remain hard under these conditions. We also introduce average probabilistic dimension complexity (adc), which admits an infinite separation from standard dimension complexity and clarifies the importance of distri- butional assumptions for gradient-based methods.
Barak, B., Edelman, B., Goel, S., Kakade, S., Malach, E., and Zhang, C. Hidden progress in deep learning: Sgd learns parities near the computational limit. Advances in Neural Information Processing Systems, 35:21750- 21764, 2022.
Ben-David, S., Eiron, N., and Simon, H. U. Limitations of learning via embeddings in euclidean half spaces. Journal of Machine Learning Research, 3(Nov):441144) 2002.
Blum, A., Furst, M., Jackson, J., Kearns, M., Mansour, Y., and Rudich, S. Weakly learning dnf and characterizing statistical query learning using fourier analysis. In Pro- ceedings of the twenty-sixth annual ACM symposium on Theory of computing, pp. 253-26332262 1994.
Practical implications. When designing learning algo- rithms, there is often a tension between making them work for all possible distributions (distribution free) versus opti- Our
mizing for expected scenarios (distribution-specinfe) result suggests that pursuing distribution-free guarantees may come at substantial cost in terms of model expres- siveness. This provides theoretical support for the common practice of incorporating domain knowledge and distribu- tional assumptions into model design. What does this imply for the design of future learning algorithms? Our work sug- gests that embracing distributional assumptions may be key to unlocking the full potential of gradient-based optimiza- tion.
Chizat, L., Oyallon, E., and Bach, On lazy training in differentiable programming. Advances in neural informa- tion processing systems, 32, 2019.
Chung, F. R. and Tetali, P. Communication complexity and quasi randomness. SIAM Journal on Discrete Mathemat- ics, 6(1): 10-123, 1993.
Daniely, A. Sgd learns the conjugate kernel class of the network. Advances in neural information processing systems, 30, 2017.
Impact Statement
Domingo, C., Watanabe, O., et al. Madaboost: A modifica- tion of adaboost. In COLT, pp. 180-189, 2000.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Du, S., Lee. J., Li, H., Wang, L., and Zhai, X. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pp. 1675- 1685. PMLR, 2019.
References
Du, S. S., Zhai, X., Poczos, B., and Singh, A. Gradient descent provably optimizes over- aver-parameterized neural networks. arXiv preprint arXiv:1810.02000 2018
Abbe, E., Kamath, P., Malach, E., Sandon, C., and Srebro, N. On the power of differentiable learning versus pac and sq learning. Advances in Neural Information Processing Systems, 34:24340-24351, 2021.
Edelman, B. L., Goel, S., Kakade, S., Malach, E., and Zhang, C. Pareto frontiers in neural feature learning: Data, com- pute, width, and luck. arXiv preprint arXiv:2309.03800, 2023.
Allen -hu, Z. Li, Y., and Liang, Y. Learning and generaliza- tion in overparameterized neural networks, going beyond

---

The Power of Random Features and the Limits of Distribution-Fre Free Gradient Descent
Freund, Y. and Schapire, R. E. A decision-theoretie general- ization of on-line learning and application to boosting- Journal of computer and system sciences, 55(1):119-139 1997.
Jacot, A., Gabriel, F., and Hongler, C. Neural tangent ker- nel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Kamath, P., Montasser, O., and Srebro, N. Approximate is good enough: Probabilistic variants of dimensional and margin complexity. In Conference on Learning Theory, pp. 2262.. PMLR, 2020.
Karbasi, A. and Larsen, K. G. The impossibility of paral- lelizing boosting. In International Conference on Algo- rithmic Learning Theory, pp. 633-653. PMLR, 2024.
Karchmer, A. Agnostic membership query learning with nontrivial savings: New results and techniques. In Inter- national Conference on Algorithmic Learning Theory, pp- 654-682. PMLR, 2024a.
Karchmer, A. Distributional pac-learning from nisan's 's nat- ural proofs. In 15th Innovations Theoretical Com- puter Science Conference (ITCS 2024). Schloss-Dasstuhl- Leibniz Zentrum für Informatik, 2024b.
Kushilevitz, E. and Nisan, N. Communication complexity, 1996.
Li, Y. and Liang, Y. Learning overparameterized neural networks via stochastic gradient descent on structured data. Advances in neural information processing systems, 31, 2018.
Malach, E. Auto-regressive next-token predictors are uni- versal learners. arXiv preprint arXiv:2309.06977 2023.
Malach, E. and Shalev-Shwartz, S. Learning boolean circuits with neural networks. arXiv preprint arXiv: 1910. / 1923, 2019.
Raz, R. The bns-chung criterion for multi-party commu- nication complexity. Computational Complexity, 9(2): 113-122, 2000.
Sherstov, A. A. Communication complexity under product and nonproduct distributions. In 2008 23rd Annual IEEE Conference Computational Complexity, pp. 64-70. IEEE, 2008a.
Sherstov, A. A. Halfspace matrices. Computational Com- plexity, 17:149-178, 2008b.
Viola, E. and Wigderson, A. Norms, xor lemmas, and lower bounds for gf (2) polynomials and multiparty protocols. In -rceny--econd Anmual IEEE Conference on Computa- tional Complexity (CCC'07), pp. 141-154. IEEE, 2007.
8

---

The Power of Random Features and the Limits of Distribution-Fre Free Gradient Descent
A. Proof of Theorem 4.1
In this section we will prove Theorem 4.1.
Notation. In all of the proof, we abuse notation and write sq(4) to denote the statistical query dimension of the function class represented by the sign matrix {=1]1Fix|x] This sign matrix has rows indexed my concepts F, and columns indexed by X. For any function class F, will always write its sign matrix representation simply as A. We will use the notation x) to represent the entry of A at f and column We will also write A(fi-) denote the entire row f. which can be viewed as a table of values of the concept f E F.
We refer to Appendix section D for more preliminaries on the communication complexity used in this section.
A.1. Applying Sherstov's theorem
We make use of a theorem due to Sherstov (2008b). This theorem says that if the statistical query dimension of a sign matrix A is polynomial, then the reciprocal of the discrepancy of A, minimized over product distributions over F x X, is also polynomial.
Theorem A.1 (Sherstov (2008b) Thm. 7.1). Let A E (+11111XXX] be the sign matrix representation of a function class F. We have that:
1
V 2
(Sq(A) S disc x (A)
S 8sq(
Lemma A.2. Let A be a sign matrix. Ifdis"" (A) 2 7; then there exists a 2-bit distributional communication protocol n for over product distributions with correlation 7,. In other words, any product distribution Ç,
E (w.))~
((x:)))((
27
Using Lemma A.2 (see proof in Appendix, section D) and Sherstov's theorem, get the following combined lemma.
Lemma A.3. Let A E [+1] be the sign matrix representation of a function class F. Let Ç ê (n. p) be any product distribution over FF x X, inducing distribution over A. There exists a 2-bit distributional communication protocol for A over Ç with correlation 1/ 1/8sq(A) In other words, for any product distribution S.
IF ()))a
[T((x)
A(J:=)] 2
(3)
(A)
Proof. By Theorem A.1, we know that disc x (A) 2 1/8sq(A)2 Then by Lemma A.2 expression (3) follows.
A.2. Random Feature lemma
can use Lemma A.3 to prove our Random Feature lemma. Our Random Feature lemma essentially says that, for every prior 14, with high probability over ~ μu, then for any example distribution p, there exists feature distribution nz feaat which samples weak predictors for the target function f (with respect p).
We now state the Random Feature lemma.
Lemma A.4 (Random Feature lemma). Let A E (+1) FIx|X| be the sign matrix representation of a hypothesis class F. Let μ be distribution over F. let be 0/1 loss with respect example distribution p, and let 8 >> 0. It holds that, with probability at least - 8 over f ~ for all there exists jefat such that:
Pr flmppe feas
Fot
(f)
1 - -
2 Ω (sq(A))))
Proof. We begin by considering the following procedure.
We will demonstrate that this procedure is a randomized predictor for the unknown target of (which is sampled according to prior 4) on an input point z (which sampled according to example distribution p). In other words, we will show that for

---

The Power of Random Features and the Limits of Distribution- Free Gradient Descent
Algorithm Predict
1: input: point 2; example oracle access to function f ~ μ,, with respect to example distribution p.
2: Sample y ~
3: Sample (z, f(x)) from example oracle.
4: predict: g(2) g(x) f(x)
the unknown target f. it holds that, for an to be defined later:
Pr
Predict(2)= s(=) 2 +
(4)
Snmp.smmpp Pedict
After demonstrating (4), will then (4) to derive the conclusion of the present lemma.
Towards (4). Let A E {+1)1e x|XI be the sign matrix representation of function class F. Let be prior over F, and let be an example distribution over X. We will show that,
Pr famessop
(x) = f(()) 2
2 + O(sq(A)))
Consider the function Eval(r, w), which takes as input random strings r and w, and uses them sample string representation of) μ1 and x P. and then outputs (x)) Recall that by Lemma A.2, there exists 2-bit distributional communication protocol for the sign matrix A over product distribution (M, p) with correlation 1/8sq(A)². In other words, for any product distribution (ju, p),
IF (T( A(f=))] 2 (sq(
(1
Therefore, by substitution,
E rownl (1a0())))))
[x(f,x) Eval(r,))]
8sq(
By Theorem D.6, for every function F; :10,1} {0,1) + [+1}.
Cor(f,II, ) max E (f()) [()] s 2 (2
(5)
*Ell.
for x uniformly distributed over {0, 1} x {0,1) 1}. Note, II, is the class of c-bit communication protocols, which is defined in the Appendix, section D. Hence,
(E(al)))=
E ri.22 10
II
Eval(re, Wez)
((s(())))
(1..22((122)
Manipulating the RHS can see that:
E f.g-u 2,000
((x) ff(x) f(z)]
O(sq(A)8)
E Predict gnep.fuu
[Predict(2) f()]
This implies that Predict is randomized predictor for the unknown target f. which satisfies:
1 + Predict(x) s(=))
Pr
(6)
frp.sssp.Fredict
2
((s((A)))
10

---

The Power of Random Features and the Limits of Distribution-Fri Gradient Deseent
Using (4) to conclude lemma A.4. We will combine (4) and subtle "averaging" argument conclude lemma A.4.
Lemma A.5 ("Averaging argument," " see lemma A.11 of Arora & Barak (2009)). Ifa random variable E [0, 1]. and [X] = ps then for any <,,,
1-p Pr[X & cpl - cp
Let us consider Predica ct to be deterministic function that maps and random bits r to value in (+1). The random bits r encompass what is necessary to sample all random variables in the course of running P Predict (e.g., μ4, and a sample from the example oracle). We can then conclude from (6) and lemma A.5 that there exists many "good" random strings:
Pr
Pr 2mep
(x:)
[()) 2 2 + ((sq(A)8)
fope
(As{())))
Note that the deterministic version of Predict described so far uses random bits r to sample x in line 1, but then would need oracle access to f to obtain the value of f(z). We need to remove this need, and can do so as follows. Observe that the prediction output of Predi et is g(=)g(x)) Thus, the predictor predicts g(z) and negates that prediction if and Bernoulli random variable, which can be considered independent of 2, g and f.
only if (x) 1. Now, (()) The mean p of this random variable depends on p. Hence, can sample this random variable directly, instead of using oracle access to f. Thus, under this version of Predict, we include the random coins to sample the Bernoulli inside and again apply lemma A.5 to now instead conclude:
1 Predict, = f(=)] 2 ((sq(A)))
Pr fruur
Pr grup
2 O(s((A)8)
Note that now Predict depends on p but not the example oracle.
From here, we would like to show that:
Pr
Pr
Pr (P(ediic, = f(z)] 2 + 2 2 8
(8)
frop
Smip
where 8 is small positive constant, and we use in place of O(sq( ()) streamline notation. Note that, (8) holds for any prior
To show this we assume, for the sake of contradiction, that the set of functions f for which
Pr Pr
2 + <e
(9)
has probability greater than under μ.. That is,
Pr
Pr Pr (re)iict = [(=)]
+e <e >d
fuu
Now, let yt be new distribution over functions f defined as the conditional distribution of restricted to this "bad" set.
Formally, for any set S of functions,
(((S) (S Bad)
(Bad)
where
Bad
{
Pr
Pr [Preddict,(x))= = [(=))(())))))))) zuup
<E
Note that, since y (Bad) 5, 1t' is well-defined probability distribution.

---

The Power of Random Features and the Limits of Distribution-Fre Gradient Descent
We compute the joint probability under yl:
Pr (opl
Pr (r) = [(=)] 2 2 + gmp
For each f in the support of p., have:
Pr
Pr (reddcct((st)) + <6
zup
Therefore,
1 + <e
c
Pr
Ppredict,(zt [()) zmp
Pr
2
We now apply this towards the contradiction. Inequality (7) states that for any distribution je (including μa), we have:
1 + 2
Pr Pr (t,edd f()) foull r pmpp
2
This leads to contradiction because under y', the probability is less than e, whereas it must be at least Therefore, the set Bad has small measure. Indeed, the contradiction implies that our assumption about the size of Bad must be false. Therefore, the measure of Bad under y must be at most 6:
Pr
Pr
Pr (t s(=)] 2 = + -~pp
< 2
fou
Equivalently, the probability that is such that
Pr
Pr (Ptddicct((tt) [()]] 2 + ze
zup
is at least 1 - 8:
Pr frum
Pr
Pr [Predict,(zix)- = f(z)] 2 grup
2 + 2
2 8-
Now, sampling a string of random bits and then hard-coding into Predi ct. induces distribution functions. Note that, this distribution is potentially different for each example distribution p. because Predict samples p. Therefore, we can take this distribution over functions as ufeat, and conclude that,
Pr f~
Vp 3
feat
Pr pampf
Col Col
DDPP(f)) S 2
1 -2 (sq(A)))) 1 (sq(A)))8) 2 21-6
cat
A.3. Proof of Theorem 4.1 via Constructive Boosting
Now that we have the Random Feature lemma, we prove Theorem 4.1. In order to do so, we will use equivalence of weak-to-strong learning in the PAC-setting.
Theorem A.6 (Adaboost-Freee
& Schapire (1997) (see also Karbasi & Larsen (2024))), Let be an oracle that accepts an example distribution p' over X and returns a 7-weak learner furk with respect to 0-1 loss. There exists an algorithm BOOST that, for any example distribution p, makes -2) queries O and outputs g X {+1} such that, for any h H. and any 5 > 0.
Pr BO00O
Pmi (g) I 2 1-8
12

---

The Power of Random Features and the Limits of Distribution-Fri Free Gradient Deseent
Here, θ hides logarithmic factors in 1/6, 1/e, 1/7, and the dimension of the class that O oouppus weak learners from. Moreover, the final hypothesis 9 found by BOOST is of the form
(0 2)
g(z) A sign
Σ
Wi
fiuk (x)
W R. fin t
Proof of Thm. 4.1. To prove the statement, we need to show that, given prior 1 over function class F, the smallest positive integer d such that there exists a distribution & over embeddings Φ X + Rd, such that
Vp fru
Pr
E
inf C +))) WER
2 1
at most O(c"'sq(F) (6++) for arbitrarily small 8 0. Specifically, we will show this when E is defined as the probabilistic process that samples embedding & by sampling -'. S1 ~ //eat .... feaat " for some O(sq(F)21.0) and outputting their direct product (Jí, ... f.). Observe that the underlying example distribution may be different for each f(. We will illuminate how each pi is chosen.
To prove this, first let us apply the Random Feature lemma to the conditions of the present theorem, to conclude that,
Pr Frup
Vp
up
feat
Pr Mnwup feat
Col (2)ia()) -
1 - (sq(F)-8) 2 (sq(F)) 2 21-8
Establishing this essentially gives weak learning algorithm for each example distribution p. To see this, observe that the above equation says that, with probability 1 over μl, for every p. p1 uffar weakly approximates f over p with probability (ss((F))). The weak approximator has population loss 1 7 for y ((sq(F) We call a y-weak approximator. Also, we call f' that satisfy this event "good."
Under this weak approximator interpretation of the Random Feature lemma, it becomes clear that we should sample "'. ugeaa,, ...p/eatt for successive Pi in accordance with standard weak-to-strong accuracy boosting algorithm such as Adaboost.
we do this, then by Theorem A.6, we can constructively derive, for any p. a linear combination w such that,
c/ ( 5 : g(z) ف sign ((w, o))
(10)
....pfeatt feat for the appropriate Ps. Note, also from Theorem A.6, E g0(T Thus, we will conclude the desired statement by upper bounding the number of samples we need from successive jf (i.e., the quantity d) as follows.
given enough samples from i feat ... Pa
Let D denote random variable of the number of features we need to sample until we can find linear combination features g satisfy eq. (10). We compute the expected value of D. We can analyze by "rounds." At round 0, there is pool of Z = (() example distributions which require a y-weak approximator. Now, at each round r. suppose single random feature f' is sampled from n.feat as potential y-weak approximator for Pr- We progress to the next round if a y-weak approximator is sampled for Pr. and remove pr from the pool of distributions which needs an approximator. Hence, round r indicates that r weak approximators have been found, and Z - r remain in the pool. We terminate if we reach round Z.
At each round,
2 Ω (sq(F) 2 (5Q(F)-8)
Pr Pimp feat
Hence the expected number of samples from un ufeat needed to satisfy the event that at least of the samples is "good" is (s))(F)))) Then, since Z = Ō()-2), the expected number of samples to get "good" feature for each the example distribution is (ss(FF))) 0(sq(FF) = ((s
We thus conclude,
Pr E [ < (sq 2 fru
13

---

The Power of Random Features and the Limits of Distribution- Free Gradient Descent
By the Markov inequality,
Pr fmpp
Pr
D (F)2(1))))1)
S sc/2
1 1
Combining this with (10), we have:
Pr fou
Ap:
E doeE
inf (sign(()
Sc 2 21-6
weRd
for d s (FF344)).
B. Average Probabilistic Dimension Complexity
B.1. Background
Towards understanding the limits or the power of learning linear combinations over features, one of the fundamental quantities of interest the dimension complexity of a hypothesis class (see e-g. Ben-David et al. (2002)). Roughly, the dimension complexity of hypothesis class H. full of functions X + IR the least positive d Z such that there exists feature map Φ X RR such that for every h H. there exists linear combination R which satisfies h(x)= (w, ((x)) for all r E X.
More formally:
Definition B.1 (Standard dimension complexity). The quantity de(H) is the smallest positive integer d such that there exists a feature map o : X + R2, such that for every p over X, and every h E H.
inf C ((w, W WERd
(11)
Showing an upper bound on the dimension complexity d of a hypothesis class is thus sufficient to reduce a Machine Learning problem to linear learning over the d-dimensional feature map implied by the upper bound. The smaller d, the more efficient learning can be (in terms of sample complexity, for example).
However, this standard notion of dimension complexity is in some sense "overkill" for this reduction. It was pointed out by Kamath et al. (2020) that the standard dimension complexity is not necessury for Machine Learning, since for effective Machine Learning, one only needs to design feature map that allows for e-approximation by linear combination of the features, for each function in the hypothesis class. This also means that not only are upper bounds on dimension complexity overkill, but lower bounds do not necessarily rule out efficient learning.
B.2. Probabilistic dimension complexity
In light of this, Kamath et al. (2020) introduced probabilistic variants of dimension complexity to get closer to the notion of dimension complexity that is necessary and sufficient for this reduction. Mainly, their definition subs out exact representation by a linear combination in favor of e-approximation. The following is their definition:
Definition B.2 (Probabilistic dimension complexity). The quantity do. (H) is the smallest positive integer d such that there exists a distribution& over feature maps Φ : X + Rdd, such that for every p over X, and every h E H.
(Pwr)((, 01) Se
E C
inf
(12)
WERd
Only requiring e-approximation also means that the definition can allow for a distribution over feature maps (for free, in sense). This further opens up the possibility of using probabilistic dimension complexity study the LLRF method.
The immediate question concerning probabilistic dimension complexity is whether it can be significantly smaller than standard dimension complexity. This is an important question because a yes answer would present hypothesis class for which a lower bound on its dimension complexity would not necessarily rule out the effectiveness of the LLRF method. Indeed, Kamath et al. (2020) demonstrate this very possibility by giving an exponential separation between the probabilistic and standard dimension complexity.
14

---

The Power of Random Features and the Limits of Distribution-Fre Free Gradient Descent
Theorem B.3 (Thm 6. of Kamath al. (2020)). There exists hypothesis class H, with domain {+1}² and range (+1}. which satisfies for 0/1 loss:
de(H) E 20(n2)
dc, (en
remains unknown whether there exists an "infinite" separation between standard dimension complexity and probabilistic dimension complexity. In fact, Kamath al. (2020) explicitly leave it as an open question: does there exists a hypothesis class H. which satisfies for 0/1 loss, and some functions f, f N + N. de(H) O(f(n) and de, (H)) E (()
B.3. Average Probabilistic Dimension Complexity
The definition of probabilistic dimension complexity maintains universal quantification over possible hypotheses h H (this quantifier was unchanged from standard dimension complexity). In other words, there still needs to exist one distribution over feature maps such that for every h E H. (12) holds.
As we alluded to previously, in this work, we point out that while universal quantification of H is desirable, this also makes easier to prove a lower bound by constructing a pathological Machine Learning problem, when at the same time is possible that all other instances of the Machine Learning problem have significantly lower complexity. This would make the lower bound hard apply in practical situations-rarely would hypothesis functions be chosen "adversarially," (wherein universal guarantees would be the go-to).
In summary, while (Kamath et al. (2020) argued that) standard dimension complexity is overkill for reduction to the LLRF method, we now point out that probabilistic dimension complexity might still be overkill for reduction to the LLRF method in practical situations.
more practical setting might be the average-case or "Bayesian view," where the learning problem is not necessarily chosen by an adversary (universal quantification). but instead by randomized process known the learner. The randomized process is the prior for the learner. Hence, we introduce further relaxation of dimension complexity, where the new goal is probabilistic guarantees over both the accuracy, and the hypothesis class." We define dimension complexity in this setting as follows:
Definition B.4 (Average probabilistic dimension complexity). The quantity adc,,s(k), given prior distribution μu over a hypothesis class H. is the smallest positive integer such that there exists a distribution & over embeddings & X - Rd. such that
Pr hrg
Vp
IF dne
inf (Pai S 2 1 werdd
After defining average probabilistic dimension complexity, we would hope find hypothesis class that has very low average probabilistic dimension complexity- even lower than its probabilistic dimension complexity, and hopefully much lower than standard dimension complexity. This would formally motivate our definition, and it would shed light when the LLRF method might still be effective on most instances of a Machine Learning problem, or when the learner has an accurate prior.
C. Results on Average Probabilistic DC vs. Standard DC
Consider hypothesis functions h X {+1} over a finite domain X. A hypothesis class H is set of concepts h: X 1=1 As mentioned previously, one of our main theorems proves that average probabilistic dimension complexity is polynomially related to statistical query dimension. Thus recall the definition of statistical query dimension.
Definition C.1 (Statistical query dimension). Let p be a distribution over domain X. The statistical query dimension over of H. denoted sq(H,, p). is the largest number d such that there exists d functions f1, .. fa E H that satisfy, for all + j:
1 à
E [+(+))((0)) smup
We define sq(H) = max, sq(H,
We can also view the average probabilistic dimension complexity as probabilistic dimension complexity of large probability of hypotheses the class H (with respect to the prior 1t).
15

---

The Power of Random Features and the Limits of Distribution- Free Gradient Descent
We recall main theorem from the body of the paper.
Theorem C.2 (Restated Theorem 4.1). Let H. be hypothesis class, distribution over H. and let be 0 1 loss. We have:
adc,, ( - 0(sq(H))2401
where o > 0 are arbitrarily small constants.
Infinite separation between ade and de'. As an application Theorem 4.1, we make some possible progress towards answering the open question left by Kamath et al. (2020). We recall there question was whether there exists a hypothesis class H. which satisfies for 0/1 loss, and some functions f, / N + N, de(H) E O((n)) and de, (H) E (()/f())))?
Our result, shows that the answer is yes, if we take add's instead of dé.
Corollary C.3 (Infinite Separation between ade', and dd²). There exists hypothesis class H. with domain {+1}" and range {+1}, which satisfies for 0/1 loss and any prior distribution p over H. and arbitrarily small constant 8 0:
dc(H) 2
(H)) E O(1/e).
This separation follows immediately from Theorem 4.1 and a theorem of Sherstov (2008a), which is concerned with the following family of matrices.
Definition C.4 (Zarankiewicz Matrices). Let (NN, c) denote the class of N x N sign matrices that never have any c sub-matrix with all of its entries set to 1.
Theorem C.S. Let e > 0 be an arbitrary constant. We have,
A A ([(]) sq(A) E 0(1)
A E (NN2(()] dc(A) E Q(NT-9)
C.1. Towards Infinite Separation Between Probabilistic DC and Standard DC
In the previous section, we used Theorem 4. to prove an infinite separation between average probabilistic dimension complexity and dimension complexity. On the other hand, for probabilistic dimension complexity, Kamath et al. (2020) gave "just" an exponential separation (O(n) vs. 20(1)), Thus, in this section, we consider whether or not it is possible to improve the separation of Kamath et al. (2020) infinite. This was posed explicitly as an open problem by Kamath et al. (2020).
Said differently, would like to understand if the relaxation from probabilistic dimension complexity average probabilis- tic dimension complexity is necessary (and not merely sufficient) to prove an infinite separation with respect to dimension complexity.
As first try towards proving that the relaxation is indeed necessary, we might try to again use Zarankiewicz matrices to show that there exists A e 2 (NN, c) such that (A) E (N))) for a super-constant function f.
viable. Towards Theorem C.5, Sherstov uses result of Ben-David et al. (2002) obtain the dimension complexity lower bound matrix in the Zarankiewiez family. However, Sherstov (2008a) notes, Ben-David et al. (2002) actually something stronger. They show that, for a fixed e Z, all but vanishing fraction of 2(N, c) have dimension complexity ((N1)22/)) This implies that, given 0,
Unfortunately, we go deeper in understanding Zarankiewicz matrices, we can see that this approach
Pr A- ((N,o)
(dc E ((S(N))) 2 0.99
(13)
for [(N)=
= N1-2
Therefore, a random Zarankiewicz matrix has large dimension complexity. As a result, trying to prove (13) for e >> 0 is actually impossible, even for f E -(/o)) To see this, observe that if we did show that, then this would essentially be a proof of addc,,(Unif(Z(N,,, e ((f(N)). By Theorem 4.1, we now understand this statement to be false, for super-constant, ft
16

---

The Power of Random Features and the Limits of Distribution-Fri Free Gradient Descent
C.2. Barrier to Separation of Average Probabilistic DC and Probabilistic DC
Beyond the case of Zarankiewicz matrices, in general, it seems it will be difficult prove that there exists H. p such that
a < do, (H)
(14)
In this section, we formalize this by demonstrating a barrier to proving (14), if we also restrict the separation to occur on bounded 11-norm version of average probabilistic dimension complexity.
Definition C.6 (Bounded norm odc,,,(())). The quantity a given prior f over a hypothesis class H. is the smallest positive integer d such that there exists a distribution & over embeddings Φ X + R such that
Pr haye
vp
E aop
inf
Ø1)
Se 21 -1-8
weR"
willsb
Here, |//11 A Σ; Wi/.
We note that both Theorem 3.3 and the separation (Corollary C.3) actually apply to ad)), for b poly(sq(7().
For now, we will prove complexitytheereeic barrier, based on the long-time difficulty of proving super polynomial threshold circuit size lower bounds.
Theorem C.7 (Complexity barrier). Let b - 2 for some constant 0 < <<< 1. Suppose that
( < (c)(H)
holds. Then, depth-2 threshold circuits computing Eval(H) (h, .) + h(x) require superpolynomial size (where h, x are binary encodings of h E H and x E X).
To do so, we use a theorem due to Alman & Williams (2017) which relates circuits size of depth-2 threshold circuits of evaluating a hypothesis class, and the probabilistic dimension complexity of the class.
Lemma C.8 (Alman & Williams (2017)). If Eval(H) (h, .) - hx) (where h x are binary encodings of h E H and x X) is computable by depth-2 threshold circuit of size s, then:
52 log (H) 1X1I)
dc, (H) 50
Proof of Theorem C.7. It it is true that, for < 2n for every H and μ over H. there exists some constant 7 > such that,
ve(H)" < adc (H)
then, if prove that there exists H. a such that
add (1)=)(())(( < dcc(H))
then we deduce that,
vo(H))(11) s (H)
(15)
When (15) holds, can apply Lemma C.8 conclude that
vo(H))ut)) so (0
(000 log gogg2(12)) (174)-1X11)
(X11))
where s is circuit size a 2 threshold circuit computing Eval(H). Choosing H. appropriately, this implies a super-polynomial lower bound on for Eval EH)..
17

---

The Power of Random Features and the Limits of Distribution- FFee Gradient Descent
Thus, it remains to show that for every H. and μ over H. there exists some constant 7 0 Such that,
ve(H)) S ado, (())
To prove this, we negate towards contradiction. Suppose that there exists H. f such that for every constant; 7 > 0, it holds that ve(H)) > adc (H). Then, for H. the class of parities, and j the uniform distribution, we get that for every ? adc,, < ve(H)) n². Using this bound on ade (4),, ( parities, whose complexity violates known lower bounds of (())).
can now derive distributional communication protocol for
The protocol for computing the communication matrix A(fs, r) for parities works as follows. The player who owns samples the embedding Φ ~ & guaranteed by adc,, (1) < n The player then computes 6(z), and then sends the results to the player who owns h. This player then computes the linear combination of ((x), which e-approximates l(()), which also guaranteed by adc",s < n².
Since adc (n) < n²,, this protocol for A gives that A E 1IS for log(b) (see section D for definition of _,,,)) Finally, since we stipulated that b S 2n" we see that A E ITS for c = O( which gives the desired contradiction, and concludes the theorem.
Remark. We note that, by inspection of Adaboost, the weights of the linear combination in our construction in Theorem 4.1 are bounded. Hence, the above theorem indicates that if we want to avoid the tohplexityttheoreiic need different technique or construction prove that our construction and relaxation was necessary to get the infinite separation.
-thooretcc barrier, then we
D. Communication Complexity Preliminaries
Let A be a sign matrix (one with entries taking only values in (=1)). We define the discrepancy of sign matrix. Let X, Y, be two sets indexing the rows and columns of A. We write (2; denote the entry of A indexed by x E X,y E Y. A rectangle R is the set B x C for B X, C Y. For a fixed distribution ( over X x Y, the discrepancy of A with respect to is defined as
disce (A) A max R
Σ ((x,)) A(x:8)
(aN))R
As special case, we define discrepancy over product distributions
disc (A) A min disce
subject to the constraint that Ç is product distribution over X x Y.
D.1. Communication Models
It is well known that discrepancy of sign matrix is related to the communication complexity of the sign matrix. We define models of communication now.
The 2-party communication model is the following. There are 2 parties, each having unbounded computational power, who try to collectively compute a function. The input to the function is separated into 2 segments, and the 5th party sees the 7th segment. The parties can send each other direct messages.
Each party may transmit messages according to a fixed protocol. The protocol determines, for every sequence of bits transmitted up that point (the transcript), whether the protocol is finished (as function of the transcript), if, and which, party writes next (as function of the transcript) and what that party transmits (as function of the transcript and the input of that party). Finally, the last bit transmitted is the output of the protocol, which is value in {+]} The complexity measure of the protocol is the total number of bits transmitted by the parties.
Definition D.1 (II. class). II. is defined to be the class functions f :(0,1) x {0, 1) - {+1} that can be computed by a 2-party deterministic communication protocol with complexity e.
18

---

The Power of Random Features and the Limits of Distribution- Frree Gradient Descent
Frequently it is useful think of being represented by sign matrix, where A( A f(x y). Hence, may abuse notation and write that A cT
A model more relaxed than deterministic communication is distributiioal communication.
Definition D.2 (Distributional II.). The distributional 2-party communication model allows the protocol to certain inputs. Fix distribution p over {0, }} x {0, A function f [0,1) (0,1) {+1) is in ITg if there exists communication protocol π E II, such that
E
(2)) ((11, 2 27
(#1,22)
Distributional communication complexity can be thought of as correlation with TT.-
Definition D.3 (Boolean function correlation). Define Cor(f,A) A max4ex [E (f)) h(x)] where is sampled from distribution Ç over the domain.
When want measure correlation between two function classes, we have defined follows:
Definition D.4 (Boolean function correlation). Define Cor(C, A) - minyee maX [E [f(x) 1(=)] where is sampled from distribution Ç over the domain.
D.2. Discrepancy vs. 2-bit Communication
Proof of Lemma A.2. Let R' be the rectangle that witnesses the maximum value of
Σ <'(x,y) A(x; 8)
(x.g)ER'
with respect to the worst-case product distribution ç'. construct x as follows. Alice and Bob, receiving as input and respectively, which sampled according to Ç', each send bit indicating whether or not their respective input is contained in R'. If both inputs contained in R', then they output bit according to the bias over A projected to R' induced by ç². Otherwise, they output random bit.
First, observe that the output of this protocol by definition satisfies
E (a.w)~<''
((x ((.,8)((z)) A);(<;)))) v)]
Σ <'(x,)) ((x,,)-B(x(r,))) B(x(x,)) A(z;0) (2,0)ER
Now, with probability (p + 1)/2, for certain E [-1, 1], π(Σ, v) = A(x; Thus, for (z, R, -(xr)) = with probability (1/1) Therefore E, [π(x, v) A(r;y)1 = Hence,
=p.
E [T(2, x){(;;)]] =p Σ <'(x,y) (x.,))<''
(x.0)ER
Note that p chosen the proposed protocol specifically so that this implies:
E [ύ(x,)) v) A(x;))]] (2.0)~<'
Σ (((x,))((;:))
(a.eER
Recalling the definition of discrepancy:
disc x (A)=
Σ
S' v) A(z:v)
('
19

---

The Power of Random Features and the Limits of Distribution-Fri Free Gradient Descent
If we apply this definition and the conditions of the theorem, then get that:
(r(x,)))(13) vI] 27
E
(..))
D.3. 2-party Norm
Additionally, important quantity will consider is the 2-party nomn of a function, R2(f), which is defined to be the expected product of function computed on list of correlated inputs.
Definition D.5 (2-party norm). For f {0, 1} (0, 1} {+1}, the 2-party norm of f is defined
E R2(f) o af at (0.1)
II
(16)
(1,62E(0.1)
For us, the most important property of R2(f) is that it upper bounds the correlation of f with functions computable by deterministic 2-party communication protocols. We denote by II, the set of all f {0, 1} x {0, + {=1} that have deterministic 2-party communication protocols with cost at most c.
Chung & Tetali (1993); Raz (2000); Viola Wigderson (2007) demonstrate the following bound: Theorem D.6. For every function f (0,0 1} x {0, + {=1).
Cor( IIe) = max E [f(x) T(=) - =
for x uniformly distributed over (0.1) x 1).
20


Reviews:
[{"review_id": "PDiJu2ejGc", "reviewer": "Reviewer_NhLC", "summary": "This paper investigates how powerful are gradient-based algorithms on some differentiable models for **distribution-free** learning settings. The main theoretical result (see Theorem 3.2) is: essentially, whenever the function class is SQ learnable or differentiably learnable in the sense of [Abbe et al. 2021] then it is also learnable with some random feature kernel up to polynomial blow-ups. So the result essentially establishes that without making any assumptions on the input distribution, it is not possible to show exponential separations between Gradient algorithms and random feature kernels.\n\nThe only small caveat, and perhaps necessary to show this result, is that the guarantee holds with high probability over the function class for an arbirary prior. But does not hold for any function in the class. Perhaps, this is inherently necessary to show the result.\n\nSo to show such guarantees, the paper introduces another notion of average complexity measure--average probabilistic dimension complexity (adc)---which is shown to be polynomially related to statistical query dimension, to achieve the desired claim.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer NhLC,\n\nThank you for your thoughtful review. We will directly respond to the weaknesses and questions that you outlined.\n\n> Overall, the paper's exposition can be improved. Line 21: \"though the distribution free learning is the desired goal.\" I strongly disagree with this statement. I don't think this is the ultimate goal. The goal is to come up with the right assumptions that can inform us why learning works. And it is well-known that distribution-free settings are too pessimistic due to the worst-case hardness results. This is never taken as the ultimate goal. \n\nThank you for this feedback. Line 21 says “While distribution-free learning is a desirable goal, it is often computationally challenging, as it requires the algorithm to handle worst-case scenarios.” We feel that this line is meant to say something different than the way it was interpreted, so we will modify it to prevent this. We do not intend to weigh in on what the “ultimate goal” is (or should be), and we just meant to say that distribution-free algorithms can be desirable (in a literal sense), and add the context that it is often computationally challenging to achieve.\n\n> Line 64-67 \"a common finding...learning outcomes\": The statement does not read well...\n\nThank you for pointing it out, and we intend to improve it. To improve it, we like your suggested point as a template, and will include something similar in the “this work, in a nutshell” paragraph. E.g., \n\nInput data comes from a specific distribution. However, the distribution-independent settings are easier to discuss and have been extensively studied.Yet, hardness results in this setting should not be seen as a fundamental barrier. Taken at face-value, they only apply to some worst-case distribution. In this paper, we make this formal in the context of kernel vs gradient-based method on NNs, by showing that ...\n\n> The entire 2nd (line 76-86) on general references on parity can be either completely removed...\n\nWe will move this information elsewhere. Indeed, it may break the flow, but for some readers less familiar with parities, and the study of parities, it may be helpful context.\n\n> in what distribution-specific setting parties are not hard to learn? Generally, uniform distribution is also seen as the distribution-specific setting, so it is better to specify the distribution as well.\n\n[1] Consider a family distributions where parities are not hard. As a special case, they consider a biased product distribution over the hypercube. We will specify this as an example.\n\n> IMPORTANT: doesn't the centered statement in lines 52-53, right side at the end of page 1 summarizing the result, create a wrong impression of the order of quantifiers?\n\nUsing the phrasing then **most** functions in the class must have a relatively simple random feature representation alludes to the case where the prior μ is fixed to uniform. In this case there is one random feature distribution constructed by our proof. So while our statement is correct, it may not be clear, and we definitely do not want to create the wrong impression. We will clarify in the final version.\n\nQuestions:\n\n1. Yes (latex rendering error)\n\n2. The main intuition is that in the proof of the random feature lemma (page 10), we use the ability to sample new concepts from the distribution. This seems unavoidable to apply our communication complexity technique which operates in the “distributional” communication model. While our techniques basically operate only in this setting, it is not clear if it is necessary. \n\n3. Yes, it can hold for more general loss functions than sqr loss, using the flexibility of the theorem of [2], which converts bSGD to SQ. For the random feature representation, our communication complexity technique produces random features that are essentially weak learners for the target distribution w.r.t. 0-1 loss. However, if there is a boosting theorem that we can use to boost such weak learners to a strong learner under a different loss function, then this should allow one to expand the conclusion on the random feature representation to other loss functions. \n\n[1] Malach, E. and Shalev-Shwartz, S. Learning boolean circuits with neural networks. arXiv preprint arXiv:1910.11923, 2019.\n\n[2] Abbe, E., Kamath, P., Malach, E., Sandon, C., and Srebro, N. On the power of differentiable learning versus pac and sq learning. Advances in Neural Information Processing Systems, 34:24340–24351, 2021.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "I havn't checked. But the claims seem to be correct and enough discussed in the main text.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "When NN trained with gradient-based algorithms are more powerful than kernel methods is an important question in learning theory.  At least hundreds of works, if not more, have looked at this question from several different points of view. The results of this paper are essentially saying that the assumption on the input distributions is necessary to understand this separation. Otherwise, if the goal is to succeed over all distributions, then this separation collapses, and they are the same up to polynomial factors. I think the findings are new.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "See summary for strengths. The paper has a good theoretical contribution.\n\nWeaknesses: Overall, the paper's exposition can be improved. \nLine 21: \"though the distribution free learning is the desired goal.\" I strongly disagree with this statement. I don't think this is the ultimate goal. The goal is to come up with the right assumptions that can inform us why learning works. And it is well-known that distribution-free settings are too pessimistic due to the worst-case hardness results. This is never taken as the ultimate goal.\n\"The \"theoretical value of this result\" paragraph can be improved.\n1. Line 64-67 \"a common finding...learning outcomes\": The statement does not read well. It is not that assumption enables better learning outcomes. Perhaps a better way to put this point forward, which I did not find very clearly in the entire paper either, is as follows. \"Input data comes from a specific distribution. However, the distribution-independent settings are easier to discuss and have been extensively studied. However, indeed, the lower bounds on this should not be seen as the fundamental barrier, as this bounds are too pessmistic, i.e. it holds over some worst-case distribution. The result in this paper makes this formal in the context of kernel vs gradient-based method on NNs.\" This can be also said in the \"This work in a nutshell\" paragraph before the last line. \n2. The entire 2nd (line 76-86) on general references on parity can be either completely removed (or delayed if authors mention these works anyway). But they don't add anything to the point. It hurts the flow of reading to the most important paragraph to follow after that. Also, in lines 100-101, in what distribution-specific setting parties are not hard to learn? Generally, uniform distribution is also seen as the distribution-specific setting, so it is better to specify the distribution as well.", "other_comments_or_suggestions": "Please see the weaknesses. Also, though I don't have line-by-line suggestions, see if the introduction can be made more effective overall.\n\nCan you please make the dependence on \\ell explicit throughout in the notation of adc itself, like Kamath et al? Though it has been specified several times clearly, I suggest you create a notation where this is explicit.\n\nAlso, the square loss notation can be ell_{sqr} rather than capital SQ, which is relevant for the statistical query. Please try to make this different if possible.\n\nIMPORTANT: doesn't the centered statement in lines 52-53, right side at the end of page 1 summarizing the result, create a wrong impression of the order of quantifiers? This is also used in TL;DR. Perhaps, it should have been:\n\"...., then there exists a random feature (depending on a prior) that can express most functions under the prior.\" or make it even more clear:\n\"...., then for any prior over function class, there is a random feature model that can express most functions under that prior.\"", "questions_for_authors": "1. Is the 0-1 loss in line 254 defined incorrectly? Should it have \\neq instead of equal-to? This mistake is also there at other places.\n2. Can you please walk me through the argument as to why this prior mu over function is necessary for this type of result to hold? What is the main intuition on why this could be necessary?\n3. Why do you ell_sq for bSGD, but the result for kernel is shown over 0-1 loss? I understand that for bSGD, you need the loss to be an almost differentiable one, so can you show this for general surrogate losses? More importantly, can you show the result for random feature approximation for, let's say sqr loss? Can you explain to me a bit about this discrepancy and to what extent it could be avoided?", "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": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "lmPY3BZ17s", "reviewer": "Reviewer_9ucH", "summary": "This paper revisits the power of learning with gradient based methods in a distribution free setting. The main result is to show that if a hypothesis class $F$ can be learnt using gradient descent on some parameterized model with a distribution-free guarantee then for any prior distribution $\\mu$ over $F$, there exists a probability distribution over random features such that $h \\sim \\mu$ with high probability can be approximated by a linear function over those random features; this is formalized in the notion of _average probability dimension complexity_ introduced in the paper.\n\nThis is interpreted in the paper by saying that any distribution-free guarantee on learning with gradient descent must be very limited because it implies that _most_ functions in the class can be represented efficiently using a random feature representation.\n\nThe proof technique is as follows:\n1. A result of Abbe et al. (2021) is invoked to say that learning with gradient descent implies a statistical query learning algorithm, which by standard arguments, implies upper bounds on the _statistical query (SQ) dimension_.\n2. The main technical contribution of the paper then is to show an upper bound on average probabilistic dimension complexity in terms of the SQ dimension of the class.\n\nAs a corollary, Part 2 resolves a weaker version of a conjecture from Kamath et al. (2021) that asks for an infinite separation between _probabilistic dimension complexity_ and (deterministic) dimension complexity; namely, here an infinite separation is shown between _average probabilistic dimension complexity_ and _dimension complexity_.\n\nThe proof for Part 2 involves techniques from communication complexity, a \"random feature lemma\" and a boosting procedure.\n\n### Post-rebuttal update\n\nBased on the rebuttal discussion, I am increasing my score to 3, since the authors have acknowledged that the concerns raised in this review would be discussed in a revision.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer 9ucH,\n\nWe appreciate your thoughtful review. We will respond to specific weaknesses that you addressed in your review.\n\n> One thing that I feel is problematic is: In Theorem 3.3, why is the condition bc^2≥Ω(log⁡Tp/δ)\n not required?\n\nYes, it is required. This restriction is introduced in the text preceding the theorem (top of paragraph 2 in section 3.2 - line 238). We will include this inside the theorem for extra clarity.\n\n> If this condition is indeed required, then I feel the narrative of the paper changes quite a bit. The story is not really about any gradient descent based method, but only one with \"low precision\" (as defined in  [4]). In that sense, the paper is really about statistical query learning methods, and the \"gradient descent\" part is not providing that much insight.\n\nWe believe that your interpretation is technically correct in some sense. However, there is a large body of work that studies limitations of gradient descent through SQ lower bounds. For a quintessential example, see [5].\n\nAdditionally, we want to point out that expecting this type of result to apply to any gradient descent based method is not well-founded. This is because our theorem *does not hold* when there is no restriction on the precision of the gradients. To see this, we can borrow from [4], who show in theorem 1a of their paper that (distribution-free) PAC-learning algorithms can be simulated by (distribution-free) bSGD algorithms, when allowed fine enough gradient precision c (depending on the batch size b, specifically, c < 1/8b; note, in their paper they use \\rho to denote gradient precision). Using this theorem, it follows that for (b,c) such that c < 1/8b, then bSGD can learn parities in the distribution-free case. From here, we can conclude that our transformation from bSGD to random features cannot hold for (b,c) such that c < 1/8b, since the random feature representation would violate SQdim lower bounds for parities.\n\nWe do think this discussion is insightful and plan to discuss this in the final version of this paper.\n\n> I feel the notion of average probabilistic dimension complexity is not that well motivated... All this notion says is that for any prior μ  over the hypothesis class, there exists a random features representation such that most functions in the class are well approximated. But since this random features representation depends on μ, this does not lead to a learning algorithm. So, from that point of view, I don't fully buy the narrative that having small average probabilistic dimension complexity suggests any limitation of the hypothesis class\n\nIt is true that the order of quantifiers makes it so that “the learner must know the prior μ” so-to-speak. This is why we interpret the theorem, as explained in the introduction, as support for the the statement:\n\n*If a function class is learnable in a distribution-free manner by gradient descent (with some restricted precision), then most functions in the class must have a relatively simple random feature representation.*\n\nThis statement is fully supported by our theorem if you fix μ to be the uniform distribution, as this means most functions in the class (i.e., a large fraction of the class, or any large subset of the class) have a small random feature representation. Moreover, **we must emphasize** that the fact that any large subset of the class has a random feature representation is a major limitation. Many works give relevant examples of classes that **cannot** be represented in such a way at all: [1] [2] [3]. [1] does this for parity functions on k bits, [2] does (single) ReLUs, and [3] does “ResNets.” **Hence, the fact that we show such a scheme *exists* at all is a strong statement.**\n\nOn the other hand, as you pointed out, when μ is “unknown,” there is no explicit feature distribution. Thus, we do not interpret the theorem as saying that  gradient descent can be replaced by random feature learning algorithms. This is touched on in the first page of the introduction, but we are happy to expand this discussion in the final version of the paper for maximum clarity.\n\nReferences\n\n[1] Amit Daniely and Eran Malach. Learning parities with neural networks. arXiv preprint arXiv:2002.07400, 2020.\n\n[2] Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for understanding neural networks. In Advances in Neural Information Processing Systems, pages 6598–6608, 2019.\n\n[3] Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? In Advances in Neural Information Processing Systems, pages 9017–9028, 2019.\n\n[4] Abbe, E., Kamath, P., Malach, E., Sandon, C., and Srebro, N. On the power of differentiable learning versus pac and sq learning. Advances in Neural Information Processing Systems, 34:24340–24351, 2021.\n\n[5] Surbhi Goel, Gollakota, A., Jin, Z., Karmalkar, S., Klivans, A. Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent. arXiv:2006.12011, 2020.", "claims_and_evidence": "Claims are supported by proofs in the main body or in the Appendix.", "methods_and_evaluation_criteria": "The paper is entirely theoretical, so I believe this question is not relevant.", "theoretical_claims": "Proofs have been provided for all theoretical claims in the paper.\n\nOne thing that I feel is problematic is: In Theorem 3.3, why is the condition $bc^2 \\\\ge \\\\Omega(\\\\log Tp/\\\\delta)$ not required? The proof seems to simply invoke Theorem 3.4 as the first step, which does seem to have this condition. If this condition is indeed required, then I feel the narrative of the paper changes quite a bit. The story is not really about _any_ gradient descent based method, but only one with \"low precision\" (as defined in Abbe et al. (2021)). In that sense, the paper is really about statistical query learning methods, and the \"gradient descent\" part is not providing that much insight.", "experimental_designs_or_analyses": "The paper is entirely theoretical and there are no experiments.", "relation_to_broader_scientific_literature": "The paper introduces a novel notion of average probabilistic dimension complexity, and shows that it can be upper bounded in terms of the SQ dimension. This is the main result in the paper.", "essential_references_not_discussed": "I think all essential references have been discussed.", "other_strengths_and_weaknesses": "### Strengths\nI think the paper shows a nice result that average probabilistic dimension complexity can be upper bounded in terms of statistical query dimension. While the techniques are borrowed from powerful techniques from prior work, I feel there is some novelty in this technical contribution.\n\n### Weaknesses\n\nI already raised a concern about Theorem 3.3 (main theorem) regarding the condition $bc^2 \\\\ge \\\\Omega(\\\\log Tp/\\\\delta)$ (see \"Theoretical Claims\" section). I feel this breaks the narrative about \"gradient descent\" in the paper.\n\nBut beyond that, I feel the notion of average probabilistic dimension complexity is not _that_ well motivated. In particular, it does not really help with learning a worst case hypothesis in the class, which is the usual setting of learning. All this notion says is that for any prior $\\mu$ over the hypothesis class, there exists a random features representation such that most functions in the class are well approximated. But since this random features representation depends on $\\mu$, this does not lead to learning algorithm. So, from that point of view, I don't fully buy the narrative that having small average probabilistic dimension complexity suggests any limitation of the hypothesis class, even though, I agree that parities are hard even in this sense.", "other_comments_or_suggestions": "I think the notation of average probabilistic dimension complexity would simpler with a single parameter $\\epsilon$, defined as, $\\\\mathrm{adc}\\_\\\\epsilon(\\\\mu)$ equal to the smallest $d$ such that there exists a distribution $\\\\mathcal{E}$ over $d$-dimensional representations such that $\\\\mathbb{E}\\_{h \\\\sim \\\\mu} \\\\sup\\_{\\\\rho \\\\in \\\\Delta(X)} \\\\mathbb{E}\\_{\\\\phi \\\\sim {\\\\cal E}} \\\\inf\\_{w} {\\\\cal L}^{\\\\mathcal{D}\\_{h, \\\\rho}}\\_{01}(\\\\langle w, \\\\phi \\\\rangle) \\le \\epsilon$. It is possible to convert to the two parameter version by using Markov's inequality, since only the case of small constant $\\delta$ is considered.\n\nIncidentally, there is [another paper](https://arxiv.org/abs/2411.10784) that also tries to address the conjecture in Kamath et al. (2021), but it does it in a very different way, by considering partial functions. I believe the techniques are also very different. But it might still be interesting to discuss this paper in the context of the conjecture.\n\nI was looking at the paper of Kamath et al. (2021), and they have a notion of probabilistic distributional dimension complexity $\\\\mathrm{dc}\\_{\\\\epsilon}^{\\\\mathcal{D}}$ and they show an \"infinite gap\" between this and deterministic dimension complexity. Is there any relation between $\\\\sup\\_{\\\\mathcal{D}} \\\\mathrm{dc}\\_{\\\\epsilon}^{\\\\mathcal{D}}(F)$ and $\\\\sup_{\\\\mu} \\\\mathrm{adc}_{\\\\varepsilon}(F)$ (as in the one-parameter version of $\\\\mathrm{adc}$ defined above)? Maybe there isn't, but I was just wondering.\n\n### Minor comments\n* Line 215 (left): There seems to be some typo in definition of $\\phi_t : X\\\\{\\pm 1\\\\} \\to [-1, 1]$", "questions_for_authors": "I would like to hear from the authors regarding the weaknesses pointed out above.", "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": "", "extra_scores": {}}, {"review_id": "CTlNaaJzDn", "reviewer": "Reviewer_7FE4", "summary": "This paper proposes a new link between learning a parametric model with mini-batch stochastic gradient descent (SGD) and the approximation of a function class by random features: if a family of functions can be learned, then there exists a distribution of random features (in dimension that is polylogarithmic in all relevant parameters) so that all functions in the family can be well approximated by a linear combination of features.\n\nThis is done with a new notion of dimension complexity (\"adc\"), and through a reduction to statistical query learning.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer 7FE4,\n\nThank you for your review, we hope to answer your questions below.\n\n> (1) Is there any issue with the fact that stochastic gradient descent may have difficulties reaching a global minimum? (I suspect not)\n\nNo, since the statement considers probably approximately correct learnability in terms of the global optimum.\n\n> (2) Could you clarify which losses are considered and where, as at the moment it is a bit unclear? (e.g., from line 165, it could be both square and 0/1, but this is probably not the case any more for GD as 0/1 is not differentiable, so the one in line 192 is probably the square loss).\n\nRight now we are using sq loss for the bSGD learning, since as you say it needs to be differentiable. For the random features, we are using 0-1 loss. However, in both cases, we could potentially consider other losses. To generalize the sq loss in bSGD learning, we can use the flexibility of the conversion from bSGD to SQ of [1]. For flexibility on the 0-1 loss, we could use a different boosting theorem (we use an adaboost theorem). If there is a boosting theorem that we can use to boost weak learners on 0-1 loss to a strong learner under a different loss function, then this should allow one to expand the conclusion to other loss functions.  \n\n> (3) The paper focuses on target function classes with values in {-1,1} and the square loss, which is not the standard in ML. Would this apply to logistic loss as well?\n\nOur results start by invoking the transformation of [1], to convert a bSGD algorithm into a related SQ algorithm. In [1], the proof of this transformation considers square loss on labels {0,1}, but the choice of loss function can indeed be modified up to change of technical details in the proof. What is important is the differentiability. So, yes, our results could begin with bSGD on logistic loss instead.\n\n[1] Abbe, E., Kamath, P., Malach, E., Sandon, C., and Srebro, N. On the power of differentiable learning versus pac and sq learning. Advances in Neural Information Processing Systems, 34:24340–24351, 2021.", "claims_and_evidence": "The authors do their best to show how the theorem is proved, but given that I was not familiar with the papers that the current paper builds on (e.g., the paper by Abbe et al.), it is hard for me to understand the proof and its validity (in a traditional reviewing form, I would put low confidence, but this does not seem to be possible here).\n\nAs in most theory papers, the authors also rightfully try to interpret their result. They claim surprise in the proposed equivalence, with the underlying understanding that linear random features are a form a weak learners. \n\nI mostly agree with them with the fact that it is surprising that learnability by mini-batch SGD implies the existence of a random feature distribution. However, the author should insist more on the fact that the distribution of random feature is unknown and depends on the function class in ways unknown to a practitioner. Most of the related work that the paper describes corresponds to explicit random features.", "methods_and_evaluation_criteria": "N/A (theory paper)", "theoretical_claims": "Not in details.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper makes the effort of relating to previous work, but since I don't know that line of work, I can't tell if this is done correctly or not.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "*", "other_comments_or_suggestions": "In the related work section, the description of the work of Chizat et al. , 2019 (on lazy training) is inaccurate: all layers do not move, and not only the bottom layer, showing that the NTK regime is achieved.", "questions_for_authors": "(1) Is there any issue with the fact that stochastic gradient descent may have difficulties reaching a global minimum? (I suspect not)\n(2) Could you clarify which losses are considered and where, as at the moment it is a bit unclear? (e.g., from line 165, it could be both square and 0/1, but this is probably not the case any more for GD as 0/1 is not differentiable, so the one in line 192 is probably the square loss).\n(3) The paper focuses on target function classes with values in {-1,1} and the square loss, which is not the standard in ML. Would this apply to logistic loss as well?\n\nADDED AFTER REBUTTAL\nThanks for your responses. If the paper ends up being accepted and you have one more page, I would strongly suggest to make it more self contained. It currently requires to know in depth several other papers without much explanation. This would greatly increase its impact.", "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": "", "extra_scores": {}}, {"review_id": "xIIpqtc9Av", "reviewer": "Reviewer_AcC1", "summary": "This paper studies the learning capacity of stochastic gradient algorithms. The main results focus on the case of binary classification with either square loss or $01$-loss trained with mini-batch SGD with $c$-approximate clipped gradient. Moreover it is assumed that the data is generated using a function in the considered function class $\\mathcal{F}$, ie, we are in a realisable setting. In this setting, it is shown that if the algorithm is able to learn a good predictor regardless of the source data distribution (which is generated by a feature distribution and a function in $\\mathcal{F}$), then most of the functions of the function class can be approximated by a linear combination of random features, in a certain sense. This result has two main interpretations: first it means that if we want a gradient algorithm to work on every data distribution, then it not necessary to use models that are more complex than random features. On the other hand, it shows that the function classes that can be learnt from SGD in a distribution-free way mostly contain simple functions. The authors prove their result by extending existing statistical tools, in particular buy introducing a notion of average probabilistic dimension complexity.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer AcC1,\n\nThank you for your thoughtful consideration. We will respond directly to the potential weaknesses that you outlined, as well as your questions.\n\n> The analysis is limited to binary classification and in particular does not encompass regression problems. The mains theorems are restricted to the square loss, which might be restrictive in the case of binary classification.\n\nYes, we consider classification, but our results can extend to other loss functions like bSGD with logistic loss, instead of sq loss. This is true because of the flexibility of the transformation from bSGD to SQ of [1]. Additionally, we do not rule out obtaining an analogous result with sq loss or logistic loss instead of 0-1 loss for the random features. To accomplish that, we could use a different boosting theorem (we use an adaboost theorem). If there is a boosting theorem that we can use to boost weak learners on 0-1 loss to a strong learner under a different loss function, then this should allow one to expand the conclusion to other loss functions.  \n\n> The setup is restricted to the realisable case, ie, when the function class contains the optimal predictor that has been used to generate the data distribution. This might not be realistic in a modern machine learning setting.\n\nOur setup is separate from realizable / non-realizable learning. Note, we do not make *any* restrictions on the class $\\cal{F}$ of functions (it can be the set of all functions). Instead, complexity is implicitly handled because our theorem’s conclusion (i.e., the size of the random feature representation) is expressed in terms of the number of parameters and gradient steps needed to learn the class $\\cal{F}$. For example, if the number of parameters or gradient steps needed to learn $\\cal{F}$ is massive due to huge complexity of $\\cal{F}$, then the random feature representation would also be massive. A typical example to keep in mind for this case is learning the set of parity functions of the uniform hypercube with bSGD.\n\n**Questions**\n\n> Is it possible to extend the results to cross-entropy loss and / or regression problem?\n\nYes to cross-entropy, please see the answer to your first weakness above. For regression, it is likely that new techniques would be needed, but we don't think it is inherently impossible.\n\n> Can you explain why SGD with c-approximate clipped gradient is considered? Does you results hold with vanilla SGD? This part is not clear to me.\n\nIn short, our theorem is not true for non-clipped gradients. GD with non-clipped gradients is as powerful as general PAC-learning (see [1]), so it’s not possible to convert such algorithms to random features with violating SQ lower bounds.\n\n> What is the notation suph←A? The way the error is defined in section 3.2 is not clear to me.\n\nSupremum is used because we consider worst-case behavior for gradient clipping/rounding. That is, error is with respect to a valid gradient clipping chosen by an adversary at each gradient step. Please see line 195 for explanation of how the gradient clipping works.\n\n> You mention the 01-loss, but how can this be used in your results, as you consider gradient-based optimisation?\n\nThe 01 loss is only used to evaluate the random feature representation, which is constructed from the bSGD algorithm. For the bSGD algorithm, indeed the loss must be differentiable such as sq loss or a logistic loss.\n\n> Do your results extend to the case where there is label noise, ie, the data is not generated using a deterministic predictor\n\nWe don’t rule out this possibility, but extending it to this setting requires verifying that nothing breaks down across the variety of transformations we have borrowed from other works. For example, the transformation from bSGD to SQ from [1], and SQ lower bounds from [2].\n\n[1] Abbe, E., Kamath, P., Malach, E., Sandon, C., and Srebro, N. On the power of differentiable learning versus pac and sq learning. Advances in Neural Information Processing Systems, 34:24340–24351, 2021.\n\n[2] Blum, A., Furst, M., Jackson, J., Kearns, M., Mansour, Y., and Rudich, S. Weakly learning dnf and characterizing statistical query learning using fourier analysis. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pp. 253–262, 1994.", "claims_and_evidence": "The main claims are well explained, first in an informal way and then more formally with proofs.", "methods_and_evaluation_criteria": "The approach seems to be well-aligned with the existing literature and makes sense for proving the claims.", "theoretical_claims": "I did not check the correctness of the theoretical claims, as the involved tools are a bit far from my expertise.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The authors extend the setting of (Abbe et al., 2021) and the links with the aforementioned paper are made clear. \nMoreover, an existing notion of probabilistic dimension complexity from (Kamath et al., 2020) is extended.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Here are a few potential weaknesses:\n - The analysis is limited to binary classification and in particular does not encompass regression problems. The mains theorems are restricted to the square loss, which might be restrictive in the case of binary classification.\n - The setup is restricted to the realisable case, ie, when the function class contains the optimal predictor that has been used to generate the data distribution. This might not be realistic in a modern machine learning setting.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "- Is it possible to extend the results to cross-entropy loss and / or regression problem?\n- Can you explain why SGD with $c$-approximate clipped gradient is considered? Does you results hold with vanilla SGD? This part is not clear to me.\n- What is the notation $\\sup_{h\\leftarrow A}$? The way the error is defined in section 3.2 is not clear to me.\n- You mention the $01$-loss, but how can this be used in your results, as you consider gradient-based optimisation?\n- Do your results extend to the case where there is label noise, ie, the data is not generated using a deterministic predictor", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proves a novel theoretical connection between a model’s optimizability by gradient descent and its approximability by random features, characterized by a new average variant of the probabilistic dimension complexity and using tools from statistical-query learning and community complexity theories. In a nutshell, it shows if a differentiable parametric model can be successfully optimized by a distribution-free and unnecessarily very precise mini-batch gradient descent technique, then the model can be well approximated by a linear combination of random features with high probability (w.r.t. a prior distribution on the model space) where the combination size is upper bounded by a polynomial function of the descent step size. This can be interpreted as a fundamental limitation of distribution-free learning i.e., if a model class is learnable by distribution-free gradient descent, then it is approximable by a random feature representation and thus inherits its known limited expressive power. 

--- 

All reviewers find the paper acceptable, and most commend the theoretical contribution. A notable issue raised by reviewers NhLC/7FE4/AcC1 is the choice of squared loss instead of 0-1 loss for measuring classification error. In rebuttal, authors explain this is due to the invoking of a prior result that transforms gradient descent to statistical-query learning which considers squared loss, and clarify more general loss functions can be chosen as long as they are differentiable. In addition, reviewer 9ucH suggests the condition of `low precision’ is not sufficiently discussed which may change the narrative quite a bit, but raises his score after authors provide more explanations in rebuttal and promise to add more in the final paper. 

Overall, the paper provides an interesting and novel theoretical insight backed up by solid and novel theoretical justifications. I think its contribution outweighs the slightly restrictive (yet seemingly extendible) setting and a few clarity issues in presentation. The paper could be accepted if there is a room in the program. Should it be accepted, authors are encouraged to incorporate all feedback in revision, especially regarding the discusssions on 0-1 loss and low-precision condition -- perhaps a more appropriate claim is a model optimizable by low-precision gradient descent has limited expressive power? 

---

p.s. While the work is well contextualized in the deep learning literature, I’m curious if it may have any connection to the broader random feature literature e.g., [1,2]. (not a must) 

[1] Weighted Sums of Random Kitchen Sinks: Replacing minimization with randomization in learning, NeurIPS 2008. 

[2] Generalization Properties of Learning with Random Features, NeurIPS 2017.
Decision: Accept (poster)