Learnability of high-dimensional targets by two-parameter models and gradient flow

Authors: dmitry  yarotsky
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-04 22:58:51

Abstract: We explore the theoretical possibility of learning $d$-dimensional targets with $W$-parameter models by gradient flow (GF) when $W<d$. Our main result shows that if the targets are described by a particular $d$-dimensional probability distribution, then there exist models with as few as two parameters that can learn the targets with arbitrarily high success probability. On the other hand, we show that for $W<d$ there is necessarily a large subset of GF-non-learnable targets. In particular, the set of learnable targets is not dense in $\mathbb R^d$, and any subset of $\mathbb R^d$ homeomorphic to the $W$-dimensional sphere contains non-learnable targets. Finally, we observe that the model in our main theorem on almost guaranteed two-parameter learning is constructed using a hierarchical procedure and as a result is not expressible by a single elementary function. We show that this limitation is essential in the sense that most models written in terms of elementary functions cannot achieve the learnability demonstrated in this theorem.

Main paper: 
 introduction: 
 Starting from the works of Cantor [Cantor, 1878] , it is well-known that all finite-dimensional (or even countably-dimensional) real spaces are equinumerable and so, in principle, a set of several real numbers is as descriptive as a single number, or in other words multi-dimensional vectors can be represented by scalars. The idea of reduction of higher-dimensional descriptions to lower-dimensional ones has since appeared in many mathematical works. A couple of notable examples are continuous space-filling curves that fill the whole R d [Peano, 1890 , Hilbert, 1891] and the Kolmogorov-Arnold Superposition Theorem (KST, Kolmogorov [1957] ) that states that any multivariate continuous function can be exactly represented in terms of compositions and sums of finitely many univariate continuous functions.In the context of machine learning, these results suggest that models with a small number of parameters can potentially be used to represent or approximate high-dimensional objects. In particular, Maiorov and Pinkus [1999] give an example of neural network that has a fixed number of weights but can approximate any continuous function: Theorem 1 (Maiorov and Pinkus 1999) . There exists an activation function σ which is real analytic, strictly increasing, sigmoidal (i.e., lim x→-∞ σ(x) = 0 and lim x→+∞ σ(x) = 1), and such that any f ∈ C([0, 1] n ) can be uniformly approximated with any accuracy by expressions6n+3 i=1 d i σ( 3n j=1 c ij σ( n k=1 w ijk x k + θ ij ) + γ i ) with some parameters d i , c ij , w ijk , θ ij , γ i .Refinements of this result are given by Guliyev and Ismailov [2016, 2018a,b] . While Theorem 1 contains a non-explicit function σ, Boshernitzan [1986] , Laczkovich and Ruzsa [2000] , Yarotsky [2021] give examples of fully explicit fixed-size analytic expressions that also can approximate arbitrary continuous functions. KST has inspired many other results on expressiveness of machine learning models, see e.g. Montanelli and Yang [2020] , Schmidt-Hieber [2020] , Kȗrková [1991 Kȗrková [ , 1992]] , Köppen [2002] , Igelnik and Parikh [2003] . The idea of space-filling curves is used in recent works on generating higher-dimensional distributions from low-dimensional ones [Bailey and Telgarsky, 2018 , Perekrestenko et al., 2020 , 2021] .While the model appearing in Theorem 1 looks like a standard neural network (apart from the special activation), the proof of its universal approximation property has nothing to do with the method of gradient descent (GD) invariably used nowadays to train neural networks. The proofs of the universal approximation property in this and similar theorems (including the classical universal approximation theorems of Cybenko [1989] , Leshno et al. [1993] that consider neural networks with a growing number of neurons) normally consist in presenting, or demonstrating existence of, parameters making the model output arbitrarily close to the target f . There is no guarantee whatsoever that these parameters can actually be learned by GD. Moreover, learning by GD is especially problematic for models with a small number of parameters.In this regard, note that modern deep neural networks are typically abundantly parameterized, with the largest models containing hundreds of billions of weights [Brown et al., 2020 , Smith et al., 2022] . One obvious reason for that is the necessity to store a substantial amount of information. But another, more subtle property of large models is that they are easier to train by GD-based optimization [Choromanska et al., 2015] , which can be explained by the optimizer having more freedom in finding good descent directions, in particular evading spurious local minima and saddle points.A convincing and rigorous demonstration that overparameterization may be beneficial for training is provided by the infinite width limits of neural networks in regimes such as NTK [Jacot et al., 2018] and Mean-Field [Mei et al., 2018 , Rotskoff and Vanden-Eijnden, 2018 , Chizat and Bach, 2018] . While the number of weights in these limits is effectively infinite, the resulting macroscopic loss surface is relatively simple (even convex after reparameterization, in the NTK case); the GD dynamics is analytically tractable and, under mild assumptions, provably trains the model to perfect fit.In contrast, if the number of parameters is small, then the loss surface tends to be rough and GD inefficient [Baity-Jesi et al., 2018] . Suboptimal local minima are known to be a general feature of finite neural networks with nonlinearities [Auer et al., 1995 , Yun et al., 2018 , Swirszcz et al., 2016 , Zhou and Liang, 2017 , Christof and Kowalczyk, 2023] . As the number of parameters is decreased, the chances for GD to get trapped in a bad local minimum increase [Safran and Shamir, 2018] .The above discussion raises a natural abstract question that we address in the present paper:Can models with a small number of parameters learn high-dimensional targets by gradient descent?In other words, we ask if the possibility of a reduction of a high-dimensional target space to a low-dimensional parametric description reflected in Theorem 1 can at least theoretically be combined with learning by GD, or if this is prevented by fundamental obstacles.We are not aware of existing rigorous results addressing this question. As remarked, existing results on approximation by highly expressive models do not discuss learning by GD, while publications on GD usually consider standard models such as conventional neural networks. However, we want to address the above question in the most abstract way without assuming any particular model structure. It is clear that models having a small number of parameters and yet GD-learnable, if at all possible, require a very special design.Our contribution in this paper is a resolution of the above question. 1. Our main result is the proof that if the learned targets are represented as d-dimensional vectors and are described by a probability distribution in R d , then there exist models with just W = 2 parameters that can learn these targets by Gradient Flow (GF) with success probability arbitrarily close to 1 (Theorem 6).2. We show that Theorem 6 is actually close to being optimal, since underparameterization with W < d generally implies severe constraints on the set of GF-learnable targets:(a) Under a mild nondegeneracy assumption, the GF-learnable targets are not dense in R d (Theorem 3). In particular, the success probability cannot generally be made exactly equal to 1 in Theorem 6. (b) In contrast, the non-learnable targets are dense in R d . Moreover, any subset of R d homeomorphic to the W -sphere contains non-learnable targets (Theorem 4).(c) The number of parameters in Theorem 6 cannot be decreased to one. 3. In the proof of Theorem 6, the model is constructed using an infinite hierarchical procedure making it not expressible by a single elementary function. We conjecture that the result established in Theorem 6 cannot be achieved with models implementable by elementary functions. For such functions not involving sin or cos with unbounded arguments, we prove this as a consequence of the closure of the model image having zero Lebesgue measure in the target space.We describe the details of our setting in Section 2. In Section 3 we give several general results showing that the underparameterized (W < d) learning is theoretically challenging. Then, in Section 4 we present our main result on the almost guaranteed learnability with two parameters. After that, in Section 5 we consider models expressible by elementary functions. Finally, in Section 6 we summarize our findings and discuss several questions that are left open by our research.Some (more complex or less important) proofs are given in the appendix; in these cases the respective sections are indicated in the theorem statements.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
the setting: 
 In supervised learning one is usually interested in learning target functions (or simply targets) f : X → Y , with some input and output spaces X and Y . We will consider the setting in which the space of targets is a linear space with a euclidean structure. To this end, suppose that Y is a euclidean space with a scalar product ⟨•, •⟩, and X is endowed with a measure ν reflecting the distribution of inputs x ∈ X of the function f . One can then form the Hilbert space L 2 (X, Y, ν) of functions f : X → Y equipped with the standard scalar product ⟨f, g⟩ = X ⟨f (x), g(x)⟩ν(dx). We will assume that the target space H is a (finite-or infinite-dimensional) subspace of this Hilbert space L 2 (X, Y, ν).1. The full space H = L 2 (X, Y, ν) represents all maps f : X → Y distinguishable on sets of positive measure ν. If Y = R m with the standard scalar product and ν = 1 N N n=1 δ xn is an empirical distribution corresponding to a finite subset of X, then H is finite-dimensional, H ∼ = R d with d = N m. On the other hand, if ν is not finitely supported, then dim H = ∞. 2. Let X = R n , Y = R, and the targets f : X → Y be linear functions. If ν is nondegenerate in the sense that the covariance matrix[ x i x j ν(dx)] n i,j=1 is full-rank, then the respective target space H is n-dimensional (otherwise, dim H < n). 3. Let X = R n , Y = R,and the targets be polynomials of degree not larger than q. Then dim H ≤ n+q q , with equality attained for suitably nondegenerate measures ν.We will often write the function f considered as an element of H as f . Throughout the paper, we refer to the dimension of the target space H as target dimension and denote it by d. Note that the target dimension d is not to be confused with the dimensions of X and Y (in fact, X does not even have to be a linear space and have a dimension). Rather, the target dimension d is the number of scalar parameters required to specify a particular target f within the space H of considered targets.Suppose that we are learning the target f ∈ H using a parametric model with W parameters. We will view this model as a map Φ : R W → H between the parameter space R W and the target space H.We will consider Gradient Flow (GF), i.e. the continuous version of gradient descent. Learning by GF prescribes that the parameter vector w be evolved byEQUATIONwhere we use the standard square loss,EQUATIONHere, the subscripts Y, H on the norms indicate the respective spaces. We will assume for definiteness that GF starts from w(t = 0) = 0.We will always assume that W is finite and Φ is differentiable with a Lipschitz-continuous differential.In this case Eq. ( 1) is, by Picard-Lindelöf theorem, uniquely solvable locally (i.e., for a bounded interval of times). It is possible to relax the Lipschitz differentiability assumption using the special structure of the gradient flow equation (see e.g. the expository paper Santambrogio [2017] ), but we will not need this in this work.In fact, GF (1) is solvable not only locally, but also globally, i.e. the solution w(t) exists for any t > 0. Indeed, the only obstacle for the global existence is the divergence of the solution in finite time, but it is ruled out by the inequality∥w(t)∥ 2 ≤ t 0 ∥ dw(τ ) dτ ∥dτ 2 ≤ t t 0 ∥ dw(τ ) dτ ∥ 2 dτ (3) = -t t 0 dL f (w(τ )) dτ dτ = (L f (0) -L f (w(t)))t ≤ L f (0)t.Let F Φ denote the set of targets f for which the respective GF converges to f :F Φ = {f ∈ H : inf t L f (w(t)) = 0 for w(t)given by (1)}.(4)Our goal in the remainder of this work will be to examine if we can ensure, by a suitable design of the map Φ : R W → R d with W < d, that the set F Φ is sufficiently large. 1 We will refer to targets f ∈ F Φ as GF-learnable or simply learnable. We remark that, assuming a standard norm topology in H, the set F Φ is Borel-measurable as the countable intersection of the open sets {f ∈ H : inf t L f (w(t)) < 1/n, where w(t) is given by (1)}, n = 1, 2, . . .To clarify our setting, suppose that we fit to data a linear function f (x) = k T x with k, x ∈ R d for some d (see example 2 earlier in the section). Normally, this function is learned by applying GF to the d-dimensional parameter vector k. In our setting, however, we rather rewrite this model in the form y = Φ(w) T x, with some generally nonlinear Φ : R W → R d , and ask if we can learn the model by using GF w.r.t. w with W < d. In this sense, we decouple the linear weight-dependence from the linear input-dependence and replace it by a nonlinear one.Note that formulation (1)-(2) of GF is stated purely in terms of vectors and maps in Hilbert spaces, without any reference to the underlying sets X, Y and the measure ν. It is this abstract Hilbert space formulation that we will deal with in the remainder of the paper. Some of our results, including the main "positive" Theorem 6, require the target Hilbert space to be finite-dimensional, i.e. H ∼ = R d with d < ∞. Others (namely the "negative" Theorems 2, 3, 4) remain valid for infinite-dimensional Hilbert spaces H. By a slight abuse of notation, in this latter case we also write H ∼ = R d , but with d = ∞.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: Our work is a comprehensive theoretical study of the addressed question (i.e., learnability of targets using models with a small number of parameters and gradient flow). We provide both positive (Theorem 6) and negative (Theorems 2, 3, 4, 8, 10) results. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
general impossibility results: 
 We start with several general results showing fundamental limitations of GF with a small dimension W . First, it is easy to see that one-parameter models can ensure GF convergence only for a very small set of targets. Proposition 2. Let W = 1. Then, if a target f ∈ F Φ , then either f = Φ(w) for some w, or f ∈ {f -, f + } = {lim w→±∞ Φ(w)} (if any of these two limits exist). In particular, ifH = R d with 2 ≤ d < ∞, then F Φ has Lebesgue measure 0 in H.Proof. The first statement follows since the optimization trajectory w(t) is a scalar monotone function of t. The second statement on Lebesgue measure follows by Sard's theorem.The next result shows that if W < d and Φ is sufficiently regular and non-degenerate at w = 0, thenF Φ cannot be dense in H. G Φ(R W ) g(y t ) g(-y t ) Φ(z t )Figure 1 : Proof of Theorem 4. GF cannot converge for all points of G: such a convergence would require Φ(z t ) to be simultaneously close to both g(y t ) and g(-y t ), which are far from each other.Theorem 3. Let 1 ≤ W < d ≤ ∞ and Φ : R W → H be a C 2 map such that at w = 0 the Jacobi matrix J 0 = ∂Φ ∂w (0) has full rank W . Then F Φ is not dense in H.Proof. We show that there is a ball of targets for which the GF trajectory gets trapped at a local minimum due to a loss barrier. Without loss of generality, assume that Φ(0) = 0. Let f 0 ∈ R d be some length-l vector orthogonal to the range of the differential J 0 ; such an f 0 exists becaused > W . Let B f0,ϵ = {f ∈ R d : ∥f -f 0 ∥ < ϵ}. Since Φ is C 2 , we have Φ(w) = J 0 w + R(w),with a remainder ∥R(w)∥ ≤ C∥w∥ 2 for all sufficiently small ∥w∥ with some constant C. Then, for f ∈ B f0,ϵ we haveL f (w) -L f (0) = 1 2 ∥f -Φ(w)∥ 2 -1 2 ∥f ∥ 2 = 1 2 ∥Φ(w)∥ 2 -⟨f , Φ(w)⟩ ≥ 1 2 ∥J 0 w∥ 2 -(Cl∥w∥ 2 + ∥J 0 ∥ϵ∥w∥) + O(ϵ 2 + ∥w∥ 3). Since rank J 0 = W , the matrix J * 0 J 0 is strictly positive definite. Choose l small enough so that J * 0 J -Cl is still strictly positive definite. Then, if we subsequently choose r and then ϵ small enough, we have L f (w) -L f (0) > 0 for all w such that ∥w∥ = r, i.e. for f ∈ B f0,ϵ the GF trajectory w(t) never leaves the ball U r = {w ∈ R W : ∥w∥ ≤ r}. Then, since Φ is continuous, if ϵ < l and r is small enough, B f0,ϵ ∩ Φ(U r ) = ∅ and so the ball B f0,ϵ cannot be reached by GF.Finally, we show that for W < d any subset of R d homeomorphic to the W -sphere contains non-learnable targets: Theorem 4. Let 1 ≤ W, d ≤ ∞. Suppose that a set G ⊂ R d is the image of the W -dimensional sphere S W = {y ∈ R W +1 : ∥y∥ = 1} under a continuous and injective map g :S W → R d . Then G ̸ ⊂ F Φ .Proof (see Figure 1 ). We use the Borsuk-Ulam antipodality theorem saying that for any continuous map ϕ : S W → R W there exists a pair of antipodal points y, -y ∈ S W such that ϕ(y) = ϕ(-y).Let w f (t) denote the solution of GF (1) with target f . For any t > 0, consider the map ϕ t : S W → R W given by ϕ t (y) = w g(y) (t). By the assumption on g and the continuous dependence of GF on the target, the map ϕ t is continuous. By Borsuk-Ulam, it follows that there is y t ∈ S W such that ϕ t (y t ) = ϕ t (-y t ). Denote this common output vector by z t .Let l = inf y∈S W ∥g(y) -g(-y)∥. Observe that l > 0, by the continuity and injectivity of g as well as compactness of S W . Then for any tEQUATIONNow suppose that G ⊂ F Φ . Then for any y ∈ S W the function t → L g(y) (w g(y) (t)) monotonically converges to 0 as t → ∞. However, since S W is compact and L g(y) (w g(y) (t)) is continuous in y, such a convergence must be uniform over y ∈ S W , contradicting the lower bound (5).Note that we did not assume that W < d in this theorem, but it is vacuous for W ≥ d because (again by Borsuk-Ulam) there are no continuous injective maps g : S W → R d . On the other hand, there are plenty of such maps for W < d, implying in particular the following corollary.Corollary 5. If W < d, then H \ F Φ is dense in H.Our use of the Borsuk-Ulam theorem is inspired by DeVore et al. [1989] who used it to establish lower bounds on nonlinear n-widths in an abstract approximation setting.Figure 2 : In Theorem 6, we ensure that the learnable set of targets F Φ contains a multidimensional "fat" Cantor set F 0 having almost full measure µ. The set F 0 has the formF 0 = ∩ ∞ n=1 ∪ α B (n) α , where {B (n)α } n,α is a nested hierarchy of rectangular boxes in R d . Here, n is the level of the hierarchy and α is the index of the box within the level.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
almost guaranteed learning with two parameters: 
 Results of the previous section show that for models with W < d parameters there is always a significant amount of non-learnable targets, and models with just W = 1 parameter cannot learn sets of targets of positive Lebesgue measure. We give now our main result showing that already with W = 2 parameters, one can design maps Φ : R W → R d for which the learnable set is arbitrarily large with respect to a given probability distribution on the target space: Theorem 6 (A). Let H = R d with d < ∞, and let µ be any Borel probability measure on H. Then for any ϵ > 0 there exists a C ∞ map Φ : R 2 → H such that µ(H \ F Φ ) < ϵ.Example: Suppose again that we learn a linear functionf k (x) = k T x with k, x ∈ R d for some d.Assuming a non-degenerate distribution of inputs ν, the target space H ∼ = R d . Suppose now that possible coefficient vectors k have, say, the prior distribution µ ∼ N (0, 1 d×d ) in R d . Then Theorem 6 states that for any ϵ > 0 there exists a two-parameter model Φ : R 2 → R d such that for all target vectors k except for a set of µ-measure ϵ, for the GF trajectory w(t) ∈ R 2 defined by (1) we havelim t→∞ Φ(w(t)) = f k .We give now a sketch of proof of Theorem 6, illustrated by Figures 2 and 3a-3c .The key challenge in proving this theorem is to ensure that for a majority of targets f the GF trajectory will not be trapped at a local minimum. This is difficult because, due to the low parameter dimension, a typical point w in the parameter space belongs to a large number of optimization trajectories with different targets f , and all these trajectories are controlled by a single map Φ : R 2 → R d .The key idea of our construction is to implement an aligned hierarchical decompositions of both the parameter and target spaces so that each element of the hierarchy of target subsets can be served by a respective element of the hierarchy of parameter subsets.The targets for which we guarantee learnability form a d-dimensional Cantor set F 0 (product of one-dimensional sets) of almost full measure µ (see Figure 2 ). This Cantor set is constructed by a sequence of "carving" (or "splitting") stages. Accordingly, the map Φ is sub-divided into a sequence of maps Φ (n) associated with stripes of the w-plane and aligned with the respective carving stages (see Figures 3a-3b ).One of the two parameters, u, always increases during GF for targets from F 0 , and the map Φ can be described in terms of the "level lines" l u = {(u, v) : v ∈ R} in the parameter space and the respective "level curves" Φ(l u ) in the target space. To define stage-n sub-maps Φ (n) corresponding to levels n of the target Cantor hierarchy, we choose a discretized sequence 0 = u 0 < u 1 < u 2 < . . .. The domains of the maps Φ (n) are then separated by the respective level lines l (n) ≡ l un . The stage-n map Φ (n) can be thought of as describing the transformation of the level curve Φ(l (n) ) to Φ(l (n+1) ).Each stage n is associated with a particular splitting index k n ∈ {1, . . . , d}. The level curve Φ(l (n) ) includes multiple linear segments Φ(l x knx kn+1 x kn+2 v u u n u n+1 u n+2 l un l un+1 l un+2 w(t n ) w(t n+1 ) w(t n+2 ) Φ (n) Φ (n+1) Φ (a)Stage-wise decomposition of the map Φ. The map Φ is defined by its stagesΦ (n) = Φ| un≤u≤u n+1 separated by the level lines l (n) ≡ lu n = {(u, v) : u = un} and respective level curves Φ(l (n) ). Each stage Φ (n) deforms the level curve Φ(l (n) ) in the splitting direction x k n+1 to form the new level curve Φ(l (n+1) ). A non-exceptional GF trajectory w(t) = (u(t), v(t)) passes through all level lines. The splitting indices kn cycle over the values 1, . . . , d to ensure convergence w.r.t. each coordinate.x knx kn+1 B (n+1) 1 B (n+1) 6 Φ(l (n+1) 1 ) Φ(l (n+1) 6 ) f Φ(w(t n )) Φ(w(t n+1 )) v u u n u n+1 l (n) α l (n+1) 1 l (n+1) 6 w(t n ) w(t n+1 ) Φ (n) (b)Box splitting and curve-box alignment at the stage Φ (n) . The stage curve Φ(l (n) ) includes segments l (thick blue). The splitting only affects the coordinates x kn and x k n+1 . During the splitting, gaps are left in the direction x kn between the child boxes, and in the direction x kn between the level curve Φ(l (n) α ) and the child boxes, to accommodate convergent GF trajectories. Each non-exceptional GF trajectory w(t) passes through some aligned segments l(n) α , l (n+1) β . 0 a b 2a x kn x kn+1 B (n+1) 2 u ′ u * u ′′ I(u ′′ ) f Φ(w(t n )) Φ(w(t n+1 )) (c) Transition from Φ(l (n) ) to Φ(l (n+1) ) through intermediate level curves Φ(l u ′ ), Φ(lu * ), Φ(l u ′′ ) (violet).These curves ensure that during the n'th stage, for all targets f = (f1, . . . , f d ) in the respective boxB (n+1) β , a point Φ(w(tn)) having a coordinate Φ kn (w(tn)) ≈ f kn is moved by GF to a point Φ(w(tn+1)) with a coordinate Φ k n+1 (w(tn+1)) ≈ f k n+1 .The points Φ(w(t)) are approximately those closest to f on the respective level curves. To avoid local minima, the level curves Φ(lu) at each u must be deformed at each u so as to bring such points closer to f . The desired propagation from Φ(w(tn)) to Φ(w(tn+1)) can be achieved by first deforming Φ(lu) so as to bring Φ(w(t)) to the tip of the line Φ(lu * ) ("gathering sub-stage"), and then extending this tip so as to let Φ(w(t)) slip off it at the appropriate position x k n+1 ("spreading sub-stage"). α is removed and the map Φ (n) is adjusted so as to ensure that for each target f from the resulting Cantor set F 0 the GF trajectory goes through some aligned pieces Φ(l (n+1) β) to the very point f . In a particular stage n, the GF trajectory "goes around the corner" of the next-level box (see Fig. 3c ), so that the agreement of the current approximation Φ(w(t n )) with f in coordinate k n+1 is substantially improved at the cost of a slightly degrading agreement in coordinate k n . As the boxes become smaller, the overall disagreement between Φ(w(t n )) and f gradually vanishes.For general targets in the current box B (n) α , the GF trajectory can get trapped at a local minimumin particular, if the coordinate f kn+1 of the target is close to the respective coordinate of the aligned level piece Φ(l (n) α ). For this reason, some parts of the box B (n) are removed during splitting for the next stage. The total measure of the removed parts can be made arbitrarily small by adjusting splitting parameters. In this way we ensure that all the vectors f ∈ F 0 are learnable and the measure µ(F 0 ) is arbitrarily close to the full measure. 
models expressible by elementary functions: 
 The model Φ constructed in Theorem 6 involves an infinite hierarchy of maps Φ (n) and as a result (and in contrast to conventional models such as neural networks) is not expressible by a single elementary function. It is natural to ask if this non-elementariness is essential or only a feature of our proof. We conjecture it to actually be a necessary feature of models Φ : R W → R d when W < d and the set F Φ of GF-learnable targets is sufficiently large, say has a positive Lebesgue measure in R d .One setting in which we can prove this conjecture is when the closure Φ(R W ) of the image Φ(R W ) has Lebesgue measure 0. Obviously, this is a sufficient condition for the set F Φ of GF-learnable targets to have Lebesgue measure 0. We show that Φ(R W ) has measure 0 for so-called Pfaffian functions known to have strong finiteness properties [Khovanskii, 1991] . Pfaffian functions include all elementary functions, but not necessarily on the largest domain of their definition; most importantly, sin is Pfaffian only when considered on a bounded interval.Precisely, a Pfaffian chain is a sequence g 1 , . . . , g l of real analytic functions defined on a common connected domain U ⊂ R W and such that the equations ∂gi ∂wj (w) = P ij (w, g 1 (w), . . . , g i (w)), 1≤i≤l 1≤j≤W hold in U for some polynomials P ij . A Pfaffian function in the chain (g 1 , . . . , g l ) is a function on U that can be expressed as a polynomial P in the variables (w, g 1 (w), . . . , g l (w)). Complexity of the Pfaffian function is determined by the length l of the chain, the maximum degree α of the polynomials P ij , and the degree β of the polynomial P , and so can be defined as the triplet (l, α, β).We say that a vector-valued function Φ(w) = (Φ 1 (w), . . . , Φ d (w)) is Pfaffian if each component Φ i is Pfaffian with the same domain U . See Khovanskii [1991] , Zell [1999] , Gabrielov and Vorobjov [2004] for background and further details. The following shows that the set of Pfaffian functions is quite large. Theorem 7 (Khovanskii, "elementary functions are Pfaffian"). Suppose that a function g on a domain U ⊂ R W is defined by a formula constructed from the variables w 1 , . . . , w W using finitely many real numbers, standard arithmetic operations (+, -, ×, /), elementary functions ln, exp, sin, arcsin, and compositions. Suppose that for each w ∈ U the value g(w) is well-defined in the sense that during the computation the functions ln and arcsin are applied on the intervals (0, ∞) and (-1, 1), respectively, and there is no division by 0. Moreover, suppose that there is a bounded interval (a, b) to which the arguments of sin always belong for all w ∈ U . Then the function g is Pfaffian with complexity depending only on the size of the formula and the length of the interval (a, b).Our theorem on learnable targets can then be stated as: Theorem 8 (B). Suppose that Φ : R W → R d is a Pfaffian map and W < d. Then the closure Φ(R W ) has Lebesgue measure 0 in R d . In particular, the GF-learnable targetsF Φ have Lebesgue measure 0 in R d .If Φ is defined by elementary functions involving sin on an unbounded domain, then Φ(R W ) need not have Lebesgue measure 0. As the simplest family of examples, consider Φ = (Φ 1 , . . . , Φ d ) given-1 0 1 -1 -0.5 0 0.5 1 Φ(w(t = +∞)) f Φ(w(t = 0)) x = sin(w) y = sin( √ 2w)Figure 4 : The curve Φ(w) = (sin(w), sin( √ 2w)) densely fills the square [-1, 1] 2 , but for all targets f except for a set of Lebesgue measure 0 the respective GF trajectory w(t) is trapped at a spurious local minimum so that Φ(w(t)) ̸ → f . Corollary 10 shows that this is true for all models (6) with any number of parameters W < d.byEQUATIONwith some constants a ij . Kronecker's theorem [Kronecker, 1884, Gonek and Montgomery, 2016] implies that the points ( j a 1j w j , . . . , j a dj w j ) densely fill the torus (R/2πZ) d as w runs over R W whenever the vectors a i = (a i1 , . . . , a iW ), i = 1, . . . , d, are linearly independent over the rationals Q. Accordingly, in this case Φ(R W ) = [-1, 1] d . However, the GF-learnable targets will still have Lebesgue measure 0 due to the prevalence of trapping local minima, as can be seen by a suitable extension of Theorem 3:Proposition 9 (C). Let 1 ≤ W < d < ∞ and Φ : R W → R d be C 2 .Suppose that for some open U ⊂ R d the first and second derivatives of Φ are uniformly bounded on Φ -1 (U ), and also the Jacobi matrix J(w) = ∂Φ ∂w (w) is uniformly non-degenerate there in the sense that the lowest eigenvalue of J * (w)J(w) is uniformly bounded away from 0 on Φ -1 (U ). Then F Φ ∩ U ⊂ Φ(R W ).Corollary 10 (D). Let 1 ≤ W < d < ∞ and Φ : R W → H = R d be given by Eq. (6) with some constants a ij . Then, regardless of these constants, the set F Φ of respective learnable targets has Lebesgue measure 0.In Figure 4 we illustrate this result for W = 1.Summarizing, Theorems 7, 8 imply that if the scalar components of the map Φ : R W → R d with W < d are elementary functions not involving sin (or related functions) acting on an unbounded domain, then Φ can GF-learn only exceptional targets in R d . Moreover, even if Φ involves sin, there is no obvious mechanism how this would help GF-learn a non-negligible set of targets: examination of the basic family of sin-models (6) in Corollary 10 suggests that GF trajectories would still be predominantly trapped at spurious minima. 
discussion: 
 Main takeaways. Our results show that GF-learning with the number of parameters less than the target dimension is objectively problematic, but not impossible. By Theorems 3 and 4, the set of non-learnable targets is dense in the target space, while the set of learnable targets is not. Also, Theorem 8 shows that the set of learnable targets has zero Lebesgue measure for models expressible by elementary functions not involving sin on an unbounded domain.Nevertheless, we have shown in Theorem 6 that if the targets are described by a known probability distribution, then it is possible to handcraft a (fairly complicated) model with just two parameters that learns the targets with probability arbitrarily close to 1. The learnable targets in our proof form a multi-dimensional Cantor set. Such a complicated structure is not surprising, since by Theorem 4 each subset of the target space homeomorphic to the 2-sphere must contain non-learnable targets. One can expect learnable sets to be more regular for models with a larger number of parameters (see an open question below).Open questions. Our results leave various open questions, especially with regard to more detailed characterization of learnable sets of targets.Target measures with µ(H) = ∞. It was crucial for our proof of main Theorem 6 that we could restrict our attenton to targets lying in a bounded box in R d . We could consider only such targets because if µ is a Borel measure on R d and µ(R d ) < ∞, then µ(H \ B) can be made arbitrarily small for a suitable bounded box B. However, one can ask if Theorem 6 also holds for measures with µ(R d ) = ∞, e.g. the Lebesgue measure. In this case there is no reduction to a bounded box, and our methods don't seem to work.Infinite-dimensional target spaces. We prove Theorem 6 only for finite-dimensional target spaces H, but one can also ask if it holds for an infinite-dimensional separable Hilbert space. As discussed in Section 2, this would cover the case of general distributions of inputs x for target functions.Non-density of the learnable targets for degenerate models. Our proof that the subset F Φ of learnable targets cannot be dense in the target space R d if the number W of parameters is less than d (Theorem 3) heavily relies on the relatively strong assumption that Φ is C 2 and has a full rank Jacobian at the initial point. It would be interesting to clarify if this result holds without nondegeneracy assumptions and under weaker regularity assumptions, say for Φ differentiable with a Lipschitz gradient as sufficient for local integrability of the gradient flow.Learnable sets for general 1 < W < d. It would be interesting to generally describe target sets that can be GF-learned for 1 < W < d. Our Theorem 6 only does that for W = 2 and for a family of multi-dimensional Cantor sets. Theorem 4 imposes weaker conditions on learnable target sets as W increases (since higher-dimensional spheres contain lower-dimensional ones, but not the other way around), suggesting that with higher W learnable sets become larger and more regular.Non-learnability using elementary functions involving sin. As discusssed in Section 5, we expect that the high-probability learning proved in our main Theorem 6 cannot be established using models expressed through elementary functions, even if they involve sin with unbounded arguments.Hierarchical structure of the learnable set. We will construct a set F 0 such that µ(F 0 ) > 1 -ϵ and for a suitable model Φ : R 2 → R d the targets f are Φ-learnable, i.e. F 0 ⊂ F Φ , thus ensuring that µ(F Φ ) > 1 -ϵ. We will occasionally refer to targets from F 0 (respectively, from the complement R d \ F 0 ) and the associated GF trajectories as non-exceptional (respectively, exceptional). The set F 0 has the formF 0 = ∩ ∞ n=1 ∪ α B (n) α , where B (n)α is a nested hierarchy of rectangular boxes in R d (see Figure 2 ). Each level-n box B α do not completely fill this box (we will need the gaps between them to support non-exceptional GF trajectories and to ensure their non-trapping in local minima; see again Figure 3b ). We will ensure, however, that these gaps are small enough so that µ(F 0 ) > 1 -ϵ.In particular, we choose the root box B = B (1) as B = [-c, c] d , where c is large enough so that µ(B) > 1 -ϵ/2. α by what we call splitting (also referred to as carving in the main text). Choose some sequences of splitting coordinates x kn with k n ∈ {1, . . . , d} and integer splitting numbers s n , n = 1, 2, . . . We require that k n+1 ̸ = k n for all n.The number of child boxesB (n+1) β contained in the parent box B (n)α is 2s n (e.g., s n = 3 in Figure 3b ). The splitting of the parent box B The splitting along x kn will ensure that the GF trajectory gets closer to the target in the (x kn , x kn+1 )plane, while the x kn+1 -contraction of the boxes will be used to avoid getting trapped at a local minimum. We will return later to the conditions on the splitting numbers and coordinates necessary to ensure that F 0 ⊂ F Φ and µ(F 0 ) > 1 -ϵ.The two parameters and u-monotonicity. Let u and v be the two parameters of the model, so that w = (u, v). These two parameters will play very different roles. We will ensure that for all nonexceptional targets f ∈ F 0 , u(t) is a monotone increasing function of t on the whole GF trajectory (u-monotonicity). To this end, we ensure that the whole trajectory w(t) belongs to a domain in R 2 in which ∂ u L f < 0, so that du dt > 0 by definition of GF. In particular, this allows to parameterize the trajectories w(t) and Φ(w(t)) by u ≥ 0.Level curves. The map Φ can be described in terms of the curves Φ(u, v) where u is fixed and v varied. We refer to the respective straight lines l u = {(u, v) : v ∈ R} ⊂ R 2 in the parameter space as level lines and the curves Φ(l u ) ⊂ H in the target space as level curves. A GF trajectory w(t) can be specified by a single point on each level line l u .Level-set-based description of Φ. It will be convenient to simplify the description of the map Φ by only describing the level curves Φ(l u ) as subsets of H, without specifying parameterizations v → Φ(u, v). This simplified description can be justified by making the variable u slow and keeping the variable v fast, in the following sense. Suppose that we already have some map Φ : R 2 → H, and define a new map Φ by stretching the variable u by a large factor λ: Φ(u, v) = Φ(u/λ, v). This rescales the u-derivative:∂ u Φ = λ -1 ∂ u Φ. Then, at λ ≫ 1 we have |∂ u Φ| ≪ |∂ v Φ| and accordingly |∂ u L f | ≪ |∂ v L f | unless |∂ v Φ| ≈ 0.This means that GF associated with Φ proceeds in the v-direction much faster than in the u-direction (i.e., transition along a level curve occurs much faster than from one level curve to another) unless near a v-stationary point. This implies that each point w(t) of a GF trajectory can be approximately found by locally minimizing the distance to the target on the level curve Φ(l u(t) ):EQUATIONIn general, the minimizer here should be local, but in our construction of Φ it will also be global. This approximation can be made arbitrarily accurate by sufficiently stretching the parameter u.Since w * (u) only depends on u, the trajectory w(t) is approximately independent of how level curves are parameterized by v. Accordingly, in the sequel we can ignore the details of this parameterization and just describe the level curves as subsets of H rather than functions of v.The aligned hierarchical structure of Φ (Fig. 3a ). Our construction of Φ is described in terms of a hierarchical structure of level sets aligned with the hierarchy of boxes B(n) α . First, let 0 = u 0 < u 1 < u 2 < . . . be a sequence of particular values of u. We construct the map Φ separately for each strip {(u, v) : u n ≤ u ≤ u n+1 }. We refer to the respective restriction Φ (n) ≡ Φ| un≤u≤un+1 as the n'th stage of Φ. The monotonicity of u(t) for targets f ∈ F 0 will ensure that each respective trajectory w(t) sequentially passes through all the stages in their natural order. We denote by l (n) ≡ l un the level lines serving as the boundaries for the domains of the stages Φ (n) .Each stage Φ (n) is associated with the splitting of the level-n boxes B (n) α and can be viewed as defining a deformation of the level curve Φ(l (n) ) to the level curve Φ(l (n+1) ) lying closer to the targets in the new boxes B (n+1) β .Alignment between target boxes and level curves (Fig. 3b ). Each box B (n) α is accompanied by a respective aligned piece Φ(l(n) α ) of the level curve Φ(l (n) ), where l (n)α is a segment of the level line l (n) , and the segments corresponding to different α are disjoint. The aligned piece Φ(l(n) α ) is a straight line segment. It lies outside the box B (n)α , but close to one of its 1D edges oriented along the splitting coordinate x kn . As u increases from u n to u n+1 , the level curve segment Φ(l (n) α ) is deformed in the new splitting direction x kn+1 so that Φ(l (n+1) ) now contains segments Φ(l(n+1) β )aligned with some x kn+1 -oriented edges of the sub-boxes B (n+1) β , and the new stage n + 1 can commence.We will ensure that each non-exceptional trajectory Φ(w(t)) goes through one of the aligned pieces Φ(l(n) α ) at each stage n.Reformulations of u-monotonicity. We need to ensure the u-monotonicity of non-exceptional trajectories, i.e. the condition ∂ u L f (w(t)) < 0 holding on the whole trajectory w(t). In terms of the map Φ, this condition readsEQUATIONAt a local minimizer w * (u) given by Eq. ( 7) we have ⟨∂ v Φ(w * (u)), f -Φ(w * (u))⟩ = 0. Then, if a GF trajectory is approximated by the minimizer trajectory w * = w * (u) (by stretching the parameter u), the condition of u-monotonicity becomesEQUATIONOne can also equivalently write this last condition in the formEQUATIONwhere P ⊥ ∂vΦ ∂ u Φ(w) denotes the projection of ∂ u Φ(w) to the direction orthogonal to ∂ v Φ(w) in the plane (∂ u Φ(w), ∂ v Φ(w)). Condition (10) means geometrically that a level curve Φ(l u ) locally, near the point Φ(w * (u)), gets closer to the target f as u increases.Transition from Φ(l (n) ) to Φ(l (n+1) ) (Fig. 3c ). During the n'th stage, all the components of the map Φ (n) : R 2 → R d are constant in the strip {(u, v) : u n + ϵ < u < u n+1 -ϵ} except for the components k n and k n+1 associated with splitting directions. Here, we consider a substrip u n + ϵ < u < u n+1 -ϵ of the full stage-n strip u n ≤ u ≤ u n+1 because we need to ensure that Φ is C ∞ . In the remaining narrow substrips u n ≤ u ≤ u n + ϵ and u n+1 -ϵ ≤ u ≤ u n+1 the map Φ (n) is smoothly connected to the maps Φ (n-1) and Φ (n+1) , respectively. It is easy to see that such a smooth connection can be ensured with arbitrarily small ϵ by additionally suitably varying the components k n-1 and k n+1 in the respective substrips; we omit these details.We construct the map Φ so that each aligned piece Φ(l (n) α ) is a segment of the straight line oriented in the splitting direction x kn . In each box B (n) α , the transformation of the level curve to the 2s n next-level pieces is performed symmetrically (Fig. 3b ), so we need to only describe the transformation in one of these 2s n sub-boxes (Fig. 3c ).Suppose for simplicity that the sub-box B (n) α in question has the form [0, a] × [0, b] w.r.t. the coordinates (x kn , x kn+1 ) and the aligned curve Φ(l (n) ) lies to the left as in Fig. 3c (a general case is treated similarly using a translation and possibly a reflection). The intermediate level curves Φ(l u ), u n ≤ u ≤ u n+1 , can then be generally described in the (x kn , x kn+1 ) plane as formed in two sub-stages separated by some u * ∈ (u n , u n+1 ).1. "Gathering" sub-stage u ∈ [u n , u * ]: for some ϵ > 0 the level curve Φ(l u ) can be given on the segment x kn ∈ [ϵ, aϵ] by x kn+1 = α(u)x kn -ϵ(u) with some small monotone decreasing ϵ(u) > 0 and some monotone increasing α(u) such that α(u n ) = 0 and α(u * ) = 1. In particular, at u = u * the level curve is given by x kn+1 = x kn -ϵ(u * ). In the remaining small segments x kn ∈ [0, ϵ] ∪ [aϵ, a] neighboring with the other sub-boxes the level curve is extended in some way (by suitable arcs) to ensure its smoothness and, moreover, concavity on the interval (aϵ, a] as a function x kn+1 = x kn+1 (x kn ).2. "Spreading" sub-stage u ∈ [u * , u n+1 ]: the level curve Φ(l u ) is evolved by extending its tip at x kn = a all the way to x kn+1 > b. Specifically, Φ(l u ) contains a straight line segment I(u) parallel to the axis x kn+1 and eventually, at u = u n+1 , including the aligned piece Φ(l(n+1) β). The x kn position of the segment I(u) is monotone decreasing in u, but remains close to a. The x kn+1 position of the left endpoint of I(u) remains close to a, while for the right endpoint x kn+1 increases from around a to b as u increases from u * to u n+1 . The right endpoint remains smoothly connected by a suitable concave arc to the analogous point in the neighboring box. See Fig. 3c for an illustration.The idea of this whole construction is to ensure that, as u is increased, the points on the level curves Φ(l u ) closest to the target f go around the corner of the box B (n+1) β as shown in Fig. 3c . The purpose of the "gathering" sub-stage is to force the trajectory Φ(w(u)) by u = u * to get to the tip of the level curve Φ (n) (l u * ) at x kn ≈ a. Then, in the "spreading" sub-stage the trajectory remains close to the moving tip until its coordinate x kn+1 reaches the respective coordinate f kn+1 of the target f , after which the trajectory slips off the tip to the straight line segment I(u) (the concavity of the arcs mentioned above ensures that the trajectory is not trapped on the arcs). The trajectory then maintains the target coordinate (Φ(w(u))) kn+1 = f kn+1 until reaching the aligned piece Φ(l(n+1) β).Let us discuss now how the above picture may break down for some targets f . First, it breaks down if the pair of target components (f kn , f kn+1 ) belongs to the domain swept by Φ (n) (i.e., (f kn , f kn+1 ) ∈ Φ (n) (l u ) for some u ∈ (u n , u n+1 )). In this case the u-monotonicity conditions ( 9), (10) are violated for u ≥ u and the GF trajectory gets trapped at a local minimum.Next, for some f the u-monotonicity holds, but the trajectory Φ(w) fails to reach the tip region x kn ≈ a. This occurs for the targets f such that f kn + f kn+1 ≤ 2a -for such targets the trajectory gets stuck near the orthogonal projection of (f kn , f kn+1 ) to the line x kn+1 = x kn .Finally, if f kn = 0, then the k n -component of the trajectory is stuck at 0 too. Moreover, if f kn is nonzero but close to 0, then the trajectory Φ(w(u))) remains close to the plane x kn = 0 and so again fails to reach the tip region. (This happens because near this plane ∂Φ(w(u n )) ≈ 0, invalidating our argument that we can ensure |∂ u L f | ≪ |∂ v L f | by stretching the variable u -the necessary stretching blows up as f kn → 0.) If the target f lies outside these three regions, then the map Φ (n) succeeds in guiding the trajectory Φ(w(t)) from a point on the aligned piece Φ(l (n) α ) near the orthogonal projection of f of that piece to a point on the aligned piece Φ(l(n+1) β) near the orthogonal projection of f to this piece. In particular, it is sufficient to require that (f kn , f kn+1 ) belongs to the rectangle R = [ϵ, aϵ] × [2a, b] with some ϵ > 0: we can then suitably stretch u and adjust the map Φ (n) so that for all targets with (f kn , f kn+1 ) ∈ R the above transition holds, and moreover with desired accuracy uniform in R.The initial map Φ (0) . The construction of the initial map Φ (0) is slightly different (and simpler) than the above inductive construction for general stage n. The GF starts from the particular point w = 0 of the left level line l(0) = {(u, v) : u = 0} of stage 0. Its right level line l (1) = {(u, v) : u = u 1 } has a single aligned piece Φ(l (1)1 ) aligned with the initial box B (1) at some 1D edge along the direction x k1 . We only need to ensure that for all targets f in the initial box B (1) , the GF trajectory approaches by u = u 1 a point on Φ(l EQUATIONIt is easy to see that for all f ∈ B (1) the respective GF trajectory (u(t), v(t)) satisfies du dt > 0 and, by choosing u 1 large enough, at t 1 such that u(t 1 ) = u 1 we will have |v(t) -f 1 | < ϵ with arbitrarily small ϵ.Ensuring convergence inf t L f (w(t)) = 0 for all f ∈ F 0 . The presented construction of the maps Φ (n) and the boxes B (n+1) β ensures that for all targets f ∈ B (n+1) β the following approximately occurs with the components of the respective discrepancy vector f -Φ(w(t)) as a result of the n'th stage of GF:1. The component k n+1 approximately vanishes.2. The component k n , which is approximately zero at the beginning of the stage, becomes nonzero, but limited by the size ofB (n+1) βin the k n 'th coordinate direction.3. The other components remain approximately the same.("Approximately" here means minor corrections due to the imperfect approximation by level curve minimizers ( 7), due to gaps between the boxes and the aligned level curves, and due to smoothing of the overall map Φ at the boundaries of the restrictions Φ (n) ; all these corrections can be made arbitrarily small).Clearly, it follows that if the sequence k n takes each of the values 1, . . . , d infinitely many times, then, since the size of B (n+1) β in any direction vanishes in the limit n → ∞, the vectors f -Φ(w(t))converge to 0 for all targets fromEQUATIONEnsuring µ(F 0 ) ≥ 1 -ϵ. The set F 0 is obtained by removing a countable number of rectangular parts from the root box B (1) that was chosen to have measure µ(B (1) ) > 1 -ϵ/2. Accordingly, we only need to show that the removed part can be made arbitrarily small with respect to the measure µ.The removed parts are of two kinds (see Fig. 3b ):1. Those associated with the gaps between sub-boxes B (n+1) β in the direction k n .2. Those associated with the gaps between the aligned pieces Φ(l) and sub-boxesB (n+1) β in the direction k n+1 .The width of the parts of the first kind can be made arbitrarily small. The width of the parts of the second kind was shown to be approximately equal to 2a, where a is the width of the sub-box B (n+1) β in the direction k n (see Fig. 3c ). However, a can also be made arbitrarily small by increasing the splitting number s n .Employing the σ-additivity of µ, we conclude that the only obstacle to making the measure of the removed parts arbitrarily small is that if some of the splitting hyperplanes of co-dimension 1 used in the construction have positive measure (and so we cannot make the measure of the removed parts arbitrarily small by decreasing their width). However, the number of values c such that µ({x k = c}) > 0 is countable, so we can avoid such hyperplanes by slightly shifting the root box B (1) .The crucial property of Pfaffian functions, due to Khovanskii, is that their level sets can only have a bounded number of connected components. This result relies on some mild assumptions on the domain U ; we will assume for simplicity that U = R W (see Remark 2.12 in Gabrielov and Vorobjov [2004] ). We state the result in a form suitable for our purposes (see, e.g., Corollary 3.3 in Gabrielov and Vorobjov [2004] ).Theorem 11. Let g 1 , . . . , g k be Pfaffian functions on R W . Then the number of connected components of the set {w ∈ R W : g 1 (w) = . . . = g k (w) = 0} (12) is bounded by a finite value only depending on k and the complexities of the functions g i .An important special case occurs if k = W and the solutions of the system (12) are non-degenerate in the sense that the respective Jacobians ∂gi ∂wj (w) are non-degenerate. In this case the level set (12) consists of isolated points, and their number is bounded by a number only depending on the complexities of the functions g i .The proof of Theorem 8 is a reduction to Theorem 11.Proof of Theorem 8. It is sufficient to consider the case W = d -1 (by trivially extending Φ to more arguments). It is also sufficient to prove that Φ(R W ) has Lebesgue measure 0 in the cube [0, 1] d : by rescaling and shifting, it then has Lebesgue measure 0 in any other cube and then, by σ-additivity, in the whole space R d .Let N be a large integer. Consider the d-dimensional grid of cubes ∆ n of size 1 N given byEQUATIONwhere y * = (y * 1 , . . . , y * W ) is some reference point. For each i = 1, . . . , d consider the mapΦ i : R W → R d-1 ∼ = R W obtained from Φ by removing the i'th component, i.e. Φ i = (Φ 1 , . . . , Φ i-1 , Φ i+1 , . . . , Φ d ).We will choose y * so that for each i and n ∈ Z W the pointEQUATIONis a non-critical value of Φ i , i.e. for any w such that Φ i (w) = y i, n the Jacobian ∂ Φi ∂wj (w) is nondegenerate. To this end, recall that by Sard's theorem the set V i of critical values of Φ i has Lebesgue measure 0. Then the setV ′ i = ∪ n∈Z W (V i -n N ) also has Lebesgue measure 0 in R d-1 . It follows that V ′′ i = {y ∈ R d : (y 1 , . . . , y i-1 , y i+1 , . . . , y d ) ∈ V ′ i } has Lebesgue measure 0 in R d . Then V = ∪ d i=1 V ′′ i also has Lebesgue measure 0 in R d . The complement R d \ Vis precisely the set of all y * such that the values ( 14) are non-critical for all i and n. Since R d \ V has full Lebesgue measure, we can find a suitable y * ; moreover, we can choose it so that 0 < y * i < 1 N , which will be convenient. Consider the cubes ∆ n lying in [0, 1] d , i.e., with n ∈ {0, . . . , N -2} d . There are (N -1) d such cubes. Suppose that the interior of a cube ∆ n contains a point of Φ(R W ). Then, since Φ(R W ) is connected, either Φ(R W ) ⊂ ∆ n or Φ(R W ) intersects the boundary of ∆ n . In the first case the Lebesgue measure of Φ(R W ) does not exceed N -d , so if this case occurs for arbitrarily large N , Φ(R W ) has Lebesgue measure 0.We can thus assume that if the interior of ∆ n contains a point of Φ(R W ), then the boundary of ∆ n intersects Φ(R W ). We will argue now that the number of such cubes ∆ n in [0, 1] d is O(N d-1 ), i.e. is vanishing compared to the total number (N -1) d of the cubes. Indeed, the boundary of ∆ n consists of cubic faces of dimensions 1, . . . , d -1 (ignoring the vertices, i.e. faces of dimension 0). Let s be the lowest dimension of a face intersecting Φ(R W ). Denote by R such a face. Consider two cases.1. s = 1. In this case the face R is a segment oriented along some coordinate i and with the other coordinates forming a point y i, n of the form (14). Recall that by construction the points y i, n are non-critical values of the map Φ i . The pre-image Φ -1 (R) is a subset of Φ -1 i (y i, n ) and so it consists of isolated points. Since ∆ n ⊂ [0, 1] d , the multi-index n of the segment belongs to {0, . . . , n -1} d-1 . By Theorem 11, the number of points in Φ -1 i (y i, n ) is bounded by a constant only depending on the complexity of the map Φ. The total number of points in the pre-image Φ -1 i ({y i, n : n ∈ {0, . . . , n -1} d-1 }) is then O(N d-1 ). It follows that the total number of points mapped by Φ to one-dimensional faces of all the cubes ∆ n ⊂ [0, 1] d is O(N d-1 ). Since each of these faces is a face for at most 2 d cubes, we conclude that the total number of cubes ∆ n ⊂ [0, 1] d whose one-dimensional faces intersect Φ(R W ) is O(N d-1 ).2. s > 1. In this case the intersection R ∩ Φ(R d ) lies in the interior of the face R. Let I = {i 1 , . . . , i s } be the coordinates along which the face is oriented. Similarly to the case s = 1, consider the map Φ I obtained from Φ by dropping all the components i ∈ I.The pre-image Φ -1 (R) lies in the pre-image Φ -1 I (y) of the point y ∈ R d-s formed by the coordinates i / ∈ I of the face R. Since R ∩ Φ(R d ) lies in the interior of the face R, the pre-image Φ -1 (R) is a subset of Φ -1 I (y) disconnected from the rest of Φ -1 I (y). In particular, if there are several s-dimensional faces (of several cubes) with the coordinates i / ∈ I forming the same point y and having non-empty intersections with Φ(R d ) that also lie in their interiors, then there are at least as many connected components in the pre-image Φ -1 I (y). By Theorem 11, the number of these connected components is bounded by a constant. Since possible values y belong to a (ds)-dimensional grid with spacing 1 N , the total number of such faces in the cube [0, 1] d (over all possible y's) is O(N d-s ), and then the number of respective cubes is also O(N d-s ).Taking the limit N → ∞, we conclude that the Lebesgue measure of Φ(R W ) is 0 as desired.Let f ∈ U and L f (w 0 ) < ϵ for some w 0 . We will show that if ϵ is small enough, then there is a barrier of high loss at the sphere bounding the ball B w0,r = {w ∈ R W : ∥w -w 0 ∥ = r} with a suitable radius r. Then, f belongs to the closure Φ(B w0,r ), while, by compactness and continuity, Φ(B w0,r ) = Φ(B w0,r ) ⊂ Φ(R W ).Assuming ϵ and ∆w ≡ ww 0 are sufficiently small so that the segment [Φ(w 0 ), Φ(w)] ⊂ Φ -1 (U ), we have c∥∆w∥ ≤ ∥J(w 0 )∆w∥ ≤ C∥∆w∥ and ∥Φ(w) -Φ(w 0 ) -J(w 0 )∆w∥ ≤ C∥∆w∥ 2 with some U -dependent constant 0 < c, C < ∞. Then, with ∥∆w∥ = r,EQUATIONChoosing r = ϵ 1/3 , at small ϵ we get L f (w) -L f (w 0 ) > 0 uniformly on ∂B w0,r , as desired.First, observe that the loss is constant along directions orthogonal to the rows of the matrix A = (a ij ), and GF is orthogonal to these directions. Therefore, by performing an orthogonal transformation and discarding these directions, we can assume without loss of generality that Φ i (w) = sin( W j=1 a ij w j + b i ) with some constants b i and a matrix A that has full rank W . The Jacobian J(w) = ∂Φ ∂w (w) can be represented as J(w) = D(w)A, whereD(w) = diag[cos( W j=1 a ij w j + b i ), i = 1, . . . , d].Now let U = (-c, c) d with some 0 < c < 1. Then, for all w ∈ Φ -1 (U ), the diagonal elements cos( W j=1 a ij w j + b i ) of the matrix D(w) are uniformly separated from 0 by a distance not less than √ 1 -c 2 > 0. Hence, in the operator sense, J * (w)J(w) = A * D 2 (w)A ≥ (1 -c 2 )A * A ≥ c1 for some c > 0, i.e. J(w) is uniformly non-degenerate on Φ -1 (U ). Applying Proposition 9, we conclude thatF Φ ⊂ ∂[-1, 1] d ∪ Φ(R W ), which has Lebesgue measure 0 in R d . 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: The paper is purely theoretical and does not include experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: The research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: Our paper clarifies a theoretical question relevant for machine learning and optimization, and can thereby be beneficial to other researchers in these fields. We do not see any potential negative impact of our work.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The paper poses no such risks. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: The paper does not use existing assets. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. 
 
 Appendix:  


Decision: The paper investigates an interesting and novel question with mathematical rigor. Most reviews all lean towards acceptance.

Reviews: review: paper_summary: paper_summary: This submission studies the learnability of high-dimensional targets with models having fewer parameters. The manuscript considers training with Gradient Flow and studies when the target -- identified by a general d-dimensional probability distribution -- can be learned by $W-$ parameter models, with $W <d$. First, the authors provably show general impossibility results, i.e., there is always a substantial amount of non-learnable targets (with the extreme case to be zero-Lebesgue measure for $W=1$). However, they prove also positive results regarding GF learnability with $W=2$: it is always possible to find a map $\Phi$ for which the learnable set can be made arbitrarily large.
strength_weakness: strength_weakness: The weakness of this paper is the clarity of the exposition. I believe that many parts of the main body could be moved to the appendix to make the submission more readable for non-expert readers. This comment is not set to undermine the quality of the contribution, which has nice theoretical aspects, but to enhance the presentation of the main results. See the section below for pointers.
questions: questions: - As described above I believe that many formalities should be moved to the appendix to be accessible for the NeurIPS audience. My main concern is on Section 5, which I believe to be interesting, but hard to read. I would enlarge the discussion part of this section considering that only two lines are used after corollary 9. 
- How would the present construction relate to general kernel /random feature methods? The mathematical apparatus is similar (RKHS), but with different purposes. I believe connection with classical machine-learning tools would help the typical NeurIPS reader.  (Page 4 for example). 
- Maybe the authors could use also polynomial targets in their "Examples" paragraph (which are more than welcome to help the reader)? More generally, non-linear targets would help to see the extent of the present setting. 
- Am I correct to understand that general non-linear function are not admissible in the present setting? If that is the case, stating it explicitly would help the reader. 
- I feel like the nomenclature for target-dimension ad $d$ is confusing as one might be led to think that is the output dimension (Y). Maybe it could be emphasized more in the text. 
- Below Eq. (1) I would expand on what is meant to be "locally solvable" given that the whole paper will turn around the GF setting. 
- Is there a connection of your results to the recent work [1]? I acknowledge that the reference was only recently put on arxiv and I am just wondering out of curiosity for this minor point. In any case, I think it would be good to mention that ideas using KST are recently used in the machine-learning community.  
- How important is in your work the condition $w(0) = 0$? What would it change if the weights could be somehow correlated with the target's ones? 


[1] KAN: Kolmogorov–Arnold Networks. Liu et al. 2024. arXiv:2404.19756.
limitations: limitations: The limitations are discussed in the submission.
paper_summary: paper_summary: This paper analyzes when it is possible to define a map $\Phi: \mathbb{R}^W \to \mathbb{R}^d$ such that any point $y \in \mathbb{R}^d$ is ``learnable'' via gradient flow on the square loss $\|y - \Phi(w)\|^2$. They show that for any distribution over $y$, there exists a map $\Phi: \mathbb{R}^2 \to \mathbb{R}^d$ such that gradient flow on the square loss gets arbitrarily close to any $y$ with probability arbitrarily close to $1$. It also shows that it is impossible for this to hold with probability exactly $1$ for any $W < d$, and shows that in this case the non-learnable targets are dense in $\mathbb{R}^d$.
strength_weakness: strength_weakness: - The construction and proof sketch for Theorem 5 and the diagrams in Figure 2 are very difficult to follow.
- It is strange to define the setting in terms of abstract Hilbert spaces only to immediately specialize to the case of $\mathbb{R}^d$. In the supervised learning analogy, this corresponds to the uniform measure over a finite sample of $n = d$ datapoints.
questions: questions: - Why is it necessary to restrict to $\mathcal{H} = \mathbb{R}^d$? Is it possible to extend the arguments to infinite dimensional spaces?
- Is it possible to simplify the construction in Theorem 5 for some easy target distributions to simplify exposition?
limitations: limitations: The authors have adequately addressed the limitations of their work.
paper_summary: paper_summary: The paper studies the *learnability* of finite dimensional space of functions $\mathcal{H}$ of dimension $d$. The learnability criterion is related to the gradient flow according to the canonical $L^2$ error, associated with a certain $\Phi$-parametrized family of dimension $W$, that can be chosen. The authors proposes the following results:

- **Theorem 3**: For $W < d$, under some regularity assumption on $\Phi$, there exists a ball in $\mathcal{H}$ with non-reachable function. It implies that under this condition on the choice of $\Phi$-space, the GF-learnable function space is not dense in $\mathcal{H}$.

- **Theorem 4**: Any subset homeomorphic to the $W$-sphere contains non learnable targets.

- **Theorem 5**: On the positive side, there exists for $W = 2$ models that can learn targets with probability arbitrarily close to $0$.

- **Results 7-9**: Finally the authors try to answer the question of learnability of functions expressible with elementary operations ("simple functions"). For this, Pfaffian maps are defined and for underparametrized Pfaffian models, GF-reachable functions have Lebesgue-measure $0$.
strength_weakness: strength_weakness: Reviewing such a paper in a conference (along with 5 others) is a very difficult task given the time constraint and the technicality of the present paper. Hence, I apologize in advance if the questions I am raising are due to the limit of my knowledge and not the lack of clarity of the authors. Yet, considering that I might be a typical reader of the article I want to mention the following points that could help improving the manuscript:

The statements given by theorems 3 and 4 on the one side and theorem 5 on the other side seem to go in two opposite directions, at least qualitatively: indeed Theorems 3 and 4 go in the direction that there always exists non-reachable functions (even an open Ball for Thm 3!), whereas Theorem 5 argues that if we equip the space of function with any Borel measure, GF-learnability can be almost surely certified. Althought, the two statement do not contradict themselves, it would be good to comment more on this fact: under this form, it does not help me picturing exactly what the set of learnable function look like. For example, if we restrict the space of functions to a compact subset of $\mathcal{H}$, doesn't Theorem 5 implies a sort of density of learnable functions?
questions: questions: See above for an important first question.

-  line 298, and line 195, the authors argue that the consequence of Theorem 4 is that the set of non-learnable function is dense for $W < d$. As far as I felt it, it seems to be a direct consequence of the fact that a neighborhood of some $f$ always contains a set homeomorphic to the W-dimensional sphere, but 
    - it would be better to have a clear (even if two-line) proof
    - that would help the reader to have a clear **corollary** to stamp this property

- I would change the title to * **Learnability** of high-dimensional targets by two-parameter models with gradient flow*  to put emphasis that the authors do not study a specific class of models but more whether certain functions are not learnable.

Minor additionnal comments:

- l. 68-69: I do not see why Theorem 1 is *a low-dimensional reduction* reflected in Theorem 1.
- l. 172: $J^*_0 J_0$ instead of $J^*_0J$ 
- l.252 : in which
limitations: limitations: No
paper_summary: paper_summary: This paper studies the problem of learning a target function $f$ lying in some $d$-dimensional Hilbert space $\mathcal{H}$ via gradient flow on a $W$-parameter model with $W < d$. The main result, Theorem 5, is that for $W = 2$, given a distribution over $\mathcal{H}$ there exists a parametric map $\Phi : \mathbb{R}^2 \rightarrow \mathcal{H}$ such that gradient flow converges to the target with probability approaching 1. In contrast, if the map $\Phi$ is constructed via "elementary functions," then the set of learnable targets has Lebesgue measure 0.
strength_weakness: strength_weakness: - I struggle to understand the relevance of the problem studied in this paper to the NeurIPS community / the field of Machine Learning. The construction for $\Phi$ in Theorem 5 is quite pathological, whereas parametric models used in ML/statistics are much more regular. In fact, in Section 5 the authors prove that if $\Phi$ is an elementary function, then only a measure 0 set of targets are learnable by GD. I thus do not see the significance of studying parametric models $\Phi$ which essentially act as space-filling curves and map $\mathbb{R}^2$ to $\mathbb{R}^d$ in a very complicated manner.

- Furthermore, in ML settings, when the parametric map $\Phi$ cannot express the ground truth target $f$, then the goal is to instead converge to the best possible predictor i.e obtain a loss $\inf_w \frac12\||f - \Phi(w)\||^2_{\mathcal{H}}$. Prior works studying the loss landscape of underparametrized models typically operate in the setting where the number of parameters is fewer than the number of *data points* and thus the training loss cannot go to zero. This paper is substantially different, and focuses on the problem where the number of parameters is smaller than the dimension of the function class, but we are still interested in learning a large portion of this function class, which to me feels quite strange.

- I find the proof sketch for Theorem 5, in particular a description of the construction of $\Phi$, to be unclear. A more detailed definition of objects like the Cantor set $F_0$ is needed, since this may not be familiar to the NeurIPS optimization/theory community. I also don't think the boxes $B_\alpha^{(n)}$ are ever defined in the main text.
questions: questions: - Can you provide intuition on why Theorem 5 does not apply to infinite-dimensional target spaces?
limitations: limitations: N/A

Comments: title: After Rebuttal
Thank you for your rebuttal
Response
comment: Thank you for this feedback. We understand and appreciate your view, but respectfully would like to challenge it.

> I do believe that theoretical work should model/explain some relevant aspect of reality, which I don't believe is accomplished by this paper.

**Comparison with KST.** Let us compare our main theorem 5 with Kolmogorov Superposition Theorem (KST) saying that multivariate continuous functions can be represented in terms of univariate ones and summations. KST has inspired many papers/ideas/discussions related to ML/neural networks, primarily with the focus on confirming or increasing expressiveness of ML models. One work, very recent but already having received much attention, is mentioned by Reviewer MmYK [1]. Some others are cited in our paper. 

The construction used in KST is arguably much more pathological than ours in Theorem 5. The functions used in KST are very complicated continuous functions; they cannot be chosen as elementary or smooth, even locally. Also, the representation of the target function is obtaned by a fairly non-constructive argument.

In contrast, our map $\Phi$ is smooth, can be chosen piecewise elementary, and the fitting is performed by standard gradient flow. 

Accordingly, we don't see why our work models/explains relevant aspects of reality worse than KST. If ML community finds KST useful, why should it not find useful our work, in which the model is much more regular and the fitting procedure the most standard?

We also emphasize that while ideas of using KST for high expressiveness of ML models have a long history dating back to Hecht-Nielsen [2] and Kůrková [3], we are not aware of any previous works analyzing to which extent high expressiveness can be combined with gradient flow. We believe our work to be the first in this respect, and moreover providing a fairly balanced and comprehensive analysis.

[1] KAN: Kolmogorov–Arnold Networks. Liu et al. 2024. arXiv:2404.19756.  
[2] R. Hecht-Nielsen, Kolmogorov's Mapping Neural Network Existence Theorem, First IEEE International Conference on Neural Networks, San Diego, Vol. 3, 1987    
[3] V. Kůrková, Kolmogorov's Theorem Is Relevant, Neural computation 3 (4), 617-622, 1991

**Negative results.** Your arguments seem to primarily address Theorem 5. But we also have "negative" theorems 2, 3, 4, 7, 9,  that actually *confirm* your point of pathology by clarifying precisely in which sense this pathology is manifested. These are new, rigorous and not so obvious results that constitute a significant part of our contribution. 

> I do not know of any examples in the statistics/ML literature where one is interested in *exactly* fitting a dimension $d$ model with $W<d$ parameters.

If we are interested only in a non-exact fitting, say with accuracy $\delta>0$, then a respective GF-learnable 2-parameter model can be easily constructed by truncating the model $\Phi$ presented in Theorem 5. Such a truncated model is no longer pathological, in the sense that it is now expressible by an elementary function, say in the form of some finite neural network (Theorem 7 no longer applies). We don't claim that such a model is *practically useful*, but our construction shows that it is theoretically possible while being relatively realistic.
Thank you for addressing my questions and concerns. I still believe that while the paper is well written and the results are surprising, the paper is held back by a lack of intuition for the main result (Theorem 5). I have decided to keep my score.
I thank the authors for the rebuttal. I still find the article a very elegant contribution and keep my score.
I thank the authors for their rebuttal that clarified my concerns. After carefully reading the authors' responses along with other reviewers’ comments, I believe the proposed changes will improve the quality of the submission. I would like to keep my score as in the original review.
Thank you to the authors for their response.

I still find that the problem studied in this paper is not well motivated. It seems to me that in order for a function to be "GF-learnable" per the definition in the paper, the image of $\Phi(w)$ must cover most of $\mathcal{H}$ and thus the map $\Phi$ must necessarily be very pathological; no reasonable statistical model will be of this form. In fact, I do not know of any examples in the statistics/ML literature where one is interested in *exactly* fitting a dimension $d$ model with $W < d$ parameters. The usual setup in the underparameterized setting is not to obtain exactly zero training loss, but rather to converge to the predictor with the smallest loss over the candidate class of functions. While modern neural networks are indeed very complicated, I am very skeptical that they behave like the construction $\Phi$ presented in this work. And while I acknowledge that theoretical work does not have to have a direct practical impact, I do believe that theoretical work should model/explain some relevant aspect of reality, which I don't believe is accomplished by this paper. I thus am leaning towards maintaining my original score.
Just a friendly reminder to the reviewers to acknowledge the author's rebuttal, so that the discussion period can be used efficiently.