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

Thank you for the careful reading of our paper and your useful feedback and critique.

• "I struggle to understand the relevance of the problem studied in this paper to the NeurIPS community.. The construction for $\Phi$ in Theorem 5 is quite pathological.."

That's true, the construction in the proof looks pathological. But suppose you know nothing about the proof and just see the statement of Theorem 5. Would you say that this statement is irrelevant to ML/NeurIPS? We believe that it involves only natural and standard ML concepts (gradient descent, parametric models, target spaces ...), the only nonstandard thing being the scenario of a small number of parameters. In our opinion, the question addressed by Theorem 5 is not unreasonable and certainly not trivial. Our goal was to understand what can theoretically happen in this scenario, be it with or without complicated constructions. If we could prove Theorem 5 without complicated constructions, we would have done so.

Another point to mention, Theorem 5 deals with the extreme case of just two parameters and a full convergence to the targets. We expect (and briefly mention in the Discussion) the pathologies to weaken if, e.g., the number of parameters is closer to the dimensionality of the target space.

Also, while the parametric models used in ML/statistics are indeed more regular, modern neural networks can still be very complex in terms of their architectures, activation functions, etc. Their learning dynamics is not well-understood. We don't see why Theorem 5 could not potentially be relevant for some of their learning poperties (though this is of course purely hypothetical; we don't claim at this point any specific direct connection to practical models).

• "..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."

But we also know that modern neural networks often contain much more parameters that the number of training data points. The dimensionality of the function class in this case is certainly much smaller than the number of parameters. If this is a valid scenario, why is it unreasonable to theoretically examine the opposite scenario?

• "I find the proof sketch for Theorem 5 .. to be unclear"

Thank you for this feedback. We admit that some elements of the proof sketch may be not clear enough. We wanted to convey the key ideas, but due to the size constraints we found it hard to give more than a flavor of the proof. We'll try to improve this sketch. Meanwhile, please see Appendix A, where the full proof is carefully described.

Thank you for the careful reading of our paper and many useful comments.

• "I would enlarge the discussion part [of Section 5]"

Thank you for this feedback. Indeed, we agree that it can be useful to add some comments and maybe a graphic illustration here.

• "Am I correct to understand that general non-linear function are not admissible in the present setting?"

To clarify, we assume the target space $\mathcal H$ to be a linear space of functions, but the functions themselves need not be linear (or have any other particular form). Examples include those we mention in lines 111-119 (the full $L^2$ space, linear targets, polynomial targets) and RKHS subspaces associated with finite sets of data points (see below). Our results only use the euclidean structure of the space $\mathcal H$ (i.e., as a linear space with a scalar product). Representation of targets in $\mathcal H$ as particular functions is the starting point of our study, but it only affects the GF flow through this euclidean structure. In other words, once we know the scalar products between targets, their other properties do not play any role in our theorems.

• "Maybe the authors could use also polynomial targets in their "Examples" paragraph"

Sure, we do that (our third example).

• "How would the present construction relate to general kernel /random feature methods?"

One can consider a subspace of RKHS as our target space $\mathcal H$. Specifically, suppose we have a kernel $K(\cdot, \cdot)$ on the input space $X$, and a finite training set $(\mathbf x_n, y_n)_{n=1}^N$ representing some function $f:X\to \mathbb R$.

In kernel methods, the function $f$ is fitted by functions $\widetilde f_{\mathbf c}(\mathbf x)=\sum_{k=1}^N c_k K(\mathbf x,\mathbf x_k),$ with some coefficients $\mathbf c=(c_1,\ldots,c_N)$. We can naturally view such functions $\widetilde f_{\mathbf c}$, with various $\mathbf c$, as forming our target space $\mathcal H$. Assuming the kernel is non-degenerate, $\mathcal H$ is $N$-dimensional, with vectors uniquely corresponding to the coefficient vectors $\mathbf c$. Then Theorem 5 shows that, by using gradient flow with a suitable two-parameter map $\Phi:\mathbb R^2\to\mathcal H$, we can, with a high probability, learn the target $\widetilde f_{\mathbf c^*}$ that interpolates the training data $(\mathbf x_n, y_n)_{n=1}^N$.

• "I feel like the nomenclature for target-dimension as $d$ is confusing"

Thanks for this feedback; we'll clarify this point.

• "Below Eq. (1) I would expand on what is meant to be "locally solvable""

Thanks for this feedback, we'll clarify that ("locally solvable" means solvable at least for a finite interval of times).

• "Is there a connection of your results to the recent work [1]?"

Yes, we are familiar with that work. Both that work and our paper have a common general theme of a low-dimensional reduction (that we alluded to in our introduction), but otherwise the connection is fairly weak. The work in question proposes a KST-inspired architecture and focuses on its expressivity, whereas our focus is on GF optimization. Also, our construction is rather different from the one used in KST.

• "How important is in your work the condition $\mathbf w(0)=0$? What would it change if the weights could be somehow correlated with the target's ones?"

The condition that GF starts from $\mathbf w(0)=0$ is not important, one could instead start GF from any fixed $\mathbf w_0$.

Regarding a target-dependent initial condition, it's an interesting question. Some of our "negative" results such as Theorems 2 and 3 do not apply in this setting (at least without some essential modifications). On the other hand, the negative Theorem 4 based on Borsuk-Ulam remains valid as long as the initial condition $\mathbf w_0$ depends continuously on the target. An important difference would be in our main positive Theorem 5: as we mention in the discussion, we have not been able to prove it for infinite measures such as the Lebegue measure. However, this can certainly be done with a target-dependent initial condition: we can just split the space into finite boxes, assign a separate initial condition for each box, and define the map $\Phi$ separately in each respective region of the parameter space by following the existing proof for a finite box.

Thank you for the useful feedback and a very positive evaluation of our work!

• "What the set of learnable functions look like... Doesn't Theorem 5 implies a sort of density of learnable functions?"

The right geometric picture for the set of learnable functions in Theorem 5 would be a multidimensional "fat Cantor set" (a.k.a. Smith–Volterra–Cantor set), see e.g. this Wikipedia article and the illustrations there. Such sets are not dense in the ambient space, but can be quite large in terms of their measure. This is exactly what happens in Theorem 5.

It is an interesting question whether the set of learnable targets may need to actually have more "holes" than predicted by Theorems 3 and 4. In particular, Theorem 3 only constructs a single ball devoid of learnable targets. However, the learnable set constructed in Theorem 5 is even nowhere dense, i.e. an arbitrary ball in the target space contains a ball devoid of learnable targets - a strictly stronger property. In this sense, our results are not tight.

• "It would help the reader to have a clear corollary.. that the set of non-learnable function is dense for $W<d$"

Indeed, such a corollary would be quite reasonable, thank you for this suggestion.

• "*I would change the title to Learnability of ... *"

Yes, this is also quite reasonable, thank you.

• "I do not see why Theorem 1 is a low-dimensional reduction reflected in Theorem 1"

This sentence is indeed somewhat awkward and probably needs to be clarified. We just meant to say that Theorem 1 gives an example of a reduction of a high-dimensional target space to a low-dimensional parametric description, and we ask if such or similar reduction can be combined with learning by GD.

Thank you for your careful reading and a positive evaluation of our work!

• "The construction and proof sketch for Theorem 5 and the diagrams in Figure 2 are very difficult to follow."

Thank you for this feedback. We admit that some elements of the proof sketch may be not clear enough. We wanted to convey the key ideas, but due to the size constraints we found it hard to give more than a flavor of the proof. We'll try to improve this sketch. Meanwhile, please see Appendix A, where the full proof is carefully described.

• "Is it possible to extend the arguments to infinite dimensional spaces?"

This is an interesting question. In fact, an inspection of our "negative" Theorems 2-4 shows that they remain valid if the target space is an infinite-dimensional Hilbert space while the number of parameters is finite. This is natural because, clearly, the addressed problem becomes harder if the dimensionality of the target space increases.

Following this logic, the negative Theorem 7 about elementary functions can probably also be generalized to infinite dimensions, though in this case some reformulation is definitely required because there is no Lebesgue measure on the infinite-dimensional Hilbert space.

Our main "positive" Theorem 5 can probably also be extended to infinite dimensions, but such an extension has some aspects that we haven't figured out; please see our general response.

• "Is it possible to simplify the construction in Theorem 5 for some easy target distributions?"

The natural simple target distribution is just the standard uniform distribution in a box. Our construction for a general distribution is only a small modification of the construction for this special case. However, this means that all the essential elements of the construction are present in this special case and so, unfortunately, it is not much easier than the general case.