Learnability of high-dimensional targets by two-parameter models and gradient flow
Authors: Dmitry Yarotsky
Venue: NeurIPS 2024 poster (2024)
Keywords: gradient descent
gradient flow
learning
optimization
local minima
Cantor set
elementary function
Pfaffian function
Borsuk-Ulam antipodality theorem
Primary area: optimization

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.

Learnability of high-dimensional targets by two-parameter models and gradient flow
Dmitry Yarotsky
Skoltech d. yarrossky@skoltech..n
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, show that for W < d there is necessarily large subset of GF-non-learma set of learnable targets not dense in R and any subset of Rd homeomorphic to the W -y-dimensional sphere contains non-learnable targets. Finally, we observe that the model our main theorem on almost guaranteed two-parameter learning is constructed using hierarchical procedure and as result is not expressible by a single elementary function. We show that this limitation is essential the sense that most models written in terms of elementary functions cannot achieve the learnability demonstrated in this theorem.
targets. In particular, the
1 Introduction
Starting from the works of Cantor [Cantor 1878), is well-known that all finite-dimensional (or even
real spaces are equinumerable and so, in principle, set of several real numbers is as descriptive as a single number, or in other words multi muulti-dimensionl vectors can be represented by scalars. The idea of reduction of higher-dimensional descriptions to nower-dimensional ones has since appeared in many mathematical works. A couple notable examples are continuous space-filling curves that fill the whole Rd (Peano 1890 Hilbert 1891] and the Kolmogorov Superposition Theorem (KST, Kolmogorov [1957) that states that any multivariate continuous function 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 small number of parameters can potentially be used to represent or approximate high-dimensional objects. In particular, Maiorov and Pinkus [1999] give example of neural network that has fixed number of weights but can approximate any continuous function:
Theorem 1 (Maiorov and Pinkus 1999). There exists an activation function a which is real an- alytic, strictly increasing. sigmoidal (í.e., lim axx) 0 and lim (x) = 1), and such that any E C((0, 1]") can be uniformly approximated with any accuracy by expressions 3n BBn43 do ( C Wijx2 + 02y) + 7/) with some parameters de, Cijy Wijk, Wijk.0iy 7-
Refinements of this result are given by Guliyev and Ismailov 2016 2018a b). While Theorem contains a non-explicit function a, Boshernitzan [1986]. Laczkovich and Ruzsa 2000), Yarotsky (022 give examples of fully explicit fixed-size analytic expressions that also can approximate arbitrary continuous functions. KST has inspired many other results expressiveness of machine learning models, see e.g. Montanelli and Yang 2020), Schmidd-HHeber 2200)) Kürková [19] 1992
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Köppen 2002 Igelnik and Parikh| 2003]. The idea of space-filling curves is used in recent works
on generating dineessoninn distributions from low-dimensional ones [Bailey and Telgarsky
2018 Perekrestenko et al. 2020 2021
While the model appearing in Theorem looks like 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 proof' of the universal approximation property in this and similar theorems (including the classical universal approximation
theorems of Cybenko [989]. 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, |mmihh 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 that they are easier train by GD-based optimization [Choromanska et al. 2013). which can be explained by the optimizer having more freedom in finding good descent directions, particular evading spurious local minima and saddle points.
A convincing and rigorous demonstration that overparameteriizaion may be beneficial for training is provided by the infinite width limits of neural networks in regimes such NTK (Jacot 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 analytically tractable and, under mild assumptions, provably trains the model 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 general feature of finite neural networks with nonlinaarities [Auer et al.] 1995, Yun et al. [001 Swirszez et al.) 2016 Zhou and Liang] 2017 Christof and Kowalczyk/ [203]. 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 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 I 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 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 probability distribution in Rd then there exist models with just W = 2 parameters that can learn these targets by Gradient Flow (GF) with success probability arbitrarily close to (Theorem
2. We show that Theorem 6 is actually close to being optimal, since underparamettrrizttin with W < d generally implies severe constraints on the set of GF-leamable targets:
(a) Under a mild nondegeneracy assumption, the GF-learnable targets are not dense in Rd (Theorem 3 In particular, the success probability cannot generally be made exactly equal in Theorem
(b) In contrast, the non-learnable targets are dense in Rd. Moreover, any subset of d homcomorphic to the W 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 single elementary function. We conjecture that the result established in Theorem [6] camnot be achieved with models implementable by elementary functions. For such functions not involving sin cos with unbounded arguments, 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 In Section we give several general results showing that the underparameterized (W < d) learning is theoretically challenging. Then, in Section we present our main result on the almost guaranteed learnability with two parameters. After that, in Section S consider models expressible by elementary functions. Finally, in Section 6 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.
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 linear space with a euclidean structure. To this end, suppose that Y is euclidean space with a scalar product (,,), and is endowed with measure v reflecting the distribution of inputs x E X of the function f. One can then form the Hilbert space L2 Y,v) of functions f X + Y equipped with the standard scalar product (f.g) = [x (f),, g (dx)). We will subspace of this Hilbert space
assume that the target space H. is (finite- I,2 V),
Examples:
1. The full space -,, represents all maps f X + distinguishable on sets of positive measure v. If = =R" with the standard scalar product and v/ = > 6x, is empirical distribution corresponding to finite subset of X, then H. is finite-diment fimiteddimeniionll H. = Rd with d = Nm. On the other hand, v is not finitely supported, then dim H = co.
2. Let x R" Y R. and the targets f X + Y be linear functions. If v is nondegenerate in the sense that the covariance matrix [[ 2, (dx)), is full-rank, then the respective target space is n-dimensional (otherwise, dim < n).
3. Let X
Ra Y R. and the targets be polynomials of degree not larger than q. Then dim H. < (n with equality attained for suitably nondegenerate measures v.
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 linear space and have 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 E H using parametric model with W parameters. We will view this model as a map + R W > between the parameter space RW and the target space H.
We will consider Gradient Flow (GF), i.e the continuous version of gradient descent. Learning by GF preseribes that the parameter vector w be evolved by
dw(t) = V Le((())))
(1)
dt
where we use the standard square loss, Lr(w)= = 2 Ex Il (x)-x(w))))))) (x)) which can equivalently be written
1 -|| o (ww))
Le(w) = Here, the subseripts Y, H on the norms indicate the respective spaces. We will assume for definiteness that GF starts from w(t 0) 0.
3

---

We will always assume that W is finite and Φ is differentiable with Lipschitz-continuous continuous differential. In this case Eq. ① is. by Picard-Lindelóf theorem, uniquely solvable locally (i.e., for 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 Santambrooooo (2077), but we will not need this in this work.
In fact, GF T is solvable not only locally, but also globally, i.e. the solution w(t) exists for any t >> O. Indeed, the only obstacle for the global existence is the divergence of the solution in finite time, but is ruled out by the inequality
[|w(1)12 = (f.1 12
2 l(dT)
S stl
1/1
dw(r) 12 dr
(3)
dr
= -1 S. (le(w(r)) dr = (Ix(0) Le( (0)
dr
Let Fs denote the set of targets for which the respective GF converges to f:
Fs = f H inf Le(w(l) 0 for w() given by [
Our goal in the remainder of this work will be to examine if we can ensure, by a suitable design of the map to targets f E F& as GF-learnable norm topology in H. the set F& is forel-measurable as the countable intersection of the open sets {f H. inf, (r(w(t)) < 1/n, where w(t) is given by [ n. 2,.....
RW + Rd with W < d, that the set Fs sufficiently large We will refer simply learnable. We remark that, assuming standard
Example: To clarify our setting, suppose that we fit to data a linear function f(x) = kTx x with x E Rd for some d (see example 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) ) x, with some generally nonlinear + I W + Rd 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 inpudddeeeneence and replace it by nonlinear one.
Note that formulation 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.
2 of GF is stated purely in terms of vectors and maps in Hilbert spaces,
Some of our results, including the main "positive" Theorem 6 require the target Hilbert space to be inite-dimensionall i.e. H = Rd with < xc. Others (namely the "negative" Theorems 2 remain valid for anfinteedimensiinall Hilbert spaces H. By a slight abuse of notation, in this latter case we also write H Rd, but with d co.
3 General impossibility results
We start with several general results showing fundamental limitations of GF with small dimension W. First, it is easy to see that one-ooneneeee mue-paraettrr models can ensure GF convergence only for a very small set of targets.
Proposition 2. Let W = 1. Then, if target f E F&, then either f = (ww) for some or
f E (f_, f+] = (lim--1ice [ww}} (if any of these two limits exist). In particular, if = Rdd with 2 S d < 20, then F4 has Lebesgue measure 0 in H.
Proof. The first statement follows since the optimization trajectory w(() is a scalar monotone function of I. 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, then Fe cannot be dense in H.
NNote that if W 2 d, then we easily ensure F H. by taking any surjective linear operator w gd as the model. Indeed. this case for any target f e wed the loss function Lr(w) _ @w
is quadratic with the global minimum Lr(w.) O, the GF is solved as w(t) = - -1 (1 - - -00T and @w()) 5 f.

---

y-y)))
Figure 1: Proof of Theorem GF cannot converge for all points of G: such a convergence would require + ((z,) to be simultaneously close to both g(x)) and g(-Yr), which are far from each other.
((zz).
g(ye)
(((TR (IRW)
Theorem 3. Let 1 S W < d S do and & R. H be C² map such that at 0 the Jacobi matrix Jo Jw (0) has full rank W. Then F3 is not dense H.
Proof. We show that there is ball of targets for which the GF trajectory gets trapped at local minimum due to a loss barrier. Without loss of generality, assume that ((0) = 0. Let fo E Rd be some length-/ vector orthogonal to the range of the differential Jo: such fo exists because W. Let Bra. = {f E _² :If foll < e). Since & is C2, we have 2(w) = Jow + R(().
with remainder [[[(w]] S C [[]l for all sufficiently small ||w] with some constant C. Then, for
f E B we have
Lf(w)- - (0) = } f|f - (w))l 111111 [1) (f, ((w))
2 Jow [C [Joll/|w]]] + 0 + ||
Since rank Jo = W, the matrix Jo strictly positive definite. Choose small enough so that J/J- is still strictly positive definite. Then, if we subsequently choose r and then small enough, we have Lr(w)- - Lr(0) > for all w such that |||| r, i.e. for E Bt., the GF trajectory w(t) never leaves the ball U,- = {w E W ||w|l & r). Then, since & is continuous, e < and is small enough, Br. n (U,)) = and the ball Br. cannot be reached by GF.
Finally, we show that for W < d any subset of R& homeomorphic to the W W-sphere contains non-learnable targets:
Theorem 4. Let 1 < W. d < co. Suppose that set G Ted is the image of the W W-dimensional
sphere SW = (y E RRW+ |yll 1] under a continuous and injective map g SW - Rdd. Then G & Fa.
Proof (see Figure 7l. We use the Gorsuk-Ulan antipodality theorem saying that for any continuous map o: gW R there exists a pair of antipodal points y, -y sW such that Φ(y) = (-y).
Let wr( denote the solution of GF I with target f. For any / > O, consider the map d; : SW + RW given by de (y) w W (t). By the assumption on g and the continuous dependence of GF the target, the map de is continuous. By Borsuk Ulam, follows that there is yt E sW such that (y:) = (x)... Denote this common output vector by 2,-
Let I iew (l g--y)] Observe that by the continuity and injectivity of g as well as compactness of sW Then for any
sup L (w (t))) = sup yeaw
Ells(y) - + (WWot)))))] (+)]l1
yesw
2 2 max (119(1)) (zz))) ( y.) +(()))1)) 2 (0)) >
(5)
Now suppose that c Fg. Then for any y E SW the function 1 1 Lgtn) (Wa(y) (1)) monotonically converges to as > co. However, since gW is compact and T.yty) (Ws(y)()) (t)) is continuous in y, such a convergence must be uniform over E sW contradicting the lower bound (
Note that we did assume that W in this theorem, but is vacuous for W > d because (again by Borsuk-Ulane -lam) there are no continuous injective maps g SW + RR. On the other hand, there are plenty of such maps for W d, implying particular the following corollary.
Corollary 5. W < d, then H. \ F4 is dense in H.
Our use of the Borsuk-Ulan theorem is inspired by De Vore al. 1989 who used to establish lower bounds on nonlinear r-widths in an abstract approximation setting.
5

---

Figure 2: In Theorem 6 ensure that the learnable set of targets Fe contains a multidimensional "fat" Cantor set Fo having almost full measure J.. The set Fo has the form Fo = - Ua B(n), where {B! Jn.a is a nested hierarchy of rectangular boxes in R2. Here, n is the level of the hicrarchy and is the index of the box within the level.
4 Almost guaranteed learning with two parameters
Results of the previous section show that for models with W < d parameters there is always 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 main result showing that already with W = parameters, one can design maps & RW + IR for which the learnable set is arbitrarily large with respect to given probability distribution
the target space:
Theorem (A). Let H IR with d < oc, and let μ be any Borel probability measure on H. Then for any e > 0 there exists C map 4 : I22 - H such that μ(H F&) <
Example: Suppose again that learn linear function fx(x) kf with k. Rdd for some d. Assuming non-degenerate distribution of inputs v. the target space H ~ IRd Suppose now that possible coefficient vectors k have, say, the prior distribution j ~ (O, 1dxd) in IR. Then Theorem states that for any >> 0 there exists a two-parameter model : R2 + Rd such that for target vectors k except for a set of j--maaure for the GF trajectory w w() E R defined by ① we have lim; O0 w (I)) fi-
We give now sketch of proof of Theorem 6 illustrated by Figures and
3a
3c
The key challenge in proving this theorem is to ensure that for 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, typical point w in the parameter space belongs to large number of optimization trajectories with different targets f, and all these trajectories are controlled by a single map
R² + R
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 Fo (product of one-dimensional sets) of almost full measure (see Figure 2). This Cantor set is constructed by sequence of "carving" (or "splitting") stages. Accordingly, the map & is sub-divided into sequence of maps ((n) associated with stripes of the w-plane and aligned with the respective carving stages (see Figures 3b).
One of the two parameters, u, always increases during GF for targets from Fo. and the map & can be described in terms of the "level lines" 4, = {(u, v) v E R) in the parameter space and the respective "level curves" ((,,)) in the target space. To detine stage-n sub-maps ((x)) corresponding to levels of the target Cantor hierarchy, we choose discretized sequence 0- 14 < u1 < U2 <....
The domains of the maps (n) are then separated by the respective level lines [(m) = I.... The stage-n map (m) can be thought of as describing the transformation of the level curve 4 (((")) to (1(++1)).
Each stage n is associated with a particular splitting index kn E (1,...,d). The level curve (((m))
includes multiple linear segments ((((()) oriented along the k, 'th axis and approximately coinciding ("aligned"") with certain one-dimensional edges of the boxes (²(") that represent the n'th level of the Cantor set Fg- During each "carving" stage each box B((") is split into sub-boxes B(a+1) along the axis kn At the same time, the map ((x) describes the transformation of the aligned segments & (((")) to the neve- segments & ((((+))), aligned with the boxes B along the axis kn+1-

---

Lun
lawes
w w(tx+1)
a ww(t)) )
((fn+2)
((x))
Mm
J2,,12
(a) Stage-wise decomposition of the map The map defined by its stages (()) f/un SuSunt separated by the level lines ((m) Lu, [(u,v)
un} and respective level curves ((((m)). Each stage ((") deforms the level curve (((()) in the splitting direction # to form the new level curve ((I(++1)), A
non-exceptional GF trajectory w(t) (u(t),v(t) passes through all level lines. The splitting indices kin cycle over the values 1,...,d to ensure convergence w.r.t each coordinate.
k..
B 1)
1 (1
(((+1))
(1,))
gm+1)
((w(tn+13)
((w(t.))
B ((++))
(b) Box splitting and curve-box alignment at the stage (x)) The stage curve ((((")) includes segments ((a) (thick red and blue segments) aligned with respective boxes (3()) of the box hierarchy. On the right, a box B{()) (the big square) split into 2s,, smaller boxes B(++1) along the splitting direction #x,, Accordingly,
aligned segment ((*) is transformed into 6 new aligned segments ((n++1) (thick blue). The splitting only affects the coordinates æx,, and #k,+1 During the splitting, gaps left in the direction æk., between the child boxes, and the direction ii,, between level curve 4 ((((")) and the child boxes, to accommodate convergent GF trajectories. Each exceexcctti GF trajectory w(t) passes through some aligned segments ((.) . ((++1)
D ((W((n++1)
B(a+1)
4 (w(()))
2a
Tk.ee
(c) Transition from (((())) to ((((++1) through intermediate level curves ((I,)), ((l,),))(),))),, ((l.-),(((..) (violet). These curves ensure that during the n'th stage, for all targets f = (fi...., fa) in the respective box B( a point & (tw(t))) having coordinate 4t,, (w(tn))
fc, moved by GF a point ((w(t,-1)) with a coordinate 4 (w(fn+1)) &e fRom1. The points ((((t)) are approximately those closest to f on the respective level curves. To avoid local minima, the level curves (lo.) at each must be deformed at each to bring such points closer to f. The desired propagation from (ww()))) to ((w(l.-1)) can be achieved by deforming (l... so as bring &( (((()) the tip the line (t...) ("gathering sub-stage") then extending this tip so as to let & (w(()) slip off it at the appropriate position 2 ("spreading sub-stage").
Figure 3: The map from Theorem (see Section A for details).
7

---

During each stage part of the box /%x is removed and the map Φ(x) is adjusted so to ensure that for each target from the resulting Cantor set Fo the GF trajectory goes through some aligned pieces $ (1 to the very point f. In a particular stage the GF trajectory "goes around the corner" of the next-level box (see Fig. Be), so that the agreement of the current approximation & (ww(tn)) with f in coordinate kn+1 is substantially improved at the cost of a slightly degrading agreement in coordinate kn As the boxes become smaller, the overall disagreement between Φ (t((t,) and f gradually vanishes.
For general targets in the current box _ the GF trajectory can get trapped at a local minimum in particular, if the coordinate fk..1 of the target is close to the respective coordinate of the aligned
level piece )((""). For this reason, some parts of the box g(") 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 ensure that all the vectors f E Fo are learnable and the measure yu (Fo) is arbitrarily close to the full measure.
5 Models expressible by elementary functions
The model & constructed in Theorem involves an infinite hierarchy of maps ((() and as 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 only feature of our proof. We conjecture it to actually be a necessary feature of models $ R.W + Rd when W < d and the set Fg of GF-learnalle targets is sufficiently large, say has a positive Lebesgue measure in R..
One setting in which we can prove this conjecture is when the closure + ( of the image &b ( 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 (RW) has measure O for so-called Pfaffian functions known to have strong finiteness properties KKhovanskii [991]. 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 91...., 9t of real analytic functions defined on a common connected domain U R W and such that the equations
Bos 8uy
(w) = PPy( (ww.:w.www
ISi 15J5W
hold in U for some polynomials P.z. A ffnction function in the chain (gi..... 91) is a function on U that can be expressed as a polynomial P' in the variables (w, 91 (w), ... . (w)). Complexity of the Pfaffian function is determined by the length of the chain, the maximum degree a of the polynomials P.j. and the degree 3 of the polynomial P. and can be defined as the triplet (1, a, We say that
vector-val valued function (ww) = ( (w)..... L (w) )) is Pfaffian if each component O; 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 Pfaffan functions is quite large.
Theorem 7 (Khovanskii, "elementary functions are Pfaffian"), Suppose that a function g on a domain U C RW is defined by a formula constructed from the variables wi...., WW using finitely many real numbers, standard arithmetic operations (+, -, x/)), elementary functions functiion In, exp, sin, arcsin, and compositions. Suppose that for each w U the value g(w) is well-defindd in the sense that during the computation the functions In and aresin are applied on the intervals (0, oo) and (-1, respectively, and there is no division by O. Moreover, suppose that there is bounded interval (a, b) to which the arguments of sin always belong for all w E U. Then the function 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 + Rdd is Pfaffian map and W < d. Then the closure ((RW) has Lebesgue measure 0 in Rd. In particular, the GF-leurnable targets Fo have Lebesgue measure 0 in IRd.
If is defined by elementary functions involving sin on an unbounded domain, then (RR) need not have Lebesgue measure 0. As the simplest family of examples, consider + (#1...., 42) given
8

---

1
(00)
(300
0.5
Figure 4: The curve ((w) = (sin(w) sin 22w) densely fills the square 1-1, but for all targets f except for set of Lebesgue measure 0 the re- spective GF trajectory w(t) is trapped at a spurious local minimum that 4 ((w(t)) A f. Corollary I0 shows that this true for all models (6 with any number of parameters W d.
0
Pifft
0))
-0.5
0
sin sin(w)
by
(.(w) = sin Σ ayww); i= i= I=.....,d
(6)
with some constants Gij. Kronecker's theorem [Koneeker 1884 Gonek and Montgomery 2016 implies that the points (E, "iy E, ady wyy densely fill the torus (R/2*2) as w runs over (ail..... a.w) ). = ,,...,d, d, are linearly independent over the rationals Q Accordingly, in this case ((T [-1, 1jd. However, the GF-learnable targets will still have Lebesgue measure 0 due to the prevalence of trapping local minima, as can be seen by suitable extension of Theorem 3
R whenever the vectors
W < and 4 BRW + Ed be C2, Suppose that for some open U C IR the first and second derivatives of are uniformly bounded on 4 (U), and also the Jacobi matrix J(w) 8 (w) is uniformly non-degenerate there in the sense that the lowest eigenvalue of Ow
Proposition 9 C Let
J J'(W) is uniformly bounded away from O on Φ- (U). Then F& NU (TRWW.
Rd be given by Eq. (6) with some constants aij- Then, regardless of these constants, the set F&, of respective learnable targets has Lebesgue measure O.
Corollary 10 (D. Let 1 W < d oc and R
In Figure 4 we illustrate this result for W 1.
Summarizing, Theorems imply that if the sealar components the map RWW -> Rd with W < d are elementary functions not involving sin (or related functions) acting on an unbounded domain, then & can Ge-learn only exceptional targets in Rd Moreover, even if Φ involves sin, there no obvious mechanism how this would help GF-learn non-negligible set of targets: examination of the basic family of sin-models (6) Corollary 10 suggests that GF trajectories would still be predominantly trapped at spurious minima.
Discussion
Main takeaways. Our results show that GFFllearnigg with the number of parameters less than the target dimension is objectively problematic, but not impossible. By Theorems Bndd 4 the set of non-lcarnable 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 that if the targets are described by a known probability distribution, then is possible handcraft a (fairly complicated) model with just two parameters that learns the targets with probability arbitrarily close to I. The learnable targets in our proof form multi-dimensional Cantor set. Such a complicated structure not surprising, since by Theorem 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 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 p(H) = oc. It was crucial for our proof of main Theorem that we could restrict our attenton to targets lying in a bounded box in R4, We could consider only such targets because if ju is Borel measure on _d and (IIR)) < co, 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 ((R1)) = oc, e.g. the Lebesgue measure. In this case there is no reduction bounded box. and our methods don't 't seem to work.
Infiniteddiment dimensiondl target spaces. We prove Theorem 6 only for finiteddimensional target spaces H. but one can also ask if it holds for an infinitediimensional 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 largets cannot be dense in the target space g if the number W of parameters is less than d (Theorem 3) heavily relies on the relatively strong assumption that 4 is C2 and has a full rank Jacobian the initial point. It would be interesting to clarify if this result holds without nondegeneracy assumptions and under weaker regularity assumptions, say for d differentiable with Lipschitz gradient as sufficient for local integrability of the gradient flow.
Learnable sets for general 1 <. W <, dl It would be interesting generally describe target sets that can be GF-learned for 1 < W < d. Our Theorem 66 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-dine dimensional spheres contain lower-dimensional ones, but not the other way around), suggesting that with higher W learnable sets become larger and more regular.
Von-learnability using elementary functions involving sin. As discusssed in Section5] we expect that the high- gigh-rrbbbbility learning proved in main Theorem cannot be established using models expressed through elementary functions, even if they involve sin with unbounded arguments.
Acknowledgment
The author thanks the reviewers for several useful suggestions that helped improve the paper.
References
Peter Auer, Mark Herbster, and Manfred KK Warmuth. Exponentially many local minima for single neurons. Advances in neural information processing systems, 8, 1995.
Bolton Bailey and Matus Telgarsky. Size-noise tradeoff's in generative networks. Advances in Neural Information Processing Systems, 31, 2018.
Marco Baity-Jesi, Levent Sagun, Mario Geiger, Stefano Spigler, Gérard Ben Arous, Chiara Cam- marota, Yann LeCun, Matthieu Wyart, and Giulio Biroli. Comparing dynamics: Deep neural networks versus glassy systems. In International Conference on Machine Learning, pages 314-323.
PMLR, 2018.
Michael Boshernitzan. Universal formulae and universal differential equations. Annals of mathemat- ics, 124 1986.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 13:1877-1901, 2020.
Georg Cantor. Ein Beitrag zur Mumnigfaliggkeisslhree Journal für die reine und angewandte Mathematik (Crelles Journal), 1878(84):242-255) 1878.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over per-pearamteriieed models using optimal transport. Advances in neural information processing systems, 31, 2018.
Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In Artificial intelligence and statistics, pages 192-204. PMLR, 2015.
10

---

Constantin Christof and Julia Kowalczyk. On the omnipresence of spurious local minima in certain neural network training problems. Constructive Approximation, pages 1-28, 2023.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
Ronald A Derore, Ralph Howard, and Charles Micchelli. Optimal nonlinear approximation. Manuscripta mathematica, 63(4)):69-477, 1989.
Andrei Gabrielov and Nicolai Vorobjov. Complexity of computations with pfaffian and noetherian functions. Normal forms, bifurcations and finiteness problems in differential equations, 137: 211-250, 2004.
Steven M Gonek and Hugh L Montgomery. Kronecker's approximation theorem. Indagationes Mathematicae, 27(2):506 523, 2016.
Namig J Guliyev and Vugar E Ismailov. A single hidden layer feedforward network with only one neuron in the hidden layer can approximate any univariate function. Neural computation, 28(7): 1289-13044 2016.
Namig Guliyev and Vugar E Ismailov. Approximation capability of two hidden layer feedforward neural networks with fixed weights. Neurocomputing, 316:262-269, 201 8a.
Namig
Guliyev and Vugar Ismailov. On the approximation by single hidden layer feedforward neural networks with fixed weights. Neural Networks, 98:296-306 304, 2018b.
David R. Hilbert. über die stetige abbildung einer line auf ein flächenstück. Mathematische Annalen, 38:459-460, 1891.
Boris Igelnik and Neel Parikh. Kolmogorov's spline network. IEEE transactions on neural networks, 14(4):725-733, 2003.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
A. G. Khovanskii. Fewnomials. Vol. 88 of Translations of Mathematical Monographs. American Mathematical Society, 1991.
Andrei Kolmogorov. On the representation of continuous functions of many variables by superposition of continuous functions of one variable and addition. In Doklady Akademii Nauk, volume I 114, pages 953-956. Russian Academy of Sciences, 1957.
Mario Köppen. On the training of kolmogorov network. In Artificial Neural Srlworks-ICANE 2002: International Conference Madrid, Spain, August 28-30, 2002 Proceedings /2, pages 474-479. Springer, 2002.
Leopold Kronecker. Näherungsweise ganzzahlige Auflösung linearer Gleichungen. Monats. Königl. Preuss. Akad. Wiss. Berlin, pages 1179-1199 1193, 1271-1299, 1884.
Véra Kürková. Kolmogorov's 's theorem is relevant. Neural computation, 3(4):617-622, 1991.
Vêra Kürková. Kolmogorov's theorem and multilayer neural networks. Neural networks, 5(3): 501-506, 1992.
Miklós Laczkovich and Imre Z Ruzsa. Elementary and integral-clementary functions. Illinois Journal of Mathematics, 44(1):161-182, 2000.
Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural networks, 6(6):861-867, 1993.
Vitaly Maiorov and Allan Pinkus. Lower bounds for approximation by mlp neural networks. Neuro- computing, 25(1-3):81-91, 1999.

---

Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two- layer neural networks. Proceedings of the National Academy of Sciences, 115633)E77655-7777 2018.
Hadrien Montanelli and Haizhao Yang. Error bounds for deep relu networks using the kolmogorov- arnold superposition theorem. Neural Networks, 129:1-6, 2020.
Giuseppe Peano. Sur une courbe, qui remplit toute une aire plane. Mathematische Annalen, 36: 157-160, 1890.
Dmytro Perekrestenko, Stephan Müller, and Helmut Böleskei. Constructive universal high- dimensional distribution generation through deep relu networks. In International Conference on Machine Learning, pages 7610-7619. PMLR, 2020.
Dmytro Perekrestenko, Léandre Eberhard, and Helmut Bölcskei. High-dimensional distribution generation through deep neural networks. Partial Differential Equations and Applications, 2(5):64, 2021.
Grant M Rotskoff and Eric Vanden-Eijnden. Trainability and accuracy of neural networks: An interacting particle system approach. arXiv preprint 1805.00805 2018.
Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. In International conference on machine learning, pages 4433-4441, PMLR, 2018.
Filippo Santambrogio. (Euclidean, metric, and Wasserstein] gradient flows: overview. Bulletin of Mathematical Sciences, 7:87-154, 2017.
Johannes Schmidt-Hieher. The Kolmoggrov-arrole representation theorem revisited. arXiv e-prints, pages arXiv-2007, 2020.
Shaden Smith, Mostofa Patwary, Brandon Norick, Patrick LeGresley, Samyam Rajbhandari, Jared Casper, Zhun Liu, Shrimai Prabhumoye, George Zerveas, Vijay Korthikanti, et al. Using deepspeed and megatron to train megatron-turing nlg 530b, a large-scale generative language model. arXiv preprint ar arXiv:2201.11990, 2022.
Grzegorz Swirszez, Wojeiech Marian Czamecki, and Razvan Pascanu. Local minima in training of neural networks. arXiv preprint arXiv:161 1.0.3611..0611. 2016.
Dmitry Yarotsky. Elementary superexpressive activations. In International Conference Machine Learning, pages I 1992-11 1940. PMLR, 2021.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small nonlinearities in activation functions create bad local minima in neural networks. arXiv preprint arXiv: 1802v 0802.03487 2018.
Thierry Zell. Betti numbers of semi-pfaffian sets. Journal of Pure and Applied Algebra, 139(1-3): 323-338, 1999.
Yi Zhou and Yingbin Liang. Critical points of neural networks: Analytical forms and landscape properties. arXiv preprint arXiv:1710.11205 2017.
A Proof of Theorem 6
Hierarchical structure of the Icarnable set. We will construct a set Fo such that (u(F)) > 1 - and for a suitable model t _ + Rd the targets f are @-learnable, i.c. Fo C Fg. thus ensuring that u(Fs) > 1 - e. We will occasionally refer to targets from F, (respectively, from the complement Rd Fb) and the associated GF trajectories as non-exceptional (respectively, exceptional). The set Fo has the form Fo = n Ua ((()) where (! a nested hierarchy of rectangular boxes Rdd (see Figure 2). Each level-n box B.("
(m) contains several non-intersecting level-(n + 1) sub-boxes 13(3 (n+1)
of equal sizes (e.g, the big box shown the right of Figure 3b contains 6 sub-boxes (
12

---

The sub-boxes B of the 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 (u(F)) > 1 c. In particular, we choose the root box = B()) as = [-c, c)d, where e is large enough so that (BB) > (183)1-11 e/
Box splitting. The next-level boxes B/x+1) are obtained from the parent box B(a)) by what we call splitring (also referred to carving in the main text). Choose some sequences of splitting coordinates Jk., with hin E {1,....d} and integer splitting numbers Sn, n. = 1,2,... We require that kn+1 # ki for all n.
The number of child boxes B/ B contained in the parent box B²x) 2sh (e.g., 8n in Figure 3bp.
The splitting of the parent box B(a)) into 1z(+11) only involves the coordinates Ik, and TR441' Specifically, if the parent box has Ik.. E [a, b), then the child boxes B with B = 1,.................. 28n have 2b, E [a + (3 - 1)hr + En. a + 3hn, - 6n). where hn = (b - a2/(2sn) and en > 0 is a sufficiently small number. Regarding the other coordinate I 2h the parent box has 2k,-1 E [c. d]. then the child boxes will have Tkn+1 E [c+ 2hn, d] or 2h,411 E [c, d - 2/m], depending on whether the aligned piece of the level curve lies near the side with Ik,,11 = c or with Thh+1 = (see details on level curves below).
The splitting along Fk., will ensure that the GF trajectory gets closer to the target in the (IR., , FRR44 )- plane, while the Jh contracction 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 Fo C Fg. and ((Fo)= > e.
The two parameters and u-monotonicity. Let and be the two parameters of the model, that w = =-uu v). These two parameters will play very different roles. We will ensure that for all non- exceptional targets f E Fo. u(t) is 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 R2² in which L. < 0, so that du trajectories w(t) and (t) by 2 O.
de > 0 by definition of GF. In particular, this allows to parameterize the
Level curves. The map & can be described in terms of the curves (u,, e) where u is fixed and v varied. We refer to the respective straight lines L, = {(u, v) o E [R] C TR22 in the parameter space as level lines and the curves (l,). C H in the target space as level curves. A GF trajectory w(t) can be specified by single point each level line 4.
Level-set-based description of 4. It will be convenient to simplify the description of the map & by only describing the level curves ((I,) as subsets of H. without specifying parameterizations + (uu, 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 & RR2 + H. and define a new map & by stretching the variable u by large factor X: D(u, v) = $(u/A,u) v). This rescales the u-derivative: O x 0- Then, at À >> 1 we have |8, << | and accordingly [0, Lel < | unless | ~ O. 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 GF trajectory can be approximately found by locally minimizing the distance to the target on the level curve & (lu(t)):
w(t) w (u(t)); w'(u) mig ||f ([(()]]
wel.
In general, the minimizer here should be local, but in our construction of &b 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 T (Fig. 3a). Our construction of T is described in terms of hierarchical structure of level sets aligned with the hierarchy of boxes R²("), First, let 0 = tio < u1 <
U2 < ... be sequence of particular values of u. We construct the map & separately for each strip
13

---

{(u, v): un S u S un+1). We refer to the respective restriction ②(n) = O Llu,, SuSun+r as the n 'th stage of 4. The monotonicity of u(t) for targets f Fo will ensure that each respective trajectory w(t) sequentially passes through all the stages in their natural order. We denote by ((x) la the level lines serving as the boundaries for the domains of the stages 4(").
Each stage ((") is associated with the splitting of the level-n boxes BL") and can be viewed as defining a deformation of the level curve ((((m) to the level curve $ (((n+1)) lying closer to the targets in the new boxes B (
Aligument between target boxes and level curves (Fig. 3bb. Each box _Ln) is accompanied by respective aligned piece (((")) of the level curve ((((m),, where z(a) is segment of the level line ((m), and the segments corresponding to different a are disjoint. The aligned piece &b (((5") is a straight line segment. It lies outside the box B(") but close to of its ID edges oriented along the splitting coordinate TR.,- As u increases from Un to un+1, the level curve segment + ((!!") is deformed in the new splitting direction 1 so that ((((=11) now contains segments (((++)))
aligned with some Tka+1 Tka+; -oriented edges of the sub-boxes = and the new stage + 1 can commence.
We will ensure that each non-exceptional trajectory Φ (w()) goes through one of the aligned pieces &b (1(h)) at each stage n.
Reformulations of u-monotonicity. We need to ensure the u-moootonicity of non-exceptional trajectories, i.e. the condition T (t) holding on the whole trajectory w(). In terms of the map क. this condition reads
(0. (t),, ((w(t))) > 0.
(8)
At a local minimizer w" (u) given by Eq. we have (0, (3w (w)), x(w" (w)) 0. Then, if GF trajectory is approximated by the minimizer trajectory w = w (u) (by stretching the parameter u), the condition of u--mootonicity becomes
d du llf o ((w < O.
(9)
One can also equivalently write this last condition in the form
0,000 (u)), f 2(w" (u))) 0,
(10)
where Pal. a. Ou (w) denotes the projection of O, (w) to the direction orthogonal O (w) in the plane (0, ( w). a, (w)). Condition (TOp means geometrically that level curve (lwx) locally, near
the point 4 (w" (u)). gets closer to the target f as u increases.
Transition from &b ((())) to ((((++1) (Fig. (e). During the n 'tth stage, all the components of the map ((n) R² + IRd are constant in the strip {(,, v) : Un + e < u < un+1 - e} except for the components kn and kn+1 associated with splitting directions. Here, we consider substrip un + < u < ua+1 - 6 of the full stage-n strip Uh S u S Un+1 because we need to ensure that T is C In the remaining narrow substrips un S u S Un + and un+1 --11-6 C u S un+1 the map ((n) is smoothly connected to the maps (fx-1) and ((x+1), respectively. It easy to see that such a smooth connection can be ensured with arbitrarily small by additionally suitably varying the components kn-1 and kn+1 in the respective substrips; we omit these details.
We construct the map & so that each aligned piece ((((")) ) is a segment of the straight line oriented
in the splitting direction TR.,- In each box [²()) the transformation of the level curve the 2s,,
next-level pieces is performed symmetrically (Fig. 3b), so we need to only describe the transformation in one of these 2s, sub-boxes (Fig. Bc).
Suppose for simplicity that the sub-box B(")) in question has the form [0, a] x [0, b] w.r.t. the
coordinates (#a,, #*A,, .) and the aligned curve (((())) lies to the left as in Fig. 3c (a general case is treated similarly using translation and possibly a reflection). The intermediate level curves
(l.,), un S u S Ux+1, 1, can then be generally described the (IA.,) 2k 1) plane as formed two sub-stages separated by some sn (un, Un+1).
14

---

1. "Gathering" sub-stage E [un, w²]: for some é > 0 the level curve ((a,) can be given on the segment 2k, E [e, a - c| by 2kn-1 a(,) ?(u) with some small monotone decreasing E(u) > 0 and some monotone increasing a(()) such that a(un) = 0 and a(u")= = 1. In particular, at = u" the level eurve is given by skh+1 = Fk, - =(u"). the remaining small segments Fk. [0, c U (a - c,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 the interval (a e, a] as function 2R,,1
22 (IKK.).
2. "Spreading" sub-stage E [u" Un+1]: J: the level curve ((4,,) is evolved by extending its tip at I'k a all the way to Tku41 > b. Specifically, ((..) contains a straight line segment (u)) parallel to the axis Tkn+1 and eventually, at u un+1, including the aligned piece
$ (155 The kk. position of the segment [(u) is monotone decreasing in u, but remains close to a. The JR..I1 position of the left endpoint of ((u) remains close to a, while for the right endpoint Th increases from around endpoint remains smoothly connected by suitable concave are to the analogous point in the neighboring box. See Fig. 3c for an illustration.
6 as u increases from u² to Un+11 The right
The idea of this whole construction is to ensure that, as u is increased, the points on the level curves (lu) closest to the target f go around the corner of the box BB(+1) as shown in Fig. 3c The purpose of the "gathering" sub-stage is to force the trajectory o (w(()) by u² to get to the tip of the level curve (1() (hu.) at at. a. Then, in the "spreading" sub-stage the trajectory remains close to the moving tip until its coordinate 11,, reaches the respective coordinate Sk.,: of the target f, after which the trajectory slips off the tip to the straight line segment / [()) (the concavity of the ares mentioned above ensures that the trajectory is not trapped on the ares). The trajectory then maintains the target coordinate (f(w(u))) km+1 = =fint until reaching the aligned piece $11 (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 [J,,, belongs to the domain swept by ((") (i.e., (fr. fk E ((n)) (Iz) for some ū (un, un+1)). In this case the u-monotonicity conditions (
(10) are violated for u 2 ū 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 Jk.. R a. This occurs for the targets f such that fr. + fkutt S 2a for such targets the trajectory gets stuck near the orthogonal projection of Skae,) to the line Tk.+1 Ik..
Finally, if fk. O, then the kn component of the trajectory is stuck 0 too. Moreover, if Ss,, is nonzero but close to O, then the trajectory & (w(())) remains close to the plane Fk. = 0 and so again fails to reach the tip region. (This happens because near this plane aD ((w))) R O, invalidating our argument that we can ensure |å,Lrl < Lrl by stretching the variable u the necessary stretching blows up as fx.. 0.)
If the target f lies outside these three regions, then the map ((r)) succeeds in guiding the trajectory & (t) from a point on the aligned piece (<((()) near the orthogonal projection of f of that piece to a point on the aligned piece ((((+t))) near the orthogonal projection of f to this piece. In particular, it is sufficient to require that (fk., fA,)1) belongs to the rectangle R = [e, a - e] [2a, b] with some E > 0: we can then suitably stretch u and adjust the map ((") so that for all targets with (fr., fk.4:) E R the above transition holds, and morcover 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 = of the left level line (00) = {((u v) : u = 0} of stage O. Its right level line z(1) = {(u, v) : u = u, } has single aligned piece ((1(") aligned with the initial box B()) at some 1D edge along the direction
Tky- We only need to ensure that for all targets f in the initial box B(1), the GF trajectory approaches
by u- = i1 point on ((((1) close to the orthogonal projection of f to ((1())).
Recall that ((1) = [-c, cjdd, Suppose, for example, that the edge question is (c, -c] x (c, cy...,., c) and the aligned piece of level line is [c, -c] (a, a..... a) with some a > Then we can define
15

---

( as the linear map
Φ (0)
uu, 8
i= 1 u
(11)
aa+1 a
1> 1.
is easy to see that for all f E B the respective GF trajectory (u(t), v(t)) satisfics du > and, by choosing in large enough, at & such that u(tz) ii will have (e(t) fil with arbitrarily small c.
de
Ensuring convergence inf, (t) for all f Fo- The presented construction of the maps ((n) and the boxes BB ensures that for all targets E B the following approximately occurs with the components of the respective discrepancy vector ((((t) result of the n ''th stage of GF:
1. The component ka+1 approximately vanishes.
2. The component k., which is approximately nonzero, but limited by the size of B(=+1) the kn 'th coordinate direction.
the beginning of the stage, becomes
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 smoothing of the overall map & at the boundaries of the restrictions d(n); all these corrections can be made arbitrarily small).
Clearly, it follows that if the sequence k, takes each of the values 1,..., d infinitely many times,
then, since the size of B B(=+1) in any direction vanishes in the limit oc, the vectors f ((w(t))
converge to 0 for all targets from Fo - U₂ B!a)
Ensuring (Fo) 21 - The set Fo is obtained by removing countable number of rectangular parts from the root box (()) that was chosen to have measure yu ((B()) > 1 - c/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 (n+1) the direction hin-
2. Those associated with the gaps between the aligned pieces (() and sub-boxes (n+1) in the direction kn+1.
The width of the parts 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 is the width of the sub-box 2 in the direction k. (see Fig. 3c). However, can also be made arbitrarily small by increasing the splitting number 8,.
Employing the o-additivity of μ. we conclude that the only obstacle to making the measure of the removed parts arbitrarily small is that some the splitting hyperplanes of co-dimension used in the construction have positive measure (and we cannot make the measure of the removed parts arbitrarily small by decreasing their width). However, the number values such that u( (ax = c)) 0 is countable, so we can avoid such hyperplanes by slightly shifting the root box B())
B Proof of Theorem g
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 domain U; we will assume for simplicity that U = R (see Remark 2.12 in Gabrielov and Vorobjov (2004)). ) We state the result form suitable for our purposes (see, e.g., Corollary Gabrielov and Vorobjoy (2004)).
16

---

Theorem 11. Let ,......99 99 be Pfaffian functions on IR Then the number of connected components of the set
{w R.W. g9((w) - ... g (w) =0
(12)
is bounded by a finite value only depending on k and the complexities of the functions 9:-
important special case occurs if W and the solutions of the system (12) are non-degenerate dag in the sense that the respective Jacobians Bhy (w) are non-degenerate. In this case the level set
(12) consists isolated points, and their number is bounded by a number only depending on the complexities of the functions 9t-
The proof of Theorem is a reduction Theorem
Proof of Theorem 8 It is sufficient to consider the case W = dd-1a (by trivially extending & to more arguments). It is also sufficient to prove that ((RW) has Lebesgue measure 0 in the cube [0, 1]d: by rescaling and shifting, it then has Lebesgue measure in any other cube and then, by o-additivity, in the whole space I
Let N be a large integer. Consider the d-dimensional grid of cubes A, of size given by
An = ty E Rd y. + S 34 S y + " n = ===n (ni...., nd) Zz
(13)
where y (yi ................................ v() is some reference point.
For each i 1, ,..., d consider the map क. R. Rd-11 N R.W obtained from & by removing the i'th component, i.e. b (4 (#1...... 2.-1: .I. Da). We will choose y" that for each and z" the point
yta (vi,... Vi-b4i411 1............................ vā) + N
(14)
a+: (w) is non- Bhy degenerate. To this end, recall that by Sard's theorem the set VÚ; of critical values of 4; has Lebesgue measure 0. Then the set V/' = Usezw (V:- ②) also has Lebesgue measure in Rd-1 It follows that V."" = (y E IR (yi...., 1 11+11 ................................ Ma) E V/} has Lebesgue measure 0 in Rd. Then V= - V"" also has Lebesgue measure 0 in Rd. The complement Rd \ V is precisely the set of all y such that the values (14) are non-critical for all and fi. Since IR V has full Lebesgue measure, can find suitable y" moreover, we can choose
a non-critical value of L,, i.c. for any w such that (w)) = Yiñ the Jacobian
that 0 < vI N. which will be convenient.
Consider the cubes An lying in [0, 1]3, i.e., with fO...., N 2) There are (N 1)d such cubes. Suppose that the interior of cube An contains a point of (RR"). Then, since (KR") is connected, either (RR" An or ((R") intersects the boundary of An. In the first case the Lebesgue measure of (RW) does not exceed N-d, so if this case occurs for arbitrarily large N, ((BW) has Lebesgue measure 0.
We can thus assume that if the interior of An contains a point (RR then the boundary of An intersects & (TRW). We will argue now that the number of such cubes An in [0, 1] is O(Nd-1), i.e. is vanishing compared to the total number (N - 1)d of the cubes.
Indeed, the boundary of An consists of cubic faces of dimensions 1..... d (ignoring the vertices.
i.e. faces of dimension 0). Let s be the lowest dimension of a face intersecting ( (RW). Denote by R such a face. Consider two cases.
1. s 1. 1. In this case the face R is a segment oriented along some coordinate i and with the other coordinates forming a point Yi, of the form (4). Recall that by construction the
points Yt, are non-critical values of the map क. The pre-image b-)(R) is subset of $ (y,,n) and so it consists of isolated points. Since A, 1]", the multi-inded ñ of the segment belongs to (O....,
1]d=1, By Theorem I1 the number of points in क (y: is bounded by constant only depending on the complexity of the map 4. The total number of points in the pre-image - E {O...., n- - 1)d-1]) is then O(Nd11). follows that the total number of points mapped by & to one-dimensional faces of all the
17

---

cubes An C. [0, 1]4 is O(NV-1). Since each of these faces is face for at most 2d cubes, we conclude that the total number cubes An C [0, 1] whose one-dimensional faces intersect Φ ((R iis O(N
2. s > 1. In this case the intersection At n ((Rd)) lies in the interior of the face R. Let -= (.,) be the coordinates along which the face oriented. Similarly to the case 8 = 1, consider the map 1 obtained from by dropping all the components i E The pre-image & (1t) lies in the pre-image 2 (y) of the point y E R2- formed by the coordinates i I of the face R. Since R n 4 (R.) lies in the interior of the face R. is a subset of , (y) disconnected from the rest of ( In particular, if there are several s-dimensional faces (of several cubes) with the coordinates & I forming the same point y and having non-empty intersections with ((R)) that also lie in their interiors, then there are at least as many connected components in the pre-image 1 (y). By Theorem 11 the number of these connected components is bounded by constant. Since possible values y belong to (d - s)-dimensional grid with spacing N. the total number of such faces in the cube [0, 1j (over all possible y's) is O(Nd=*), and then the number of respective cubes is also ONN-=s).
the pre-image x- (Rt (
Taking the limit N + 0o, conclude that the Lebesgue measure of ((RW) is 0 desired.
C Proof of Proposition 9
Let f E U and (wo) < for some Wo- We will show that if is small enough, then there is a barrier of high loss the sphere bounding the ball Bwar {w E w2 : ||w woll = r) with suitable radius r. Then, f belongs to the closure 4 (Bworr). while, by compactness and continuity, B(Bwa.r) = 3b(Bworr C (
Assuming and Aw = W- wo are sufficiently small so that the segment (wo). [(w)] C (U),
we have c||Aw/| S (w) Aw| || < C'IAw/| and [[ )- x(wo) - J(wo Aww] C||Aw/| with some U-dependent constant 0 < c, C < oc. Then, with | =r,
Lr(w) Lr(wo)
2 - (2)) //1 f- ((wo)ll
(15)
[l(((w) - (w())) - (f (ww)), ((w) ((wo))
(16)
)1ll( Awll Call--clllwwwwww [tWp:////////////V///\//w////a/ + C'IAw
[3)
(17)
-2p3
C2ps - -V2C- +2))
(18)
Choosing c//3, small c we get Lr(w) Lr(wo) uniformly on BBworrs as desired.
D Proof of Corollary 10
First, observe that the loss is constant along directions orthogonal to the rows of the matrix A = (ac)). 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 (w(w) = sin( wyy b.) with some constants b; and a matrix A that has full rank W. The Jacobian J(w) 2w (w) can be represented as J(w)= = (A where D(w)= diag cos Σj= Wy + by), = 1.....d.. d).
Now let U (-c, c)dd with some < c < Then, for all w o (U)( the diagonal elements 0:jW1 + b.) of the matrix D(w) are uniformly separated from by a distance not less cos( - j-
W
than v1 d² > 0. Hence, in the operator sense, J' ((ww) A ( (1- A al for some ē > 0, i.c. J(w) is uniformly non-degenerate on Φb (U)) Applying Proposition 9 we conclude that Fo c 0(-1, 1]d "). which has Lebesgue measure 0 Rd.
18

---

NeurIPS Paper Checklist
1. Claims
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 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 is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations 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
g 10 results.
Guidelines:
The answer NA means that the paper has 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 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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or 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 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
19

---

Answer: [Yes]
Justification: For each new theoretical result (Theorems 2 3
4
6
8
9
10
the paper
provides the full set of assumptions and complete and correct proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
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.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
20

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper is purely theoretical and does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ "cippscc/puullc//uuu /ttoe//uuuddeeoooouuumbiiiiiii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
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 experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of 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 authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
21

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 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.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with NeurlPS Code of Ethics http:///www.ppp.ccpppppp///eeeia
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consid- eration due to laws or regulations in their jurisdiction).
10. 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 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 why the paper does not address societal impact.
22

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 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 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe 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)?
Question:
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 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 best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include 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 use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
23

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.


Reviews:
[{"review_id": "OjMLpWlExD", "reviewer": "Reviewer_MmYK", "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.", "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. \n- 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). \n- 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. \n- 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. \n- 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. \n- 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. \n- 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.  \n- 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? \n\n\n[1] KAN: Kolmogorov–Arnold Networks. Liu et al. 2024. arXiv:2404.19756.", "limitations": "The limitations are discussed in the submission.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The main strength of the present submission is the strong theoretical apparatus built to prove the desired results. From the text, the authors specify what results are conjectured and what are rigorously proven. On the other hand, the formal presentation sometimes penalizes the readability of the text (see the section below).", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the careful reading of our paper and many useful comments.\n\n* \"*I would enlarge the discussion part [of Section 5]*\"\n\nThank you for this feedback. Indeed, we agree that it can be useful to add some comments and maybe a graphic illustration here.\n\n* \"*Am I correct to understand that general non-linear function are not admissible in the present setting?*\"\n\nTo 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. \n\n* \"*Maybe the authors could use also polynomial targets in their \"Examples\" paragraph*\"\n\nSure, we do that (our third example).\n\n* \"*How would the present construction relate to general kernel /random feature methods?*\"\n\nOne 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$. \n\nIn 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$.  \n\n* \"*I feel like the nomenclature for target-dimension as $d$ is confusing*\"\n\nThanks for this feedback; we'll clarify this point.\n\n* \"*Below Eq. (1) I would expand on what is meant to be \"locally solvable\"*\"\n\nThanks for this feedback, we'll clarify that (\"locally solvable\" means solvable at least for a finite interval of times).\n\n* \"*Is there a connection of your results to the recent work [1]?*\" \n\nYes, 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. \n\n* \"*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?*\"\n\nThe condition that GF starts from $\\mathbf w(0)=0$ is not important, one could instead start GF from any fixed $\\mathbf w_0$.\n\nRegarding 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jWxLT5fxVP", "reviewer": "Reviewer_XxKo", "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$.", "questions": "- Why is it necessary to restrict to $\\mathcal{H} = \\mathbb{R}^d$? Is it possible to extend the arguments to infinite dimensional spaces?\n- Is it possible to simplify the construction in Theorem 5 for some easy target distributions to simplify exposition?", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The existence of the map $\\Phi$ in Theorem 5 is surprising, especially given the less surprising results in Theorems 3,4.\n- The impossibility results in Theorems 3,4 are clear and well presented.", "weaknesses": "- The construction and proof sketch for Theorem 5 and the diagrams in Figure 2 are very difficult to follow.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reading and a positive evaluation of our work!\n\n* \"*The construction and proof sketch for Theorem 5 and the diagrams in Figure 2 are very difficult to follow.*\"\n\nThank 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. \n\n* \"*Is it possible to extend the arguments to infinite dimensional spaces?*\"\n\nThis 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.   \n\nFollowing 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.  \n\nOur 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](https://openreview.net/forum?id=8XoWofmZkI&noteId=qNVXBofICV).\n\n* \"*Is it possible to simplify the construction in Theorem 5 for some easy target distributions?*\"\n\nThe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5PGfcmV58s", "reviewer": "Reviewer_hbxS", "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:\n\n- **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}$.\n\n- **Theorem 4**: Any subset homeomorphic to the $W$-sphere contains non learnable targets.\n\n- **Theorem 5**: On the positive side, there exists for $W = 2$ models that can learn targets with probability arbitrarily close to $0$.\n\n- **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$.", "questions": "See above for an important first question.\n\n-  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 \n    - it would be better to have a clear (even if two-line) proof\n    - that would help the reader to have a clear **corollary** to stamp this property\n\n- 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.\n\nMinor additionnal comments:\n\n- l. 68-69: I do not see why Theorem 1 is *a low-dimensional reduction* reflected in Theorem 1.\n- l. 172: $J^*_0 J_0$ instead of $J^*_0J$ \n- l.252 : in which", "limitations": "No", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper has the following strengths:\n\n- The presentation is very clear, even-though the theme of the study is difficult and technical. The proofs presented are clear and sharp, the main Theorem is illustrated and the idea of the construction is nicely displayed. Finally, the overall questioning of the authors is clear and very nicely presented into a self-contained story. This is a very nice article to read! \n\n- All the results try to give a picture of the set of function that is GF-learnable: it is a (super) hard task and yet, the authors tackle it very elegantly. \n\n- Technically the results *seem* very strong.", "weaknesses": "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:\n\nThe 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the useful feedback and a very positive evaluation of our work!\n\n* \"*What the set of learnable functions look like... Doesn't Theorem 5 implies a sort of density of learnable functions?*\"\n\nThe 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](https://en.wikipedia.org/wiki/Smith%E2%80%93Volterra%E2%80%93Cantor_set) 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. \n\nIt 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. \n\n* \"*It would help the reader to have a clear corollary..  that the set of non-learnable function is dense for $W<d$*\"\n\nIndeed, such a corollary would be quite reasonable, thank you for this suggestion. \n\n* \"*I would change the title to **Learnability of ...** *\"\n\nYes, this is also quite reasonable, thank you.\n\n* \"*I do not see why Theorem 1 is a low-dimensional reduction reflected in Theorem 1*\"\n\nThis 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "u9eexlKlWZ", "reviewer": "Reviewer_qWpD", "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.", "questions": "- Can you provide intuition on why Theorem 5 does not apply to infinite-dimensional target spaces?", "limitations": "N/A", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "- The results of the novel and quite technically impressive, though I admit I am not so familiar with the related literature and did not fully follow the proof sketch.\n- For the most part the paper is well written, and I do like the addition of Figure 2 to help understand the proof of the main theorem.", "weaknesses": "- 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.\n\n- 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.\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the careful reading of our paper and your useful feedback and critique.\n\n* \"*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..*\"   \n\nThat'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.    \n \nAnother 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. \n\nAlso, 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).   \n\n* \"*..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.*\"\n\nBut 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?  \n\n* \"*I find the proof sketch for Theorem 5 .. to be unclear*\"\n\nThank 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank the reviewers for a careful reading of our paper and many useful comments and suggestions. 

Reviewers XxKo and qWpD ask about a possible extension of our main Theorem 5 to infinite-dimensional target spaces. We believe that this can be done, but there are some subtleties that we haven't worked out yet.

One immediate obstacle is as follows. Our finite-dimensional proof very much relies on the fact that we can choose in the target space a box $[-c,c]^d$ having measure $1-\epsilon$. The Cartesian product structure of the box is crucial for the proof. In the infinite-dimensional setting, the natural analog would be a box $\times_{k=1}^\infty [-c_k, c_k]$ in the Hilbert space $l^2$. For this box to lie in $l^2$, we need the convergence $\sum_{k=1}^\infty c_k^2<\infty$. However, we haven't managed to prove that such a box of measure $1-\epsilon$ can be found for an arbitrary Borel (with respect to the norm topology) measure on $l^2$. So either this has to be additionally proved, or the theorem must be stated for a more restrictive set of measures than arbitrary Borel measures considered in Theorem 5.

Meta-review: The paper investigates an interesting and novel question with mathematical rigor. Most reviews all lean towards acceptance.
Decision: Accept (poster)