One Network Fits All? Modular versus Monolithic Task Formulations in Neural Networks
Authors: Atish Agarwala
Abhimanyu Das
Brendan Juba
Rina Panigrahy
Vatsal Sharan
Xin Wang
Qiuyi Zhang
Venue: ICLR 2021 Poster (2021)
Keywords: deep learning theory
multi-task learning

Abstract: Can deep learning solve multiple, very different tasks simultaneously? We investigate how the representations of the underlying tasks affect the ability of a single neural network to learn them jointly. We present theoretical and empirical findings that a single neural network is capable of simultaneously learning multiple tasks from a combined data set, for a variety of methods for representing tasks---for example, when the distinct tasks are encoded by well-separated clusters or decision trees over some task-code attributes. Indeed, more strongly, we present a novel analysis that shows that families of simple programming-like constructs for the codes encoding the tasks are learnable by two-layer neural networks with standard training. We study more generally how the complexity of learning such combined tasks grows with the complexity of the task codes; we find that learning many tasks can be provably hard, even though the individual tasks are easy to learn. We provide empirical support for the usefulness of the learning bounds by training networks on clusters, decision trees, and SQL-style aggregation.

Published as a conference paper at ICLR 2021
ONE NETWORK FITS ALL? MODULAR VERSUS MONOLITHIC TASK FORMULATIONS IN NEURAL NETWORKS
Atish Agarwala & Abhimanyu Das
Brendan Juba Washington U. St. Louis" bjuba@ wustlew
Rina Panigrahy
Google Research
Google Research rinap @ @oogle.oooommmm
abbedss @ google.com
Vatsal Sharan MIT!
Xin Wang & Qiuyi Zhang
Google Research
vsharan @ mit.edu
wianxin.quuyiz) @ googgle.com
ABSTRACT
Can deep learning solve multiple tasks simultaneously, lated and very different? We investigate how the representations of the underlying tasks affect the ability of a single neural network to learn them jointly. We present theoretical and empirical findings that single neural network is capable of si- multancously learning multiple tasks from combined data set, for a variety of methods for representing tasks-for example, when the distinct tasks are en- coded by well-separated clusters or decision trees over certain task-code attributes. More concretely, we present a novel analysis that shows that families of simple programming-Iee constructs for the codes encoding the tasks are learnable by two-layer neural networks with standard training. We study more generally how the complexity of learning such combined tasks grows with the complexity of the task codes; find that combining many tasks may incur sample complexity penalty, even though the individual tasks are easy to learn. We provide empirical support for the usefulness of the learning bounds by training networks clusters, decision trees, and SQL-style aggregation.
when they unre-
INTRODUCTION
Standard practice in machine learning has long been to only address carefully circumscribed, often very related tasks. For example, we might train a single classifier to label an image as containing objects from certain predefined set, or to label the words of a sentence with their semantic roles. Indeed, when working with relatively simple classes of functions like linear classifiers, it would be unreasonable to expect train a classifier that handles more than such carefully scoped task (or related tasks in standard multitask learning). As techniques for learning with relatively rich classes such as neural networks have been developed, it natural ask whether or not such scoping of tasks is inherently necessary. Indeed, many recent works (see Section I.2) have proposed eschewing this careful scoping of tasks, and instead training single, "monolithic" " function spanning many tasks.
Large, deep neural networks can, in principle, represent multiple classifiers in such monolithic learned function (Hornik [991), giving rise to the field of multitask learning. This combined function might be learned by combining all of the training data for all of the tasks into one large batch-see Section 1.2 for some examples. Taken to an extreme, we could consider seeking to learn a universal circuit that is, circuit that interprets arbitrary programs in a programming language which can encode various tasks. But, the ability to represent such a monolithic combined function does not necessarily entail that such function can be efficiently learned by existing methods. Cryptographic hardness theorems (Kearns & Valiant 1994) establish that this is not possible in general by any method, let alone the specific training methods used in practice. Nevertheless, we still can ask how
Work performed in part while visiting Google.
Work performed in part while affiliated with Stanford, and in part while interning at Google.

---

Published as a conference paper at ICLR 2021
Input: Positions of & bodies each with mass Output: Gravitational force F;
Class:
Person
Class: Address
Table: zip_map
string name Address address income
string street string city
Table mapping
zip, code (latitude, longitude)
F2
m (Xy xi)
string zip_code
boolean in_same_zijg hatee//ip__ood(e((ee code((eeeonn A, Person B):
Declsion tree with different functions at leaf nodes:
evaluate if A & live same code
float get..straight. stttstrraitt_ieneee wwweedddssttteeeeeeeeeee
A, Person B):
lookup (latitude, longitude) of Person A & B from table zip_may
evaluate Euclidean distance between based on (latitude, longitude)
float ovg_ wvg_income._o income_zip_..... zip code(string zip_code):
construct SQL table T with income, zip_code for all instances of Person evaluate query "SELECT AVG(income) FROM T WHERE ZIP_000E=zip_code
f
f
fs
f
Figure I: Our framework shows that it is possible to learn analytic functions such as the gravitational force law, decision trees with different functions at the leaf nodes, and programming constructs such as those on the right, all using non-modular monolithic architecture.
rich a family of tasks be learned by these standard methods. In this work, study the extent to which backpropagation with stochastic gradient descent (SGD) can learn such monolithic functions on diverse, unrelated tasks. There might still be some inherent benefit an architecture in which tasks are partitioned into sub-tasks of such small scope, and the training data is correspondingly partitioned prior learning. For example, in the early work on multitask learning, Caruana (1997) observed that training a network to solve unrelated tasks simultancously seemed to harm the overall performance. Similarly, the seminal work Jacobs et al. (199)) begins by stating that "If backpropagation is used to train single, multilayer network to perform different subtasks on different occasions, there will generally be strong interference effects that lead to slow learning and poor generalization" ". We therefore ask if, for unfortunate choice of tasks in our model, learning by standard methods might be fundamentally impaired.
As point of reference from neuroscience, the classical view is that distinct tasks are handled in the brain by distinct patches of the cortex. While is a subject of debate whether modularity exists for higher level tasks (Samuels, 2006), it is accepted that there are dedicated modules for low-level tasks such as vision and audio processing. Thus, it seems that the brain produces a modular architecture, in which different tasks handled by different regions of the cortex. Conceivably, this division into task-specific regions might be driven by fundamental considerations of learnability: A single, monolithic neural circuit might simply be too difficult to learn because the different tasks might interfere with one another. Others have taken neural networks trained by backpropagation as a model of learning in the cortex (Musslick et al.) 2017); the extent that this reasonable, our work has some bearing on these questions as well.
1.1 OUR RESULTS
We find, perhaps surprisingly, that combining multiple tasks into one cannot fundamentally impair learning with standard training methods. We demonstrate this for a broad family of methods for combining individual tasks into single monolithic task. For example, inputs for each individual tasks may come from a disjoint region (for example, disjoint ball) in common input space, and each individual task could then involve applying some arbitrary simple function (e.g., a separate linear classifier for each region). Alternately there may be an explicit "task code" attribute (e.g., one-hot code), together with the usual input attributes and output label(s), where examples with the same task code are examples for the same learning task. Complementing our results that combining multiple tasks does not impair learning, we also find that some task coding schemes do incur a sample complexity penalty.
vast variety of task coding schemes may be used. As a concrete example, when the data points for each task well-separated into distinct clusters, and the tasks are linear classification tasks, show that a two-layer architecture trained with SGD successfully learns the combined, monolithic function; the required amount of data simply scales the sum of the amount required to learn each
2

---

Published as a conference paper at ICLR 2021
task individually (Theorem 2 Meanwhile, if the tasks are determined by balanced decision tree of height on d code attributes (as in Fig. [ left), we find that the training time and amount of data needed scales as d quasipolynomial in the 2 leaves (distinct tasks) when d is of similar size to h, and thus when the coding is efficient (Theorem [3. We also prove a corresponding lower bound, which shows that this bound is in fact asymptotically tight (Theorem 3). More generally, for task codings based on decision trees using linear splits with a margin of at least y (when the data has unit l2 norm), the training time and required data are asymptotically bounded by ~ e00//9) which for constant y is polynomial in the 2 functions (Theorem
We generalize from these cluster-based and decision-tree based task codings to more complex codes that are actually simple programs, For instance, we show that SQL-style aggregation queries over a fixed database, written as functions of the parameters of the query, can also be learned this way. More generally, simple programming constructs (such as in Fig. | right), built by operations such as compositions, aggregation, concatenation, and branching on small number of such learnable functions, are also learnable (Theorem 55). In general, we can learn a low-depth formula (circuit with fan-out 1) in which each gate is not merely a switch (as in decision tree), but can be any analytic function on the inputs, including arithmetic operations. Again, our key technical contribution is that we show that all of these functions are efficiently learned by SGD. This is non-trival since, although universal approximation theorems show that such functions can be expressed by (sufficiently wide) two-layer neural networks, under standard assumptions some expressible functions are not learnable Klivans & Sherstov (2009). We supplement the theoretical bounds with experiments on clusters, decision trees, and StL-style aggregation showing that such functions are indeed learned in practice.
We note that the learning of such combined functions could have been engineered by hand: for example, there exist efficient algorithms for learning clusterings or such decision trees, and it is easy to learn the linear classifiers given the partitioned data. Likewise, these classes of functions are all known to be learnable by other methods, given an appropriate transformation of the input features. The key point is that the two-layer neural network can jointly learn the task coding scheme and the task-specific functions without special engineering of the architecture. That is, it is unnecessary to engineer way of partitioning of the data into separate tasks prior to learning. Relatedly, the time and sample requirements of learning multiple tasks on a single network in general is insufficient to explain the modularity observed in biological neural networks if their learning dynamics are similar to SGD -ie., we cannot explain the presence of modularity from such general considerations.
All our theoretical results are based upon a fundamental theorem that shows that analytic functions can be efficiently learnt by wide (but finite-width) two-layer neural networks with standard activation functions (such as ReLUU, using SGD from random initialization. Specifically, we derive novel generalization bounds for multivariate analytic functions (Theorems I and g by relating wide networks to kernel learning with specific network-inducee kernel (Jacot et al., 2018 Du al., 2019; Allen-Zhu et al., 2019:] Arora et al., 2019a; Lee et al.] (019). known as the neurul langent kernel (NTK) (Jacot et al. 2018). We further develop a calculus of bounds showing that the sum, product. ratio. and composition of analytic functions is also Iearnable, with bounds constructed using the familiar product and chain rules of univariate calculus (Corollaries T (2. These above learnability results may be of independent interest; for example, they can be used to show that natural physical laws like the gravitational force equations (shown in Fig, [T] can be efficiently learnt by neural networks (Section B.Ip. pp. Furthermore, our bounds imply that the NTK kemel for ReLU activation has theoretical learning guarantees that are superior to the Gaussian kernel (Section A.2). which we also demonstrate empirically with experiments on learning the gravitational force law (Section B.2
1 1.2 RELATED WORK
Most related to our work are a number of works in application areas that have sought to learn a single network that can perform many different tasks. In natural language processing. (aaii et al. (2019) show that a single model can solve machine translation across more than 50 languages. Many other works in NLP similarly seek to use one model for multiple languages, even multiple tasks (Johnson et al., 2017 Aharoni et al. 2019: Bapna et al. 2019 Devlin et al. 2018). Monolithic models have also been successfully trained for tasks in very different domains, such speech and language (Kaiser et al.) 2017). Finally, there is also work on training extremely large neural networks which have the capacity
to learn multiple tasks (Shazeer et al., 2017 Raffel et al. 2019). These works provide empirical clues
3

---

Published as a conference paper at ICLR 2021
that suggest that single network can successfully be trained to perform wide variety of tasks. But, they do not provide a systematic theoretical investigation of the extent of this ability as we do here.
Caruana 1197) proposed multitask learning in which a single network is trained to solve multiple tasks on the same imput simultancously, as vector of outputs. He observed that average generalization error for the multiple tasks may be much better than when the tasks are trained separately, and this observation initiated an active area of machine learning research (Zhang & Yang. 2017). Multitask learning obviously related to our monolithic architectures. The difference that whereas in multitask learning all of the tasks are computed simultaneously and output on separate gates, here all of the tasks share common set of outputs, and the task code inputs switch between the various tasks. Furthermore, contrary to the main focus of multitask learning, we are primarily interested in the extent to which different tasks may interfere, rather than how much similar ones may benefit.
Our work is also related to studies of neural models of multitasking in cognitive science. In particular, Musslick et al. (2017) consider similar two-layer architecture which there is a set of task code attributes. But, in multitask learning, they are interested in how many of these tasks can be performed simultaneously, on distinct outputs. They analyze the tradeoff between improved sample complexity and interference of the tasks with handcrafted "gating" scheme, in which the parts of activity are zeroed out depending on the imput (as opposed to the usual nonlincarities) in this model, they find out that the speedup from multitask learning comes at the penalty of limiting the number of tasks that can be correctly computed as the similarity of inputs varies. Thus, in contrast to our model where the single model is computing distinct tasks sequentially, they do find that the distinct tasks can interfere with each other when we seek to solve them simultaneously.
2 TECHNICAL OVERVIEW
We now give a more detailed overview of our theoretical techniques and results, with informal statements of our main theorems. For full formal statements and proofs, please see the Appendix.
2.1 LEARNING ANALYTIC FUNCTIONS
Our technical starting point is to generalize the analysis of Arora al. (2019b) in order to show that two-layer neural networks with standard activation, trained by SGD from random initialization, can learn analytic functions on the unit sphere. We then obtain our results by demonstrating how our representations of interest can be captured by analytic functions with power series representations of appropriately bounded norms. Formal statements and proofs for this section appear in Appendix A.2 Let St denote the unit sphere in d dimensions.
Theorem 1. (Informal) Given an analytic function g(y), the function g(B for fixed B Rd (with def (1 and imputs E Sá is learnable to error with (((3'( (0))2/e²) examples using a single-hidden-layer finite width neural network of width poly(n) trained with SGD, with
(v))
la ly
k=
where the ag are the power series coefficients of g(v).
We will refer to g1(1) as the norm of the function g this captures the Rademacher complexity of learning g. and hence the required sample complexity. We also show that the ğ function in fact tightly captures the Rademacher complexity of learning g, i.e. there is lower bound on the Rademacher complexity based on the coefficients of ğ for certain input distributions (see Corollary 3 in Section C in the appendix).
We also note that we can prove much more general version for multivariate analytic functions g(x), with modified norm function o(y) constructed from the multivariate power series representation of gxx) (Theorem in Appendix A.2). The theorems can also be extended to develop a "calculus of bounds" which lets compute new bounds for functions created via combinations of learnable functions. In particular, we have a product rule and a chain rule:
4

---

Published as a conference paper at ICLR 2021
#9=1
W n
Find closest
-BC- ker
center
c c<t K<r
MG =
HG =
M =
If 65 0
f
ft
f
f
Figure 2: Some of the task codings which fit in our framework. On the left, we show a task coding via clusters. Here, c(i) the code for the ith cluster. On the right, we show task coding based on low-depth decision trees. Here, is the ith coordinate of the code of the input datapoint.
Corollary (Product rule). Let g(x) and h(x) meet the conditions of Theorem Then the product g(x)h(x) is efficiently learnable well, with (Mggn/e" samples where
=
(()) + +0)))((0).
Corollary (Chain rule). Let g(y) be an analytic function and h(x) be efficiently learnable, with auxiliary functions g(y) and h(y) respectively. Then the composition g(h(x)) is efficiently learnable as well with OMMorh/ E²) samples where
Mggh = (b((()))) +(h())).
(3)
provided that h()) and h(1) in the radius of convergence of g-
The calculus bounds enables us prove learning bounds on increasingly expressive functions, and we can prove results that may be of independent interest, As example, we show in Appendix B. that forces on bodies interacting via Newtonian gravitation, as shown Figure can learned to error using only (In(k())))) examples (even though the function 1/2 has a singularity 0).
2.2 TASK CODING CLUSTERS
Our analysis of learning analytic functions allows prove that single network with standard training can learn multiple tasks. We formalize the problem of learning multiple tasks as follows. In general, these networks take pairs of inputs (c, x) where is task code and is the input (vector) for the chosen task represented by c. We assume both and x have fixed dimensionality. These pairs are then encoded by the concatenation of the two vectors, which we denote by c; x. Given tasks, corresponding evaluation of functions fi...., f' respectively on the input the ith task has corresponding code c Now, we wish to learn a function g such that ();())
f((x) for examples of the form (c()); x. (x)). This is "monolithic" function combining the & tasks. More generally. there may be some noise (bounded within a small ball around el in the task codes which would require learning the monolithic function g(e, x) = (x) where j = argmin, Alternttly the task-codes are not given explicitly but are inferred by checking which ball-center (ii) (unique per task) closest the input x (see Fig. (left) for an example). Note that these are all generalizations of a simple one-hor hot coding.
c 1]2
We assume throughout that the f, are analytic, with bounded-norm multinomial Taylor series rep- resentations. Our technical tool is the following Lemma (proved in Appendix A.2) which shows that the univariate step function ((r 2 0) can be approximated with error e and margin y using low-degree polynomial which can be learnt using SGD.
Lemma 1. Given scalar x, let
( 7,6) = (1/2) erf (1 (Cuvlo8((e//1))
5

---

Published as a conference paper at ICLR 2021
where erf is the Gauss error function and C. is a constant. Let 4 (x, (,C) be the function Φ(x, 7, 7, with its Taylor series truncated at degree (llog(1/e)/)) Then,
[(({) 1-- O())
I -/2
Φ' V' 7,6)
2 1/2
Also, 4 ()) can be learnt using SGD with at most ( examples.
Using this lemma, we show that indicator functions for detecting membership in a ball near prototype c(9) can also be sufficiently well approximated by functions with such a Taylor series representation. Specifically, we use the truncated representation of the erf function to indicate that ||c |c low-norm function this way using Lemmal] [ For example, to check if c is within distance r of center c( we can use [[|c - ( 2 I )² which can be approximated using the ø' function in Lemma Then given such approximate representations for the task indicators (c)).... .......... I& (c), the function g(c: = I (c) (x) + ... + (c) f& has norm linear in the complexities of the task functions, so that they are learnable by Theorem [ (we scale to inputs to lie within the unit ball required by
| is small. As long the centers sufficiently well-separated, we find low-degree,
Theorem D. We state the result below, for the formal statement and proof see Appendix [A.3]
Theorem 2. (Informal) Given analytic functions having Taylor series representations with norm at most poly(k/e) and degree at most (loog(kje)) two-layer neural network trained with SGD can learn the following functions g(c; x) on the unit sphere to accuracy e with sample complexity poly(k/ (k/e) times the sum of the sample complexities for learning each of the individual functions:
for sepaarted codes el ( (k),, ifllc- 1ic-cc cc S 0()), then g(c;x) =x((x).
2.3 TASK CODING VIA LOW-DEPTH DECISION TREES
Theorem 2 can be viewed as performing single k-way branching choice of which task function to evaluate. Alternatively, we can consider a sequence of such choices, and obtain a decision tree in which the leaves indicate which task function is to be applied to the input. We first consider the simple case of a decision tree when is a [+1] -valued vector. We can check that the values cI,...,ch Ch match the fixed assignment cl ..... % that reaches a given leaf of the tree using the
function Less (c) = Ii= c)tc(")
2 (or similarly for any subset of up to h of the indices). Then g(c; x = Jaen(e (x) +...... ..... + Lew (x) represents our decision tree coding of the tasks (see Fig. (right) for an example). For the theorem, we again scale the inputs lie within the unit ball:
Theorem 3. (Informal) Two-layer neural networks trained with SGD learn such decision tree with depth within error e with sample complexity (dd /22 times the sum of the sample complexity for learning each of the individual functions the leaves. Furthermore, conditioned on the hardness of learning parity with noise, dil(h) examples are in fact necessary to learn a decision tree of depth h.
We can generalize the previous decision tree to allow a threshold based decision at every internal node, instead of just looking at coordinate. Assume that the input data lies in the unit ball and that each decision is based on a margin of at least y. We can then use a product of our truncated erf polynomials to represent branches of the tree. We thus show:
Theorem 4. (Informal) If we have decision tree of depth h where each decision is based on margin of at least y,, then we can learn such a such a function within error e with sample complexity eOt (e(l)))/²²) times the sample complexity of learning each of the leaf functions.
For the formal statements and proofs, see Appendix A.4 Note that by Theorem 3 the exponential dependence on the depth in these theorems is necessary.
2.4 SIMPLE PROGRAMMING CONSTRUCTS
So far, we have discussed jointly learning l: functions with task codings represented by clusters and decision trees. We now move more general setup, where we allow simple programming constructs such as compositions, aggregation, concatenation, and branching on different functions. At this stage, the distinction between "task codes" and "inputs" becomes somewhat arbitrary. Therefore,

---

Published as a conference paper at ICLR 2021
we will generally drop the task codes с from the inputs. The class of programming constructs can learn is a generalization of the decision tree and we refer to it as a generalized decision program. Definition 1.
We define generalized decision program to be circuit with fan-out 1 (i.e., a tree topology). Each gate in the circuit computes a function of the outputs of its children, and the root (top) node computes the final output. All gates, including the leaf gates, have access to the imput x.
We can learn generalized decision programs where each node evaluates one among a large family of operations, first described informally below, and then followed by a formal definition.
learnability of analytic functions not only allows us to learn functions with bounded Taylor series, but also sums, products, and ratios of such functions. Thus, we can learn constant-depte arithmetic formulas with bounded outputs and analytic functions (with appropriately bounded Taylor series) applied to such learnable functions.
Arithmetic/analyyicc formulas As discussed in Section 2.1
Aggregation We observe that the sum of k functions with bounded Taylor representations yields a function of the same degree and norm that is at most k times greater; the average of these functions, meanwhile does not increase the magnitude of the norm. Thus, these standard aggregation operations are represented very efficiently. These enable us to learn functions that answer a family of SQL-style queries against fixed database as follows: suppose [xx, r) is an indicator function for whether or not the record r satisfies the predicate with parameters x. Then a sum of the m entries of a database that satisfy the predicate given by x is represented by [xx, (())))(1) + ..... + [(x, r r(m))),(m) Thus, as long as the predicate function and records y((() have bounded norms, the function mapping the parameters x to the result of the query is learnable. We remark that max aggregation can also be represented as a sum of appropriately scaled threshold indicators, provided that there is a sufficient gap between the maximum value and other values.
Structured data We note that our networks already receive vectors of inputs and may produce vectors of outputs. Thus, one may trivially structured inputs and outputs such as those in Fig. (right) using these vectors. We now formalize this by defining the class of functions we allow.
Definition 2. We support the following operations at any gate in the generalized decision program. Let every gate have at most k children. Let g be the output of some gate and fI,,.., fu} be the outputs of the children of that gate.
1. Any analytic function of the child gates which can be approximated by polynomial of degree at most p. including sum g =Ek= ft and product of p terms g = -f
2. Margin-based switch (decision) gate with children [2] and some constant margin 7, i.e., g -i if (B, a S -7/2, and g = if (f, x) 2 7/2, for a vector and constant a. 3. Cluster-based switch gate with k centers {c(1) ,..... (8)) with separation (for some constant r). i.e. the output is fo if ||x e S <r/3. A special case of this is a look-up up table which returns value vi xf===x== c0 and 0 ifx does not match any of the centers.
4. Composition of two functions, g(x) = (f2(xx)).
5. Create a tuple out of separate fields by concatenation: given inputs {fi...., f&3 g outputs tuple [fi.... fx], which creates a single data structure out of the children. Or, extract field out of tuple: for a fixed field i, given the tuple [Iy.... ... fic], g returns f.
functioo b. and an analytic 6. For fixed table T with k entries fri....,TH. r,), Boolean-valued function
function f. SQL queries of the form SELECT SUM f(r f(r_i), WHERE (r_i,, x) for the inpul x, i.e., g computes Exb(r;x)=1 (r.). (We assume that I takes bounded values and b can be approximated by analytic function of degree at most p.) For an example, see the function sog__nncmm_zaeee zip_code () in Fig. [ (right).
As an example of a simple program we can support, refer to Fig. D (right) which involves table lookups, decision nodes, analytic functions such as Euclidean distance, and SQL queries. Theorem 3 our learning guarantee for generalized decision programs. See Section A.5 in the Appendix for
proofs, formal statements, and a detailed description of the program in Fig. (right).
Theorem 5. (Informal) Any generalized decision program of constant depth h using the above operations with p I (log(k/cc) can be learnt within error e with sample complexity (ooby(oo((/e)). For the specific case of the program in Fig. (right), it can be learnt using (k/e))(log) (llg(()))))) (19) examples, where k is the number of individuals in the database.
7

---

Published as a conference paper at ICLR 2021
85
100
80
Test accuracy
90
accuracy
75-
70-
Test Testaccul
k
65
70
k 50
60
60
K 250
55
10
500
50
50
45
10
10
10
10a
10
Number of examples per cluster
Number of examples per cluster
(a) Random linear classifier for cach cluster.
(b) Random teacher network for each cluster.
Figure Binary classification on multiple clusters, results are an average over trials. single neural network does well even when there multiple clusters. The error does not increase substantially on increasing the number of clusters &
EXPERIMENTS
We next empirically explore the learnability of multiple functions by a two layer neural network when the tasks are coded by well-separated clusters or decision trees, and more generally the learnability of SQL-style aggregation for a fixed database. We find good agreement between the empirical performance and the bounds of Section 2 See Appendix for more details of the experimental setup.
Learning binary classification for well-separated clusters data We demonstrate through ex- periments on synthetic data that single neural network can learn multiple tasks if the tasks are well-separated into clusters, as we discussed in Section [.22 Here the data is drawn from mixture of l well-separated Gaussians d = 50 dimensions. Within each Gaussian, the data points are marked with either of two labels. For the label generation, we consider two cases, first when the labels within each cluster are determined by a simple linear classifier, and second when the labels given by random teacher neural network with one hidden layer of 10 hidden units. Fig. shows the performance of a single two-layer neural network with 50k hidden units on this task. The performance of the neural network changes only slightly on increasing the number of clusters (k), suggesting that a single neural network can learn across all clusters.
Learning polynomial functions on leaves of a decision tree We consider the problem of learning polynomial functions selected by decision tree. The data generation process is follows. We first fix parameters: tree depth h, decision variable threshold margin y, number of variables k; and degree p for leaf functions. Then we specify full binary decision tree of depth h with random polynomial function on each leaf. To do this, we first generate thresholds 4, l,,,,,...44 In from the uniform distribution on [0, 1] and 2 leaf functions which are homogeneous polynomials of l variables and degree p, with uniformly distributed random coefficients in [0, 1]. A train/test example (x, y) where
(I1, ..., The #h.,1..., Th+p) is generated by first randomly sampling the az's from the uniform distribution on [0, 1]. selecting the corresponding leaf based on æ1, ...,.... Thh. (that is, go left at the first branch if xı < f1, otherwise go right, etc), and computing y by evaluating the leaf function at (Ia+1, ...., Fh+p)) The data is generated with the guarantee that each leaf has the same number of data points. Fig. shows the performance of a two-layer neural network with 32 x 2 hidden units, measured in the R-squared metric. Here the R-squared metric is defined as 1 E. / (3 2 and is the fraction of the underlying variance explained by the model. Note that for model that outputs the mean for any input, the R-squared metric would be zero. We observed for a fixed number of training samples, accuracy increases as threshold margin increases, and the dependence of sample complexity on test agrees with the bound in Theorem
Learning SQL-style aggregation queries We demonstrate the leamabiliiyy of SQL-style aggregation queries, which are functions of the form SELECT SUM/MIN /MAX f (x) WHERE p (x) from DATABASE. The train and test datasets are generated from the Penn World
8

---

Published as a conference paper at ICLR 2021
500
depth=6
examples per leaf
depth=7
0.9980
400
depth=9
depth-8
Test R-squared
depth-10
300
0.0970
0.9965
200
examples per kaff66
0.9960
examples per 1ef=1128
examples per
100
0.9955
examples per 1eaf
0.001
0.002
0.004
0.005
0.006
0.025 0.050 0.075 0,100 0.125 0.150 0.175 0.200
1 Test R-squared
Decision variable threshald margin
(a) Fixed threshold margin y 0.1.
(b) Fixed tree depth h 10.
Figure 4: Learning random homogeneous polynomials variables and degree on the leaves of decision tree, the results are averaged over 7 trials. (a) Sample complexity scales as e0 hog(1/e)/>² with error e, where error is measured by (1-Test R-squared). (b) For fixed tree depth, accuracy increases with increasing margin.
Table dataset (Feenstra et al. 2015), which contains 11830 rows of economic data. The WHERE clause takes the form of (xi, 2 bi AND ... AND (zi, 1ig), where Ziy..... ... Fi, are k randomly selected columns and t. s......, ti, are randomly selected values from the columns. The query target function randomly selected from SUM, MAX, and MIN and is over fixed column (pl_x x in the table, which stands for price level for imports). The R-squared metric for a two-layer neural network with 40k hidden units summarized in Table We observe that a neural network learns to do SQL-style aggregation over dozens of data points, and for a fixed database, the test error only varies slightly for different numbers columns in the WHERE clause.
Table 1: R- R-Squared for SQL-style aggregation. A single network with one hidden layer gets high Squared values, and the error does not increase substantially the complexity of the aggregation increased by increasing the number of columns in the WHERE clause
columns WHERE clause
3
4
Median # data points
21
4
3
Test R-Squared
(93.31 # 0.11) (93.01 2.7%%
(91.86 = 2.59) % (94.8 1.86 %
(92.51 + 2.2) %
4 CONCLUSION AND FUTURE WORK
Our results indicate that even using single neural network, we can still learn tasks across multiple, diverse domains. However, modular architectures may still have benefits over monolithic ones: they might use less energy and computation, as only a portion of the total network needs to evaluate any data point. They may also be more interpretable, as it clearer what role each part of the network is performing. It is an open question if any of these benefits of modularity can be extended to monolothic networks. For instance, which perform identifiable simple computations? And if so, can efficiently identify these from the larger network? This could help in interpreting and understanding large neural networks.
necessary for monolithic network to have modular parts
Our work also begins to establish how neural networks can learn functions which are represented as simple programs. This perspective raises the question, how rich can these programs be? Can we learn programs from full-featured language? In particular, supposing that they combine simpler programs using other basic operations such as composition, can such libraries of tasks be learned as well, i.c., can these learned programs be reused? We view this compelling direction for future work.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGEMENTS
Brendan Juba was partially supported by NSF Awards CCF-1718380, IIS-1908287, and IIS- 1939979777 and was visiting Google during portion of this work. Vatsal Sharan was supported in part by NSF award 1704417.
REFERENCES
Roee Aharoni, Melvin Johnson, and Orhan Firat. Massively multilingual neural machine translation. arXiv preprint arXiv:/908 /903.0009, 2019.
Zeyuan Allen-Zhus Yuanzhi Li, and Yingyu Liang. Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers. In Advances in Neural Information Processing Systems 32, pp. 6155-6166. Curran Associates, Inc., 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-Graines Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks. In International Conference Machine Learning, pp. 322-332, May 2019a.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-graing Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint 19Xxvv:9010085000 2019b.
Ankur Bapna, Colin Andrew Cherry, Dmitry Dima Lepikhin, George Foster, Maxim Krikun, Melvin Johnson, Mia Chen, Naveen Ari, Orhan Firat, Wolfgang Macherey, et al. Massively multilingual neural machine translation in the wild: Findings and challenges. 2019.
Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant Icarninn the parity problem, and the statistical query model. Journal of the ACM (JACM), 50(4):506-519, 2003.
Rich Caruana. Multitask learning. Machine learning, 28(1):41-7) 1997.
Jacob Devlin, Ming-Was Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: 14,0000 2018.
Simon S. Du, Xiyu Zhai, Barnabás Póczos, and Aarti Singh. Gradient Descent Provably Optimizes Over-parameterized Neural Networks. In 7th International Conference on Learning Representa- lions, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Robert Feenstra, Robert Inklaar, and Marcel Timmer. The next generation of the penn world table. American economic review, 105(10)33150-8) 82, 2015.
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2): 251-257, 1991.
Robert A Jacobs, Michael Jordan, Steven Nowlan, and Geoffrey Hinton. Adaptive mixtures of local experts. Neural computation, 3(1):79-8) 87,99877777 1991.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. In Advances in Neural Information Processing Systems 31, pp. 8571-8580. Curran Associates, Inc., 2018.
Melvin Johnson, Mike Schuster, Quoe V Le, Maxim Krikun, Yonghui Wu, Zhifeng Chen, Nikhil Thorat, Fernanda Viégas, Martin Wattenberg, Greg Corrado, al. Google's 's multilingual neural machine translation system: Enabling zero-shot translation. Transactions of the Association for Computational Linguistics, 5:339-351, 2017.
Lukasz Kaiser, Aidan N Gomez, Noam Shazeer, Ashish Vaswani, Niki Parmar, Llion Jones, and Jakob Uszkoreit. One model leam them all. arXiv preprint ar0i:: 2017.
Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 9506)0983- 1998.
10

---

Published as a conference paper at ICLR 2021
Michael Kearns and Leslie Valiant. Cryptographic limitations learning boolean formulae and finite automata. Journal of the ACM (JACM), 41(1):67-95, 1994.
Adam R Klivans and Alexander A Sherstov. Cryptographic hardness for learning intersections of halfspaces. Journal of Computer and System Sciences, 75(1):2-12, 2009.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent. In Advances in Neural Information Processing Systems 32, pp. 8570-8581. Curran Associates, Inc., 2019.
Sebastian Musslick, Andrew Saxe, Kayhan Özcimder, Biswadip Dey, Greg Henselman, and Jonathan D Cohen. Multitasking capability versus learning efficiency in neural network ar- chitectures. In CogSci, pp. 829 834, 2017.
Colin Raffel, Noam Shazeer, Adam Roberts. Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer. 1910 [cs, stat], October 2019.
Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6): 2009.
Richard Samuels. Is the mind massively modular? 2006.
Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer. arXiv preprint arXiv:1701.066. 066588, 2017.
Le Song, Santosh Vempala, John Wilmes, and Bo Xie. On the complexity of learning neural networks. In Advances in neural information processing systems, pp. 5514-5522, 2017.
Michel Talagrand. Sharper bounds for gaussian and empirical processes. The Annals of Probability, pp. 28-76,11 1994.
Henry Tsai, Jason Riesa, Melvin Johnson, Naveen Arivazhagan, Xin Li, and Amelia Archer. Small and practical bert models for sequence labeling. arXiv preprint arXiv: (tt:::999000000 2019.
Gregory Valiant. Finding correlations subquadratic time, with applications learning parities and the closest pair problem. Journal of the ACM (JACM), 62(2):1-45, 2015.
Yu Zhang and Qiang Yang. A survey multi-task learning. arXiv preprint arXiv:1707.08// 14, 2017.

---

Published as a conference paper at ICLR 2021
A THEORETICAL RESULTS
A.1 KERNEL LEARNING BOUNDS
In this section, we develop the theory of learning analytic functions. For a given function g. we define parameter Mg related to the sample complexity of learning g with small error with respect to given loss function:
Definition 3. Fix a learning algorithm, and a 1 I-Lipschitz loss function L. For a function over a distribution of inputs D, a given error scale e, and a confidence parameter 6, let the sample complexity (g, 8) be the smallest integer such that when the algorithm is given ng.ple, 5) i..dd examples of g on D. with probability greater than 1 5, it produces trained model 9 with generalization error Fx (xgg(x) ((x)((()))))))))))) less than c. Fix a constant C >> O. We say is efficiently learned by the algorithm (w.r.f C) if there exists constant Mg (depending g) such that for all e, 5, and distributions DD the inputs of g. ng, 8) I C(MM log( 8 (o]{))
For example, it is known (Talagrand (1994)) that there exists suitable choice of C' such that empirical risk minimization for class of functions efficiently learns those functions with Mg at most the VC-dimension of that class.
Previous work focused on computing Mg. for functions defined on the unit sphere, for wide neural networks trained with SGD. We extend the bounds derived Arora al. (2019a) to analytic functions, and show that they apply to kernel learning methods as well as neural networks.
The analysis in Arora et al. (2019a) focused on the case of training the hidden layers of wide networks with SGD. We first show that these bounds are more general and in particular apply to the case where only the final layer weights are trained (corresponding to the NNGP kernel in Lee et (2019), and therefore our results will apply to general kernel learning as well. The proof strategy consists of showing that mithh networks have a sensible infinite-width limit, and showing that training causes only a small change in parameters of the network.
Let be the number of hidden units, and be the number of data points. Let y be the x 1 dimensional vector of training outputs. Let h be a n x m random matrix denoting the activations of the hidden layer (as function of the weights of the lower layer) for all data points. We will first show the following:
Theorem 6. For sufficiently large m, a function g can be learned efficiently in the sense of Desinition by training the final layer weights only with SGD, where the constant Mg given by
Mg. S y (H
(4)
where we define T as
H E(hh"
(5)
which is the NNGP kernel Lee et al. (2019)
We require some technical lemmas in order to prove the theorem. We first need to show that H is, with high probability, invertible. If K [(x, x'), the kernel function which generates H is given by infinite Taylor series in x x' it can be argued that H has full rank for most real world distributions. For example, the ReLU activation this holds as long no two data points are co-linear (see Definition 5.1 in Arora et al.) (2019a)). We can prove this more explicitly in the following lemma:
Lemma 2. If all the n data points x are distinct and the Taylor series of K(x, x') in x x' has positive coefficients everywhere then H is not singular.
Proof. First consider the case where the input is a scalar. Since the Taylor series corresponding to K [(z,x') x²) consists of monomials of all degrees of xx,, we can view it as some inner product in a kernel space induced by the function d(x) = (1, x, ..)...), where the inner product is diagonal (but with potentially different weights) in this basis. For any distinct set of inputs 1 In the set of vectors ((x,) are linearly independent. The first n columns produce the Vandermonde matrix obtained by stacking rows 1, x,, ..., == for n different values of z, which is well known to be non-singular (since a zero eigenvector would correspond to degree n polynomial with n distinct roots (nn)).,,,)).
12

---

Published as a conference paper at ICLR 2021
This extends to the case of multichmennionall x if the values, projected along some dimension, distinct. In this case, the kernel space corresponds to the direct sum of copies of & applied elementwise to each coordinate x,. If all the points are distinct and and far apart from each other, the probability that given pair coincides under random projection is negligible. From a union bound, the probability that given pair coincide is also bounded so there must be directions such that projections along that direction are distinct. Therefore, H can be considered to be invertible in general.
As m -> oc, hh concentrates to its expected value. More precisely, (hh")-1 approaches (Ho)-1 for large m if we assume that the smallest eigenvalue Amin (H*) 2 Ao. which from the above lemma we know to be true for fixed n. (For the RcLU NTK the difference becomes negligible with high probability for any bounds involving the former.
poly(n/ Ao) Arora et al. (2019a).) This allows us to replace hh with H in
We can get learning bounds in terms of hh by studying the upper layer weights of the network after training. After training. we have y = w h. If hh is invertible (which the above arguments show is true with high probability for large m)) the following lemma holds:
Lemma 3. If we initialize random lower layer and train the weights of the upper layer. then there exists a solution w with norm (hh""--y
Proof. The minimum norm solution to y w Thhii. is
w" = (h (hhhh>11n -
(6)
The norm squared (w")Tw" w" of this solution is given by y ("hhh"h "
We claim that h(hTh ²h = (hhT) -1 To show this, consider the SVD decomposition
USVT. Expanding have
h(h hT USV (VS'VVV VSUT..
Evaluating the right hand side gets us US u = (hhT)-!
Therefore, the norm of the minimum norm solution is (Thh")
We can now complete the proof of Theorem
Proof of Theorem 6 For large m, the squared norm of the weights approaches y (Ho))- Since the lower layer is fixed, the optimization problem is linear and therefore convex in the trained weights w. Therefore SGD with small learning rate will reach this optimal solution. The Rademacher complexity of this function class is at most vyT (Hx)) which we at most by / MM, where Mg is an upper bound on y" y The optimal solution has O train error based on the assumption that H is full rank and the generalization error will be no more than O( (T(
1x) which is most e if we use at least ((Mg/ (²) training samples note that this is identical to the previous results for training the hidden layer only Arora al. (2019a): Du et (2019).
2n
A.2 LEARNING ANALYTIC FUNCTIONS
Now, we derive generalization bounds for single variate functions. We use Theorem 6 to prove the following corollary, a more general version of Corollary 6.2 proven in Arora al. (20 9a) for wide ReLU networks with trainable hidden layer only:
Corollary 3. Consider the function g Rd - RR given by:
g(x) [ax(oT))
(8)
Then, if g is restricted to ||x|| 1, and the NTK NNGP kernel can be written (xxxx') = En ba(x x²)², the function can be learned efficiently with wide mee-hddden-layer network in the sense of Desinition wwith
MM, =
Σ bx 1/2 a 1 1
(9)
13

---

Published as a conference paper at ICLR 2021
up g-independent constants of O(1) where 3x -11x In the particular case of a ReLU network, the bound is
VMg
xlax x|0x1113111
(10)
The original corollary applied only to networks with trained hidden layer, and the bound on the ReLu network excluded odd monomials of power greater than 1.
Proof. The extension to NNGP follows from Theorem 6. which allows for the application of the arguments used to prove Corollary 6.2 from Arora et al. 2019a) (particularly those found in Appendix E).
The extension of the ReLu bound odd powers can be acheived with the following modification. consider appending a constant component to the input x so that the new input to the network is 1/VV2,1/V2). The kernel then becomes:
K(x,x)) x x' +
xxx' + +1)) 2
x x'
( arccos
(11)
4
Re Re-writing the power series expansion around x' O, we have terms of all powers. An asymptotic analysis of the coefficients using known results shows that coefficients by are asymp- totically O(k-3//3 meaning Equation 10 applies to these kernels, without restriction to even k.
Equation 9 suggests that kernels with slowly decaying (but still convergent) by will give the best bounds for learning polynomials. Many popular kernels do not meet this criteria. For example, for inputs on the sphere of radius r, the Gaussian kernel [(x, x') e e-1xx-x'1P/2 can be written as K [(x, x') e- exxx This has by 1/2 e" /k!, which increases rapidly with k. This provides theoretical justification for the empirically inferior performance of the Gaussian kernel which we will present in Section B.2
Guided by this theory, we focus on kernels where br 1-1/2 < O(k), for all & (or, by 2 0(k 2)). The modified ReLu meets this criterion, as well as hand-crafted kernels of the form
K(x,x') Σ k xxxx''
(12)
with E (1, is a valid slowly decaying kernel on the sphere. We call these slowly decaying kernels. We note that by Lemma 3 the results of Corollary 3 apply networks with output layer training only, as well as kernel learning (which can be implemented by training wide networks).
Using the extension of Corollary 3 to odd powers, first show that analytic functions with appropri- ately bounded norms can be learnt.
Theorem 7. Let g(y) be a function analytic around with radius of convergence Rg. Define the auxiliary function g(y) by the power series
20
g(v)
Σ kmm
la ly
(13)
where the 0g are the power series coefficients of g Then the function g x), for some fixed
vector B3 Rdd with ||x|| = 1 efficiently learnable the sense of Definition uuiig model with slowly decaying kernel K with
MMg = 3ğ' (3) + g(0)
(14)
the norm ||:]|2 is less than Rg-
Proof. We first note that the radius of convergence of the power series of ğ(y) is also Rg since g(v) analytic. Applying Equation IO pulling out the Oth order term, and factoring out B, we get
V M2 |ool +B
k k/ap| &h 33' +0)
(15)
since B < Rg.
14

---

Published as a conference paper at ICLR 2021
The tilde function is the notion of complexity which measures how many samples need to learn a given function. Informally, the tilde function makes all coefficients in the Taylor series positive. The sample complexity is given by the value of the function at 1 (in other words, the L1 norm of the coefficients the Taylor series). For a multivariate function gxx), we define its tilde function ī(v) by substituting any inner product term (a, x) by a univariate y. The above theorem can then also be generalized to multivariate analytic functions:
Lemma 4, Given a collection of vectors B, in IR,, the function f(x) = -T G, x is efficiently learnable with
M I1 3
(16)
where B, = 3
Proof. The proof of Corollary 6.2 in Arora et al. (2019a) relied on the following statement: given
positive semi-definite matrices A and B, with A B, we have:
PB PB - B
(17)
where is the Moore-Penross pseudoinverse, and P is the projection operator.
We can use this result, along with the Taylor expansion of the kernel and a particular decomposition of multivariate monomial in the following way. Let the matrix X to be the training data, such that the ath column x; is unit vector in R Given K = X the matrix of inner products, the Gram matrix H of the kernel can be written
H Σ k
(18)
where o is the Hadamard (elementwise) product. Consider the problem of learning the function
fxx = I B, x. Note that we write:
((x) = (x ok 8 B,.
(19)
Here @ the tensor product, which for vectors takes an n2 dimensioonll vector and an n2 dimensional vector imputs vectors and returns n2n2 dimensional vector:
WiV1 W1 U/
W 2
V
W1 Una W2U1
(20)
Wn, Una
The operator @ is the Khatri-Rao product, which takes an ni x ny matrix A (ai, ang) and n2 @ ny matrix B (bı,... ,bny) and returns the nin2 ng dimensional matrix
o B (al X bl...., ans X bns).
(21)
For 2, this form of ((X can be proved explicitly:
x T
3 @ 3, = (x1 X x1.
xP 2 xp) B1 B2.
(22)
The ath element of the matrix product is
(xo @ xx) (B, x B2) = (B, xx.) x.)
(23)
which is exactly (xx).. The formula can be proved for p > 2 by finite induction.
With this form of f(X), can follow the steps of the proof in Appendix E Arora et al. 2019a).
which was written for the case where the ,3 were identical:
H (H
(,)=1,)) (H (X & Ar-
(24)
15

---

Published as a conference paper at ICLR 2021
Using Equation 17 applied to K we have:
y" H y
(25)
7 1 10 1 3.) ' PP Pk P of =1 3
Since the X are eigenvectors of Pko, with eigenvalue 1, and X (K")) Px Pxer, we
have:
(H S '.p' (6%-19))) 3 Pxer 1
(26)
p
y yH S II 3 B,
(27)
For the slowly decaying kernels, b, 2 p. Therefore, we have v (Ho) S MM for
v M 11 8
(28)
where B; = B2112 desired.
This leads to the following generalization of Theorem 7
Theorem 8. Let gxx) be a function with multivariate power series representation:
9(x) = ΣE a I x)
(29)
DEVA
i=1
where the elements of V3 index the kih order terms of the power series. We define g(v) = En ōxy" with coefficients
āg Σ Jayl
B
(30)
vEVi
If the power series of g(y) converges at y = 1 then with high probability g(x) can be learned efficiently in the sense of Definition 3 with /M,- = g1( + g()).
Proof. Follow the construction in Theorem using Lemma to get bounds on the individual terms. Then sum and evaluate the power series of g (1) to arrive at the bound.
Note that the ÿ function defined above for multivariate functions depends on the repre- sentation, i.e. choice of the vectors 3. Therefore be fully formal g(y) should instead be ğa(y). For clarity, we drop /3 from the expression go(y) and it is implicit in the ğ notation.
Remark 1.
Remark 2. If g(x) can be approximated by some function Gapp such that Ig(x) guppl S e' for all x in the unit ball, then Theorem can be used to learn g(x) within error e' with sample complexity O(M (M
To verify Remark 2 note that we are doing regression on the upper layer of the neural network, where the lower layer random. So based gapp there exists low-norm solution for the regression coefficients for the upper layer weights which gets error at most e'. we solve the regression under the appropriate norm ball, then get training error at most c', and the generalization error will be at most c with
(c) samples.
We also derive the equivalent of the product and chain rule for function composition.
Proof of Corollary 7 Consider the power series of (x)),(x), which exists and is convergent since each individual series exists and is convergent. Let the elements of Vi.9 and Ve. index the jth order terms of y and the kth order terms of h respectively. The individual terms in the series look like:
Dw II ='=1
w x) II k==1
(Bn. W x) for Vig. E Vish
(31)
16

---

Published as a conference paper at ICLR 2021
with bound
A B.. for Vi w E VasA
(1 + a) bbol
II B II 5'=1
(32)
k==1
for all terms with j + k > 0 and (0) for the term with j = k 0.
Distribute the & product, and first focus on the j term only. Summing over all the V&, for all k we get
ΣΣ I WEVe.
jl
π
II
Bunk
p=1
===1
(33)
a f==1
II
h(L).
Now summing over the and Vi. we get (1))) If do the same for the is term, after summing we get (1)) These bounds add and we get the desired formula for / which, up to the additional 5(0)h(0) term looks is the product rule applied to and h.
One immediate application for this corollary is the product of many univariate analytic functions. If we define
G(x) II (3 x)
(34)
where each of the corresponding (v) have the appropriate convergence properties, then G is efficiently learnable with bound Mg given by
V MM = dy (T.(
+ aI.
(35)
y=1
Proof of Corollary 2 Writing out g(h(x)) power series in h(x), we have:
g(h(x)) (x(x))))*
(36)
k=
We can bound each term individually, and use the k-wise product rule bound each term of (A(x)))*
Doing this, we have:
Mgoh
Σ klax (1(())(1)**
las ((()*
(37)
Factoring out (1) from the first term and then evaluating each of the series gets us the desired result.
The following corollary considers the case where the function g(x) is low-degree and directly follows from Theorem g
Fact 1. The following facts about the tilde function will be useful in our analysis-
1. Given a multivariate analytic function g(x) of degree for in the d-dimensional unit ball, there a function ğ(y) as defined in Theorem & such that g(x) is learnable to error with (pp(()/e samples.
2. The tilde of a sum of two functions is most the of the tilde of each the functions, i.e. if h then f(y) S z(y) h(y) for y 2 0.
3. The tilde of product of two functions is at most the product of the tilde each of the functions, i.e. g h then fly) o(y)h(y) for y O.
17

---

Published as a conference paper at ICLR 2021
4. 9 f(xx), then g(y) flay) y 0.
5. If (x) - [x + c) for some ||||| - 1, then f(y) S (y + 1).orr 2 0. By combining this with the previous fact, if g()) = fa c)) for some ||c| s 1, then 9(1) S f(2a).
To verify the last part. note that in the definition of 9 we replace (B, x) with y. Therefore, we will have additional (3, c) term when compute the tilde function for g(x) f(x+c). As ||||| S 1, the additional term at most 1.
The following lemma shows how polynomial if is at least 7/2 far away from a. We will use this primitive several times to construct low-degree analytic approximations of indicator functions. The result is based on the following simple fact.
approximate the indicator 1(r a) with low-degree
Fact If the Taylor series of g(x) exponentially decreasing, then we can truncate degree Ollog(1/e) /e)) ) to get error. We will use this fact to construct low-degree approximations of functions.
Lemma 5. Given a scalar x, let the function
(1x, (5,,7,,,)) = (1/2) (x=))(lv-avvylog(//e)
for some constant Let D' (z. 7, a)) be the function ((x, 7/s e, with its Taylor series truncated at degree 0(log(1/e)/7) Then for |a|| <
fc a
t' ('E,,,,,,))
11-6 x 2 a 7/2.
Also, Ma is most (((1ox(1/0//))
Proof. Note that (ar, Y, e, a) is the cumulative distribution function (cdf) of a normal distribution with mean and standard deviation O(7/ (trl/llg(1/e)) Note that at most e/100 of the probability mass of Gaussian distribution lies more than ((V/oo((1)) standard deviations away from the mean. Therefore,
c/100
x x a 7/2, x M a + 7/2.
Φ 7,,,7,,,) = c/100
Note that
erf(x) = VT J0
E -t dt
(-1)
(2i +1)
Therefore, the coefficients in the Taylor series expansion of erf((x a) (o)/////()()())) in terms of (x a) are smaller than for i > O(log(//e)/")) and are geometrically decreasing hence- forth. Therefore, we can truncate the Taylor series at degree 0(log(1/c//7) and still have an (c)) approximation. Note that for f(x) erf(x).
2 f(v) < Vi
2 ye S O(v))
Ed
After shifting by a and scaling by Ol (lg(/1/))) we get ('(v) 1, this is at most (llo(()/e)//?)) Hence the result now follows by Fact
For
A.3 LEARNABILITY OF CLUSTER BASED DECISION NODE
In the informal version of the result for learning cluster based decisions assumed that the task-codes e are prefixed to the input datapoints, which we refer to as X For the formal version of the theorem, use small variation. The task code and the input c, Ximp gets mapped
Ximp (r/3) (r/3) for
18

---

Published as a conference paper at ICLR 2021
some constant 1/6. Since Xmp resides the unit sphere, x will be distance at most (r/3) from the center it gets mapped to. Note that the overall function f can be written as follows,
f(x) Σ 1 [ (r/2)9) ((x j=1
where fj is the function corresponding to the center Cj. The main idea will be to show that the indicator function can be expressed as an analytic function.
Theorem 9. (formal version of Theorem 2 Assume that d 2 10 (otherwise we can pad by extra coordinates increase the dimensionaliry). Then least r apart, for some constant r. Let
find & centers in the unit ball which are at
f(x) Σ 1 1 (Ix-c,lll= (((2)) cc))(r/3)) 5=1
where fg is the function corresponding the center cj. Then each f3 is degree p polynomial, Mj of the function is p poly(k/e) $ - pob((k/e)6/r)
Proof. Let
(x) Σ Φ (|xx (tse-cc/l..6//2..e//.//// ((x (xx- (xx-c,)/(r/3))
where Φ' is defined in Lemma 5 Let
(x) 4'([x (|x- (/1 (r/4)))
The indicator (x) checks if ||x - c, is constant fraction less than r/2, or a constant fraction more than r/2. Note that if is from different cluster, then ||x cyl is at least some constant, and hence (x) at most e/k. The contribution from & such clusters would be at most e. If ||x cyll < <//k, /k then the indicator suffices to show learnability of Japp-
least 1 (e/k). Hence fapp is an O (pp-rrppoxiinooonn
f, by Remark
If y (x, сÿ} and assuming and the centers C, are unit sphere,
[v( 4 2y.r/3, //33/ (log((k/e)
poly(k:cc.
By Fact 1
f(0) poly(k/e) 1(6m).
As fj most degree p.
F(0) S poly(k/e))
(, sp <p-poly(//e)///// 510)
Corollary 4. The previous theorem implies that we can also learn f where f is a lookup table with M, pollyk/e), as long as the keys C; well separated. Note that as long the keys e; distinct (for example, names) we can hash them to random vectors on a sphere so that they are all well-separated
Note that the indicator function for the informal version of Theorem stated in the main body is the same as that for the lookup table in Corollary Therefore, the informal version of Theorem follows Corollary of Theorem
19

---

Published as a conference paper at ICLR 2021
A.4 LEARNABILITY OF FUNCTIONS DEFINED ON LEAVES OF A DECISION TREE
We consider decision trees on inputs drawn from (-1, 1)a. We show that such a decision tree can be learnt with M, < O From this section onwards, view the combined input c, x as The decision tree y can be written as follows,
(xx) (x)x))
where the summation runs over all the leaves, (x) is the indicator function for leaf j. and Vy E [-1, 1] is the constant value the leaf j. We scale the inputs by vd to make them lie on the unit sphere, and hence each coordinate of x is either +1/Vd.
Let the total number of leaves in the decision tree be B. The decision tree indicator function of the j-th leaf can be written the product over the path of all internal decision nodes. Let jr be variable at the I-th decision node on the path used by the j-th leaf. We can write,
1x(x) = II TT + b)),
where each 2,, E (-1/vd,1/val and aj E (-vd/2, vd/2} and by: (-1/2, Note that the values of aj and ,3. are chosen depending on whether the path for the j-th leaf choses the left child or the right child at the 1-th decision variable. For ease of exposition, the following theorem is stated for the case where the leaf functions are constant functions, and the case where there are some analytic functions the leaves also follows in the same way.
Theorem 10. If a function is given by g(x) = ンド= [x(x0 where 1x(x) is a leaf indicator functionn in the above form, with tree depth h, then Mg is at most (dd)).
Proof. Note that
m(v) S Σ L
ΣII Vdy/2 1/22
5(1) - 2 (V4/2 1/2)a < d².
As the degree of g is at most h, therefore M, h1) hdd.
Remark 3. Note that by Theorem 10 we need (log k) ())okke-)) samples to learn lookup table based on a decision tree. On the other hand, by Corollary A lookup table using cluster based decision nodes. This shows that using a hash function to obtain random Olog k) bit encoding of the indexes for the lookups more efficient than using a fixed log k length encoding for the le lookups.
Awe we need poly(k/e) samples to learn
We also prove a corresponding lower bound in Theorem 14 which shows that (P))) samples are necessary to learn decision trees of depth h.
We will now consider decision trees where the branching is based on the inner product of x with some direction / f3. Assume that there is a constant gap for each decision split, then the decision tree indicator function can be written as,
[x)) II [((x > ag.)-
Theorem 11. (formal version of Theorem 4 decision tree of depth h. where every node partitions in certain direction with margin " can be writlen as g(x) 1 then the final
Mg = e Oth (oghto////)//))) + hlog 1/() Σ J1(1),
where p is the maximum degree of fz-
20

---

Published as a conference paper at ICLR 2021
Proof. Define Japp.
Happ (x)
Σ
TT ((x, 2, t.e/ (z)
where d' is as defined in Lemma
Note that for all 1,
T (1, 71,7,5//o (1,,,,5//,, 0(log(10)/77)
Therefore,
Pupp (1) $
11 (
$ 00ooo((1/)) Σ (1).
Note that the degree of Supp most O(p + h hog Therefore,
Man o ((hloo((10//7))) (og((/oogl])))) log(1/e)/7?) E.
By Remark 2
learnability of g follows from the learnability of its analytic approximation Sapp-
A.5 GENERALIZED DECISION PROGRAM
In this section, instead a decision tree, we will consider a circuit with fan-out I, where each gate (node) evaluates some function of the values returned by its children and the input x. A decision tree a special case of such circuits which the gates are all switches.
So far, the function outputs were univariate but we will now generalize and allow multivariate (vector) outputs as well. Hence the functions can now evaluate and return data structures, represented by vectors. We assume that each output is at most d dimensional and lies in the unit ball.
Definition 4. For a multivariate output function f, we define fly) as the sum of fy( for each of the output coordinates ft.
Remark 4. Theorem 9. 10 and extend to the multivariate output case. Note that if each of the individual functions has degree at most p. then the sample complexity for learning the multivariate output is most ((pf(1/ee) (where the multivariate tilde function defined Definition 4).
We now define generalized decision program and the class of functions that support.
Definition 5. We define generalized decision progrum to be circuit with fan-out (i.e., tree topology) where each gate evaluates function of the values returned by its children and the input x, and the root node evaluates the final output. All gates, including those at the leaves, have access to the imput x. We support the following gate operations. Let be the output of a gate, let each gate have at most k children, and let {f1....,ft. fk} be the outputs of its children.
1. Any analytic function of the child gates of degree at most p, including sum h Et and product of p terms h = IT" S
2. Margin based switch (decision) gate with children f2], some constant margin ? vector B and constant a.
fi
(B,x) S -7/2,
f2 if (B.x)
7/2
3. Cluster based switch gate with &o centers (c.))....,c(k)) with separation for some constant and the output is Js |[ c S r/3. A special case of this is a look-up table which returns value if e and 0 if does not match any of the centers.
4. Create data structure of separate fields by concatenation such constructing tuple [f....., fel which creates a single data structure out of its children, or extract a field out of data structure.
21

---

Published as a conference paper at ICLR 2021
5. Given table T with k entries fri...., rk), a Boolean-valued function and analytic function f. SQL queries of the form SELECT SUM E {(x_i), WHERE p (x_i, x). Here, we assume that f has bounded value and p be approximated by an analytic function of degree at most p.
6. Compositions of functions, h(x) [((()).
First, we note that all of the above operators can be approximated by low-degree polynomials.
Claim 1. ! S Ollog(k/e)), each of the above operators in the generalized decision progrum can be expressed as polynomial of degree most ([oog(k/e)) where is maximum out- out-degree of any of the nodes.
Remark 5. Note that for the SQL query, we can also approximate other aggregation operators apart from SUM, such as MAX or MIN. For example, to approximate MAX of Ii,..., ......,,2 2x up to where the
input lies between [0, we can first write as
MAX( MA.., Ik) = = [[(m)>e)>>))
and then approximate the indicators by analytic functions.
Lemma 6 shows how compute the tilde function of the generalized decision program.
Lemma 6. The tilde function for generalized decision program can be computed recursively with the following steps:
1. For a sum gate h =
f. h(v) f f(v) - -vy).
2. For a product gate, = f.g. h(y) = fly) -gy)-
3. For a margin based decision gate (switch) with children f and = Isefef + (1 Itefel and h(y) = Itest(f( + g(v)) + ī(y). Here lift is the indicator for the case where the left child is chosen.
4. For cluster based decision gate (switch) with children (f....,fe)) h(y) S E, E.I.((6y/ Here I the indicator for the cluster corresponding to the i-th child.
5. For a look-up table with l key-values, h(v) S kf(y) as long the & norm of each key-value is at most
6. Creating a data structure out of separate fields can be done by concatenation, and h for the result is at most of the original tilde functions. Extracting field out of a data structure can also be done in the same way.
7. Given an analytic function f and a Boolean function P. for SQL operator h over SELECT SUM I ((ri), WHERE p pr__, x). or in other words h Err(r:)(rr v), h(y)
table T with entries {Fi,...;:kk representing
E.r.. where Ip.r. is the indicator for p(r,, For example, I here can denote some threshold value to be applied to column of the table, or selecting some subset of entries (in Fig, 7 x is the zip-code).
8. For h(x) f(g(x)), h(l)) < f(G())).
All except for the last part of the above Lemma directly follow from the results in the previous sub-section. Below, we prove the result for the last part regarding function compositions.
Lemma 7. Assume that all functions have imput and output dimension most d. If ʃ and g are two functions with degree at most and Pa. then h(x) f((()) has degree at most P1P2 and h(y)) < f((()))
Proof. Note that this follows f and are both scalar outputs and inputs. Let g(x) = (gi (x))....((x)) (x)). Let us begin with the case where f (B, x), where ||3]|| Then
22

---

Published as a conference paper at ICLR 2021
h(y) = EB S (v) I í(y). When f= (3 h(v) . < f((()) The same argument works when we take a linear combination, and also for multivariate function (as f for a multivariate f is the summation individual ft. by definition).
We now present our result for learning generalized decision programs.
Theorem 12.
Let the in in-ree of any gate be most k. The sample complexity for learning the following classes of generalized decision programs is follows:
1. If every gate is either decision node with margin k, then Mg e 1
gate, lookup of size most
2. For some constant C, if there are at most C product gates with degree at most and every other gate is decision gate with margin or a sum gate with constant functions at the leaves, then Mg S Ohh log(1 (c)
3. Given a function f and a Boolean function p which can be approximated by polynomial of degree at most (log((//))) for operator g over a table T with k entries (ri,..., Tk
representing SELECT SUM E {(ri), WHERE P (r_i, x), Mg S E, (p.r
4. Let the function at every gule be analytic function I of degree at most p and the sum of the coefficients of f is upper bounded by e for some constant c. Then note that fly) S (cy)) for y 2 1. Therefore, the final function g(y) S (cky)o and hence Mg S (ck)p".
Proof. The first three claims can be obtained using Lemma
For the final claim, consider the final polynomial obtained by expanding the function at each gate in a bottom-up way. We will upper bound ç(y) for the overall function g corresponding to the generalized decision program. ğ(y) can be upper bounded by starting with fly for the leaf nodes For any internal gate i, let gi(x) = St(f,, (z)..... (I:) where fj. are the outputs of the children of the gate i. We recursively compute (v) = fi(E, (v)). Therefore, for gate with & children (e( & (c Ei (1))P. Therefore, for the root gate 9o. (1) S (cky)""
Remark 6. Note that the dependence on h is doubly exponential. We show corresponding lower bound Theorem 75 that this is necessary.
Theorem 12 implies that
learn programs such the following formal version of Fig. (right) which involves analytic functions, SQL queries, data structures, and table look-up.
Example 1. Consider the following program:
class Person
string name;
Address address;
int income; public string get_zip_code()
return address wwt.eess.ip_ccddee
init (input_name, input_address, input_income)
name input_name;
address imput_address,
income input income;
class Address(
int street_number: string street_name string city;
string state; string zip_code;
23

---

the same analysis in Published as a conference paper at ICLR 2021
public string get_ zip_codee () return zip_code;
init(...) function to create new object with input values
dictionary name_to_ade aba_tto__ddrees_ttleee
dictionary zip_code_toe rip_code_toolat__onng #maps zip_code to tuple (latitute, longitude)
boolean in_same_zip_coe (Person A, Person B)
return A.get_zip_code () == seget_zip_cofe ()
float wtt.striiggh_neeeediititttteeeee (Person A, Person B) {
lat_longA abg_ccoee_to__la__ooggg//geeggg_ ());
lat_longB abb._poee.tooeetttoooo.eSeeeeee_ () ());
return auciicen__disttnnce(aLL....... lat_longB)
float www_iincoe_iipppoo (string zip_code)
construct. sQL table with income, zip_code from
return output of SQL query "SELECT AVG (INCOME) FROM T WHERE ZIP XTP_CO0B=zip_code
The following claim follows from Theorem 12
The above classes and functions can be implemented and learnt using (k/e) ((lg(/)())))) samples, where the tables are of size most k.
Claim 2.
Proof. We begin with the in__smee saane__ip_codee () function. Note that this is special case the cluster based functions. As in Corollary all attributes such zip-code are appropriately hashed such that they are well-separated. We can now test equality by doing an indicator function for ball around the zip-code of Person A. The indicator function for ball be approximated by low-degree polynomial as in the cluster- based branching results in Theorem 9 As the total number of individuals is at most k; therefore by Theorem 9 the sample complexity is most poly(k/e).
For the avg piccmm_zip__omm () function, we use the SQL query result Theorem 12 Note that the indicators testing equality in the of program, and hence in the previous case we can use the cluster-based branching result in Theorem Ioo approximate these indicators by polynomial functions, obtain sample complexity of poly(k7e).
Finally, we argue that we can learn the we are composing two functions and (g1. 92) where f is the distance function and (91. are the lookups for the latitude and longitude for Person A and B. By Corollary 4 the lookups have (1) & poly(k//c). By part of Lemma the tilde for the concatenation is the sum of the tilde for the individual functions. For computing the Euclidean distance VE(,, - . note that the square root function does not have Taylor series defined O. However, the proof for learning the 1/x function in the gravitational law (see Appendix(B.. (. to get polynomial of degree at most Ologg( 1/e)), and hence f(y) < (O(y)) log(1/)), Thus using the composition rule in Lemma 6 the sample complexity (k/e ) (log(ee))
() function. Here,
24

---

Published as a conference paper at ICLR 2021
B LEARNING DYNAMICAL SYSTEMS
B.I GRAVITATIONAL FORCE LAW
We can use the product and chain rules show that many functions important in scientific applications can be efficiently learnable. This is true even when the function has singularity. As an example demonstrating both, we prove the following bound on learning Newton's 's law of gravitation:
Theorem 13. Consider system of k bodies with positions x; R² and masses my interacting via the force:
mam
F
X -0-0 x;)
(38)
34
where rij ||x -xx] We assume that R Tmaaz/ miaaa/mmin- the ratio between the largest and smallest pairwise distance between any two bodies, is constant. Suppose the my have been rescaled to be between O and 1. Then the force law is efficiently learnable in the sense of Definition 3 usiin the modified ReLU kernel to generalization error less than using (m(((())) samples.
Proof. We will prove learning bounds for each component of F separately, showing efficient learning with probability greater than 1-5/3k. Then, using the union bound, the probability of simultaneously learning all the components efficiently will be 1 - 8.
There two levels of approximation: first, we will construct function which is within c/2 of the original force law, but more learnable. Secondly, we will prove bounds on learning that function to within error e/2.
We first rescale the vector of collective {xi} so that their collective length is at most 1. In these new units, this gives x2 max < E. The first component of the force on X1 can be written as:
(Fi) mimy ((x))1(Xxi)))) - (x1)1)
(39)
r
r1j
If we find a bound MMy for an individual contribution f to the force, we can get a bound on the total VMF (k= 1) My. Consider an individual force term in the sum. The force has singularity Tıj = 0. In addition, the function rıy itself is non-analytic due to the branch cut at O.
We instead will approximate the force law with a finite power series in rīj- and get bounds on
learning said power series. The power series representation of (1 x) 3/2 Eumo (2n)!! x." If
(2n+1)!!
we approximate the function with terms, the error can be bounded using Taylor's theorem. The Lagrange form of the error gives the bound
(2n + 1)!! (2n)!!
nd 2 d++
(40)
x 3/2
x 15/24d
where we use (2n+11)!! (2n)!!
nn for large n. We can use the above expansion by rewriting
rig rTj²= = a (1 (1 - (a)rrr)))))-0
(41)
for some shift a. Approximation with fa(rtz), the first d terms of the power series in (1 - (1-12//00)
r22//a2
gives us the error:
Vnd 1- 129.
[a(rit)) rT. a
(42)
- 2
which we want to be small over the range Tmin < rij S Tman-
The bound is optimized when it takes the same value at Tiin and Tmans SO we set a² = 2 2 1/2. In the limit that Taaz Tiins where learning is most difficult, the bound becomes
lfa(rz,) - -
v d
(R² /2) 3/22// 1)d+
(43)
3 max
25

---

Published as a conference paper at ICLR 2021
where R /maa////aa I mins which is constant by assumption.
In order to estimate an individual contribution to the force foree to error c/2h (so the total error is e/2), must have:
miniyTmaa ( - -1 S
(44)
2k
This allows us to choose the smallest which gives us this error. Taking the logarithm of both sides, we have:
2 Im(d) (5/2 d) In (2/1²) - 1)/R² & In(e/k²).
(45)
where we use that r 'aa 2/k after rescaling. The choice d 2 R In(k² (kk2/e) /e) ensures enror less than c/2k per term.
Using this approximation, we can use the product and chain rules get learning bounds on the force law. We can write the approximation
F((x)= = Σ (xm)
(46)
1F1
where hx(x = |x x; and kig (xxx = (x1)1 (xz); The number of samples needed for efficient
learning is bounded by / VMF. y/sk Ap, for
Ar. F((((L)) FA((()))
(47)
with
k(y) V2y, h(y) = Falv) - + w/aa)a.
(48)
Evaluating, we have
12 d
12
d-1
Ar. V2nd 1
v
1+
(49)
man
mma
which, after using 2 max S 2/k and = R2 In (k22 /E) gives us the bound
Mr. 1/2 RRa In (k22 (e) 3/2 (24k) R² mn(//e))
(50)
The asymptotic behavior is
V Mr. = ((m(k()))
(51)
since is bounded.
We can therefore learn an e22-approximation of one component of F,, with probability at least 1- 1-8/36 8/3k and error e/2 with (4, + log(3k/)))/²²) samples. Therefore, we can learn F1 to error with the same number of samples. Using union bound, with probability at least 1 - 8 we can simultaneously learn all components of all {F,} with that number samples.
We note that since the cutoff of the power series d(e) O In(k2 /e)) dominates the bound, we can easily compute learning bounds for other power-scries kernels as well. If the dth power series coefficient of the kernel is by, then the bound on FM is increased by (d(e) (d(e))ba(e)))11/ 1/2 For
example, for the Gaussian kernel, since by 1/2 v dl, the bound becomes
VFr. (R² (kk
(52)
which increases the exponent of k by factor of In lnkk2 /c)).
B.2 EMPIRICAL CONFIRMATION OF LEARNING BOUNDS
We empirically validated our analytical learning bounds by training models to learn the gravitational force function for k bodies (with l ranging from 5 to 400) in a a 3-ddimensional space. We created synthetic datasets by randomly drawing points from [0, 1]3 corresponding to the location of bodies, and compute the gravitational force (according randomly from [0, 1)3. To avoid singularities, we ensured a minimum distance 0.1 between the target body and the other bodies (corresponding to the choice R 10). As predicted by the theory,
Figure [1] on target body also drawn
26

---

Published as a conference paper at ICLR 2021
none of the models learn well if R is not fixed. We randomly drew the masses corresponding to the k + bodies from [o, 10). We generated 5 million such examples each example with 4(k + 1) features corresponding to the location and mass of each of the bodies, and single label corresponding to the gravitational force F on the target body along the r-axis. We held out 10% of the dataset as test data compute the root mean square error (RMSE) in prediction. We trained three different neural networks on this data, corresponding to various kernels we analyzed in the previous section:
1. A wide one hidden-layer ReLU network (corresponding the ReLU NTK kernel),
2. A wide one hidden-layer ReLU network with constant bias feature added to the input (corresponding to the NTK kernel).
3. A wide hidden-layer network with exponential activation function, where only the top layer of the network is trained (corresponding to the Gaussian kernel).
We used hidden layer of width 1000 for all the networks, as we observed that increasing the network width further did not improve results significantly. All the hidden layer weights were initialized randomly.
In Figure we show the normalized RMSE (RMSE/[FMad Faz - Fmin)) for each of the neural networks for different values of the number of bodies
Generalization error vs. k
10a
Normalized RMSE
10a4
10
ReLU
Gaussian kernel
10a
50
100
300
400
(number of bodies)
Figure 5: RMSE vs number of bodies & for learning gravitational force law for different kernels. Normalized by the range Fmaz Fmin of the forces. Gaussian kernels learn worse than ReLU at large k.
All three networks able to learn the gravitational force equation with small normalized RMSE for hundreds of bodics. Both the ReLU network and ReLU with bias outperform the network corresponding to the Gaussian kernel (in terms of RMSE) kernel learning seems to quickly degrade at around 400 bodies, with a normalized RMSE exceeding 50%. This is consistent with the learning bounds for these kernels in Section A.2 and suggests that those bounds may in fact be useful to compare the performances of different networks in practice.
increases. In particular, the Gaussian
We did not, however, observe much difference in the performance of the ReLU network when adding a bias to the input, which suggests that the inability to get an analytical bound due to only even powers in the ReLU NTK kernel might be shortcoming of the proof technique, rather than a property which fundamentally limits the model.
C LOWER BOUNDS
First, we show an exponential dependence on the depth h is necessary for learning decision trees. The result depends on the hardness of solving parity with noise.
Conjecture 1. (hardness of parity with noise) Let a, x E (0, 1)dd be d-dimensional Boolean vectors. In the parity with noise problem, we are given noisy inner products modulo of the unknown vector x with the examples ai i.e. b, = (a,, x) + тj mod 2 where q is a Binomial random variable which with probability 0.1. J. Then any algorithm for finding x needs least 200d) time or examples
27

---

Published as a conference paper at ICLR 2021
(where 52 hides roly-logaritmmic factors in d), Similarly. if x is given to be s-sparse for & d, then any algorithu for finding x needs at least (s time or examples.
Note that the hardness of learning parity with noise is standard assumption in computational learning theory and forms the basis of many cryptographic protocols (Regev) 2009). The best known algorithm for solving parity needs 20(d/ log d) time and examples Bllum et al. 2003). Learning parities is also known to provably require 20(d) samples for the class of algorithm known as statistical query algorithms-thes are algorithms are only allowed obtain estimates statistical properties the examples but cannot see the examples themselves (Kearns) [998). Note that the usual stochastic algorithms for training neural networks such as SGD can be implemented in the statistical query model (Song et al., 2017). Similar hardness result are conjectured for the problem of learning sparse parity with noise, and the best known algorithm runs in time d( (Valiant 2015).
Based on the hardness of parity with noise, we show that exponential dependence on the depth for learning decision trees is necessary.
Theorem 14. Conditioned on the hardness of the sparse parity with noise problem, any algorithm for learning decision trees of depth needs at least d time or examples.
Proof. Note that we can represent a parity with noise problem where the answer is h-sparse by a decision tree of depth h where the leaves represent the solutions to the parity problem. The result then follows by the hardness of the sparse parity with noise problem.
We also show that the doubly exponential dependence the depth for learning generalized decision programs is necessary.
Learning generalized decision program which is a binary tree of depth h using stochastic gradient descent requires least 2 examples. Conditioned the hardness of learning noisy parities, any algorithm for learning generalized program of depth lt needs at least 22 time or examples (where Ot hides poly-logaritmiic factors in h).
Theorem 15.
Proof. Note that a generalized decision program of depth h can encode parity function over D = 2 bits. Any statistical query algorithm to learn a parity over D bits needs at least 20(() samples. As stochastic gradient descent can be implemented in the statistical query model, hence the bound for stochastic gradient descent follows.
To prove the general lower bound, note that a generalized decision program of depth can also encode a noisy parity function over D = 2 bits. Conditioned on the hardness of parity with noise, any algorithm for learning noisy parities needs least 2Q(D) samples. Hence the bound for general algorithms also follows.
In our framework, we assume that all the underlying functions that we learn are analytic, or have an analytic approximation. It is natural to ask if such an assumption is necessary. Next, we show that learning even simple compositions of functions such as their sum is not possible without some assumptions the individual functions.
Lemma 8. There exists function classes F1 and F2 which can be learns efficiently but for every fi E F1 there exists f2 E F22 such that fi + f2 is hard to learn (conditioned on the hardness of learning parity with noise)
Proof. Both f1 and f2 are modifications of the parity with noise problem. The input in both cases is x E {0, 1jd. Let 3 be the solution to the noisy parity problem. The output for the function class Fi is [,3 w). where is the value of the noisy parity for the input. The output for the function class Fz is [-3, vl. where y is again the value of the noisy parity for the input. Note that F1 and F2 are trivial to learn, as the solution B to the noisy parity problem is already a part of the output. For any fi Fi. choose f2 E F2 to be the function with the same vector B.. Note that conditioned on the hardness of learning parity with noise, + is hard leam.
28

---

Published as a conference paper at ICLR 2021
C.I LOWER BOUNDS FOR LEARNING ANY ANALYTIC FUNCTION
In this section, we show that there is a lower bound on the Rademacher complexity y H based on the coefficients in the polynomial expansion of the ÿ function. Hence the 9 function characterizes the complexity of learning
For any J = (JI,.... Jn) E N", write a monomial XJ = = Define | Σx Jr. For polynomial p(z) -b a where a. C. its degree deg(p) m [J]. The following fact shows that monomials form an orthogonal basis over the unit circle in the complex plane.
= 1 if = J' and 0 otherwise (here, (s )o denotes the inner product over the unit circle in the complex plane).
Fact 3.
Note that according to Theorem 7 the sample complexity for learning g(x) depends on ğ'(1) Σn ااراز. and hence is the & norm of the derivative. The following Lemma shows that this is tight in the sense that 52 E2, jaā) samples or the &g norm of the derivative are necessary for learning g(r).
For any variable x let T denote the complex conjugate of x. Let X1 Xg..... X,, denote the training examples. Let Q denote the kernel polynomial so that K (x,,xy) x2) Q(x xx). Let Q(t) Σ, q.t For simplicity, let us look at the case where the power series and the kernel polynomial are univariate polynomials of bounded degree deg(q). We will assume that we have enough samples that Fact 3 hold when averaging over all samples. Let qJ be the coefficient of Ty in the polynomial expansion of Q(1i + +... l.).
Lemma 9. For univariate polynomial y = =p(x) (o(z))""'H)) H E, d3/43 asymptotically in the sample size, where aj are the coefficients of the polynomial p. For a multivariate polynomial, yTH H = H.
H EE 23/9g asymptotically in the sample size. Here, H-1 denotes the pseudoinverse of
Proof. We will begin with the univariate case. Let { y1), (x2, (#2,92,- training examples and their labels. Let y be the vector of all the labels { Let d = max(deg(p), (eg(()) (where we assume that deg(g) is bounded for simplicity). Now consider the matrix G with n rows and d columns where the (i,j)-th entry is z Note that GT trans- forms y from the standard basis to the monomial basis, i.c. the expected value of (1/n)G"y is (d1.....ad) (by Fact 3). Therefore, (1/n)G"y size n. We claim that H GDG where D is the diagonal matrix where Da.k qu. To verify this, let G(a) denote that i-th row of G and observe that the (i,j)-th entry DG (
u2,,...... (Fn...,,,nnn Un)) denote the
(aI....,a.) .d) asymptotically in the sample
En udunatr* = qu ( (1), Hi.j. Now given the orthonormality of the monomial basis, (1/n) G T. Therefore since H = GDGT is the SVD of H, H-1 (1/12)GD-1GT. Hence y y ((1n)/ D
For the multivariate case, instead of having columns for G, we will have one column for every possible value of J of degree at most d. In the diagonal entry DJ.J we put qr, where qJ is the coefficient of Ty in the polynomial expansion Q(1 + Ln).
Corollary 5. For the ReLU activation q3 = ((1/j), and hence 8" H 2 ME jaz) asymptoti- cally in the sample size.
Note that in Theorem 7 the upper bound for the sample complexity was OEE, Hlay)). hence Theorem 7 is tight up to the distinction between the l and l norm (which can differ by at most V deg(p)).
D ADDITIONAL DETAILS FOR EXPERIMENTS
D.1 SETUP DETAILS
All the experiments are done in TensorFlow, trained with GPU accelerator. We use the default TensorFlow values for all hyper parameters involved in the training of the neural networks. All the experiment results averaged over runs. The number of training epochs for each experiment and
29

---

Published as a conference paper at ICLR 2021
Test accuracy
50
100
1000
10'
Number of examples per cluster
(a) An instance of the problem with multiple (b) Test accuracy number of points per clusters, each cluster indicated by a red cluster
circle.
Figure 6: Experiment where data is clustered into tasks with separate linear function for each task. A single neural network does well even when there are multiple clusters.
average runtime (for one run) are summarized Table 2 For cluster experiments, number training examples per cluster varies 1000 to 100000, average runtime varies from 2 minutes to 100 minutes. For the decision tree experiments, number of training examples per leaf node varies from 64 to 512, avarage runtime varies from 14 minutes 42 minutes. For the SQL-style aggregation experiment, the train dataset contains 16384 examples, and test dataset contains 4096 examples, average runtime is 50 minutes. The source for the Penn World Table Centtasse/Feenstrre al. (2015) used in the SQL query experiment is https: / www rug. http://wwwww...///o////oooocctct ppwt and it is also available
athttps:/ www kaggle. com/ http:///......oooo///////////eea
Table 2: Number of epochs and average runtime
Experiment name
Number of epochs
Average runtime
Cluster
100
2 100 minutes
Decision Tree
200
14 42 minutes
SQL-style aggregation
6400
50 minutes
D.2 ADDITIONAL DETAILS FOR LEARNING CLUSTERS OF LINEAR FUNCTIONS
We provide
detailed setup of the experiment reported in Fig. 3a where the task codes given by clusters, and there is separate linear function for every cluster. In this experiment, the data drawn from i clusters, and from a mixture of two well-separated Gaussians in each cluster. Data points from the two Gaussians within each cluster are assigned two different labels, for 2k labels total. Fig. [a below shows instance of this task in two dimensions, the red circles represent the clusters, and there are two classes drawn from well-separated Gaussians from each cluster. In high dimensions, the clusters are very well-separated, and doing a k-means clustering to identify the A cluster centers and then learning simple linear classifier within each cluster gets near perfect classification accuracy. Fig. shows the performance task (same as Fig. Bal in the main body). We performance with a modest increase in the required number of samples.
single neural network trained on this that single neural network still gets good
30


Reviews:
[{"review_id": "uBg44znNgtz", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper takes an interesting theoretical dive on the learnability of multiple tasks as one task, while the tasks are constructed with special structures of the cluster, decision tree, or simple program. This paper provides sample complexities analysis, showing that wide two-layer neural networks with standard activation functions and SGD optimization is able to capture the data regularity between input and output, modulated by the three kinds of task code considered. Experiment results show that the networks are flexible enough to fit complex data generated in this way.  \n\nPros: \n\n* This paper is quite novel in many aspects, including modularity v.s. monolithic, constructing task codes by SQL-style aggregation queries, \"inverse counterpart\" of multitask learning, connections to cognitive science.\n\n* This paper provides impressive sample complexity analysis, with both informal and formal versions.   \n\nCons: \n\n* The clarity of writing is low. There are many places unclear, in particular, the \"task distinctiveness\". If we view it as one complex task, with the input-output data relationship modulated by one of the three task codes, then the questions of \"learnability\" by neural networks in handling this case are well addressed by the proposed theoretical analysis and I can see the empirical study is supportive of this claim. But if we interpret them as multiple tasks, how do we know the network \"is capable of simultaneously learning multiple tasks\" instead of just one task? \n\n* Possible gaps between claims and experiment \n\nRelated to the question above, it seems very attractive to me that \"the two-layer network can jointly learn the task coding scheme and the task-specific functions without special engineering of the architecture\", but how to justify \"task-specific\" functions/task code has been successfully learned? \n\nIt seems in Section 2, it is claimed that \"we wish to learn a function g such that g(c^i; x) = f_i(x) from the examples of the form (c^(i); x, f_i(x))\". Is c known? Is the learned network being able to take task code as input? But it seems the experiment shows f is learnable not g. \n\nQuestions: \n\n* How is the distinctness of tasks defined? Although the examples shown in Figure 1 are quite heterogeneous, examples considered such as  \"learning binary classification for well-separated data\" resembles mixture-of-experts classification, which can be viewed as one task to learn directly. \n\n* How the task coding is determined by a balanced decision tree? The setup in Section 2.3 is quite confusing. Moreover, is the construction of the g function different from the cluster setting? How does the complexity of task coding schemes influence the way the g function is constructed? This paper would benefit from explaining the different complexities added to the learning by different task coding schemes, and how do they make multiple tasks potentially conflict/distinct with each other.   \n\nOverall, I think the monolithic task formulation is novel and the problems the authors would like to address are fundamentally important. I am not from the theoretical machine learning side so I am not sure about the technical contribution of the theorems. The experiments look only partially supportive of the main claims. It is very likely for me to miss something important. The lacking of clarity is a big downside. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "m4y_X9VYky", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper posits a very interesting question about provable multi-task learning by neural nets. The idea is quite interesting to encode the objectives as task codes and then to write a smooth approximation to the predictor function as a weighted sum of indicators and the try training a net to learn this smoothening. But the problem with the paper is that the presentation of the details are extremely unclear and almost nothing about the proofs can be easily followed! Let me cite a few specific issues, \n\n-  The key theorem here seems to be Theorem 8 on page 18 and it follows from Remark 2 which itself follows from Theorem 7 on page 15 whose proof is claimed to be essentially that of Theorem 6 which in turn follows from equation 9 of Corollary 3 which isn't proven here - and this corollary 3 isn't the same as the corollary 6.2 of https://arxiv.org/pdf/1901.08584.pdf because this allows for odd powers and maybe more importantly the definition of H in this corollary 3 has no analogue in 1901.08584 and hence its mysterious to me as to where does this come from! What has the H in this corollary 3 got to do with the H^\\infity of 1901.08584 which is the NTK kernel. Its far from obvious that the proof there will go through here again. So as it stands the information given in the paper makes it difficult to trust that the result is correct. I would strongly suggest resubmitting to a future venue a self-contained paper with all the proofs. This writing here is looking too messed up! \n\n- The argument between equation 22 and 23 also make similar claims about analogy to proofs in the paper https://arxiv.org/pdf/1901.08584.pdf but here its not even clear as to which proof in there is being referred to! \n\n- Around equation 4 a claim is being made that https://arxiv.org/pdf/1901.08584.pdf has training only on the second layer for randomly initialized bottom layer. This doesnt seem to be true! Can the authors point to this assumption anywhere in that paper? 1901.08584 is not a NNGP result! \n\n- The proof of Theorem 14 claims that SGD can be implemented as a SQ algorithm. Can you reference this claim? If not, it would be best to put in the proof here since this isnt obvious at all.   ", "extra_scores": {}, "extra_text": {}}, {"review_id": "TL2BS_yzvy3", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": " \nVerdict:\n\nRecommendation to REJECT; Please consider for ICLR Special Journal Issue with modifications.\n\n(Unique situation, please read fully)\n \n\n##########################################################################\n### Summary:\n\nThe paper provides insight into the boundaries and feasibilities of a monolithic formulation of multitask learning by \nneural networks. The authors show how complex tasks can be modularly formulated thus yielding a joint monolithic \nlearning possibility. They also show that such modularity can be used to interpret simple algorithms thereby also \nleading to their joint learning.\n\nThe main contributions of the authors are the following:\n\n- showing that \"the two layer neural network can jointly learn the task coding scheme and the task specific \nfunctions without special engineering of the architecture\"\n\n- \"systematic theoretical investication of the extent of this ability\" (ability = single network can successfully \nbe trained to perform a wide variety of tasks) \n\n- \"...primarily interested in the extent to which different tasks may interfere,...\" (in a multitask setting)\n\n\n##########################################################################\n\n### Reasons for recommendation / score: \n\nThe paper is composed of a vast amount of very good research work. The research results seem significantly novel and definitely not incremental or based on other similar contemporary works. The rigorous mathematics and the attention to many details is laudable. \n\nHowever, the content in the paper literally and logically coerces the reader to constantly look at the supplementary material. I could also dare to say that the paper, strictly, without the supplementary material almost seems incomplete or as a compilation of claims, making for a choppy read. This is clearly an effect of the authors trying very hard to squeeze a lot of content into the 8-page limit. This must have taken a lot of efforts and I definitely can see the work that has gone into writing this concisely.\n\nThe paper would read much better with all the appendices and supplementary material introduced in the appropriate places, in proper continuum. I could see this paper be re-written almost as a proper tutorial paper in this topic of research. I would in this context, recommend some extra experiments and discussions (commented below also), to make the work more thorough.\n\nFor these reasons, I must insist that the venue for submitting this work should be a suitable journal such as JMLR, ML, or specifically be rewritten for the Special Journal Issue @ ICLR 2021. It is not suitable to be accepted as a conference contribution, by the sheer magnitude of work and the style it is presented in.\n\nAnother possibility I see, but do not recommend, is that the main motivation of the paper be modified to a solely task solving angle rather than the science of comparison and analysis. Then the theoretical rigour could be reduced and the focus can land on experimental results. This, in my opinion, could be suitable and a definite ACCEPT for ICLR conference.\n\n##########################################################################\n### Note about the reviewer:\n\nMy area of research is Bayesian non-parametrics applied on to multitask learning. I am not very familiar with the mathematical support provided for the theorems in this work. I cannot promise a critical verification of the correctness of the proofs.\n\nPlease also keep this in mind when considering my recommendation above. \n##########################################################################\n### Pros: \n \n1. The research quality and quantity are exceeding requirements for acceptance!\n\n2. The language is clear and crisp when introducing the research area and placing it in context with its related works. I especially like the delineated \"Our Results\" section. The authors clarify and discuss the topic with respect to two landmark papers very well.\n\n3. The flow of thought is clear and makes the reader comfortable with the presented paper structure.\n\n4. All the assumptions are made evident and clarified beyond any doubts, there are no hidden assumptions or simplifications. The scope of the focused research is also well clarified.\n\n5. There is thorough mathematical justifications, case studies of monolithic formulations, guarantees on bounds and learnabilities in the supplementary material. (I have tried to not give it attention as it is not a necessary part of the submission)\n\n##########################################################################\n\n### Cons: \n \n1. The title, abstract and some parts of the conclusion suggests a tone of comparison. This makes me expect a more involved discussion about the topic \"Modular versus Monolithic Task Formulations\". The authors have a lot of insight in this matter, however, when it comes to presentation, they fall short to guide the reader through them.\n\n2. The authors have carefully cherry-picked the theorems and balanced the extent to which they explain them so that it reads with completeness on the whole. I would argue that the details are important and without the proofs and mathematical involvement the scientific reader is forced to question \"why?\" or \"how?\" quite often.\n\n3. I would have liked the authors to place themselves better in the research context. I would have liked to know the findings of the authors in the lists of references (in Sections 1.1 and 1.2) with respect to the title of this work. \n\n4. The writing in many middle sections where details are needed, are overtly compressed. This is an effect of trying to squeeze in too much in too little space. The authors do direct the reader to the supplementary material many times.\n\n5. The authors do not answer the grander questions they begin the paper with. They analyse other attributes which are aligned in the same directions as these questions. Eg. Is modular construction better than the monolithic ones? When should we use which construction?\n\n6. The authors talk about multitask learning in the same context as [Caruana 1997]; That is, they reduce the scope of their analysis to inputs of the same size for all tasks or even same inputs to different functions (or tasks) to be learnt. Is this the general case of \"any\" multitask learning scenario? \n\n7. The experiments themselves do not seem statistically thorough. There should be more than 3 trials to draw conclusions, especially when the experimental setup is based on parameters drawn from a uniform distribution.\n\n8. The authors need to address the few inconsistencies in the graphs they have shown in Fig.2. I definitely would have liked more authors' insight on the observed statistics.\n\n9. In Fig.3 are the numbers significant? They are reported in the third decimal position for the Test R-squared values. Some more explanation is needed.\n\n10. Is the monolithic formulation of multitask learning effectively: joint learning of the switching function and the task function? It would be nice to read some more of the authors' explanation of how and if they are doing something different.\n\n\n#########################################################################\n\n### Suggested Presentation Changes:\n\n1. There could be more figures explaining the schematics of the networks, explaining the setup etc. Especially Sec.2.3 and Sec.2.4.\n\n2. There could be more figures and clearer captions with simpler explanations. This is where the reader looks first. It would be nice to suggest what to expect from such a graph and then highlight any results.\n\n3. The details in Table 1 can be made more readable. It is unclear where the focus lies.\n\n4. I feel it is important, the authors highlight that the Simple Programming Cosntructs part of their research derives from their novelty in the formulation of modules in terms of mathematical functions!\n\n##########################################################boarman###############\n### Suggested Small Corrections: \n\nGenerally, try to break down longer sentences into shorter multiple sentences.\n\n- Sec. Abstract: remove or replace word \"underlying\"\n\n- Sec. Abstract: \"... trees over some task-code attributes.\" Change 'some' --> 'certain' \n\n- Sec. Introduction: \"As techniques, such as neural networks, for learning with relatively rick classes have been developed, it is ...\"\n\n- Please see if you can move the references to the end of sentences than in the middle. It makes for better readability.\n\n- Sec 1.1: move NTK references to end of the sentence.\n\n- Sec 2.2 theorem 2: for omega(1) far A...A subspaces, if A ...\n\n- Sec 2.2 theorem 2: for omega(1) separated c...c prototypes, if ||c ...\n\n- Fig.3. caption: 1-(Test R-squared). Parentheses helps understand the subtraction from unity.\n\n#########################################################################\n\nUpdates: \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "BZ0LSMQBGp2", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper sets out to show that multiple tasks can be encoded in a neural network that that does not have explicit modular construction for each tasks, which is in contrast with the work of [Bakker and Heskes, JMLR 2003], and [Jocabs, Jordan, Nowlan and Hinton, Neural Computation 1991]. The premise of the paper is that task coding as indicators can be approximated via the derivative of an approximation (erf + Taylor truncation) of the step function. This approximation is analytic and, with individual tasks being analytic, makes the entire multiple task function g(c; x) possible to be approximated by neural networks due the the universal function approximation power of neural networks.\n\nThe paper starts from Arora et al. 2019b. However, this seems unnecessary and limiting. The paper can be made more general using from earlier work, such as those since [Hornik 1991].  This is specially so when SGD is not really required by the subsequent developments in the paper.\n\nThe paper is lacking much in clarity:\n1. The definition of g(c; x) in section 2.2 should be given from the onset and the related work discussion based around that. This will dispels any notion that the paper will dwell on positive/negative transfer/multi-task learning.\n2. The paper seems to be a theory paper, but much of the important derivations in the appendix beyond the page limit. For example, Lemma 4 and Theorem 8 are the main support of the paper, and should be in the main part of the paper. Lemma 7 is also important, and it is the closest in the entire paper that answers the question set out in the last sentence of the second para of section 1. \n3. The top left box of Figure 1 only makes sense when one reads appendix B1.\n4. Overall, the main paper cannot stand on its own without the appendix, which makes it inappropriate for the a conference paper (and its associated review period). \n\nI recommend *reject* based on the clarity and structure of the paper.\n\nCOMMENTS AFTER REVISION\n=========================\nI've looked through the revised paper, and the authors has addressed my comments. Hence, I am happy to recommend an accept.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper shows how multiple tasks can be encoded in a single neural network without the need for explicit modular construction for each task. The idea is very interesting and the research work presented is of high quality. 

All the reviewers underline their interest in the presented work. However, there is a deviation in the reviewers' score with half voting 
for acceptance and the other half for rejection. The main concern of the fellow reviewers with the below acceptance threshold score was the difficulty in grapsing the theory of the research presented due to the lack of important content from the main manuscript due to space limitations. The authors have an extended supplementary material that covers the whole magnitude of their work. 

I understand the reviewers' concern on how such a dense presentation does not do justice and harms the presented effort itself. However, given the edits the authors added to address the issue rasied and the interest and potential of this work - acknowledged by all the reviewers and myself I recommend acceptance. This is a work of a quality I would like to keep seeing in ICLR. 
Decision: Accept (Poster)