PaperlayerView exact revision on arXiv

Source-linked AI summary

Reliably Learning the ReLU in Polynomial Time

Surbhi Goel, Varun Kanade, Adam Klivans, Justin Thaler

arXiv:1611.10258v1cs.LGcs.CCstat.ML

TL;DR

Learning even a single ReLU has poorly understood computational complexity. This paper develops reliable agnostic algorithms using polynomial approximations, kernel methods, and a dual-loss approach. The resulting algorithms learn over arbitrary sphere distributions for ε as small as Ω(1/log n), with runtime polynomial in dimension for each such ε.

  • Problem

    Efficient learning of even a single ReLU has been little understood, despite the importance of ReLUs as deep-network building blocks.

    Source: §1 · p. 2

  • Method

    The algorithm combines low-weight polynomial approximations and kernel methods with a dual-loss approach and clipping to learn reliably.

    Source: Optimization Problem 1 · p. 5

  • Results

    ReLUs are reliably learnable in time 2^O(1/ε)·n^O(1), including ε as small as Ω(1/log n) over any distribution on the unit sphere.

    Source: §1 · p. 2, §1.2 · p. 3

  • Takeaways & Limitations

    The work establishes nontrivial learning of ReLUs under adversarial noise for all distributions on the unit sphere, unlike the stated threshold-learning contrast.

    Source: §6 · p. 29

    The authors leave improving the 2^O(1/ε) dependence open and state that they have no reason to believe it is optimal.

    Source: §1.2 · p. 3, §6 · p. 30

Abstract

from arXiv · show

We give the first dimension-efficient algorithms for learning Rectified Linear Units (ReLUs), which are functions of the form $\mathbf{x} \mapsto \max(0, \mathbf{w} \cdot \mathbf{x})$ with $\mathbf{w} \in \mathbb{S}^{n-1}$. Our algorithm works in the challenging Reliable Agnostic learning model of Kalai, Kanade, and Mansour (2009) where the learner is given access to a distribution $\cal{D}$ on labeled examples but the labeling may be arbitrary. We construct a hypothesis that simultaneously minimizes the false-positive rate and the loss on inputs given positive labels by $\cal{D}$, for any convex, bounded, and Lipschitz loss function. The algorithm runs in polynomial-time (in $n$) with respect to any distribution on $\mathbb{S}^{n-1}$ (the unit sphere in $n$ dimensions) and for any error parameter $\epsilon = \Omega(1/\log n)$ (this yields a PTAS for a question raised by F. Bach on the complexity of maximizing ReLUs). These results are in contrast to known efficient algorithms for reliably learning linear threshold functions, where $\epsilon$ must be $\Omega(1)$ and strong assumptions are required on the marginal distribution. We can compose our results to obtain the first set of efficient algorithms for learning constant-depth networks of ReLUs. Our techniques combine kernel methods and polynomial approximations with a "dual-loss" approach to convex programming. As a byproduct we obtain a number of applications including the first set of efficient algorithms for "convex piecewise-linear fitting" and the first efficient algorithms for noisy polynomial reconstruction of low-weight polynomials on the unit sphere.

1 Introduction

The paper develops efficient algorithms for learning ReLUs under arbitrary labelings and distributions on the unit sphere, with a reliable objective that balances false positives against loss on positively labeled examples. It also applies these results to ReLU networks, polynomial reconstruction, and piecewise-linear fitting.

1 Introduction

  • The introduction presents ReLU learning as a gap between familiar linear regression and threshold learning, since a ReLU combines linear behavior with one-sided thresholding.The paper notes that this hybrid structure makes it nontrivial to choose a loss capturing both aspects.Source: §1 · p. 2

1.1 Reliably Learning Real-Valued Functions

  • Reliable learning requires false-positive rate at most ε while keeping positive-label loss within ε of the best zero-false-positive class member.The loss functions considered are convex, monotone, bounded, and Lipschitz.Source: §1.1 · pp. 2–3, §1.2 · p. 3

1.2 Our Contributions

  • ReLUs are reliably learnable in time 2^O(1/ε)·n^O(1) for the stated class of loss functions.The paper also obtains the same complexity bounds for standard agnostic learning, yielding a PTAS for a ReLU optimization problem posed by Bach [3].Source: §1.2 · p. 3
  • The results extend to efficient learning algorithms for small-depth ReLU networks and noisy low-weight polynomial reconstruction under unknown sphere distributions.The polynomial class has bounded degree and coefficient-square sum, with runtime polynomial in n, d, B, and 1/ε.Source: §1.2 · p. 4

1.3 Applications to Convex Piecewise Regression

  • For constant k, the work gives the first polynomial-time algorithms for max-k-affine and sum-of-max-2-affine regression, problems previously addressed with heuristics.The fitting algorithm runs in time 2^O((k/ε)log k)·n^O(1).Source: §1.3 · p. 4

1.4 Hardness

  • The paper also proves hardness results for reliably learning ReLUs over {0, 1}^n by reducing from learning sparse parities with noise.The authors use this contrast to motivate focusing on sphere distributions and learning problems that are not scale invariant.Source: §1.4 · p. 5

1.5 Techniques and Related Work

  • The main single-ReLU strategy relaxes learning to low-weight, low-degree polynomial approximations, then uses kernel methods and a dual-loss approach to obtain reliability.Clipping supports the generalization bounds, and the final hypothesis is max(0, h) for a clipped, kernelized polynomial.Source: Optimization Problem 1 · p. 5

Optimization Problem 1

  • For networks, the authors generalize a composition technique for smooth activations and use ReLU gadgets to derive efficient algorithms for piecewise-linear regression problems.The composition approach builds on prior work by Zhang et al..Source: Optimization Problem 1 · p. 6

2 Preliminaries

The preliminaries set the unit-sphere setting and define the ReLU and polynomial classes, learning objectives, and tools used in the paper. They also establish polynomial approximation and generalization results needed for the later algorithms.

2.1 Notation

  • The input is usually the unit sphere in R^n, and an ε-approximation uniformly differs from its target function by at most ε on that sphere.The paper uses Y = [0, 1] or [−1, 1] for outputs.Source: §2.1 · p. 6

2.2 Concept Classes

  • A ReLU applies max(0, w · x); the paper studies bounded-weight ReLUs, networks, and polynomials with bounded squared coefficient sums.The reliable-learning results focus on ReLU(n, 1).Source: §2.2 · p. 6

2.3 Learning Models

  • Reliable agnostic learning controls zero-label false positives while matching the best zero-false-positive concept's positive-label loss within ε.Both losses are measured over the full distribution, not conditioned on label subsets.Source: §2.3 · p. 7

2.3.1 Loss Functions

  • The results use convex, bounded, Lipschitz losses that are monotone; monotonicity is not essential, but non-monotone losses may worsen sample-complexity bounds.For outputs and labels in [0, 1], ℓp losses for p ≥ 1 meet these conditions.Source: §2.3.1 · p. 8

2.4 Kernel Methods

  • The multinomial kernel represents degree-at-most-d polynomials using monomial features, with polynomial representations p(w · x) having squared RKHS norm at most B when their coefficient squares sum to at most B.The authors note their kernel gives a norm bound a factor of 2^d better than the cited prior kernel for these polynomials.Source: §2.4 · pp. 8–9

2.5 Generalization Bounds

  • A bounded Lipschitz loss generalizes through Rademacher complexity, with composition bounds relating the complexity of ψ ◦ F to that of F.The cited composition bound is R_m(ψ ◦ F) ≤ 2 · Lψ · R_m(F).Source: §2.5 · pp. 9–10

2.6 Approximation Theory

  • On [−1, 1], the rectifier has a range-preserving polynomial approximation of degree O(1/ε); for weights of norm at most W, the paper obtains degree O(W/ε) and squared RKHS norm at most W^2 · 2^O(W/ε).The weighted approximation is uniform on the unit sphere and takes values in [0, W].Source: §2.6 · pp. 10–11

3 Reliably Learning the ReLU

This section addresses reliable learning of a single ReLU with weight-vector norm at most 1. Its goal is to prove Theorem 1.3 by describing an algorithm and then proving the theorem.

3 Reliably Learning the ReLU

  • The section focuses on reliably learning the class ReLU(n, 1), whose weight vectors have norm bounded by 1.Source: §3 · p. 11
  • The section's stated objective is to prove Theorem 1.3.Source: §3 · p. 11
  • The authors first describe the algorithm and then give a full proof of Theorem 1.3.Source: §3 · p. 11

3.1 Overview of the Algorithm and Its Analysis

The algorithm replaces direct ReLU optimization with convex optimization over bounded-norm polynomials represented in an RKHS. A representer-theorem reduction makes the resulting program solvable in time polynomial in the sample count.

3.1 Overview of the Algorithm and Its Analysis

  • The nonconvex ReLU optimization is relaxed to polynomial optimization in the RKHS, using degree O(1/ε) approximations with squared norm bounded by 2^O(1/ε).Source: §3.1 · p. 11

Optimization Problem 2

  • The polynomial relaxation preserves the zero-label output constraint and achieves training loss within |{i | yi > 0}| · L · ε of the optimal ReLU program.Source: Optimization Problem 2 · pp. 11–12

Optimization Problem 3

  • The representer theorem reduces optimization to sample-weight coefficients; the Gram-matrix norm constraint and convex loss yield a convex program solvable in time polynomial in m.The reduction retains the constraints on outputs for zero-labeled examples.Source: Optimization Problem 2 · p. 12, Optimization Problem 3 · p. 12

3.2 Description of the Output Hypothesis

The output hypothesis is clipped to control its range and obtain useful generalization bounds. Clipping requires monotone loss, while an unclipped output can accommodate non-monotone losses with bounds depending on loss parameters over a larger interval.

3.2 Description of the Output Hypothesis

  • Direct bounds for an un-clipped RKHS hypothesis can be weak because its values may lie in [−B, B], where some losses have exponentially large Lipschitz constants.For the example loss, the resulting sample-complexity bound is doubly exponential in 1/ε.Source: §3.2 · pp. 12–13
  • Clipping the hypothesis to [0, 1] addresses the large-range generalization-bound problem.The output is clipped using clipa,b.Source: §3.2 · p. 13
  • Clipping requires monotone loss, whereas non-monotone losses can be handled with an unclipped output and bounds polynomial in loss parameters over [−B, B].Source: §3.2 · p. 13

3.3 Formal Version of Theorem 1.3 and Its Proof

The formal theorem guarantees reliable learning of ReLUs with small false-positive loss and positive-label loss near the best zero-false-positive ReLU. Its runtime and sample complexity depend exponentially on the loss’s Lipschitz constant divided by the target accuracy.

3.3 Formal Version of Theorem 1.3 and Its Proof

  • The output h has false-positive loss O(ε) and positive-label loss at most min over c in C+(D) of L>0(c; D) + O(ε).Here C+(D) contains ReLUs with zero false-positive loss under D.Source: §3.3 · p. 13
  • Theorem 3.2 gives reliable learning for convex, monotone, L-Lipschitz, b-bounded losses in time and sample complexity polynomial in n, b, log(1/δ), and 2^O(L/ε).In particular, accuracy ε ≥ Θ(L/log(n)) gives polynomial dependence on n, b, and log(1/δ).Source: §3.3 · p. 13
  • The proof bounds false positives using a surrogate loss that is zero on positive labels and penalizes zero-labeled examples when the fitted function exceeds ε, reaching loss 1 above 2ε.When h(x)>0, the proof uses f(x)>2ε to conclude that a zero-labeled example incurs surrogate loss 1.Source: §3.3 · pp. 13–14
  • The representative-sample conditions hold with probability at least 1−2δ for the stated sample bound, and the algorithm allows failure probability 2δ.The proof invokes these conditions to transfer sample-based loss bounds to D.Source: §3.3 · p. 14
  • For positive labels, the proof compares a polynomial ε-approximation to each zero-false-positive ReLU and uses monotonicity, clipping, and Lipschitz continuity to transfer its loss bound.The approximating polynomial is feasible for the optimization problem, and its uniform error controls the loss difference.Source: §3.3 · pp. 14–15

Discussion: Dependence on the Lipschitz Constant

  • The dependence on L comes from requiring an O(ε/L)-uniform ReLU approximation, with degree O(L/ε) and squared coefficient sum 2^O(L/ε).The excess-error bound in the proof is O(Lε).Source: Discussion: Dependence on the… · p. 15
  • In agnostic learning, the exponential dependence on L can sometimes be avoided because the proof need not threshold outputs at 2ε; clipping alone suffices.The threshold contributes 2εL to the excess-error bound in the reliable-learning analysis.Source: Discussion: Dependence on the… · p. 15

3.4 An Implication for Learning Convex Neural Networks

The paper turns a ReLU maximization problem into an improper-learning task and obtains a polynomial-time approximation scheme. Its optimization variant omits reliability thresholding and clipping.

3.4 An Implication for Learning Convex Neural Networks

  • Bach’s Incremental Optimization Problem [3] uses yi·relu_w(xi) on a finite dataset; this paper restricts labels to yi ∈ [−1, 1], whereas Bach considers yi ∈ R.Source: §3.4 · p. 15

Optimization Problem 4

  • Because this optimization variant requires no reliability, it skips thresholding; its non-monotone loss also means clipping is not justified by the proof’s monotonicity argument.The analysis therefore outputs an unclipped hypothesis.Source: Optimization Problem 4 · p. 16
  • The algorithm approximates the best ReLU’s expected negative product loss within ε in time 2^O(1/ε)·n^O(1).The guarantee applies to i.i.d. examples from an unknown distribution over Sn−1×[−1,1], and the output need not itself be a ReLU.Source: Optimization Problem 4 · p. 16, §3.4 · p. 16

3.5 Noisy Polynomial Reconstruction over Sn−1

The paper gives an algorithm for noisy polynomial reconstruction over the unit sphere, equivalently agnostic learning of multivariate polynomials. It uses a kernel representation to optimize over bounded-weight polynomials in time polynomial in the weight bound and other parameters.

3.5 Noisy Polynomial Reconstruction over Sn−1

  • Noisy polynomial reconstruction over arbitrary D on Sn−1×[−1,1] runs in poly(B,n,d,1/ε) time, where B bounds the sum of squared monomial coefficients.The paper identifies this reconstruction task with agnostic learning of multivariate polynomials.Source: §3.5 · p. 16
  • An earlier non-Boolean reconstruction algorithm required product distributions over the unit cube and structured noise, with runtime poly(B,n,2^d,1/ε).The paper contrasts those requirements with its setting on the unit sphere and arbitrary distributions.Source: §3.5 · p. 16

Optimization Problem 5

  • A degree-d polynomial with squared coefficient sum at most B has a bounded-norm representation in the RKHS, making it feasible for Optimization Problem 5.The Representer Theorem rewrites the optimization using sample feature vectors, yielding Optimization Problem 6, a convex program solvable in time polynomial in m, n, and d.Source: Optimization Problem 5 · p. 18, Optimization Problem 6 · p. 18

3.6 Proper Learning

For constant-p ℓp loss, the learner can omit clipping and output a proper polynomial hypothesis, with only a polynomial increase in sample complexity.

3.6 Proper Learning

  • For constant p≥1, ℓp-loss learning can omit clipping with only a polynomial increase in sample complexity, and the resulting proper polynomial learner can compute any desired coefficient efficiently.The hypothesis is h=f, a polynomial of degree at most d.Source: §3.6 · p. 18

3.7 Formal Version of Theorem 1.6 and Its Proof

Theorem 3.5 establishes agnostic learning for bounded-degree, bounded-coefficient polynomials under convex, monotone, bounded, Lipschitz losses, with polynomial running time in the stated parameters. The proof bounds the loss relative to the best polynomial in the class and controls the algorithm’s failure probability.

3.7 Formal Version of Theorem 1.6 and Its Proof

  • A sufficiently large polynomial sample in d, n, B, 1/ε, and log(1/δ) supports the proof’s guarantee, which holds with probability at least 1 − 2δ.The algorithm is allowed to fail with probability 2δ.Source: §3.7 · p. 19
  • The comparator is the best-fitting degree-d multivariate polynomial whose coefficient squares sum to at most B.The theorem’s guarantee is against this constrained polynomial class.Source: §3.7 · p. 19
  • Theorem 3.5 gives polynomial-time agnostic learning for degree-at-most-d polynomials with coefficient-squared sum at most B under any unknown distribution on the sphere.The loss must be convex, monotone, L-Lipschitz, and b-bounded; runtime is polynomial in n, d, B, 1/ε, L, b, and log(1/δ).Source: §3.7 · p. 19
  • The learning algorithm is proper when the loss is ℓ_p for constant p > 0.Source: §3.7 · p. 19

4 Networks of ReLUs

This section extends the ReLU-learning approach to networks and piecewise-linear models using polynomial approximations and clipping. It develops learning and fitting algorithms for several transfer functions and convex piecewise-linear regression, including sums of max-affine functions.

4 Networks of ReLUs

  • Polynomial approximation and clipping extend the learning framework to activations approximable by low-weight polynomials and to a broader class of loss functions.The section's network results apply in the standard agnostic model for linear-combination outputs; a single-ReLU output can extend them to the reliable setting.Source: §4 · p. 20
  • The section also gives the first polynomial-time approximation schemes for convex piecewise-linear regression.Source: §4 · p. 20

4.2 Approximate Polynomial Networks

  • For ReLU networks, the algorithm achieves expected loss at most ε above the best depth-D network for convex, Lipschitz, bounded losses over the stated sphere-and-label domain.The guarantee applies to distributions over S^n−1 × [−M·W, M·W] and losses bounded on [−2M·W, 2M·W].Source: §4.2 · p. 23
  • Depth-2 sigmoid networks with k hidden units and unit-ℓ2 weight vectors are agnostically learnable in poly(n, k, 1/ε, log(1/δ)) time.The guarantee is over S^n−1 × [−k, k] for convex O(1)-Lipschitz losses bounded on [−2k, 2k].Source: §4.2 · p. 24

4.3 Application: Learning Parametric Rectified Linear Unit

  • With bounded |a| and a unit-ℓ2 weight vector, PReLUs are agnostically learnable in n^O(1)·2^O(1/ε)·log(1/δ) time; fixed-slope Leaky-ReLUs follow under the same conditions.Networks of PReLUs can also be learned by replacing each ReLU with a linear combination of two ReLUs.Source: §4.3 · p. 24

4.4 Application: Learning the Piecewise Linear Transfer Function

  • C-Lipschitz piecewise-linear transfer functions with unit-ℓ2 weight vectors are agnostically learnable in n^O(1)·2^O(C/ε)·log(1/δ) time.The guarantee is for learning over S^n−1 with any O(1)-Lipschitz loss function.Source: §4.4 · p. 25
  • The transfer-function application works for general constant Lipschitz loss functions.Source: §4.4 · p. 25

4.5 Application: Convex Piecewise-Linear Fitting

  • The paper gives polynomial-time approximation schemes for convex piecewise-linear regression via ReLU-network gadgets, with runtime exponential in k and no previously known provably efficient algorithms even for k = 2.The problems differ from univariate piecewise or segmented regression, for which polynomial-time algorithms were already known.Source: §4.5 · p. 25

4.5.1 Sum of Max 2-Affine

  • For sums of k maxima of two affine functions, squared-error fitting over the unit sphere has an algorithm running in n^O(1) 2^O(k^2/ε) log(1/δ).The guarantee compares the returned hypothesis with the best function in the class of such sums.Source: §4.5.1 · pp. 25–26

4.5.2 Max k-Affine

  • For max-k-affine fitting, an algorithm runs in n^O(1) 2^(O(k/ε) ceil(log k)) log(1/δ).Any convex piecewise-linear function can be represented as a maximum of affine functions, while the learnability bounds focus on bounded k.Source: §4.5.2 · pp. 26–27

5 Hardness of Learning ReLU

The paper establishes hardness results for learning ReLUs over the Boolean hypercube, contrasting with its efficient learning results on the sphere. Its reduction connects reliable ReLU learning to sparse parity learning with noise.

5 Hardness of Learning ReLU

  • The authors identify Boolean-cube distributions as a setting where ReLU hardness arises, motivating their focus on real-valued learning over the sphere.They state that ReLUs with |w · x| ∈ ω(1) are as hard as notoriously difficult computational learning problems.Source: §5 · p. 28
  • Reliable learning ReLUs over {0, 1}^n with ∥w∥_1 ≤ 2k in time g(ε) · poly(n) would yield a polynomial-time algorithm for learning sparse parities with noise of size k for ε = O(1).The proof reduces agnostic learning of conjunctions to reliable ReLU learning, then invokes a result connecting agnostic conjunction learning to sparse parity learning with noise.Source: §5 · p. 29
  • On domains where |w · x| can grow as ω(1), reliable ReLU learning would break the Sparse Learning Parity with Noise hardness assumption.The stated hardness applies to algorithms that must succeed on all such domains.Source: §5 · p. 29
  • The reduction also implies that an efficient reliable ReLU learner would yield an efficient PAC learner for DNF formulas.This follows from the cited hardness of reliably learning conjunctions relative to PAC learning DNF formulas.Source: §5 · p. 29

6 Conclusions and Open Problems

The paper presents its efficient ReLU-learning algorithms as a first result in a natural learning model. It identifies improving the dependence on 1/ε as an open problem.

6 Conclusions and Open Problems

  • The paper presents its algorithms as the first efficient algorithms for ReLUs in a natural learning model.It contrasts these results with threshold learning, where efficient learning requires stronger assumptions.Source: §6 · p. 29
  • The authors state that their approach learns ReLUs for all distributions with adversarial noise, unlike linear threshold learning as characterized in the conclusion.They attribute this contrast to focusing on settings that are not entirely scale-invariant with respect to the domain.Source: §6 · p. 29
  • Improving the main result’s dependence on 1/ε remains open, and the authors have no reason to believe 2^O(1/ε) is optimal.Source: §6 · p. 30
Loading 1611.10258v1…