PaperlayerView exact revision on arXiv

Source-linked AI summary

Breaking the Curse of Dimensionality with Convex Neural Networks

Francis Bach

arXiv:1412.8690v2cs.LGmath.OCmath.ST

TL;DR

The paper asks how neural networks can achieve provable generalization across high-dimensional problems without committing to a known structure. It analyzes convex single-hidden-layer networks with homogeneous activations and unbounded hidden units, showing adaptivity to low-dimensional structure and nonlinear variable selection while leaving efficient algorithms open.

  • Problem

    Existing methods trade flexible nonparametric modeling against restrictive parametric assumptions, motivating one method that adapts provably across structural settings.

  • Method

    The paper studies single-hidden-layer networks with non-decreasing homogeneous activations, unbounded hidden units, output-weight regularization, and geometric analyses of incremental unit selection.

  • Results

    The networks adapt to unknown low-dimensional linear structures and can achieve high-dimensional nonlinear variable selection without strong data assumptions.

  • Takeaways & Limitations

    Convex neural networks can replace dependence on ambient dimension with dependence on a relevant subspace dimension, while supporting variable selection with potentially many input variables.

  • Takeaways & Limitations

    The results apply to estimators without known polynomial-time algorithms, and sufficiently strong convex relaxations remain undiscovered.

Abstract

from arXiv · show

We consider neural networks with a single hidden layer and non-decreasing homogeneous activa-tion functions like the rectified linear units. By letting the number of hidden units grow unbounded and using classical non-Euclidean regularization tools on the output weights, we provide a detailed theoretical analysis of their generalization performance, with a study of both the approximation and the estimation errors. We show in particular that they are adaptive to unknown underlying linear structures, such as the dependence on the projection of the input variables onto a low-dimensional subspace. Moreover, when using sparsity-inducing norms on the input weights, we show that high-dimensional non-linear variable selection may be achieved, without any strong assumption regarding the data and with a total number of variables potentially exponential in the number of ob-servations. In addition, we provide a simple geometric interpretation to the non-convex problem of addition of a new unit, which is the core potentially hard computational element in the framework of learning from continuously many basis functions. We provide simple conditions for convex relaxations to achieve the same generalization error bounds, even when constant-factor approxi-mations cannot be found (e.g., because it is NP-hard such as for the zero-homogeneous activation function). We were not able to find strong enough convex relaxations and leave open the existence or non-existence of polynomial-time algorithms.

1. Introduction

The paper seeks one provably adaptive learning method spanning flexible nonlinear models and simpler structural assumptions. It studies convex single-hidden-layer neural networks, showing adaptivity to low-dimensional linear structure and high-dimensional nonlinear variable selection while identifying computational barriers.

  • Motivation: Nonparametric methods can require exponentially many observations in dimension d, whereas parametric methods have lower sample complexity but may underfit when their assumptions fail.For Lipschitz functions, the required sample size scales exponentially with d; linear models scale as n = Ω(d/ε2) under well-specification.
  • Research question: The paper asks whether a single learning method can efficiently and provably adapt across local, parametric, structured, projection-based, and variable-selection settings.The motivating settings include unknown low-dimensional subspaces and variable selection as a special case of sparse projection structure.
  • Approach: The proposed framework uses single-hidden-layer networks with non-decreasing homogeneous activations, potentially infinitely many units, and sparsity-inducing regularization on output weights.The analysis focuses particularly on threshold activations and rectified linear units, while L1 and L2 penalties provide different functional-analytic interpretations.
  • Optimization: The paper develops geometric interpretations of adding new units, reducing the core nonconvex computational tasks to separating hyperplanes or Hausdorff-distance computations between convex sets.These incremental optimization problems are identified as potentially hard elements of learning from continuously many basis functions.
  • Approximation: Approximation results show that convex neural networks adapt to linear structures by replacing exponential dependence on ambient dimension with exponential dependence on the relevant subspace dimension.The approximation analysis provides explicit bounds for monotonic homogeneous activations and connects them to prior neural-network approximation theory.
  • Generalization: Under an ℓ1-norm on input weights, high-dimensional nonlinear variable selection may be achieved with many more input variables than observations and without strong data assumptions.The paper explicitly notes that it does not provide a polynomial-time algorithm for achieving this result.
  • Computational limitations: Convex relaxations can match the same generalization error bounds under simple conditions, but the paper does not establish sufficiently strong relaxations or polynomial-time algorithms.For threshold and rectified-linear activations, constant-factor approximation can be NP-hard, leaving the existence of suitable polynomial-time algorithms open.

2. Learning from continuously infinitely many basis functions

The paper models functions as integrals over a potentially continuous family of basis functions, regularized by a variation norm. This framework supports finite representations, RKHS connections, convex optimization, and conditional-gradient approximation.

  • Variation norm: Functions in F1 are represented as integrals of basis functions against signed Radon measures with finite total variation.The variation norm γ1 is the infimum of the measure’s total variation over all such decompositions.
  • Variation norm: For finite decompositions, the measure’s total variation equals the ℓ1-norm of the coefficients, while the number of basis functions corresponds to their ℓ0-pseudo-norm.Thus variation-norm regularization controls coefficient magnitude rather than directly controlling the number of units.
  • Finite representation: With observations restricted to n input points, an optimal function in the variation-norm ball can be represented using at most n basis functions.Carathéodory’s theorem guarantees this finite support, although the identities of the selected functions are not known in advance.
  • Corresponding RKHS: Using densities relative to a full-support probability measure yields an L2-based squared norm whose function space is an RKHS.For finite V, the construction corresponds to a squared RKHS norm with a positive definite kernel; the paper extends the result to compact V.
  • Supervised machine learning: The excess risk of an approximate empirical-risk minimizer decomposes into approximation, estimation, and optimization errors.The optimization error is studied for the variation-norm space using conditional-gradient methods.
  • Incremental conditional gradient algorithms: Conditional-gradient procedures incrementally construct functions from extreme basis functions, with convergence rates in O(1/t) and approximation error O(γ(g)^2/t).After t iterations, the approximation is supported by t basis functions, requiring t = O([γ(g)/ε]^2) units for averaged error ε.
  • Incremental conditional gradient algorithms: The linear optimization step over the variation-norm ball reduces to selecting maximizers of a gradient-related functional, whose solutions generate convex combinations of basis functions and their negatives.A modified algorithm can provide a κ-factor relaxation for fixed κ ≥ 1.

3. Neural networks with non-decreasing positively homogeneous activation functions

This section specializes convex neural networks to non-decreasing positively homogeneous activations and develops their geometric and theoretical structure. Homogeneity enables a spherical reformulation, while the resulting function spaces support boundedness, approximation, adaptivity, and geometric analyses of incremental optimization.

  • Activation functions: The paper studies single-hidden-layer networks built from non-decreasing positively homogeneous activations, including hard thresholds and rectified linear units.The activation family is σ(u) = (u)^α for nonnegative integer α, with α = 0 giving thresholds and α = 1 giving ReLUs.
  • Incremental optimization: Adding a new unit has geometric interpretations involving separating hyperplanes and Hausdorff distances between convex sets, but the incremental problems remain computationally hard.For α = 0, the relevant classification problem is NP-hard and admits no constant-factor approximation; for α = 1, the problem reduces to the α = 0 case and is also NP-hard.
  • Homogeneous reformulation: Positive homogeneity permits transferring the optimization and approximation problems from the input domain to a unit sphere after augmenting inputs with a constant coordinate.The construction maps a ball in R^d into a spherical cap in dimension d+1 and normalizes the input-weight vectors.
  • Function-space properties: The induced function spaces are bounded under the stated norm constraints, and functions in F1 are Lipschitz-continuous when α ≥ 1.For f ∈ F1, the bound is expressed as f(x)^2 ≤ 2^αγ1(f)^2.
  • Function-space properties: The spherical representation preserves or controls the regularity of functions, including boundedness, Lipschitz continuity, and derivative bounds under extension to the full sphere.The construction ensures that the extended function can be chosen even or odd while retaining controlled regularity.
  • Approximation and adaptivity: The F1 space inherits approximation properties from the smaller RKHS F2 while remaining adaptive to underlying linear structures.The paper contrasts F1’s adaptivity with the RKHS norm, which does not provide such adaptivity.

4. Approximation properties

The paper develops approximation results for convex neural-network function spaces, relating finite-neuron approximation to variation norms and geometric approximation by zonotopes. The bounds also establish adaptivity to low-dimensional projections and dimension-independent behavior for certain projection functions.

  • Approximation by finite neurons: The variation norm γ1(g) controls finite-neuron approximation, with L2 error ε achievable using n = O(γ1(g)^2ε^-2) units.For rectified linear units, the paper improves the dependence on ε through zonoid and zonotope geometry.
  • Geometric interpretation: For finitely supported measures, the positive and negative components of g are support functions of zonotopes, making neuron approximation equivalent to approximating a zonoid by a zonotope.The number of neurons depends directly on the variation norm γ1.
  • Function-space approximation: Smoothness and Lipschitz conditions provide sufficient bounds placing functions in G2 or F2, with γ2 controlled by constants depending on dimension, activation degree, and regularity.The corresponding sphere and Euclidean-domain results are given in Propositions 2, 3, 5, and 6.
  • Adaptivity to linear structure: For f(x) = ϕ(w⊤x), the norm depends on ϕ over [−Rη, Rη] rather than d, whereas the corresponding RKHS is generally not adaptive.This norm behavior supports generalization bounds for functions depending on low-dimensional linear projections.
  • Adaptivity to linear structure: Without structure beyond Lipschitz continuity, the required number of hidden units remains exponential in dimension; low-dimensional linear dependence removes that exponential dependence.Using ℓ1 input-weight penalties preserves the approximation results up to dimension-dependent constants and supports projection functions without dimension dependence under bounded inputs.

5. Generalization bounds

The paper derives expected generalization bounds for convex neural networks by combining approximation results with Rademacher-complexity estimation bounds. These bounds adapt to low-dimensional structure and sparse variable selection, although some computationally efficient approximations remain unavailable.

  • Framework: The analysis minimizes empirical risk over norm-constrained function classes and separates approximation error from estimation error.Uniform deviations between empirical and expected risk are controlled with Rademacher complexities.
  • Rates: The paper provides generalization bounds for ℓ2- and ℓ1-penalized settings, including affine, projection-pursuit, and generalized projection structures.For affine targets, the norm bound is independent of d, while generalized projection rates depend on the projection dimension.
  • Projection pursuit: For one-dimensional projection pursuit, the optimized bound scales as C(α)kGRη log n / n^(1/(2α+2)), independently of d apart from R.The target is a sum of functions of one-dimensional projections, with approximation controlled through the convex neural-network norm.
  • Adaptivity: The bounds adapt to targets depending on unknown lower-dimensional subspaces, replacing exponential dependence on ambient dimension with dependence on subspace dimension.For general Lipschitz functions, the dependence on dimension is unfavorable, whereas structural assumptions remove that dependence from the rate.
  • Scope and computation: Lower bounds are outside the paper’s scope, and random sampling approximations of the ℓ1 estimator may require exponentially many samples in d.The authors also state that proposed convex relaxations can preserve approximation properties only under sufficient conditions.
  • Variable selection: With an ℓ1-norm on input weights, nonlinear variable selection remains possible when d is much larger than n, without assumptions on correlations between variables.The stated high-dimensional scaling applies beyond sparsity assumptions and does not provide a polynomial-time algorithm.

6. Convex relaxations of the Frank-Wolfe step

The paper studies convex relaxations for the nonconvex Frank–Wolfe step using geometric, direct, semidefinite, and sign-vector formulations. The proposed relaxations do not recover the required approximation scaling, and Lipschitz-based relaxations have insufficient dependence on n.

  • Problem structure: The new-unit maximization problem admits geometric interpretations as binary classification or Hausdorff-distance computation between convex sets.The relaxations focus on p = 2 and α = 1, corresponding to ℓ2 constraints and rectified linear units.
  • Approximation quality: The proposed relaxations do not attain the proper approximation scaling, as checked empirically.This prevents them from directly delivering the target generalization guarantees.
  • Computational limitation: Lipschitz-continuous relaxations have Rademacher complexity decaying as n^-1/d for larger d, which is too slow for the desired generalization bounds.For d = 2, the cited decay is n^-1/2.
  • Relaxations: Removing rank constraints yields convex semidefinite relaxations in variables representing vv⊤, uu⊤, and uv⊤.Additional quadratic-form and sign-vector constructions produce further semidefinite programs.
  • Empirical behavior: The semidefinite relaxation based on sign vectors also fails empirically to obtain the correct scaling in n for random Gaussian y.The formulation uses S = ss⊤, V = vv⊤, and J = sv⊤.

7. Conclusion

The conclusion emphasizes adaptivity to low-dimensional linear structure and nonlinear variable selection as the main statistical result. It also stresses that computational tractability remains unresolved and that extending the framework to multiple hidden layers is nontrivial.

  • Main result: Convex neural networks adapt to underlying linear structures, including dependence on a low-dimensional subspace and nonlinear variable selection with many input variables.The conclusion presents this adaptivity as the paper’s main new result.
  • Computational status: The current estimators lack known polynomial-time algorithms, while sufficient conditions for convex relaxations to match the bounds leave algorithm existence open.The associated hard problems have geometric interpretations as binary classification or Hausdorff-distance computation between zonotopes.
  • Scope: The framework readily extends to finite-dimensional vector-valued outputs but does not straightforwardly extend to multiple hidden layers.Shared first-layer weights in deeper networks require a new functional-analysis framework.

Appendix A. Reproducing kernel Hilbert spaces for ℓ2-norm penalization

The appendix shows that the function space induced by squared-integrable coefficients over continuously many features is a reproducing kernel Hilbert space. Its reproducing property follows from the integral representation and the associated operator construction.

  • Construction: The space F2 contains functions represented as integrals of feature functions ϕv weighted by a squared-integrable coefficient p.The measure τ is a Borel probability measure on a compact feature space.
  • RKHS structure: The RKHS kernel is induced by the feature integral, and the space is equipped with the corresponding inner product.The operator T maps coefficient functions in L2(dτ) to represented functions in F2.
  • Reproducing property: The reproducing property follows because the inner product with k(·, y) evaluates f at y.The appendix explicitly derives ⟨f, k(·, y)⟩ = f(y), establishing that F2 is an RKHS.
  • Norm equivalence: The RKHS norm equals γ2, the infimum of the squared coefficient integral over all decompositions of f.This identifies the ℓ2-type functional penalty with the RKHS norm.

Appendix B. Approximate conditional gradient with multiplicative oracle

The appendix modifies conditional gradient to tolerate a multiplicative approximate oracle while keeping iterates within a prescribed norm ball. Its analysis yields a bound comparing the achieved objective with the optimum over a smaller ball.

  • Oracle and feasible set: A multiplicative approximate oracle returns a unit-norm candidate, and the modified algorithm seeks h with γ(h) ≤ δ.The oracle approximation factor is κ ≥ 1.
  • Convergence analysis: For any ρ ∈ [0, 1], smoothness bounds one update by a linearized objective term plus 2Lρ^2δ^2.The bound uses the approximate oracle through maximization over the ball of radius δ/κ.
  • Algorithm: All iterates remain inside the γ-ball of radius δ under the proposed recursion.The recursion may replace exact segment minimization with the upper bound from Eq. (7).
  • Guarantee: The resulting guarantee is J(h_t) ≤ inf_{γ(h)≤δ/κ} J(h) + 4Lρ^2δ^2.This holds through the conditional-gradient proof up to the point where the iterate's objective gap becomes nonpositive.

Appendix C. Proofs for the 2-dimensional sphere (d = 1)

For d = 1, the sphere becomes a periodic interval, allowing the γ2 norm to be analyzed through Fourier frequencies. The activation's parity determines which frequency coefficients vanish and how the remaining coefficients decay.

  • Fourier representation: When d = 1, the sphere is identified with [0, 2π] under periodic boundary conditions, enabling closed-form Fourier analysis of γ2.The representation decomposes functions into frequency elements.
  • Frequency coefficients: For α = 0, λk vanishes for nonzero even k, while odd-frequency coefficients decay as 1/k.The stated nonzero pattern is given for the corresponding activation case.
  • Frequency coefficients: For α = 1, λ1 = 1/4, nonzero even-frequency coefficients decay as 1/k^2, and other odd frequencies vanish.The zero and nonzero patterns reverse relative to the α = 0 case.
  • Frequency coefficients: For α = 2, λ0 = 1/4 and λ2 = 1/8, while the nonzero odd-frequency coefficients decay as 1/k^3.Other even frequencies vanish.
  • General pattern: For integer α, coefficients with parity opposite to α decay as 1/k^(α+1), while same-parity coefficients above α vanish.All frequencies from k = 0 through α are nonzero.

C.2 Proof of Prop. 2 for d = 1

The proof characterizes membership in G2 through Fourier coefficients after accounting for the activation's parity. Sufficient smoothness of the target function then guarantees a finite γ2 representation.

  • Fourier construction: For the required parity, p is constructed by multiplying g's Fourier coefficients by a positive sequence growing as k^(α+1).This construction compensates for the decay pattern of the activation coefficients.
  • Smoothness condition: If g's (α + 1)-th derivative is square-integrable, the constructed p is square-integrable and g belongs to G2.The result applies when g has the parity required by α.
  • Parity relaxation: The parity restriction can be relaxed by adding all trigonometric polynomials of order less than α.This modifies the approximation class without changing the core Fourier argument.

C.3 Proof of Prop. 3 for d = 1

For d = 1, the proof approximates Lipschitz functions by smoother periodic functions and evaluates the resulting representation using Fourier and spherical-harmonic tools. The coefficient decay and norm asymptotics determine the approximation behavior.

  • Approximation construction: The construction smooths a Lipschitz-continuous function into an (α + 1)-times differentiable approximation while controlling its γ2 norm.The target approximation is defined using a parameter r chosen close to one.
  • Base case: For α = 0, every Lipschitz-continuous function already lies in G2 with norm less than one.This uses almost-everywhere differentiability with bounded derivative.
  • Norm control: A 1-Lipschitz function has a square-integrable derivative with norm less than 1, supporting the construction's norm control.The associated L2 quantities are bounded by 1.
  • Parameter choice: The smoothing parameter is selected by analyzing the derivative of k^(2α)r^(2k), which identifies the relevant frequency scale.The derivative is treated with k as a real variable.
  • Harmonic framework: Spherical harmonics extend Fourier analysis to higher-dimensional spheres and provide the basis for decomposing functions by degree.For d = 1, the framework reduces to Chebyshev polynomials and Fourier series.
  • Harmonic decomposition: The harmonic decomposition separates constant, linear, and higher-degree components, with orthogonality yielding Parseval identities.One-dimensional projections are represented within the same harmonic framework.
  • Spectral characterization: Activation coefficients vanish above degree α for matching parity and decay according to α, determining the RKHS norm's spectral weighting.The coefficient structure follows from orthogonality and integration by parts.
  • Asymptotics: At large frequency, the relevant asymptotic is k^(-d/2-α-1/2), while at large dimension it is d^(-α/2-k/2+1/2).These equivalents hold with α fixed in the first regime and k fixed in the second.

D.3 Proof of Prop. 2 for d > 1

The proof extends the one-dimensional argument to d > 1 by representing sufficiently smooth functions through the spherical Laplacian and using harmonic eigenvalues.

  • If g is s-times differentiable with uniformly bounded derivatives, it can be represented as g = ∆^s/2 f with bounded L2(S^d) norm.The representation uses the Laplacian on the sphere and references classical spherical-harmonic results.
  • The higher-dimensional proof follows the same structure as the d = 1 proof in Appendix C.3.
  • The spherical-harmonic components g_k are Laplacian eigenfunctions with eigenvalues k(k + d − 1).

D.4 Proof of Prop. 3 for d > 1

The proof constructs a regularized approximation ˆg to a Lipschitz function g on the sphere, then balances approximation error and norm growth through the parameter r.

  • Assuming η = 1, the argument uses the Lipschitz bound |g(x) − g(y)| ⩽ η∥x − y∥2.
  • For r ∈ (0, 1), absolute convergence defines ˆg, which has finite γ2-norm and remains close to g.
  • The constructed function ˆg belongs to G1 and satisfies γ2(g) ⩽ C(d, α)(1 − r)^((−d+1)/2)−α.
  • Because ˆg_k = r^k g_k, the approximation analysis controls the difference between g and ˆg using spherical-harmonic decay.
  • Choosing 1 − r = (C/δ)^(1/(α+(d−1)/2)) for sufficiently large δ yields the desired approximation result.

D.5 Finding differentiable functions which are not in G2

This section characterizes smooth spherical functions that fall outside G2, derives their optimal G2 approximation rates, and records related computational reductions for ellipsoid distances.

  • Finding differentiable functions which are not in G2: The target functions have the proper parity and bounded derivatives but are not in G2, motivating optimal approximation-rate analysis.
  • Finding differentiable functions which are not in G2: The harmonic count N(d, k) grows as k^(d−1), while the relevant coefficient term decreases as k^(−d−2s−1).
  • Finding differentiable functions which are not in G2: After removing harmonics with k ⩽ s to enforce the required parity, the resulting function remains a function of w⊤x.
  • Finding differentiable functions which are not in G2: When d + 2α − 2s ⩾ 0, the RKHS-norm series diverges, so the function is not in the RKHS.
  • Finding differentiable functions which are not in G2: The optimal G2 approximation uses coefficients α_k = (1 + λk^(d+2α+1))^−1 determined by a Lagrange multiplier.
  • Finding differentiable functions which are not in G2: The non-squared approximation error scales as δ^−(2s+1)/(d+2α−2s), becoming δ^−3/(d+2α−2) when s = 1.
  • Computational reductions: The ℓ2-Hausdorff distance between ellipsoids can be computed by searching over λ and solving for µ, with O(d^3) complexity per iteration.The per-iteration complexity is that of a singular value decomposition.
Loading 1412.8690v2…