acceptodds
Under review as a conference paper at ICLR 2027

"Deep lifts": Neural networks can generalize even with the dumbest optimizer

Abstract

Given a labeled dataset , consider drawing a parameter vector uniformly at random from those that interpolate the data within a width- depth- ReLU architecture with continuous weights bounded within . We study the generalization properties of in the case where the dataset can, in fact, be explained by a smaller -by- ReLU network. Despite the obliviousness of the selection rule for , it adaptively generalizes at the rate , rather than being governed by the VC dimension of the full -by- hypothesis class. The reason is due to a particular inductive bias in ReLU networks: the -by- parameter witnesses an exponential volume of -by- interpolating parameters, which dwarfs the volume of poorly generalizing parameters (conditioned on interpolation). We explicitly construct this set of near-equivalent -by- parameters by a proof technique “deep lifting,” and then tie the achievable volume to stability properties of . Examples show that these techniques allow us to convert approximation-theoretic results into generalization guarantees for nonparametric classes. We further show that generalization of uniform-random interpolators can survive label corruptions.

Primary area:
learning theory
Keywords:
deep learning, generalization

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_9BYeOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates whether overparameterized neural networks can generalize without relying on the implicit bias of a specific optimization algorithm. The authors consider an idealized learning rule that samples uniformly from the parameters of a large ReLU network that approximately interpolates the training data. A key technical contribution is the "deep lifting" construction, which maps a smaller network to a set of parameters within a larger architecture that yields approximately equivalent behavior. By introducing the concept of "structural stability," the authors derive generalization bounds that depend on the complexity of a smaller "witness" network rather than the total number of parameters. The analysis also addresses scenarios involving corrupted labels and unrealizable targets, and includes applications to Hölder and Barron function classes. The results demonstrate that, even when interpolating solutions are sampled uniformly, the network parameterization itself inherently favors simpler functions.

Critical strengths
  1. A meaningful theoretical extension of existing results. In the continuous setting, the parameters corresponding to exact copies of a smaller network generally occupy zero Lebesgue measure, so the counting arguments used in previous work no longer apply directly. The positive-volume lifting construction in Section 4, particularly Lemma 10, addresses this difficulty.

  2. A general framework connecting network stability, approximation, and generalization. Theorem 3 establishes a generalization rate of approximately (O~(wdWD/n)\widetilde O(wdWD/n)) when the target can be approximated by a smaller network. The structured-stability framework is particularly useful because it makes the dependence on the witness network explicit. The extensions to corrupted labels (Theorem 6) and unrealizable targets (Theorem 8) further strengthen the contribution. I also appreciate the Hölder and Barron examples, which illustrate how the general theory can produce concrete statistical rates.

Critical weaknesses
  1. The interpretation depends on an idealized sampling rule and parameterization. Uniform sampling from the interpolating parameter set is computationally intractable in general. Different parameterizations can induce substantially different distributions over functions. Consequently, the results establish an architectural bias under a specific parameter-space measure, but do not necessarily explain the behavior of practical optimization algorithms.

  2. The generalization guarantees depend on restrictive conditions, particularly in the noisy setting.Theorem 3 requires a uniformly accurate smaller witness network, and the bound depends on the witness depth and stability properties. It remains unclear how tight these dependencies are. The corrupted-label results also require additional assumptions on the input distribution, parameter bounds, and network capacity. In particular, Corollary 7 establishes a tempered-overfitting-type guarantee at selected sample sizes, rather than an asymptotic guarantee for a fixed corruption rate.

Questions for authors
  1. How essential is the coordinate-wise uniform distribution to the deep lifting argument?

  2. Corollary 7 provides a tempered-overfitting-type result at a particular sample size, while the authors note that the bound eventually deteriorates logarithmically. Is this deterioration inherent to the proposed analysis, or is there a specific obstacle preventing an asymptotic result?

Reviewer_hBwuOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The learner draws parameters θ^\hat\theta uniformly from the set of τ\tau-interpolating parameters of a width-WW, depth-DD ReLU network with continuous weights in [−M,M][-M,M]. The main results are as follows.

  1. Realizable case (Thm. 3): if a small w×dw \times d "witness" network approximates the target ff to within τ/2\tau/2, the τ\tau-risk is O~(wdWD/n)\tilde O(wdWD/n). This replaces the full student-complexity (VC) dependence with a bound involving both the witness and the student architecture.
  2. Technique (deep lifting): the witness is embedded into a positive-volume family of larger networks. Extra neurons are switched off with negative biases; many other weights remain unrestricted, while selected weights and biases are constrained to preserve the witness computation. The continuous-weight case is handled through structured stability, proved directly for padded witnesses in the noiseless case (Lemma 31) and otherwise derived from a stronger, composable disturbance stability (Lemma 27).
  3. Label noise (Thm. 6, Cor. 7): bounded adversarial corruptions (Assumption 4), under a marginal-density condition on μX\mu_X (Assumption 5), are handled with a memorization gadget, giving rate O~(d W(wD+m)/n)\tilde O(d\,W(wD+m)/n) (keeping the witness-depth dependence of the formal Thm. 37 explicit), plus a constant-noise corollary.
  4. Further extensions: unrealizable targets (Thm. 8), classification, and (for classification) a cross-entropy Boltzmann posterior conditioned on interpolation, with worked examples for Hölder, Barron and halfspace targets.
Critical strengths
  1. A real technical step. The paper extends lifting arguments from discrete to continuous weights for plain fully-connected ReLU networks of arbitrary depth, where prior extensions were limited to shallow or boolean networks. The reduction from disturbance stability to structured stability is modular, and identity padding keeps stability deterioration polynomial in the student depth DD, with exponential dependence only on the witness depth dd.
  2. Witness complexity drives the bound, while most student parameters stay unrestricted.
  3. Clean noise handling: the memorization gadget handles adversarial, data-dependent corruptions.
  4. The Barron example uses a deep but stable narrow witness (Lemma 35) and shows convincingly how approximation guarantees become generalization guarantees.
  5. The main text is clearly written and Fig. 2 is helpful. The paper is candid that the learner cannot feasibly be implemented and is an unrealistic learning rule; it is presented as a tool for studying generalization independent of optimizer bias, not as an algorithm.
Critical weaknesses
  1. Positioning against the closest prior work. Dziugaite & Roy (AISTATS 2025) already embed a small teacher into a larger student with complexity growing only linearly in student width and depth, use Gibbs posteriors, and convert teacher-size curves into rates, though with quantized weights; Bayesian neural-network analyses also lower-bound prior mass near an approximating network (e.g. Kong & Kim, JMLR 2025). The paper should state quantitatively what continuous ReLU lifting and structured stability add over these.
  2. The rate statements are inconsistent in their dependence on the witness depth dd. The introduction gives O~(W(wD+m) d/n)\tilde O(W(wD+m)\,d/n); informal Thm. 6 (l. 280–282) has dd only inside the polynomial in log⁡qeff,n\log q_{\mathrm{eff},n}, with no multiplicative factor; formal Thm. 37 has log⁡qeff,n≤2dlog⁡(⋯ )\log q_{\mathrm{eff},n} \le 2d\log(\cdots). Similarly, informal Cor. 7 has a factor dd that formal Thm. 40 does not. Please reconcile these.
  3. The consistency claim is too loose. Line 295 states that m=on(n)m = o_n(n) implies vanishing risk, but the displayed guarantee needs W(wD+m)log⁡qeff,n/n→0W(wD+m)\log q_{\mathrm{eff},n}/n \to 0, together with the feasibility conditions M≥poly(n)M \ge \mathrm{poly}(n) and W≳w+s+m/DW \gtrsim w + s + m/D. For example, at fixed depth W≳m/DW \gtrsim m/D adds a term of order m2/(Dn)m^2/(Dn), and log⁡qeff,n\log q_{\mathrm{eff},n} grows with log⁡n\log n. Please state the general condition and the architecture scaling it requires.
  4. The "tempered-overfitting type risk floor" wording (also "nonzero risk floor") overstates Cor. 7. Cor. 7 is an upper bound that holds at a single selected nn, with depth schedule Dn=max⁡{d, 2, ⌈mn/B⌉}D_n = \max\{d,\,2,\,\lceil m_n/B\rceil\} where mn=min⁡{n, ⌈2εn+log⁡(2/δ)⌉}m_n = \min\{n,\,\lceil 2\varepsilon n + \log(2/\delta)\rceil\}, for fixed corruption rate ε\varepsilon and fixed BB (Thm. 40). The paper itself notes that Cor. 7 is not an asymptotic result and that the guarantee eventually diverges as Θ(log⁡n)\Theta(\log n); since an upper bound at one nn cannot establish a positive floor, the "risk floor" wording should be revised.
Questions for authors
  1. Can you reconcile the main-text and appendix versions of the noise bound, and state explicit conditions under which the risk vanishes?
Reviewer_MNixOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper concerns on separating the role of neural network architecture on generalization ability of the trained model. Prior work already has shown separation, i.e., some network architectures can induce some effects on generalization. This paper extends this result for some discrete-weight architectures to ones with continuous weights. The paper also show the separation results for the cases of noisy outputs and non-realizable setting. It argues that when the target admits a smaller width-w, depth-d witness, the uniform interpolator generalizes at a rate which can be faster the rate known for discrete-weight architectures.

Critical strengths
  • The extension to continuous cases seems to be nontrivial with existing lifting ideas, because exact lifts have zero Lebesgue measure and the authors must construct positive-volume stable neighborhoods.

  • The authors obtained a generalization rate which can be tighter than the one known before for discrete-weight cases.

  • Stable approximation theory is connected to statistical rates. The Barron construction is a particularly interesting example. The authors explicitly design a constant-width, depth-r implementation whose disturbance sensitivity is linear rather than exponential in r.

Critical weaknesses
  • While be a nontrivial extension, the paper does not yet establish why this extension changes our understanding of practical machine learning. The main qualitative separation between witness complexity and ambient-network complexity is already known for discrete weights.

  • Structured stability is the central assumption enabling the continuous extension, but its practical interpretation is unclear. It requires uniform control over the entire input domain under simultaneous worst-case coordinatewise perturbations of every parameter.

  • The title and abstract seem to overgeneralize from a highly specific proof construction to ReLU networks as a broad architectural class. The results concern fully connected, fixed-width ReLU networks equipped with a coordinatewise bounded parameterization and Lebesgue-uniform measure conditioned on interpolation. The volume lower bound relies on a specific carried-versus-inactive block decomposition, large negative biases that keep added neurons identically inactive, and a quantitatively stable witness.

Questions for authors

Please see Weaknesses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.