Learning Neural Networks with Two Nonlinear Layers in Polynomial Time

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?

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 $\Omega(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(\textbf{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:

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 $\mathsf{AC}^{0}$ circuits, and submodular functions, among others. We achieve the first non-i.i.d. noise-tolerant algorithmsPreviously these classes were known to be learnable in the presence of classification noise, where each is label is flipped independently with some fixed probability. for learning these classesNon-iid/agnostic noise tolerance was known for majorities of halfspaces only for $\epsilon<1/k^{2}$, where $k$ is the number of halfspace [KKMS08].. 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 $L_{1}$-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 $\textbf{x}_{1},\ldots,\textbf{x}_{t}$, and the learner is told only some function of their labels, namely $u(c(\textbf{x}_{1}),\ldots,c(\textbf{x}_{t}))$ 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.

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 $(\textbf{x},y)$ where the conditional mean of $y$ given x is equal to $u(\textbf{w}\cdot\textbf{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 regularizationWe emphasize this to distinguish our algorithm from the usual kernel methods (e.g., kernel ridge regression and SVMs) where regularization and the representer theorem are key steps., 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.

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 $n^{d}$ monomials). It is known, however, that any polynomial that computes or even $\epsilon$-approximates a single ReLU requires degree $\Omega(1/\epsilon)$ [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, ZSJ+17, 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 $\Omega(m)\cite[cite]{[\@@bibref{}{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.

4 Notation

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

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.

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 $\psi(\textbf{x})=\textbf{x}$ and $\xi$ as the zero function.

Alphatron runs in time $\mathsf{poly}(n,m,\log(1/\delta),t_{\mathcal{K}})$ where $t_{\mathcal{K}}$ is the time required to compute the kernel function $\mathcal{K}$.

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:

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

for some constants $C>0$. Also Alphatron requires at most $O(BL\sqrt{m/\log(1/\delta)})$ 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,

The proof is the same as the proof of Theorem 2 by re-examining the proof of Theorem 1 and noticing that $\xi(\textbf{x})$ is uniformly bounded by $\epsilon$ in each inequality. ∎

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:

The following theorem is our main result for learning classes of neural networks with two nonlinear layers in polynomial time:

for $m=\left(\frac{kL}{\epsilon}\right)^{O(1)}\cdot\log(1/\delta)$. The algorithm runs in time polynomial in $m$ and $n$.

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

for $m=2^{O(kL/\epsilon)}\cdot\log(1/\delta)$. The algorithm runs in time polynomial in $m$ and $n$.

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 $\textbf{x}_{\textbf{1}},\cdots,\textbf{x}_{\textbf{m}}$, the hypothesis output by our algorithm Alphatron is of the form $h(\textbf{x})=u(\sum_{i=1}^{m}\alpha_{i}^{*}\mathcal{MK}_{d}(\textbf{x},\textbf{x}_{\textbf{i}}))=u(\langle\textbf{v},\psi_{d}(\textbf{x})\rangle)$ where $\textbf{v}=\sum_{i=1}^{m}\alpha_{i}^{*}\psi_{d}(\textbf{x}_{\textbf{i}})$ and $d$ is dependent on required approximation. As seen in the preliminaries, $\langle\textbf{v},\psi_{d}(\textbf{x})\rangle$ 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 $({k_{1}},\ldots,{k_{j}})\in[n]^{j}$ for $j\in[d]$ to tuple $(i_{1},\ldots,i_{n})\in\{0,\ldots,d\}^{n}$ such that $x_{k_{1}}\cdots x_{k_{j}}=x_{1}^{i_{1}}\cdots x_{n}^{i_{n}}$ and $C$ maps ordered tuple $(i_{1},\ldots,i_{n})\in\{0,\ldots,d\}^{n}$ to the number of distinct orderings of the $i_{j}$’s for $j\in\{0,\ldots,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.

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.

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 $L_{1}$-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.

If $P$ has $L_{1}(P)\leq k$, then $\mathsf{KM}\left(P,\frac{\epsilon^{2}}{2k}\right)$ returns $Q$ s.t. $||P-Q||_{2}\leq\epsilon$.

Let $P,P^{\prime}$ be such that $L_{\infty}(P-P^{\prime})\leq\epsilon$. Then $L_{\infty}(\mathsf{proj}_{K}(P)-\mathsf{proj}_{K}(P^{\prime}))\leq 2\epsilon$.

Let $P,P^{\prime}$ be such that $L_{\infty}(P-P^{\prime})\leq\epsilon$. Then $||\mathsf{proj}_{K}(P)-\mathsf{proj}_{K}(P^{\prime})||_{2}\leq 2\sqrt{\epsilon k}$.

KMtron. The algorithm KMtron is as follows:

The following theorem proves the correctness of KMtron.

As an easy corollary, we also obtain a simple (no Boosting required) polynomial time query-algorithm for learning DNFs under the uniform distributionFeldman [Fel12] was the first to obtain a query-algorithm for PAC learning DNF formulas with respect to the uniform distribution that did not require a Boosting algorithm.:

Let $f$ be a DNF formula from $\{-1,1\}^{n}\rightarrow\{0,1\}$ with $s$ terms. Then $f$ is PAC learnable under the uniform distribution using membership queries in time $\mathsf{poly}(n,s,1/\epsilon)$.

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).

For a class of functions ${\cal C}$, let $u({\cal C})$ denote monotone function $u$ applied to a linear combination of (polynomially many) functions from ${\cal C}$.

For the domain of $\{-1,1\}^{n}$ and degree parameter $d$, our algorithm will incur a sample complexity and running time factor of $n^{d}$, 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({\cal C})$ for any smooth, monotone $u$ and class ${\cal 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.

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(\mathsf{AC^{0}}$), generalizing majorities of constant depth circuits [JKS02].

$u(\mathsf{LTF}$), generalizing majorities of linear threshold functions [KKMS08].

$u(\mathsf{SM})$, generalizing submodular functions [CKKL12].

As a further application, we can learn majorities of $k$ halfspaces with respect to the uniform distribution in time $n^{O(k^{2}/\epsilon^{2})}$ for any $\epsilon>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 $n^{O(k^{4}/\epsilon^{2})}$ [KKMS08]Recent work due to Kane [Kan14] does not apply to majorities of halfspaces, only intersections..

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

for $m=\left(\frac{LA}{\epsilon}\right)^{O(1/\rho)}\log(1/\delta)$. The algorithm runs in time polynomial in $m$ and $n$.

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 $\{h_{1},\ldots,h_{t}\}$. An intersection of these $t$-halfspaces is given by $f_{\mathsf{AND}}(\textbf{x})=\wedge_{i=1}^{t}h_{i}(\textbf{x})$.

This result improves the previous best bound due to Klivans and Servedio [KS08] that had (for constant $\rho$) 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/\sqrt{\rho})$ dependence), as opposed to Alphatron in conjunction with the multinomial kernel.

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.

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.

The concept class $\mathcal{C}$ is $(\epsilon,\delta)$-Probabilistic MIL for $u$ with sample complexity $M$ and running time $T$ if under the probabilistic MI assumption for $u$, there exists an algorithm ${\cal A}$ such that for all $c\in\mathcal{C}$ as the instance labeling function and any distribution $\mathcal{D}$ on ${\mathfrak{B}}$, ${\cal 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-\delta$,

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

The concept class $\mathcal{C}$ is $(\epsilon,\delta)$-Probabilistic MIL for monotone $L$-Lipschitz $u$ with sample complexity $(\frac{BL}{\epsilon})^{2}\cdot\log(1/\delta)$ and running time $\mathsf{poly}(n,B,L,1/\epsilon,\log(1/\delta))$ if all $c\in\mathcal{C}$ are $(\epsilon/CL,B)$-uniformly approximated by some kernel $\mathcal{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.

References

Appendix A Background

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.

We say that a concept class $\mathcal{C}\subseteq\{0,1\}^{\mathcal{X}}$ is Probably Approximately Correct (PAC) learnable, if there exists an algorithm $\mathcal{A}$ such that for every $c\in\mathcal{C}$,$\delta,\epsilon>0$ and $\mathcal{D}$ over $\mathcal{X}$, if $\mathcal{A}$ is given access to examples drawn from $\mathcal{D}$ and labeled according to $c$, $\mathcal{A}$ outputs a hypothesis $h:\mathcal{X}\rightarrow\{0,1\}$, such that with probability at least $1-\delta$,

Furthermore, we say that $\mathcal{C}$ is efficiently PAC learnable to error $\epsilon$ if $\mathcal{A}$ can output an $h$ satisfying the above with running time and sample complexity polynomial in $n$, $1/\epsilon$, and $1/\delta$.

Furthermore, we say that $\mathcal{C}$ is efficiently p-concept learnable to error $\epsilon$ if $\mathcal{A}$ can output an $h$ satisfying the above with running time and sample complexity polynomial in $n$, $1/\epsilon$, and $1/\delta$.

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].

where $\mathcal{R}_{\textbf{m}}(\mathcal{F})$ is the Rademacher complexity of the function class $\mathcal{F}$.

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

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

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 $\mathcal{K}(\textbf{x},\textbf{x}^{\prime})=\langle\psi(\textbf{x}),\psi(\textbf{x}^{\prime})\rangle$ where $\psi$ is the associated feature map and $\mathcal{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]:

Also define $\mathcal{H}_{{\mathcal{MK}_{d}}}$ to be the corresponding RKHS.

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 $\textbf{v}\in\mathcal{H}_{{\mathcal{MK}_{d}}}$. Also, every $\textbf{v}\in\mathcal{H}_{{\mathcal{MK}_{d}}}$ can be interpreted as a multivariate polynomial of degree $d$ such that

where coefficient $\beta(i_{1},\dots,i_{n})$ is as follows,

Here, $\textbf{v}(\cdot)$ 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]:

Let $p(t)=\sum_{i=0}^{d}\beta_{i}t^{i}$ be a given univariate polynomial with $\sum_{i=1}^{d}\beta_{i}^{2}\leq B^{2}$. For w such that $||\textbf{w}||\leq 1$, the polynomial $p(\textbf{w}\cdot\textbf{x})$ equals $\langle p_{\textbf{w}},\psi(\textbf{x})\rangle$ for some $p_{\textbf{w}}\in\mathcal{H}_{{MK_{d}}}$ with $||p_{\textbf{w}}||\leq B$.

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

Let $\mathcal{X}^{*}$ denote the Kleene closure of $\mathcal{X}$.

The feature map $\psi_{\mathsf{mean}}\colon\mathcal{X}^{*}\rightarrow\mathcal{Z}$ corresponding to this kernel is given by

Also define $\mathcal{H}_{\mathsf{mean}}$ to be the corresponding RKHS.

Fact. If $\forall\textbf{x},\textbf{x}^{\prime}\in\mathcal{X},\mathcal{K}(\textbf{x},\textbf{x}^{\prime})\leq M$ then $\forall S,S^{\prime}\in\mathcal{X}^{*},\mathcal{K}_{\mathsf{mean}}(S,S^{\prime})\leq M$.

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 $\mathsf{sign}$ function was given by [Dan15]:

Let $a,\gamma,\tau>0$. There exists a polynomial $p$ of degree $O\left(\frac{1}{\gamma}\cdot\log\left(\frac{1}{\tau}\right)\right)$ such that

For ${x}\in[−a,a]\backslash[−\gamma\cdot a,\gamma\cdot a]$, $|p({x})−\mathsf{sign}({x})|<\tau$.

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

[GKKT16] showed that activation functions sigmoid: $\sigma_{sig}(a)=\frac{1}{1+e^{-a}}$ and ReLU: $\sigma_{relu}(a)=\max(0,a)$ can be $(\epsilon,B)$-uniformly approximated by the multinomial kernel for $B$ dependent on $\epsilon$, more formally they showed the following:

Further, $||\textbf{v}||\leq(1/\epsilon)^{O(1)}$. This implies that $\sigma_{sig}$ is $(\epsilon,(1/\epsilon)^{O(1)})$-uniformly approximated by $\mathcal{MK}_{d}$.

Further, $||\textbf{v}||\leq 2^{O(1/\epsilon)}$. This implies that $\sigma_{relu}$ is $(\epsilon,2^{O(1/\epsilon)})$-uniformly approximated by $\mathcal{MK}_{d}$.

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

Let $p(t)=\sum_{i=0}^{d}\beta_{i}t^{i}$ be a univariate polynomial of degree $d$. Let $M$ be such that $\displaystyle\max_{t\in}|p(t)|\leq M$. Then $\displaystyle\sum_{i=0}^{d}\beta_{i}^{2}\leq(d+1)\cdot(4e)^{2d}\cdot M^{2}$.

We have $p^{r}(t)=\sum_{i_{1},\cdots,i_{r}\in[d]}\beta_{i_{1}}\cdots\beta_{i_{r}}t^{i_{1}+\cdots+i_{r}}$. It follows that $\left(\sum_{i=0}^{d}\beta_{i}t^{i}\right)^{r}=\sum_{i=0}^{dr}\eta_{i}t^{i}$ is bounded above by

Appendix B Omitted Proofs

Let $\Delta:=\frac{1}{m}\sum_{i=1}^{m}(y_{i}-u(\langle\textbf{v},\psi(\textbf{x}_{\textbf{i}})\rangle)+\xi(\textbf{x}_{\textbf{i}}))\psi(\textbf{x}_{\textbf{i}})$ and $\Delta^{t}:=\frac{1}{m}\sum_{i=1}^{m}(y_{i}-u(\langle\textbf{v}^{\textbf{t}},\psi(\textbf{x}_{\textbf{i}})\rangle))\psi(\textbf{x}_{\textbf{i}})$. Aslo define $\rho:=\frac{1}{m}\sum_{i=1}^{m}\xi(\textbf{x}_{\textbf{i}})^{2}$. We will use the following lemma:

At iteration $t$ in Alphatron, suppose $||\textbf{v}^{\textbf{t}}-\textbf{v}||\leq B$ for $B>1$, then if $||\Delta||\leq\eta<1$, then

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

Here (4) follows from substituting the expression of $\textbf{v}^{\textbf{t+1}}$, (6) follows from bounding $||\textbf{v}^{\textbf{t}}-\textbf{v}||\leq B$ and, (8) follows from $u$ being monotone and $L$-Lipschitz, that is, $(u(a)-u(b))(a-b)\geq\frac{1}{L}(u(a)-u(b))^{2}$. (9) follows from the definition of $\widehat{\varepsilon}(h^{t})$, the second term follows from the fact that $u$ is $$and$\frac{1}{m}\sum_{i=1}^{m}\sum_{i=1}^{m}|\xi(\textbf{x}_{\textbf{i}})|\leq\sqrt{\frac{1}{m}\sum_{i=1}^{m}\sum_{i=1}^{m}\xi(\textbf{x}_{\textbf{i}})^{2}}=\sqrt{\rho}$and the third term is bounded using the assumption$||\Delta||\leq\eta$.

We now bound $||\Delta^{t}||$ as follows.

By definition we have that $(y_{i}-u(\langle\textbf{v},\psi(\textbf{x}_{\textbf{i}})\rangle+\xi(\textbf{x}_{\textbf{i}})))\psi(\textbf{x}_{\textbf{i}})$ are zero mean iid random variables with norm bounded by $1$. Using Hoeffding’s inequality (and the fact that that the $\textbf{x}_{\textbf{i}}$’s are independent draws), with probability $1-\delta$ we have

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

Now using the previous lemma with $\lambda=1/L$ and $\eta=\frac{1}{\sqrt{m}}\left(1+\sqrt{2\log(1/\delta)}\right)$, we have

Thus, for each iteration $t$ of Alphatron, one of the following two cases needs to be satisfied, Case 1: $||\textbf{v}^{\textbf{t}}-\textbf{v}||^{2}-||\textbf{v}^{\textbf{t+1}}-\textbf{v}||^{2}\geq\frac{B\eta}{L}$ Case 2: $\widehat{\varepsilon}(h^{t})\leq 3BL\eta+2L\sqrt{\rho}+\eta^{2}+2\eta=O\left(L\epsilon+LM\sqrt{\frac{\log(1/\delta)}{m}}+BL\sqrt{\frac{\log(1/\delta)}{m}}\right)$.

Let $t^{*}$ 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 $||\textbf{v}^{\textbf{0}}-\textbf{v}||^{2}\leq B^{2}$, however, in at most $\frac{BL}{\eta}$ iterations Case 1 will be violated and Case 2 will have to be true. If $\frac{BL}{\eta}\leq T$ then $t^{*}$ exists such that

We need to bound $\varepsilon(h^{t^{*}})$ in terms of $\widehat{\varepsilon}(h^{t^{*}})$. Define $\mathcal{F}=\{\textbf{x}\rightarrow u(\langle\textbf{z},\psi(\textbf{x})\rangle):||\textbf{z}||\leq 2B\}$, and $\mathcal{Z}=\{\textbf{x}\rightarrow f(\textbf{x})-u(\langle\textbf{v},\psi(\textbf{x})\rangle+\xi(\textbf{x})):f\in\mathcal{F}\}$. Using Theorem 11 and 12 we have $\mathcal{R}_{m}(\mathcal{F})=O(BL\sqrt{1/m})$. By definition of Rademacher complexity, we have

Here, $\sigma_{i}\in\{\pm 1\}$ are iid Rademacher variables hence $\forall\ i,E[\sigma_{i}]=0$ and $\textbf{x}_{\textbf{i}}$ are drawn iid from $\mathcal{D}$.

Recall that $h^{t^{*}}(\textbf{x})=u(\langle\textbf{v}^{\textbf{T}},\psi(\textbf{x})\rangle)$ is an element of $\mathcal{F}$ as $||\textbf{v}^{\textbf{T}}-\textbf{v}||^{2}\leq B^{2}$ (case 1 is satisfied in iteration $t^{*}-1$) and $||\textbf{v}||\leq B$. A direct application of Theorem 10 on $\mathcal{Z}$ with loss function $\mathcal{L}(a,\cdot)=a^{2}$, gives us, with probability $1-\delta$,

The last step is to show that we can indeed find a hypothesis satisfying the above guarantee. Since for all $h$, $\varepsilon(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/\delta)/\epsilon_{0}^{2})\leq N$. This holds as given the sample size, by Chernoff bound using the fact that $\widehat{\varepsilon}(h^{t})$ is bounded in $$, each$h^{t}$for$t\leq T$will have empirical error within$\epsilon_{0}$of the true error with probability$1-\delta/T$and hence all will simultaneously satisfy this with probability$1-\delta$. Setting$\epsilon_{0}=1/\sqrt{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.

We have for each $i\in[k]$, $\forall\textbf{x}\in\mathcal{X},|f_{i}(\textbf{x})-\langle\textbf{v}_{\textbf{i}},\psi(\textbf{x})\rangle|\leq\epsilon$ for some $\textbf{v}_{\textbf{i}}\in\mathcal{H}$ such that $||\textbf{v}_{\textbf{i}}||\leq B$. Consider $\textbf{v}=\sum_{i=1}^{k}\textbf{a}_{i}\textbf{v}_{\textbf{i}}$. We have $\forall\textbf{x}\in\mathcal{X}$,

Also $||\textbf{v}||=\left|\left|\sum_{i=1}^{k}\textbf{a}_{i}\textbf{v}_{\textbf{i}}\right|\right|\leq\sum_{i=1}^{k}|\textbf{a}_{i}|||\textbf{v}_{\textbf{i}}||\leq WB$. Thus v satisfies the required approximation. ∎

Combining Lemmas 8 and 12 we have that $\mathcal{N}_{1}$ for activation function $\sigma_{sig}$ is $(\epsilon_{0}\sqrt{k},(\sqrt{k}/\epsilon_{0})^{C})$-uniformly approximated by some kernel $\mathcal{MK}_{d}$ with $d=O(\log(1/\epsilon_{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-\delta$,

for some constants $C^{\prime}>0$. Setting $\epsilon_{0}=\frac{\epsilon}{2\sqrt{k}C^{\prime}L}$ and $m=\left(\frac{2kCL}{\epsilon}\right)^{2C}\cdot\left(\frac{4\log(1/\delta)}{\epsilon^{2}}\right)$ gives us the required result (the claimed bounds on running time also follow directly from Theorem 3).

B.3 Proof of Theorem 6

For a suitable choice of $\theta$, $||P_{t}-P||_{2}^{2}-||P_{t+1}-P||_{2}^{2}\geq\frac{2\lambda}{L}(\varepsilon(P_{t})-L\lambda)$.

Let us define the following polynomials for $t\leq T$, $Q_{t}^{\prime}=P_{t-1}+\lambda(u\circ P-u\circ P_{t-1})\text{ and }Q_{t}=\mathsf{proj}_{K}(Q_{t}^{\prime})$. For all $t\leq T$,

From Lemma 1, $L_{\infty}(\mathsf{KM}(u\circ P-u\circ P_{t-1},\theta)-(u\circ P-u\circ P_{t-1}))\leq\theta$ implying $L_{\infty}(P_{t}^{\prime}-Q_{t}^{\prime})\leq\lambda\theta\leq\theta$ since $\lambda\leq 1$.

Using Lemma 4, we have $||\mathsf{proj}_{K}(P_{t}^{\prime})-\mathsf{proj}_{K}(Q_{t}^{\prime})||_{2}\leq 2\sqrt{\theta k}$. Since $P_{t}=\mathsf{KM}(\mathsf{proj}_{K}(P_{t}^{\prime}),\theta)$ and $L_{1}(\mathsf{proj}_{K}(P_{t}^{\prime}))\leq k$, using Lemma 2, $||P_{t}-\mathsf{proj}_{K}(P_{t}^{\prime})||_{2}\leq\sqrt{2\theta k}$. Using Triangle inequality, we get,

Observe that $||Q_{t}-P||_{2}=L_{2}(Q_{t}-P)\leq L_{1}(Q_{t}-P)\leq L_{1}(Q_{t})+L_{1}(P)\leq 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 $$. Setting$\theta$such that$Ck\sqrt{\theta k}\leq\lambda^{2}$ gives the required result. ∎

As long as $\varepsilon(P_{t})\geq 2L\lambda$, we have $||P_{t}-P||_{2}^{2}-||P_{t+1}-P||_{2}^{2}\geq 2\lambda^{2}$. Since $||P_{0}-P||_{2}^{2}=||P||_{2}^{2}\leq L_{1}(P)^{2}\leq k^{2}$, after $T=\frac{k^{2}}{2\lambda^{2}}$, there must be some $r\leq T$ such that $||P_{r}-P||_{2}^{2}\geq 2\lambda^{2}$ does not hold, at this iteration, $\varepsilon(P_{t})\leq 2L\lambda=\epsilon$ for $\lambda=\frac{\epsilon}{2L}$. The last step of choosing the best $P_{t}$ would give us the required hypothesis (similar to Alphatron). Observe that each iteration of KMtron runs in time $\mathsf{poly}(n,k,L,1/\epsilon)$ (Lemma 1) and KMtron is run for $\mathsf{poly}(k,L,1/\epsilon)$ iterations giving us the required runtime.

B.4 Proof of Corollary 2

Let $\{T_{i}\}_{i=1}^{s}$ be the ANDs corresponding to each term of the DNF. Let $T=\sum_{i=1}^{s}T_{i}$. By definition of $f$, if $f(x)=1$ then $T(x)\geq 1$ and if $f(x)=0$ then $T(x)=0$. Observe that $L_{1}(T)\leq\sum_{i=1}^{s}L_{1}(T_{i})\leq s$ using the well known fact that AND has $L_{1}$ bounded by $1$.

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\circ T$ over $\{-1,1\}^{n}$.

B.5 Proof of Theorem 7

We use Lemma 7 to show the existence of polynomial $p$ of degree $d=O\left(\frac{1}{\rho}\cdot\log\left(\frac{1}{\epsilon_{0}}\right)\right)$ such that for $a\in[−1,1]$, $|p(a)|<1+\epsilon_{0}$ and for $a\in[−1,1]\backslash[-\rho,\rho]$, $|p(a)−\mathsf{sign}(a)|<\epsilon_{0}$.

Since for each $i$, $\rho\leq|\textbf{w}_{\textbf{i}}\cdot\textbf{x}|\leq 1$, we have $|p(\textbf{w}_{\textbf{i}}\cdot\textbf{x})−\mathsf{sign}(\textbf{w}_{\textbf{i}}\cdot\textbf{x})|\leq\epsilon_{0}$ such that $p$ is bounded in $$by$1+\epsilon_{0}$. From Lemma 9 and 6, we have that for each$i$,$p(\textbf{w}_{\textbf{i}}\cdot\textbf{x})=\langle\textbf{v}_{\textbf{i}},\psi_{d}(\textbf{x})\rangle$such that$||\textbf{v}_{\textbf{i}}||=\left(\frac{1}{\epsilon_{0}}\right)^{O(1/\rho)}$where$\psi_{d}$is the feature vector corresponding to the multinomial kernel of degree$d$. Using Lemma 12, we have that$\sum_{i=1}^{t}\textbf{a}_{i}h_{i}(\textbf{x})$is$\left(\epsilon_{0}A,A\left(\frac{1}{\epsilon_{0}}\right)^{O(1/\rho)}\right)$-uniformly approximated by$\mathcal{MK}_{d}$.

Subsequently, applying Theorem 3, we get that there exists an algorithm that outputs a hypothesis $h$ such that with probability $1-\delta$,

for some constants $C,C^{\prime}>0$. Setting $\epsilon_{0}=\frac{\epsilon}{2CLA}$ and $m=\left(\frac{2CLA}{\epsilon}\right)^{2C^{\prime}/\rho}\cdot\left(\frac{4\log(1/\delta)}{\epsilon^{2}}\right)$ to gives us the required result.

B.6 Proof of Corollary 3

Let $T(\textbf{x})=\frac{1}{t}\sum_{i=1}^{t}\textbf{a}_{i}h_{i}(\textbf{x})$. Consider the following $u$,

B.7 Proof of Theorem 8

Consider polynomial $P(\textbf{x})=\sum_{S:|S|\leq d}\widehat{f}(S)\chi_{S}(\textbf{x})$. We have,

We also know that $\widehat{f}(S)\leq M$ (since $|f(\textbf{x})|\leq M$) for all $S\subseteq[n]$, thus $|f(\textbf{x})-P(\textbf{x})|\leq|f(\textbf{x})|+|P(\textbf{x})|=O(n^{d}M)$ for all $\textbf{x}\in\{-1,1\}^{n}$. Also observe that

where the equality follows from Parseval’s Theorem. This implies that $f$ is $(\epsilon,\sqrt{M},n^{d}M)$-approximated by kernel $\mathcal{K}$ and RKHS $\mathcal{H}$ with feature map $\psi$ of all monomials of degree $\leq d$. This kernel takes $O(n^{d})$ time to compute. Now, we apply Theorem 2 after renormalizing the kernel to get the required result.

B.8 Proof of Lemma 5

For all $S\subseteq[n]$, we have $\widehat{f}(S)=\sum_{i=1}^{k}a_{i}\widehat{f}_{i}(S)$. Let $\epsilon$ and $d$ be as in the lemma, we have,

Here the first inequality follows from Cauchy-Schwarz, the second follows from rearranging the sum and using the fact that $\{S:|S|>d\}\subseteq\{S:|S|>d_{j}\}$ and the third follows from the Fourier concentration of each $f_{i}$.

B.9 Proof of Theorem 9

The following lemma is useful for our analysis.

We have that $\forall\textbf{x}\in\mathcal{X},|c(\textbf{x})-\langle v,\psi(\textbf{x})\rangle|\leq\epsilon$ for $v$ such that $||\textbf{v}||\leq B$. Let $\mathcal{K}_{\textsf{mean}}$ be the mean map kernel of $\mathcal{K}$ and $\psi_{\textsf{mean}}$ be the corresponding vector. We will show that v $(\epsilon,B)$-approximates $f$ in $\mathcal{K}_{\textsf{mean}}$. This follows from the following,

Consider $c\in\mathcal{C}$ that is $(\epsilon/CL,B)$-uniformly approximated by some kernel $\mathcal{K}$ for large enough constant $C>0$ (to be chosen later). Using Lemma 14 we know that $f(\beta)=\frac{1}{|\beta|}\cdot\sum_{\textbf{x}\in\beta}c(\textbf{x})$ is $(\epsilon/CL,B)$-uniformly approximated by the mean map kernel $\mathcal{K}_{\textsf{mean}}$ of $\mathcal{K}$. Applying Theorem 3, we get that with probability $1-\delta$,

for sufficiently large constant $C^{\prime}>0$. Choosing $C\geq C^{\prime}$ gives the result.