Learning ReLU networks to high uniform accuracy is intractable
Julius Berner, Philipp Grohs, Felix Voigtlaender
ICLR 2023
cs.LG, stat.ML
2022-05-27
Learning a given ReLU architecture to uniform accuracy needs samples exponential in depth and dimension; L2 error stays polynomial.
Statistical learning theory usually certifies average error: the expected loss under some data-generating distribution. That is the wrong certificate for security-critical systems, scientific computing, and any setting with distribution shift. Those applications want a guarantee at every input, i.e. a small uniform (L∞) error.
Empirically this is hard. Networks trained with SGD can reach L1 or L2 errors of order 10^{-3} while still showing large pointwise spikes. Adcock and Dexter documented the gap. This paper turns it into an information-theoretic question: if the target class contains ReLU networks of a given architecture, how many point samples does any algorithm need to reach uniform accuracy ε. The bound is algorithm-agnostic. SGD, active learning, and randomized sampling all count.
The language is information-based complexity: count point samples, ignore runtime. An algorithm may pick the next query adaptively from previous values, and may randomize; only the expected number of queries m is charged. The target class is ReLU networks whose weights and biases lie in an ℓ^q ball of radius c, with input dimension d, depth L, and hidden width at most B.
The lower bound is a packing of bump functions. A ReLU net can realize a hat supported on a cube of side about 1/M, with height controlled by c, q, and L. Taking M on the order of m^{1/d}, a volume argument shows that for any m sample locations, at least half of a grid of such bumps vanish at every sample. No algorithm can tell those bumps from the zero function, so the uniform error cannot drop. Weaker regularization (larger q or c) makes taller bumps and a worse bound.
The matching-style upper bound is coarser: these networks have an explicit Lipschitz constant, and any moderately Lipschitz function can be reconstructed by piecewise-constant interpolation. The sample complexity is exponential, not infinite. Adaptive queries do not help, because a worst-case bump can hide in any unsampled cube.
The main theorem covers L≥3 and every Lp. Any method using m point samples has minimax error at least c0·Ω/(32s)^{1+s/p}·m^{-1/p-1/s}, with s≤min{B/3,d}. For p=∞ and width at least 3d, uniform accuracy ε requires
m ≥ (Ω/(32d))^d · ε^{-d}.
A concrete case: ε=1/1024 and width at most 3d gives m ≥ 2^d · c^{dL} · (3d)^{d(L-2)}. For d=15, c=2, L=7 this already exceeds the usual estimate of the number of atoms in the universe. The same class is tractable in L2: finite pseudodimension plus empirical risk minimization yields a sample complexity polynomial in d.
Numerically, a student-teacher setup trains Adam students on random teacher nets, d=1 and d=3, m from 10^2 to 10^5, 8640 runs. L1 and L2 improve with m; L∞ is worse, and in 1D it nearly stalls. On the worst teacher at m=100, L∞ error is 2.7×10^{-3}, about 7× the L2 error 3.9×10^{-4}, caused by spikes between samples. The introductory demo at m=1000 reports L1=2.8×10^{-3} and L∞=0.19.
The hardness is informational, not computational. Even a perfect optimizer of the observed samples cannot pin a ReLU net to high uniform accuracy. Adversarial examples, hallucinations, and model-extraction attacks share a geometry: the hypothesis class contains bumps that miss every query.
If the product actually needs to be right everywhere (PDE solvers, certification, safety), more SGD on more i.i.d. points is the wrong bet. Either bake extra structure into the algorithm, or accept average error. The paper quantifies the split: L2 is learnable, L∞ is not.
ReLU only. Other activations, the authors say, need new techniques. Upper and lower bounds still gap in high dimension. This is worst-case: for every algorithm there exists at least one hard target, with no proof that the hard targets are generic. The class contains every realization of the architecture; extra side information written into the algorithm can evade the bound, which is no longer end-to-end deep learning. Experiments stop at d=3, so the exponential wall is not numerically hit in genuinely high dimension.