Learning Neural Networks with Two Nonlinear Layers in Polynomial Time

2017·arXiv

Abstract

We give a polynomial-time algorithm for learning neural networks with one layer of sigmoids feeding into any Lipschitz, monotone activation function (e.g., sigmoid or ReLU). We make no assumptions on the structure of the network, and the algorithm succeeds with respect to any distribution on the unit ball in n dimensions (hidden weight vectors also have unit norm). This is the first assumption-free, provably efficient algorithm for learning neural networks with two nonlinear layers.

Our algorithm– Alphatron– is a simple, iterative update rule that combines isotonic regression with kernel methods. It outputs a hypothesis that yields efficient oracle access to interpretable features. It also suggests a new approach to Boolean learning problems via real-valued conditional-mean functions, sidestepping traditional hardness results from computational learning theory.

Along these lines, we subsume and improve many longstanding results for PAC learning Boolean functions to the more general, real-valued setting of probabilistic concepts, a model that (unlike PAC learning) requires non-i.i.d. noise-tolerance.

1 Introduction

Giving provably efficient algorithms for learning neural networks is a fundamental challenge in the theory of machine learning. Most work in computational learning theory has led to negative results showing that– from a worst-case perspective– even learning the simplest architectures seems computationally intractable [LSSS14, SVWX17]. For example, there are known hardness results for agnostically learning a single ReLU (learning a ReLU in the non-realizable setting) [GKKT16].

As such, much work has focused on finding algorithms that succeed after making various restrictive assumptions on both the network’s architecture and the underlying marginal distribution. Recent work gives evidence that for gradient-based algorithms these types of assumptions are actually necessary [Sha16]. In this paper, we focus on understanding the frontier of efficient neural network learning: what is the most expressive class of neural networks that can be learned, provably, in polynomial-time without taking any additional assumptions?

1.1 Our Results

We give a simple, iterative algorithm that efficiently learns neural networks with one layer of sigmoids feeding into any smooth, monotone activation function (for example, Sigmoid or ReLU). Both the first hidden layer of sigmoids and the output activation function have corresponding hidden weight vectors. The algorithm succeeds with respect to any distribution on the unit ball in n dimensions. The network can have an arbitrary feedforward structure, and we assume nothing about these weight vectors other than that they each have 2-norm at most one in the first layer (the weight vector in the second layer may have polynomially large norm). These networks, even over the unit ball, have polynomially large VC dimension (if the first layer has m hidden units, the VC dimension will be Ω(m) [LBW94]).

This is the first provably efficient, assumption-free result for learning neural networks with more than one nonlinear layer; prior work due to Goel et al. [GKKT16] can learn a sum of one hidden layer of sigmoids. While our result “only” handles one additional nonlinear output layer, we stress that 1) the recent (large) literature for learning even one nonlinear layer often requires many assumptions (e.g., Gaussian marginals) and 2) this additional layer allows us to give broad generalizations of many well-known results in computational learning theory.

Our algorithm, which we call Alphatron, combines the expressive power of kernel methods with an additive update rule inspired by work from isotonic regression. Alphatron also outputs a hypothesis that gives efficient oracle access to interpretable features. That is, if the output activation function is u, Alphatron constructs a hypothesis of the form u(f(x)) where f is an implicit encoding of products of features from the instance space, and f yields an efficient algorithm for random access to the coefficients of these products.

More specifically, we obtain the following new supervised learning results:

• Let c(x1, . . . , xn) be any feedforward neural network with one hidden layer of sigmoids of size k feeding into any activation function u that is monotone and L-Lipschitz. Given independent draws (x, y) from Sn−1 × [0, 1] with E[y|x] = c(x) , we obtain an efficiently computable hypothesis u(f(x)) such that E[(c(x) − u(f(x)))2] ≤ ǫ with running time and sample complexity poly(n, k, 1/ǫ, L) (the algorithm succeeds with high probability). Note that the related (but incomparable) problem of distribution-free PAC learning intersections of halfspaces is cryptographically hard [KS09b].

• With an appropriate choice of kernel function, we show that Alphatron can learn more general, real-valued versions of well-studied Boolean concept classes in the probabilistic concept

model due to Kearns and Schapire. We subsume and improve known algorithms for uniform distribution learning of DNF formulas (queries), majorities of halfspaces, majorities of AC0 cir- cuits, and submodular functions, among others. We achieve the first non-i.i.d. noise-tolerant algorithmsfor learning these classes. Our technical contributions include

– Extending the KM algorithm for finding large Fourier coefficients [KM93] to the setting of probabilistic concepts. For the uniform distribution on the hypercube, we can combine the KM algorithm’s sparse approximations with a projection operator to learn smooth, monotone combinations of -bounded functions (it is easy to see that DNF formulas fall into this class). This improves the approach of Gopalan, Kalai, and Klivans [GKK08] for agnostically learning decision trees.

– Generalizing the “low-degree” algorithm due to Linial, Mansour, and Nisan [LMN93] to show that for any circuit class that can be approximated by low-degree Fourier polynomials, we can learn monotone combinations of these circuits “for free” in the probabilistic concept model.

– Using low-weight (as opposed to just low-degree) polynomial approximators for intersections of halfspaces with a (constant) margin to obtain the first polynomial-time algorithms for learning smooth, monotone combinations (intersection is a special case). The previous best result was a quasipolynomial-time algorithm for PAC learning the special case of ANDs of halfspaces with a (constant) margin [KS08].

We also give the first provably efficient algorithms for nontrivial schemes in multiple instance learning (MIL). Fix an MIL scheme where a learner is given a set of instances x1, . . . , xt, and the learner is told only some function of their labels, namely u(c(x1), . . . , c(xt)) for some unknown concept c and monotone combining function u. We give the first provably efficient algorithms for correctly labeling future bags even if the instances within each bag are not identically distributed. Our algorithms hold if the underlying concept c is sigmoidal or a halfspace with a margin. If the combining function averages label values (a common case), we obtain bounds that are independent of the bag size.

We learn specifically with respect to square loss, though this will imply polynomial-time learnability for most commonly studied loss functions. When the label Y is a deterministic Boolean function of X, it is easy to see that small square loss will imply small 0/1 loss.

1.2 Our Approach

The high-level approach is to use algorithms for isotonic regression to learn monotone combinations of functions approximated by elements of a suitable RKHS. Our starting point is the Isotron algorithm, due to Kalai and Sastry [KS09a], and a refinement due to Kakade, Kalai, Kanade and Shamir [KKKS11] called the GLMtron. These algorithms efficiently learn any generalized linear model (GLM): distributions on instance-label pairs (x, y) where the conditional mean of y given x is equal to u(w · x) for some (known) smooth, non-decreasing function u and unknown weight vector w. Their algorithms are simple and use an iterative update rule to minimize square-loss, a non-convex optimization problem in this setting. Both of their papers remark that their algorithms can be kernelized, but no concrete applications are given.

Around the same time, Shalev-Shwartz, Shamir, and Sridharan [SSSS11] used kernel methods and general solvers for convex programs to give algorithms for learning a halfspace under a distributional assumption corresponding to a margin in the non-realizable setting (agnostic learning). Their kernel was composed by Zhang et al. [ZLJ16] to obtain results for learning sparse neural networks with certain smooth activations, and Goel et al. [GKKT16] used a similar approach in conjunction with general tools from approximation theory to obtain learning results for a large class of nonlinear activations including ReLU and Sigmoid.

Combining the above approaches, though not technically deep, is subtle and depends heavily on the choice of model. For example, prior work on kernel methods for learning neural networks has focused almost exclusively on learning in the agnostic model. This model is too challenging, in the sense that the associated optimization problems to be solved seem computationally intractable (even for a single ReLU). The probabilistic concept model, on the other hand, is a more structured noise model and allows for an iterative approach to minimize the empirical loss.

Our algorithm– Alphatron– inherits the best properties of both kernel methods and gradient-based methods: it is a simple, iterative update rule that does not require regularization 3, and it learns broad classes of networks whose first layer can be approximated via an appropriate feature expansion into an RKHS.

One technical challenge is handling the approximation error induced from embedding into an RKHS. In some sense, we must learn a noisy GLM. For this, we use a learning rate and a slack variable to account for noise and follow the outline of the analysis of GLMtron (or Isotron). The resulting algorithm is similar to performing gradient descent on the support vectors of a target element in an RKHS. Our convergence bounds depend on the resulting choice of kernel, learning rate, and quality of RKHS embedding. We can then leverage several results from approximation theory and obtain general theorems for various notions of RKHS approximation.

1.3 Related Work

The literature on provably efficient algorithms for learning neural networks is extensive. In this work we focus on common nonlinear activation functions: sigmoid, ReLU, or threshold. For linear activations, neural networks compute an overall function that is linear and can be learned efficiently using any polynomial-time algorithm for solving linear regression. Livni et al. [LSSS14] observed that neural networks of constant depth with constant degree polynomial activations are equivalent to linear functions in a higher dimensional space (polynomials of degree d are equivalent to linear functions over monomials). It is known, however, that any polynomial that computes or even -approximates a single ReLU requires degree Ω(1/ǫ) [GKKT16]. Thus, linear methods alone do not suffice for obtaining our results.

The vast majority of work on learning neural networks takes strong assumptions on either the underlying marginal distribution (e.g., Gaussian), the structure of the network, or both. Works that fall into these categories include [KOS04, KM13, JSA15, SA14, ZPS17, ZLJ16, ZSJ17, GK17]. In terms of assumption-free learning results, Goel et al. [GKKT16] used kernel methods to give an efficient, agnostic learning algorithm for sums of sigmoids (i.e., one hidden layer of sigmoids) with respect to any distribution on the unit ball. Daniely [Dan17] used kernel methods in combination with gradient descent to learn neural networks, but the networks he considers have restricted VC dimension. All of the problems we consider in this paper are non-convex optimization problems, as it is known that a single sigmoid with respect to square-loss has exponentially many bad local

minima [AHW96].

A Remark on Bounding the 2-Norm. As mentioned earlier, the networks we learn, even over the unit ball, have polynomially large VC dimension (if the first layer has m hidden units, the VC dimension will be Ω(m)[LBW94] ). It is easy to see that if we allow the 2-norm of weight vectors in the first layer to be polynomially large (in the dimension), we arrive at a learning problem statistically close to PAC learning intersections of halfspaces, for which there are known cryptographic hardness results [KS09b]. Further, in the agnostic model, learning even a single ReLU with a bounded norm weight vector (and any distribution on the unit sphere) is as hard as learning sparse parity with noise [GKKT16]. As such, for distribution-free learnability, it seems necessary to have some bound on the norm and some structure in the noise model. Bounding the norm of the weight vectors also aligns nicely with practical tools for learning neural networks. Most gradient-based training algorithms for learning deep nets initialize hidden weight vectors to have unit norm and use techniques such as batch normalization or regularization to prevent the norm of the weight vectors from becoming large.

1.4 Notation

Vectors are denoted by bold-face and || · || denotes the standard 2-norm of the vector. We denote the space of inputs by X and the space of outputs by Y. In our paper, X is usually the unit sphere/ball and Y is [0, 1] or {0, 1}. Standard scalar (dot) products are denoted by a · b for vectors a, b ∈ Rn , while inner products in a Reproducing Kernel Hilbert Space (RKHS) are denoted by ⟨a, b⟩ for elements a, b in the RKHS. We denote the standard composition of functions f1 and f2 by f1 ◦ f2.

Note. Due to space limitations, we defer most proofs to the appendix.

2 The Alphatron Algorithm

Here we present our main algorithm Alphatron (Algorithm 1) and a proof of its correctness. In the next section we will use this algorithm to obtain our most general learning results.

Define vt = �mi=1 αtiψ(xi) implying ht(x) = u(⟨vt, ψ(x)⟩). Let ε(h) = Ex,y[(h(x) − E[y|x])2] and err(h) = Ex,y[(h(x) − y)2] . It is easy to see that ε(h) = err(h) − err(E[y|x]). Let �ε, �err be the empirical versions of the same.

The following theorem generalizes Theorem 1 of [KKKS11] to the bounded noise setting in a high dimensional feature space. We follow the same outline, and their theorem can be recovered by setting ψ(x) = x and ξ as the zero function.

Theorem 1. Let K be a kernel function corresponding to feature map ψ such that ∀x ∈ X, ||ψ(x)|| ≤ 1. Consider samples (xi, yi)mi=1 drawn iid from distribution D on X × [0, 1] such that E[y|x] = u(⟨v, ψ(x)⟩ + ξ(x)) where u : R → [0, 1] is a known L-Lipschitz non-decreasing function, ξ : Rn → [−M, M] for M > 0 such that E[ξ(x)2] ≤ ǫ and ||v|| ≤ B. Then for δ ∈ (0, 1) , with probability 1 − δ , Alphatron with λ = 1/L, T = CBL�m/ log(1/δ) and N = C′m log(T/δ)) for large enough constants C, C′ > 0 outputs a hypothesis h such that,

Alphatron runs in time poly(n, m, log(1/δ), tK) where tK is the time required to compute the kernel function K.

2.1 General Theorems Involving Alphatron

In this section we use Alphatron to give our most general learnability results for the probablistic concept (p-concept) model. We then state several applications in the next section. Here we show that if a function can be approximated by an element of an appropriate RKHS, then it is p-concept learnable. We assume that the kernel function is efficiently computable, that is, computable in polynomial time in the input dimension. Formally, we define approximation as follows:

Definition 1 ((ǫ, B, M) -approximation). Let f be a function mapping domain X to R and D be a distribution over X. Let K be a kernel function with corresponding RKHS H and feature vector We say f is (ǫ, B, M) -approximated by K over D if there exists some v ∈ H with ||v|| ≤ B such that for all x ∈ X, |f(x) − ⟨v, ψ(x)⟩| ≤ M and E[(f(x) − ⟨v, ψ(x)⟩)2] ≤ ǫ2.

Combining Alphatron and the above approximation guarantees, we have the following general learning results:

Theorem 2. Consider distribution D on X × [0, 1] such that E[y|x] = u(f(x)) where u is a known L-Lipschitz non-decreasing function and f is (ǫ, B, M) -approximated over by some kernel function K such that K(x, x′) ≤ 1. Then for δ ∈ (0, 1) , there exists an algorithm that draws m iid samples from D and outputs a hypothesis h such that with probability 1 − δ, ε(h) ≤ O(Lǫ) for m = O�� LMǫ �4 +� BLǫ �2�·log(1/δ) in time poly(n, B, M, L, 1/ǫ, log(1/δ)) where n is the dimension of X.

Proof. Let H be the RKHS corresponding to K and ψ be the feature vector. Since f is (ǫ, B, M)- approximated by kernel function K over DX , we have ∀ x, f(x) = ⟨v, ψ(x)⟩+ξ(x) for some function

Theorem 1, we have that Alphatron outputs a hypothesis h such that

for some constants C > 0. Also Alphatron requires at most O(BL�m/ log(1/δ)) iterations. Setting m as in theorem statement gives us the required result.

For the simpler case when f is uniformly approximated by elements in the RKHS we have,

Definition 2 ((ǫ, B) -uniform approximation). Let f be a function mapping domain X to R and D be a distribution over X. Let K be a kernel function with corresponding RKHS H and feature vector ψ. We say f is (ǫ, B) -uniformly approximated by K over D if there exists some v ∈ H with ||v|| ≤ B such that for all x ∈ X, |f(x) − ⟨v, ψ(x)⟩| ≤ ǫ.

Theorem 3. Consider distribution D on X × [0, 1] such that E[y|x] = u(f(x)) where u is a known L-Lipschitz non-decreasing function and f is (ǫ, B) -approximated by some kernel function K such that K(x, x′) ≤ 1. Then for δ ∈ (0, 1) , there exists an algorithm that draws m iid samples from D and outputs a hypothesis h such that with probability 1 − δ, ε(h) ≤ O(Lǫ) for m ≥�BLǫ �2 · log(1/δ) in time poly(n, B, L, 1/ǫ, log(1/δ)) where n is the dimension of X.

Proof. The proof is the same as the proof of Theorem 2 by re-examining the proof of Theorem 1 and noticing that ξ(x) is uniformly bounded by in each inequality.

3 Learning Neural Networks

In this section we give polynomial time learnability results for neural networks with two nonlinear layers in the p-concept model. Following Safran and Shamir [SS16], we define a neural network with one (nonlinear) layer with k units as follows:

for x ∈ Rn, ai ∈ Sn−1 for i ∈ {1, · · · , k}, b ∈ Sk−1 . We subsequently define a neural network with two (nonlinear) layers with one unit in layer 2 and k units in hidden layer 1 as follows:

Theorem 4. Consider samples (xi, yi)mi=1 drawn iid from distribution D on Sn−1 × [0, 1] such that E[y|x] = N2(x) with σ′ : R → [0, 1] is a known L-Lipschitz non-decreasing function and σ = σsig is the sigmoid function. There exists an algorithm that outputs a hypothesis h such that, with probability 1 − δ,

We also obtain results for networks of ReLUs, but the dependence on the number of hidden units, ǫ, and L are exponential (the algorithm still runs in polynomial-time in the dimension):

Theorem 5. Consider samples (xi, yi)mi=1 drawn iid from distribution D on Sn−1 × [0, 1] such that E[y|x] = N2(x) with σ′ : R → [0, 1] is a known L-Lipschitz non-decreasing function and σ = σrelu is the ReLU function. There exists an algorithm that outputs a hypothesis h such that with probability

Although our algorithm does not recover the parameters of the network, it still outputs a hypothesis with interpretable features. More specifically, our learning algorithm outputs the hidden layer as a multivariate polynomial. Given inputs x1, · · · , xm , the hypothesis output by our algorithm Alphatron is of the form h(x) = u(�mi=1 α∗i MKd(x, xi)) = u(⟨v, ψd(x)⟩) where v = �mi=1 α∗i ψd(xi) and d is dependent on required approximation. As seen in the preliminaries, ⟨v, ψd(x)⟩ can be expressed as a polynomial and the coefficients can be computed as follows,

Here, we follow the notation from [GKKT16]; M maps ordered tuple (k1, . . . , kj) ∈ [n]j for j ∈ [d] to tuple (i1, . . . , in) ∈ {0, . . . , d}n such that xk1 · · · xkj = xi11 · · · xinn and C maps ordered tuple to the number of distinct orderings of the ij’s for j ∈ {0, . . . , n}. The function C can be computed from the multinomial theorem (cf. [Wik16]). Thus, the coefficients of the polynomial can be efficiently indexed. Informally, each coefficient can be interpreted as the correlation between the target function and the product of features appearing in the coefficient’s monomial.

4 Generalizing PAC Learning to Probabilistic Concepts

In this section we show how known algorithms for PAC learning boolean concepts can be generalized to the probabilistic concept model. We use Alphatron to learn real-valued versions of these well-studied concepts.

Notation. We follow the notation of [GKK08]. For any function P : {−1, 1}n → R , we denote the Fourier coefficients by �P(S) for all S ⊆ [n] . The support of P, i.e., the number of non-zero Fourier coefficients, is denoted by supp(P). The norms of the coefficient vectors are defined as Lp(P) = ��S | �P(S)|p�1/p for p ≥ 1 and L∞(P) = maxS | �P(S)|. Similarly, the norm of the function P are defined as ||P||p = Ex∈{−1,1}n [�S |P(x)|p]1/p for p ≥ 1 . Also, the inner product P · Q = Ex∈{−1,1}n[P(x)Q(x)].

4.1 Generalized DNF Learning with Queries

Here we give an algorithm, KMtron, which combines isotonic regression with the KM algorithm [KM93] for finding large Fourier coefficients of a function (given query access to the function). The KM algorithm takes the place of the “kernel trick” used by Alphatron to provide an estimate for the update step in isotonic regression. Viewed this way, the KM algorithm can be re-interpreted as a query-algorithm for giving estimates of the gradient of square-loss with respect to the uniform distribution on Boolean inputs.

The main application of KMtron is a generalization of celebrated results for PAC learning DNF formulas [Jac97] to the setting of probabilistic concepts. That is, we can efficiently learn any conditional mean that is a smooth, monotone combination of -bounded functions.

KM Algorithm. The KM algorithm learns sparse approximations to boolean functions given query access to the underlying function. The following lemmas about the KM algorithm are important to our analysis.

Lemma 1 ([KM93]). Given an oracle for P : {−1, 1}n → R, KM(P, θ) returns Q : {−1, 1}n → R with |supp(Q)| ≤ O(L2(P)2θ−2) and L∞(P − Q) ≤ θ . The running time is poly(n, θ−1, L2(P)).

Projection Operator. The projection operator projK(P) for P : {−1, 1}n → R maps P to the closest Q in convex set K = {Q : {−1, 1}n → R | L1(Q) ≤ k}, i.e., projK(P) = arg minQ∈K ||Q−P||2. [GKK08] show that projK is simple and easy to compute for sparse polynomials. We use the following lemmas by [GKK08] about the projection operator in our analysis.

Lemma 4 ([GKK08]). Let P, P ′ be such that L∞(P − P ′) ≤ ǫ. Then ||projK(P) − projK(P ′)||2 ≤ 2√ǫk.

KMtron. The algorithm KMtron is as follows:

To efficiently run KMtron, we require efficient query access to u ◦ P − u ◦ Pt−1. Since Pt−1 is stored as a sparse polynomial, and we are given query access for u ◦ P , we can efficiently compute u(P(x)) − u(Pt−1(x)) for any x . We can extend the algorithm to handle distribution queries (p-concept), i.e., for any x of our choosing we obtain a sample of y where E[y|x] = u(P(x)). [GKK08] (c.f. Appendix A.1) observed that using distribution queries instead of function queries to the conditional mean is equivalent as long as the number of queries is polynomial.

The following theorem proves the correctness of KMtron.

Theorem 6. For any non-decreasing L-Lipschitz u : R → [0, 1] and function P : {−1, 1}n → R such that L1(P) ≤ k , given query access to u ◦ P , KMtron run with λ = ǫ2L, T = 2k2L2ǫ2 and θ ≤ C′ǫ4L4k3 for sufficiently small constant C′ > 0 and outputs P ∗ such that Ex∈{−1,1}n[(u(P(x)) − u(P ∗(x)))2] ≤ ǫ. The runtime of KMtron is poly(n, k, L, 1/ǫ).

Corollary 1. Let Pi be such that L1(Pi) ≤ k for i ∈ [s] . If we have query access to y for all x such that E[y|x] = u�1s�si=1 Pi� for non-decreasing L-Lipschitz u, then using the above, we can learn the conditional mean function in time poly(n, k, L, 1/ǫ) with respect to the uniform distribution on {−1, 1}n.

Observe that the complexity bounds are independent of the number of terms. This follows from the fact that L1�1s�si=1 Pi�≤ k . This leads to the following new learning result for DNF formulas: fix a DNF f and let frac(f(x)) denote the fraction of terms of f satisfied by x. Fix monotone, L-Lipschitz function u. For uniformly chosen input x, label y is equal to 1 with probability u(frac(f(x))). Then in time polynomial in n, 1/ǫ, and L , KMtron outputs a hypothesis h such that $E[(h(x)−u(frac(f(x))))2] ≤ ǫ (recall L1(AND) = 1$ ). Note that the running time has no dependence on the number of terms.

As an easy corollary, we also obtain a simple (no Boosting required) polynomial time query-algorithm for learning DNFs under the uniform distribution

Corollary 2. Let f be a DNF formula from {−1, 1}n → {0, 1} with s terms. Then f is PAC learnable under the uniform distribution using membership queries in time poly(n, s, 1/ǫ).

4.2 Extending the “Low-Degree” Algorithm

Here we show that Alphatron can be used to learn any smooth, monotone combination of function classes that are approximated by low-degree polynomials (our other results require us to take advantage of low-weight approximations).

Definition 3. For a class of functions C, let u(C) denote monotone function u applied to a linear combination of (polynomially many) functions from C.

For the domain of {−1, 1}n and degree parameter d, our algorithm will incur a sample complexity and running time factor of , so the “kernel trick” is not necessary (we can work explicitly in the feature space). The main point is that using isotonic regression (as opposed to the original “low-degree” algorithm due to Linial, Mansour and Nisan [LMN93]), we can learn u(C) for any smooth, monotone u and class C that has low-degree Fourier approximations (we also obtain non-i.i.d. noise tolerance for these classes due to the definition of the probabilistic concept model). While isotonic regression has the flavor of a boosting algorithm, we do not need to change the underlying distribution on points or add noise to the labels, as all boosting algorithms do.

Definition 4. (ǫ, d) -Fourier concentration A function f : {−1, 1}n → R is said to be (ǫ, d)-Fourier concentrated if �S:|S|>d �f(S)2 ≤ ǫ2 where �f(S) for all S ⊆ [n] are the discrete Fourier coefficients of f.

Theorem 7. Consider distribution D on {−1, 1}n × [0, 1] whose marginal is uniform on and E[y|x] = u(f(x)) for some known non-decreasing L-Lipschitz u : R → [0, 1] and f : {−1, 1}n → [−M, M]. If f is (ǫ, d) -Fourier concentrated then there exists an algorithm that draws m iid samples from D and outputs hypothesis h such that with probability 1 − δ, ε(h) ≤ O(Lǫ) for m = poly(nd, M, ǫ, log(1/δ)) in time poly(nd, M, ǫ, log(1/δ)).

The above can be generalized to linear combinations of Fourier concentrated functions using the following lemma.

Many concept classes are known to be approximated by low-degree Fourier polynomials. Combining Theorem 7 and Lemma 5, we immediately obtain the following learning results in the probabilistic concept model whose running time matches or improves their best-known PAC counterparts:

• u(AC0 ), generalizing majorities of constant depth circuits [JKS02].

• u(LTF), generalizing majorities of linear threshold functions [KKMS08].

• u(SM), generalizing submodular functions [CKKL12].

As a further application, we can learn majorities of k halfspaces with respect to the uniform distribution in time nO(k2/ǫ2) for any ǫ > 0 (choose a with each entry 1/k and let u smoothly interpolate majority with Lipschitz constant k). This improves on the best known bound of nO(k4/ǫ2) [KKMS08]

Using the fact that the AND function has a uniform approximator of degree O(√n log(1/ǫ)) [Pat92], we immediately obtain a 2 ˜O(√n) time algorithm for distribution-free learning of u(AND) in the probabilistic concept model (this class includes the set of all polynomial-size DNF formulas). The problem of generalizing the 2 ˜O(n1/3) -time algorithm for distribution-free PAC learning of DNF formulas due to Klivans and Servedio [KS04] remains open.

4.3 Learning Monotone Functions of Halfspaces with a Margin as Probabilistic Concepts

In this section we consider the problem of learning a smooth combining function u of k halfspaces with a margin . We assume that all examples lie on the unit ball Sn−1 and that for each weight vector w, ||w|| = 1. For simplicity we also assume each halfspace is origin-centered, i.e. θ = 0 (though our techniques easily handle the case of nonzero θ).

Theorem 8. Consider samples (xi, yi)mi=1 drawn iid from distribution D on Sn−1 × [0, 1] such that E[y|x] = u��ti=1 aihi(x)�where u : Rn → [0, 1] is a L -Lipschitz non-decreasing function, hi are origin-centered halfspaces with margin ρ on X and ||a||1 = A . There exists an algorithm that outputs a hypothesis h such that with probability 1 − δ,

Remark. If E[y|x] = u� 1t�ti=1 hi(x)� , that is, a function of the fraction of true halfspaces, then the run-time is independent of the number of halfspaces t. This holds since A = 1 in this case.

We now show that Theorem 8 immediately implies the first polynomial-time algorithm for PAC learning intersections of halfspaces with a (constant) margin. Consider t-halfspaces {h1, . . . , ht}. An intersection of these t-halfspaces is given by fAND(x) = ∧ti=1hi(x).

Corollary 3. There exists an algorithm that PAC learns any intersection of t-halfspaces with margin ρ > 0 on Sn−1 in time poly�n,� tǫ�(C/ρ) , log(1/δ)� for some constant C.

This result improves the previous best bound due to Klivans and Servedio [KS08] that had (for constant ) a quasipolynomial dependence on the number of halfspaces t.

Klivans and Servedio used random projection along with kernel perceptron and the complete quadratic kernel to obtain their results. Here we directly use the multinomial kernel, which takes advantage of how the polynomial approximator’s weights can be embedded into the corresponding RKHS. We remark that if we are only interested in the special case of PAC learning an intersection of halfspaces with a margin (as opposed to learning in the probabilistic concept model), we can use kernel perceptron along with the multinomial kernel (and a Chebsyshev approximation that will result in an improved O(1/√ρ) dependence), as opposed to Alphatron in conjunction with the multinomial kernel.

5 Multiple Instance Learning

Multiple Instance Learning (MIL) is a generalization of supervised classification in which a label is assigned to a bag, that is, a set of instances, instead of an individual instance [DLLP97]. The bag label is induced by the labels of the instances in it. The goal we focus on in this work is to label future bags of instances correctly, with high probability. We refer the reader to [Amo13, HVB +16] for an in-depth study of MIL. In this section we apply the previously developed ideas to MIL and give the first provable learning results for concrete schemes that do not rely on unproven assumptions.

Comparison to Previous Work. Under the standard MI assumption, various results are known in the PAC learning setting. Blum and Kalai [BK98] showed a simple reduction from PAC learning MIL to PAC learning with one-sided noise under the assumption that the instances in each bag were drawn independently from a distribution. Sabato and Tishby [ST12] removed the independence assumption and gave sample complexity bounds for learning future bags. All the above results require the existence of an algorithm for PAC learning with one-sided noise, which is itself a challenging problem and not known to exist for even simple concept classes.

In this work, we do not assume instances within each bag are independently distributed, and we do not require the existence of PAC learning algorithms for one-sided noise. Instead, we give efficient algorithms for labeling future bags when the class labeling instances is an unknown halfspace with a margin or an unknown depth-two neural network. We succeed with respect to general monotone, smooth combining functions.

Notation. Let us denote the space of instances as X and the space of bags as B ⊆ X ∗. Let N be an upper bound on the size of the bags, that is, N = maxβ∈B |β| . Let the instance labeling function be c : X → R and the bag labeling function be fbag . We assume a distribution D over the bags and allow the instances within the bag to be dependent on each other. We consider two variants of the relationship between the instance and bag labeling functions and corresponding learning models.

5.1 Probabilistic MIL

We generalize the deterministic model to allow the labeling function to induce a probability distribution over the labels. This assumption seems more intuitive and less restrictive than the deterministic case as it allows for noise in the labels.

Definition 5 (Probabilistic MI Assumption). Given combining function u : R → [0, 1], for bag β, fbag(β) is a random variable such that Pr[fbag(β) = 1] = u�1|β| · �x∈β c(x)�where c is the instance labeling function.

Definition 6 (Probabilistic MIL). The concept class C is (ǫ, δ) -Probabilistic MIL for u with sample complexity M and running time T if under the probabilistic MI assumption for u, there exists an algorithm A such that for all c ∈ C as the instance labeling function and any distribution D on B, A draws at most M iid bags and runs in time at most T to return a bag-labeling hypothesis h such that with probability 1 − δ,

The following is our main theorem of learning in the Probabilistic MIL setting.

Theorem 9. The concept class C is (ǫ, δ) -Probabilistic MIL for monotone L-Lipschitz u with sample complexity (BLǫ )2 · log(1/δ) and running time poly(n, B, L, 1/ǫ, log(1/δ)) if all c ∈ C are (ǫ/CL, B)- uniformly approximated by some kernel K for large enough constant C > 0.

Combining Theorem 9 with learnability Theorems 4 and 8 we can show the following polynomial time Probabilistic MIL results.

Corollary 4. For any monotone L-Lipschitz function u, the concept class of sigmoids over Sn−1 are (ǫ, δ) -Probabilistic MIL with sample complexity and running time poly(n, L, 1/ǫ, log(1/δ)).

Corollary 5. For any monotone L-Lipschitz function u, the concept class of halfspaces with a constant margin over Sn−1 are (ǫ, δ) -Probabilistic MIL with sample complexity and running time poly(n, L, 1/ǫ, log(1/δ)).

References

[AHW96] Peter Auer, Mark Herbster, and Manfred K. Warmuth. Exponentially many local minima for single neurons. In Advances in Neural Information Processing Systems, volume 8, pages 316–322. The MIT Press, 1996.

[Amo13] Jaume Amores. Multiple instance classification: Review, taxonomy and comparative study. Artificial Intelligence, 201:81–105, 2013.

[BK98] Avrim Blum and Adam Kalai. A note on learning from multiple-instance examples. Machine Learning, 30(1):23–29, 1998.

[BM02] Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463–482, 2002.

[CKKL12] Mahdi Cheraghchi, Adam R. Klivans, Pravesh Kothari, and Homin K. Lee. Submodular functions are noise stable. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1586–1592. SIAM, 2012.

[Dan15] Amit Daniely. A ptas for agnostically learning halfspaces. In Conference on Learning Theory, pages 484–502, 2015.

[Dan17] Amit Daniely. Sgd learns the conjugate kernel class of the network. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, NIPS, pages 2419–2427, 2017.

[DLLP97] Thomas G Dietterich, Richard H Lathrop, and Tomás Lozano-Pérez. Solving the multiple instance problem with axis-parallel rectangles. Artificial intelligence, 89(1):31–71, 1997.

[Fel12] Vitaly Feldman. Learning dnf expressions from fourier spectrum. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland, volume 23 of JMLR Proceedings, pages 17.1–17.19. JMLR.org, 2012.

[GK17] Surbhi Goel and Adam Klivans. Eigenvalue decay implies polynomial-time learnability of neural networks. In NIPS, 2017.

[GKK08] Parikshit Gopalan, Adam Tauman Kalai, and Adam R Klivans. Agnostically learning decision trees. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 527–536. ACM, 2008.

[GKKT16] Surbhi Goel, Varun Kanade, Adam Klivans, and Justin Thaler. Reliably learning the relu in polynomial time. arXiv preprint arXiv:1611.10258, 2016.

[HVB16] Francisco Herrera, Sebastián Ventura, Rafael Bello, Chris Cornelis, Amelia Zafra, Dánel Sánchez-Tarragó, and Sarah Vluymans. Multiple instance learning. In Multiple Instance Learning, pages 17–33. Springer, 2016.

[Jac97] Jeffrey C. Jackson. An efficient membership-query algorithm for learning dnf with respect to the uniform distribution. J. Comput. Syst. Sci, 55(3):414–440, 1997.

[JKS02] Jeffrey C. Jackson, Adam R. Klivans, and Rocco A. Servedio. Learnability beyond ACˆ0. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC-02), pages 776–784, New York, May 19–21 2002. ACM Press.

[JSA15] Majid Janzamin, Hanie Sedghi, and Anima Anandkumar. Beating the perils of nonconvexity: Guaranteed training of neural networks using tensor methods. arXiv preprint arXiv:1506.08473, 2015.

[Kan14] Daniel M. Kane. The average sensitivity of an intersection of half spaces. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 437–440. ACM, 2014.

[KKKS11] Sham M. Kakade, Adam Kalai, Varun Kanade, and Ohad Shamir. Efficient learning of generalized linear and single index models with isotonic regression. In NIPS, pages 927–935, 2011.

[KKMS08] Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio. Ag- nostically learning halfspaces. SIAM J. Comput., 37(6):1777–1805, 2008.

[KM93] Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the fourier spectrum. SIAM Journal on Computing, 22(6):1331–1348, 1993.

[KM13] Adam R. Klivans and Raghu Meka. Moment-matching polynomials. Electronic Colloquium on Computational Complexity (ECCC), 20:8, 2013.

[KOS04] A. Klivans, R. O’Donnell, and R. Servedio. Learning intersections and thresholds of halfspaces. JCSS: Journal of Computer and System Sciences, 68, 2004.

[KS90] Michael J Kearns and Robert E Schapire. Efficient distribution-free learning of probabilistic concepts. In Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on, pages 382–391. IEEE, 1990.

[KS04] A. Klivans and R. Servedio. Learning DNF in time 2O (n1/3). JCSS: Journal of Computer and System Sciences, 68, 2004.

[KS08] Adam R Klivans and Rocco A Servedio. Learning intersections of halfspaces with a margin. Journal of Computer and System Sciences, 74(1):35–48, 2008.

[KS09a] Adam Kalai and Ravi Sastry. The isotron algorithm: High-dimensional isotonic regression. In COLT, 2009.

[KS09b] Adam R. Klivans and Alexander A. Sherstov. Cryptographic hardness for learning intersections of halfspaces. J. Comput. Syst. Sci, 75(1):2–12, 2009.

[KST09] Sham M Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In Advances in neural information processing systems, pages 793–800, 2009.

[LBW94] Lee, Bartlett, and Williamson. Lower bounds on the VC-dimension of smoothly parametrized function classes. In COLT: Proceedings of the Workshop on Computational Learning Theory, Morgan Kaufmann Publishers, 1994.

[LMN93] Linial, Mansour, and Nisan. Constant depth circuits, fourier transform, and learnability. JACM: Journal of the ACM, 40, 1993.

[LSSS14] Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir. On the computational efficiency of training neural networks. In Advances in Neural Information Processing Systems, pages 855–863, 2014.

[LT91] Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: Isoperimetry and Processes. Springer, 1991.

[Pat92] Ramamohan Paturi. On the degree of polynomials that approximate symmetric Boolean functions (preliminary version). In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 468–474, Victoria, British Columbia, Canada, 4–6 May 1992.

[SA14] Hanie Sedghi and Anima Anandkumar. Provable methods for training neural networks with sparse connectivity. arXiv preprint arXiv:1412.2693, 2014.

[SGSS07] Alex Smola, Arthur Gretton, Le Song, and Bernhard Schölkopf. A hilbert space embedding for distributions. In International Conference on Algorithmic Learning Theory, pages 13–31. Springer, 2007.

[Sha16] Ohad Shamir. Distribution-specific hardness of learning neural networks. arXiv preprint arXiv:1609.01037, 2016.

[She12] Alexander A Sherstov. Making polynomials robust to noise. In Proceedings of the fortyfourth annual ACM symposium on Theory of computing, pages 747–758. ACM, 2012.

[SS02] Bernhard Schölkopf and Alexander J Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.

[SS16] Itay Safran and Ohad Shamir. Depth separation in relu networks for approximating smooth non-linear functions. CoRR, abs/1610.09887, 2016.

[SSSS11] Shai Shalev-Shwartz, Ohad Shamir, and Karthik Sridharan. Learning kernel-based halfspaces with the 0-1 loss. SIAM J. Comput., 40(6):1623–1646, 2011.

[ST12] Sivan Sabato and Naftali Tishby. Multi-instance learning with any hypothesis class. Journal of Machine Learning Research, 13(Oct):2999–3039, 2012.

[SVWX17] Le Song, Santosh Vempala, John Wilmes, and Bo Xie. On the complexity of learning neural networks. arXiv preprint arXiv:1707.04615, 2017.

[Val84] Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134– 1142, 1984.

[Wik16] Wikipedia. Multinomial theorem — Wikipedia, the free encyclopedia, 2016. URL: https://en.wikipedia.org/wiki/Multinomial_theorem.

[ZLJ16] Yuchen Zhang, Jason Lee, and Michael Jordan. networks are improperly learnable in polynomial-time. In ICML, 2016.

[ZPS17] Qiuyi Zhang, Rina Panigrahy, and Sushant Sachdeva. Electron-proton dynamics in deep learning. CoRR, abs/1702.00458, 2017.

[ZSJ +17] Kai Zhong, Zhao Song, Prateek Jain, Peter L. Bartlett, and Inderjit S. Dhillon. Recovery guarantees for one-hidden-layer neural networks. In ICML, volume 70, pages 4140–4149. JMLR.org, 2017.

A Background

A.1 Learning Models

We consider two learning models in our paper, the standard Probably Approximately Correct (PAC) learning model and a relaxation of the standard model, the Probabilistic Concept (p-concept) learning model. For completeness, we define the two models and refer the reader to [Val84, KS90] for a detailed explanation.

Definition 7 (PAC Learning [Val84]). We say that a concept class C ⊆ {0, 1}X is Probably Approximately Correct (PAC) learnable, if there exists an algorithm A such that for every c ∈ C,δ, ǫ > 0 and D over X, if A is given access to examples drawn from D and labeled according to c, A outputs a hypothesis h : X → {0, 1} , such that with probability at least 1 − δ,

Furthermore, we say that C is efficiently PAC learnable to error ǫ if A can output an h satisfying the above with running time and sample complexity polynomial in n, 1/ǫ, and 1/δ.

Definition 8 (p-concept Learning [KS90]). We say that a concept class C ⊆ YX is Probabilistic Concept (p-concept) learnable, if there exists an algorithm A such that for every δ, ǫ > 0, c ∈ C and distribution D over X × Y with E[y|x] = c(x) we have that A, given access to examples drawn from D, outputs a hypothesis h : X → Y , such that with probability at least

Furthermore, we say that C is efficiently p-concept learnable to error ǫ if A can output an h satisfying the above with running time and sample complexity polynomial in n, 1/ǫ, and 1/δ.

Here we focus on square loss for p-concept since an efficient algorithm for square-loss implies efficient algorithms of various other standard losses.

A.2 Generalization Bounds

The following standard generalization bound based on Rademacher complexity is useful for our analysis. For a background on Rademacher complexity, we refer the readers to [BM02].

Theorem 10 ([BM02]). Let D be a distribution over X × Y and let L : Y′ × Y (where Y ⊆ Y′ ⊆ R) be a b -bounded loss function that is L-Lipschitz in its first argument. Let F ⊆ (Y′)X and for any f ∈ F, let L(f; D) := E(x,y)∼D[L(f(x), y)] and �L(f; S) := 1m�mi=1 L(f(xi), yi), where S = ((x1, y1), . . . , (xm, ym)) ∼ Dm . Then for any δ > 0 , with probability at least 1 − δ (over the random sample draw for S), simultaneously for all f ∈ F , the following is true:

For a linear concept class, the Rademacher complexity can be bounded as follows.

Theorem 11 ([KST09]). Let X be a subset of a Hilbert space equipped with inner product ⟨·, ·⟩ such that for each x ∈ X, ⟨x, x⟩ ≤ X2, and let W = {x �→ ⟨x, w⟩ | ⟨w, w⟩ ≤ W 2} be a class of linear functions. Then it holds that

The following result is useful for bounding the Rademacher complexity of a smooth function of a concept class.

Theorem 12 ([BM02, LT91]) . Let φ : R → R be Lφ -Lipschitz and suppose that φ(0) = 0. Let Y ⊆ R , and for a function f ∈ YX . Finally, for F ⊆ YX , let φ ◦ F = {φ ◦ f : f ∈ F} . It holds that Rm(φ ◦ F) ≤ 2 · Lφ · Rm(F).

A.3 Kernel Methods

We assume the reader has a basic working knowledge of kernel methods (for a good resource on kernel methods in machine learning we refer the reader to [SS02]). We denote a kernel function by K(x, x′) = ⟨ψ(x), ψ(x′)⟩ where ψ is the associated feature map and H is the corresponding reproducing kernel Hilbert space (RKHS).

Here we define two kernels and a few of their properties that we will use for our analysis. First, we define a variant of the polynomial kernel, the multinomial kernel due to Goel et al. [GKKT16]:

Definition 9 (Multinomial Kernel [GKKT16]) . Define ψd : Rn → RNd, where Nd = 1+n+· · ·+nd, indexed by tuples (k1, . . . , kj) ∈ [n]j for each j ∈ {0, 1, . . . , d} , where the entry of ψd(x) corresponding to tuple (k1, . . . , kj) equals xk1 · · · xkj. (When j = 0 we have an empty tuple and the corresponding entry is 1.) Define kernel MKd as follows:

It is easy to see that the multinomial kernel is efficiently computable. A multivariate polynomial p of degree d can be represented as an element v ∈ HMKd . Also, every can be interpreted as a multivariate polynomial of degree d such that

where coefficient β(i1, . . . , in) is as follows,

Here, v(·) is used to index the corresponding entry in v. The following lemma is due to [GKKT16], following an argument of Shalev-Shwartz et al. [SSSS11]:

Lemma 6. Let p(t) = �di=0 βiti be a given univariate polynomial with �di=1 β2i ≤ B2. For w such that ||w|| ≤ 1 , the polynomial p(w · x) equals ⟨pw, ψ(x)⟩ for some pw ∈ HMKd with ||pw|| ≤ B.

For our results on Multiple Instance Learning, we make use of the following known kernel defined over sets of vectors:

A.4 Approximation Theory

We will make use of a variety of tools from approximation theory to obtain specific embeddings of function classes into a RKHS. The following lemma for approximating the Boolean sign function was given by [Dan15]:

The above lemma assumes sign takes on values {±1} , but a simple linear transformation also works for {0, 1}.

[GKKT16] showed that activation functions sigmoid: σsig(a) = 11+e−a and ReLU: σrelu(a) = max(0, a) can be (ǫ, B) -uniformly approximated by the multinomial kernel for B dependent on more formally they showed the following:

Lemma 8 (Approximating a Single Hidden Unit). We have,

Further, ||v|| ≤ (1/ǫ)O(1) . This implies that σsig is (ǫ, (1/ǫ)O(1)) -uniformly approximated by MKd.

Finally we state the following lemmas that bound the sum of squares of coefficients of a univariate polynomial:

Lemma 10. [Fact 3 [KS08]] Let p(t) = �di=0 βiti be a univariate polynomial of degree d such that |βi| ≤ M for all i ∈ [d]. For any r ∈ Z+ consider pr(t) =��di=0 βiti�r = �dri=0 ηiti then,

Proof. We have pr(t) = �i1,··· ,ir∈[d] βi1 · · · βirti1+···+ir . It follows that ��di=0 βiti�r= �dri=0 ηiti is bounded above by

B Omitted Proofs

B.1 Proof of Theorem 1

Let ∆ := 1m�mi=1(yi − u(⟨v, ψ(xi)⟩) + ξ(xi))ψ(xi) and ∆t := 1m�mi=1(yi − u(⟨vt, ψ(xi)⟩))ψ(xi). Aslo define ρ := 1m�mi=1 ξ(xi)2 . We will use the following lemma:

Lemma 11. At iteration t in Alphatron, suppose ||vt − v|| ≤ B for B > 1, then if ||∆|| ≤ η < 1, then

Proof. Expanding the left hand side of the equation above, we have

Here (4) follows from substituting the expression of vt+1 , (6) follows from bounding ||vt − v|| ≤ B and, (8) follows from u being monotone and L-Lipschitz, that is, (u(a) − u(b))(a − b) ≥ 1L(u(a) − u(b))2 . (9) follows from the definition of �ε(ht) , the second term follows from the fact that u is [0, 1] and 1m�mi=1�mi=1 |ξ(xi)| ≤�

assumption ||∆|| ≤ η.

Here (13) follows by expanding the square and (12) follows by applying Jensen’s inequality to show that for all a, b ∈ Rm and vectors vi for i ∈ {1, · · · , m},�� 1m�mi=1(ai − bi)vi��2 ≤ 1m�mi=1(ai − bi)2||vi||2 and subsequently using the fact that ||ψ(xi)|| ≤ 1 . Combining (9) and (12) gives us the result.

By definition we have that (yi − u(⟨v, ψ(xi)⟩ + ξ(xi)))ψ(xi) are zero mean iid random variables with norm bounded by 1. Using Hoeffding’s inequality (and the fact that that the xi’s are independent draws), with probability 1 − δ we have

Similarly, we can bound using Hoeffding’s inequality to get,

Now using the previous lemma with λ = 1/L and η = 1√m

Thus, for each iteration t of Alphatron, one of the following two cases needs to be satisfied,

Let be the first iteration where Case 2 holds. We need to show that such an iteration exists. Assume the contradictory, that is, Case 2 fails for each iteration. Since ||v0 − v||2 ≤ B2, however, in at most BLη iterations Case 1 will be violated and Case 2 will have to be true. If BLη ≤ T then exists such that

We need to bound ε(ht∗) in terms of �ε(ht∗). Define F = {x → u(⟨z, ψ(x)⟩) : ||z|| ≤ 2B}, and Z = {x → f(x) − u(⟨v, ψ(x)⟩ + ξ(x)) : f ∈ F} . Using Theorem 11 and 12 we have Rm(F) = O(BL�1/m) . By definition of Rademacher complexity, we have

Here, σi ∈ {±1} are iid Rademacher variables hence ∀ i, E[σi] = 0 and xi are drawn iid from D.Recall that ht∗(x) = u(⟨vT, ψ(x)⟩) is an element of F as ||vT − v||2 ≤ B2 (case 1 is satisfied in iteration t∗ − 1) and ||v|| ≤ B . A direct application of Theorem 10 on Z with loss function L(a, ·) = a2 , gives us, with probability 1 − δ,

The last step is to show that we can indeed find a hypothesis satisfying the above guarantee. Since for all h, ε(h) is up to constants equal to err(h) we can do so by choosing the hypothesis with the minimum err using a fresh sample set of size O(log(T/δ)/ǫ20) ≤ N . This holds as given the sample size, by Chernoff bound using the fact that �ε(ht) is bounded in [0, 1], each ht for t ≤ T will have empirical error within of the true error with probability 1 − δ/T and hence all will simultaneously satisfy this with probability 1 − δ. Setting ǫ0 = 1/√m will give us the required bound.

B.2 Proof of Theorem 4

We first extend the approximation guarantees to linear combinations of function classes using the following lemma.

Lemma 12. If for all i ∈ [k], fi is (ǫ, B) -uniformly approximated in kernel K then �ki=1 aifi(x) for a ∈ Rk such that ||a||1 ≤ W is (ǫW, WB) -uniformly approximated in kernel K.

Proof. We have for each i ∈ [k], ∀x ∈ X, |fi(x)−⟨vi, ψ(x)⟩| ≤ ǫ for some vi ∈ H such that ||vi|| ≤ B. Consider v = �ki=1 aivi. We have ∀x ∈ X,

Combining Lemmas 8 and 12 we have that for activation function σsig is (ǫ0√k, (√k/ǫ0)C)- uniformly approximated by some kernel MKd with d = O(log(1/ǫ0)) and sufficiently large constant C > 0. Thus by Theorem 3, we have that there exists an algorithm that outputs a hypothesis h such that, with probability 1 − δ,

for some constants C′ > 0. Setting ǫ0 = ǫ2√kC′L and m =�2kCLǫ �2C ·�4 log(1/δ)ǫ2 � gives us the required result (the claimed bounds on running time also follow directly from Theorem 3).

B.3 Proof of Theorem 6

Let ε(h) = Ex∈{−1,1}n[(u(P(x)) − u(h(x)))2] = ||u ◦ P − u ◦ h||22 . Similar to Alphatron, we will show that with each iteration t we will move closer to the true solution as long as ε(Pt) is large.

Proof. Let us define the following polynomials for t ≤ T, Q′t = Pt−1 + λ(u ◦ P − u ◦ Pt−1) and Qt =

From Lemma 1, L∞(KM(u◦P −u◦Pt−1, θ)−(u◦P −u◦Pt−1)) ≤ θ implying L∞(P ′t −Q′t) ≤ λθ ≤ θ since λ ≤ 1.

Using Lemma 4, we have ||projK(P ′t) − projK(Q′t)||2 ≤ 2√θk. Since Pt = KM(projK(P ′t), θ) and L1(projK(P ′t)) ≤ k , using Lemma 2, ||Pt − projK(P ′t)||2 ≤√2θk . Using Triangle inequality, we get,

Observe that ||Qt − P||2 = L2(Qt − P) ≤ L1(Qt − P) ≤ L1(Qt) + L1(P) ≤ 2k . Combining these two observations, we have

for large enough constant C > 0. Therefore,

Here, (13) follows from the triangle inequality and (B.3), (14) follows from projecting to a convex set reducing the distance to points in the convex set, (16) follows from u being monotone, L-Lipschitz with output bounded in [0, 1]. Setting θ such that Ck√θk ≤ λ2 gives the required result.

As long as ε(Pt) ≥ 2Lλ, we have ||Pt − P||22 − ||Pt+1 − P||22 ≥ 2λ2. Since ||P0 − P||22 = ||P||22 ≤ L1(P)2 ≤ k2, after T = k22λ2 , there must be some r ≤ T such that ||Pr − P||22 ≥ 2λ2 does not hold, at this iteration, ε(Pt) ≤ 2Lλ = ǫ for λ = ǫ2L . The last step of choosing the best would give us the required hypothesis (similar to Alphatron). Observe that each iteration of KMtron runs in time poly(n, k, L, 1/ǫ) (Lemma 1) and KMtron is run for poly(k, L, 1/ǫ) iterations giving us the required runtime.

B.4 Proof of Corollary 2

Let {Ti}si=1 be the ANDs corresponding to each term of the DNF. Let T = �si=1 Ti . By definition of f, if f(x) = 1 then T(x) ≥ 1 and if f(x) = 0 then T(x) = 0 . Observe that L1(T) ≤ �si=1 L1(Ti) ≤ s using the well known fact that AND has bounded by 1.

Consider the following u,

Observe that u is 1-Lipschitz. It is easy to see that f(x) = u(T(x)) on {−1, 1}n . Hence, given query access to f is the same as query access to u ◦ T over {−1, 1}n.

, KMtron outputs a polynomial P such that Ex∈{−1,1}n[(u(T(x)) − u(P(x)))2] ≤ ǫ. Recall that u ◦ P may be real-valued as KMtron learns with square loss. Let us define h(x) to equal 1 if u(P((x)) ≥ 1/2 and 0 otherwise. We will show that Ex[h(x) ̸= f(x)] ≤ O(ǫ). Using Markov’s inequality, we have Prx[(u(T(x)) − u(P(x)))2 ≥ 1/4] ≤ 4ǫ. For x, suppose

then clearly h(x) = f(x). Thus, Prx[h(x) ̸= f(x)] ≤ 4ǫ. Scaling ǫ appropriately, we obtain the required result.

B.5 Proof of Theorem 7

We use Lemma 7 to show the existence of polynomial p of degree d = O�1ρ · log�1ǫ0��such that for $a ∈ [−1, 1], |p(a)| < 1 + ǫ0 and for a ∈ [−1, 1]\[−ρ, ρ], |p(a) − sign(a)| < ǫ0.$

in [−1, 1] by 1 + ǫ0 . From Lemma 9 and 6, we have that for each i, p(wi · x) = ⟨vi, ψd(x)⟩ such that

d. Using Lemma 12, we have that �ti=1 aihi(x) is�ǫ0A, A�1ǫ0

MKd. Subsequently, applying Theorem 3, we get that there exists an algorithm that outputs a hypothesis h such that with probability

for some constants C, C′ > 0. Setting ǫ0 = ǫ2CLA and m =� 2CLAǫ �2C′/ρ ·�4 log(1/δ)ǫ2 � to gives us the required result.

B.6 Proof of Corollary 3

Observe that u is 1/t-Lipschitz. It is easy to see that fAND(x) = u(T(x) . Using Theorem 8 for L = 1 and A = 1, we know that there exists an algorithm that runs in time poly�n,� tǫ�(C/ρ) , log(1/δ)�

and outputs a hypothesis h such that Ex,y∼D��h(x) − u��ti=1 aihi(x)��2�≤ ǫ. Since h is a real-valued function, we can use sign(h) to get a 0-1 loss bound as in the proof of Corollary 2 to get the required result.

B.7 Proof of Theorem 8

Consider polynomial P(x) = �S:|S|≤d �f(S)χS(x). We have,

We also know that �f(S) ≤ M (since |f(x)| ≤ M) for all S ⊆ [n], thus |f(x) − P(x)| ≤ |f(x)| + |P(x)| = O(ndM) for all x ∈ {−1, 1}n . Also observe that

where the equality follows from Parseval’s Theorem. This implies that f is (ǫ,√M, ndM) -approximated by kernel K and RKHS H with feature map of all monomials of degree ≤ d . This kernel takes O(nd) time to compute. Now, we apply Theorem 2 after renormalizing the kernel to get the required result.

B.8 Proof of Lemma 5

Here the first inequality follows from Cauchy-Schwarz, the second follows from rearranging the sum and using the fact that {S : |S| > d} ⊆ {S : |S| > dj} and the third follows from the Fourier concentration of each fi.

B.9 Proof of Theorem 9

The following lemma is useful for our analysis.

Lemma 14. Let c be the instance labeling function mapping X to R such that c is (ǫ, B)-uniformly approximated by kernel K and feature vector . Then the function f : B → R given by f(β) =

Proof. We have that ∀x ∈ X, |c(x)−⟨v, ψ(x)⟩| ≤ ǫ for v such that ||v|| ≤ B. Let Kmean be the mean map kernel of K and ψmean be the corresponding vector. We will show that v (ǫ, B) -approximates f in Kmean . This follows from the following,

Consider c ∈ C that is (ǫ/CL, B) -uniformly approximated by some kernel K for large enough constant C > 0 (to be chosen later). Using Lemma 14 we know that f(β) = 1|β| · �x∈β c(x) is -uniformly approximated by the mean map kernel Kmean of K . Applying Theorem 3, we get that with probability 1 − δ,

for sufficiently large constant C′ > 0. Choosing C ≥ C′ gives the result.

Designed for Accessibility and to further Open Science