PaperlayerView exact revision on arXiv

Source-linked AI summary

A Closed-Form Formula for Consistent Lipschitz Regression on Metric Spaces with Sparse Neural Network Realizations

Ruiyang Hong, Hrad Ghoukasian, Anastasis Kratsios

arXiv:2609.03129v1stat.MLcs.LG

TL;DR

Neural-network regression is difficult to analyze because training is generally non-convex, and existing guarantees may leave optimization error uncontrolled. The paper gives a closed-form split-sample estimator for Lipschitz regression, with uniform recovery and exact sparse ReLU realizations in stated settings. It also establishes optimality properties and identifies settings where the theory does not cover the experimental implementation.

  • Problem

    Neural-network training is generally non-convex, and existing approximation or statistical guarantees typically do not control the optimization error of the training algorithm.

    Source: §1 · p. 2, §1.3 · p. 6

  • Method

    The paper constructs a closed-form split-sample McShane–Whitney estimator and gives exact sparse ReLU-MLP realizations on specified Euclidean domains.

    Source: §7 · p. 29

  • Results

    The estimator attains the minimax Euclidean polynomial exponent up to logarithmic factors, with recovery bounds for exact sparse ReLU realizations containing no separate optimization-error term.

    Source: §7 · p. 29

  • Takeaways & Limitations

    The stated results give uniform recovery guarantees directly for the formula and its explicit realizations, without assuming access to an exact or approximate ERM.

    Source: §7 · p. 29

    Theorem 3.2 is proved for the split-sample, fixed-cardinality estimator, whereas the experiments use an all-sample implementation and may select β by hold-out validation.

    Source: §6 · p. 23

Abstract

from arXiv · show

Several classical machine-learning methods, such as KRRs and SVRs, are both computationally and analytically tractable since their estimators either admit closed-form expressions or are obtained by minimizing convex training objectives; neither feature is generally available for deep neural networks. We address this by introducing a simple closed-form ``two-stage'' compositional formula $\hat{f}$ for reconstructing an unknown Lipschitz function $f:\mathcal{X}\to \mathbb{R}$ on a metric space $(\mathcal X,\rho)$ from $N$ i.i.d. noisy observations. Our main result is a high-probability uniform ($L^{\infty}$) recovery guarantee that jointly controls approximation and statistical errors while enjoying an optimization error of zero; in particular, we do not assume oracle access to an approximate ERM. Our secondary main results establish the optimality of our formula in three complementary senses. 1) Function space: On Ahlfors-regular metric spaces, the hypothesis class parameterized by our formula attains the optimal fat-shattering dimension. 2) Parameter space: Its dependence on the parameters is maximally numerically stable, in the sense that a smaller approximation error cannot be achieved with a smaller Lipschitz dependence on the model parameters. 3) Forward pass: Its dependence on the input is maximally regular, matching the Lipschitz constant of the target function $f$. When $\mathcal X=[0,1]^d$ is equipped with the $\ell^\infty$ norm, $\hat{f}$ admits algorithmic ReLU-MLP and exact ReLU-multi-head transformer realizations of depth $\mathcal{O}(\log(N))$ with $\mathcal{O}(N)$ nonzero parameters.

1. Introduction

The introduction frames neural-network regression as difficult to analyze because training is generally non-convex and lacks tractable closed-form solutions, leaving optimization error uncontrolled by many existing guarantees. It presents a closed-form estimator for Lipschitz regression and develops recovery, realization, and optimality results without requiring an approximate ERM.

1. Introduction

  • Neural-network training is generally non-convex and lacks tractable closed-form solutions, making approximation, statistical, and optimization errors difficult to control together.Existing approximation and statistical guarantees typically do not control the optimization error incurred by the training algorithm.Source: §1 · p. 2, §1.3 · p. 6

1.1. Main Contributions

  • The estimator provides high-probability uniform recovery without requiring an exact or approximate empirical-risk minimizer.The paper also gives an explicit ReLU-MLP realization on the stated Euclidean domains, avoiding a separate optimization-error term.Source: §1.1 · pp. 2–3
  • A split-sample formula locally averages labels near reference points, then takes the midpoint of upper and lower Lipschitz envelopes to estimate the target.The averaging step forms approximately noiseless effective training data before the central McShane–Whitney operation.Source: §1.1 · p. 3, §1.3 · p. 8

1.2. Secondary Contributions: Optimality of our Formula

  • For p∈{1, ∞}, the formula has an exact ReLU-MLP realization with depth O(log N), width O(N), and O(N) nonzero parameters.In the oracle setting, its uniform approximation bound is N^-1/d, matching the optimal exponent for continuous weight assignment.Source: §1.2 · p. 5
  • On compact d-Ahlfors-regular metric measure spaces, the realized class has fat-shattering dimension of optimal order (L/ε)^d at approximation scale ε.The stated order is necessary for any L-Lipschitz class uniformly approximating the bounded L-Lipschitz ball to accuracy ε.Source: §1.2 · p. 5
  • With oracle access to noiseless data, the parameter-to-realization map attains the Lipschitz-width benchmark up to a logarithmic factor.The comparison is among approximation families whose realization maps satisfy the prescribed Lipschitz-stability constraint.Source: §1.2 · p. 5

1.3. Related Research

  • Unlike, which computes an approximate minimizer, the metric-space guarantee applies directly to the displayed estimator; its ℓ1 and ℓ∞ specializations have exact sparse ReLU realizations.The introduction also distinguishes existence-only approximation results from implementable closed-form expressions with statistical guarantees.Source: §1.3 · p. 7

2. Preliminaries

The preliminaries establish metric-space notation and define the geometric and function-class concepts used in the analysis.

2.1. Notation

  • The paper equips finite or countable products with an additive metric that sums coordinate-wise distances.This convention measures perturbations of data clouds by summing coordinate changes.Source: §2.1 · pp. 8–9
  • A doubling space has a uniform bound on how many half-radius balls cover any ball; covering and packing numbers describe resolution-dependent observation and distinguishability.An ε-net covers the space at scale ε.Source: §2.1 · p. 9
  • A d-Ahlfors regular space has support equal to the whole space and volume growth bounded above and below by constants times the radius to power d.The paper describes this as a scale-invariant regime where covering and volume-growth dimensions agree.Source: §2.1 · p. 9
  • The unit Lipschitz model class consists of maps into [-1,1] whose output differences are bounded by input distance, and these classes use the uniform norm.The paper also introduces pointwise upper slope and a shorthand for classes on spaces with finite doubling dimension.Source: §2.1 · pp. 9–10

3. Reconstruction Guarantees

The section presents a split-sample closed-form estimator for uniform recovery, then relates its guarantees to noiseless and oracle-access settings and describes neural-network realizations and computational costs.

3. Reconstruction Guarantees

  • Theorem 3.2 gives a uniform-recovery guarantee from noisy samples, using separate reference and averaging blocks under the stated distributional assumptions.The assumptions include a compact metric space with full-support input distribution and integrable, centered noise satisfying a log-Sobolev inequality.Source: §3 · pp. 10–11

3.1. Discussion and Implications

  • The discussion distinguishes the paper’s no-oracle main setting from noiseless regression, where observations equal target values, and from approximation results that assume free target queries.The approximation setting also allows the user to choose model parameters freely.Source: §3.1 · p. 11, §3.1.1 · p. 11, §3.1.2 · p. 12

3.1.1. The Noiseless nonparametric regression setting.

  • In noiseless regression, the formula applies the central McShane–Whitney extension construction directly to raw observation pairs; its guarantee is uniform closeness to the target, not merely a classical risk bound.The central midpoint coincides with the estimator in [67, Lemma 7] when its mixing constant is set to 1.Source: §3.1.1 · pp. 11–12

3.1.2. The classical approximation setting: Oracle Access to the target function.

  • With oracle access on a compact doubling space of diameter at most 1, Proposition 3.4 gives an approximation result for Lipschitz functions using freely queried target values.The setting also permits freely chosen model parameters.Source: §3.1.2 · p. 12

3.2. ReLU-Neural Network Realizations over R𝒅

  • For Euclidean inputs with the ℓ1 or ℓ∞ metric, the formula has a ReLU-MLP realization with logarithmic depth and linear width and nonzero neurons; the transformer statement embeds the preceding MLP realization.The MLP realization is constructed algorithmically, and the stated hidden constants depend only on dimension.Source: §3.2 · pp. 13–14
  • On [0,1]^d with the ℓ∞ metric for d≥2, the formula requires O(N^2) storage and worst-case O(N^2) forward-pass evaluation because of its neighborhood matrix.A range tree can be built in O(N log^(d−1)(N)) time, but reporting the neighborhood graph may still involve O(N^2) edges in the worst case.Source: §3.2.1 · p. 14

3.2.1. Comparison: Complexity of Our Formula Vs. Exact KRR.

  • Exact KRR requires solving a linear system with an N×N kernel matrix, with algebraic complexity O(N^p) for some 2≤p<2.372; when p>2, the formula has a smaller worst-case asymptotic exponent.Dense LU implementations classically cost O(N^3), while iterative KRR methods offer a separate comparison.Source: §3.2.1 · p. 14

4. Optimality Guarantees

The section assesses the formula’s optimality through forward-pass regularity, ReLU-MLP approximation and complexity, and stable parameterization. It also discusses how Lipschitz-width benchmarks differ from other notions of nonlinear approximation.

4.1. Prescribed Lipschitz Regularity of the Forward Pass

  • Every parameter choice has a forward-pass Lipschitz constant at most the envelope slope parameter L.Proposition 4.1 states this bound for the estimator in the setting of Theorem 3.2.Source: §4.1 · p. 15

4.2. Parametric Complexity of the ReLU-MLP Realization on R𝒅

  • O(N) nonzero ReLU-MLP parameters achieve O(N^-1/d) approximation, matching the optimal continuous-weight-assignment exponent.The passage contrasts this sparse realization with a comparably wide fully connected architecture that may use up to O(N^2 log N) parameters.Source: §4.2 · p. 16
  • The ReLU-MLP is constructed directly from noisy i.i.d. samples, without oracle evaluations of f or optimization over network weights.The guarantee does not require identifying an exact or sufficiently accurate approximate empirical-risk minimizer.Source: §4.2 · p. 16

4.3. Complexity: Realized Function Class

  • On compact d-Ahlfors-regular metric spaces, Theorem 4.6 establishes optimal fat-shattering dimension at the approximation scale.Uniformly approximating the bounded L-Lipschitz ball at resolution ε requires complexity of order ε^-d.Source: §4.3 · p. 18

4.4. Complexity: Parameter-to-Realization

  • In the oracle regime, the parameter-to-function map is γ_d-Lipschitz, and the formula attains the Lipschitz-width rate up to logarithmic factors.Theorem 4.8 evaluates the formula against a benchmark that imposes stability on the realization map.Source: §4.4 · p. 19

4.4.1. Discussion: Other Notions of Optimal Nonlinear Approximation.

  • Lipschitz widths constrain stability of the realization map, whereas stable manifold widths require stability of both encoder and decoder.The discussion contrasts these stability requirements with approximation notions that do not control parameter-to-function conditioning.Source: §4.4.1 · p. 20

5. Applications

The applications extend the formula to targets with weaker continuity moduli and to permutation-invariant point-cloud inputs. They establish approximation with prescribed regularity for both settings.

5.1. Guidance on Choice of Activation Function for Low-Regularity Problems

  • A concave modulus ω transforms the metric to ρω = ω∘ρ, making ω-uniform continuity equivalent to 1-Lipschitz continuity under the transformed metric.The usual snowflake metric ρα is recovered by choosing ω(t) = t^α.Source: §5.1 · p. 20
  • For compact metric spaces and suitable concave, continuous, strictly increasing moduli, the formula approximates ω-uniformly continuous functions while preserving ω-uniform continuity.Corollary 5.1 gives approximation to every ε > 0 by a model with a suitable finite number of terms.Source: §5.1 · p. 21

5.2. Universality of DeepSets with Prescribed Lipschitz Regularity

  • A structured subclass of DeepSets approximates L-Lipschitz functions on the feature-mean embedding space with prescribed regularity.The construction admits an exact ReLU-MLP realization of depth O(log F + log M) and O(MF) width and nonzero parameters.Source: §5.2 · pp. 21–22

6. Numerical Ablations

The numerical section illustrates noiseless reconstructions, compares the closed-form estimator with ReLU MLPs, and examines noisy recovery as noise and target frequency vary. It also notes that the experiments use an all-sample implementation rather than the estimator covered by the finite-sample guarantee.

6. Numerical Ablations

  • The experiments use every training input as a reference point and average labels from its β-neighbourhood, whereas the theorem covers split-sample, fixed-cardinality estimation.With hold-out bandwidth selection, the theoretical choice β=ε/2 is not used.Source: §6 · p. 23

6.1. Closed-Form Reconstruction on R

  • The one-dimensional noiseless illustration compares the target, the lower and upper envelopes, and their midpoint estimator.It uses 50 or 100 uniformly sampled points and sets the estimator’s Lipschitz constant to 1.05 times the empirical estimate.Source: §6.1 · p. 23, Figure 6.2 · p. 24

6.2. Closed-Form Reconstruction on R2

6.3. Comparison with a Vanilla ReLU MLP

  • Both methods achieve small test MSE, with MLP baselines attaining lower error and the closed-form estimator’s empirical Lipschitz constant closer to the target value 1.The closed-form estimator maintains competitive predictive accuracy while offering controlled regularity and explicit construction.Source: §6.3 · p. 26

6.4. Closed-Form Reconstruction on R in the Noisy Case

  • The noisy one-dimensional study compares a ReLU MLP and the noisy universal formula using clean test MSE against the ground truth.Both methods train on noisy labels; the study uses 2,000 training and 2,000 test samples and averages over 10 seeds.Source: §6.4 · pp. 26–27, Figure 6.6 · p. 27
  • As observation noise increases, the selected bandwidth tends to increase, strengthening local averaging before the Lipschitz extension.Figure 6.7 reports the mean selected bandwidth over 10 runs, with one-standard-deviation error bars.Source: §6.4 · p. 27, Figure 6.7 · p. 28
  • As target frequency increases at fixed noise σ=0.1, the selected bandwidth generally decreases to avoid oversmoothing rapidly varying signals.The reported mean and standard deviation are over 10 independent runs.Source: §6.4 · pp. 28–29

7. Conclusion

The paper presents a closed-form estimator for Lipschitz regression on general metric spaces, with high-probability uniform recovery and no need for an exact or approximate ERM. It also reports complementary complexity, stability, regularity, and realization results.

7. Conclusion

  • The split-sample McShane–Whitney estimator gives high-probability uniform recovery and attains the minimax Euclidean polynomial exponent up to logarithmic factors without an exact or approximate ERM.On covered Euclidean domains, it has an exact sparse ReLU-MLP realization with explicitly assigned weights and no separate optimization-error term.Source: §7 · p. 29
  • The formula has prescribed L-Lipschitz forward regularity, optimal-order fat-shattering complexity at the stated approximation scale, and near-minimax Lipschitz-width parameterization up to logarithmic factors in the oracle regime.These results concern distinct properties: input regularity, function-class complexity, and parameterization stability.Source: §7 · p. 29
  • The conclusion distinguishes the theorem’s split-sample, fixed-cardinality estimator from the all-sample implementation evaluated in Section 6.The stated recovery guarantee applies to the former.Source: §7 · p. 29

A. Additional Technical Background

The appendix gathers technical definitions and notation for use in later proofs.

A. Additional Technical Background

  • The appendix’s definitions and notation are described as nonessential to the main exposition but useful for the following proofs.The supplied passage does not specify individual definitions.Source: A. Additional Technical Background · p. 30

B. Proofs

The proofs use symmetry to handle envelope arguments and establish uniform approximation in the noiseless case, first for a deterministic net and then for random samples.

B. Proofs

  • The envelope arguments are written for the lower envelope, with symmetry extending conclusions preserved under convex combinations to the upper envelope and central midpoint.The upper envelope follows by replacing V and f with their negatives.Source: B. Proofs · p. 30
  • Using both envelopes sharpens the central-midpoint approximation bound, whose worst-case expression is minimized at α=1/2.The stated bound is Δ + 2 max{α, 1−α}Lη, minimized to Δ + Lη.Source: B. Proofs · p. 31

B.1. Step 1: estimator in the Noiseless Case

  • For noiseless data, an ε/2-net gives a uniform approximation error of at most ε for the lower-envelope estimator.The pointwise estimates use the target’s 1-Lipschitz property and the existence of a net point within ε/2.Source: §B.1 · p. 33
  • The randomized noiseless argument combines a high-probability sample-coverage event with the deterministic uniform-approximation result.The supplied proof passages describe coverage of a compact metric space by i.i.d. samples and then invoke the net-based bound.Source: §B.1 · pp. 32–34

B.2. Step 2: Analysis Of Whitney-McShane with Noisy Measurements

The analysis controls noisy Whitney–McShane reconstruction with concentration bounds, but the unaveraged estimator remains sensitive to extreme measurement errors. Local averaging is introduced to reduce measurement noise before applying the reconstruction formula.

B.2.2. Completing The Argument: Non-Robust Version (Proposition B.2).

  • The non-robust estimator can be dominated by the maximum measurement error, including unlikely large errors.Source: §B.2 · p. 34

B.2. Step 2: Analysis Of Whitney-McShane with Noisy Measurements

  • Local averaging of nearby outputs is introduced to cancel measurement noise before applying the Whitney–McShane formula.Source: §B.2 · p. 34
  • In the noisy case, an ε/2-net event supports a uniform approximation bound for the Whitney–McShane estimator.Source: §B.2 · p. 36

B.2.1. Controlling the Fluctuations 𝚵𝑵.

  • Under centered log-Sobolev noise, the analysis establishes a high-probability bound on noise propagation through the estimator.Source: §B.2.1 · p. 37

B.3. neighbourhood-averaging: Robustification

The section robustifies Whitney–McShane reconstruction by averaging nearby noisy observations and proves a split-sample uniform-recovery rate. It also relates that rate to minimax theory and identifies the scope of the comparison.

B.3. neighbourhood-averaging: Robustification

  • With η-net centers and values within Δ of the target, the midpoint of the central envelopes has uniform error at most Δ + Lη.Source: §B.3 · pp. 39–40
  • The split-sample construction uses the first N0 observations as references and the remaining N1 observations to average at least qε nearby outputs within bandwidth β.Source: §B.3 · p. 41

B.5. Proofs of Optimality

  • The rate exponent matches the classical minimax sup-norm exponent in finite-dimensional Euclidean settings up to logarithmic factors, but no matching lower bound is claimed for the full metric-space class.Source: §B.3 · p. 41

B.3. neighbourhood-averaging: Robustification

  • N^-1/(s+2)√log N bounds the uniform error with high probability for sufficiently large N under the stated assumptions.Source: §B.3 · p. 46

B.4. Step 3: Graph Realization

  • The midpoint estimator in (B.19) is 1-Lipschitz for every sample realization and is identified with the formula in (1.2).Source: §B.4 · p. 48

B.5.1. Proof of Combinatorial Optimality.

The section proves combinatorial optimality of the realized class on compact Ahlfors-regular spaces. Its fat-shattering dimension matches the scale required by uniform approximation of Lipschitz functions.

B.5.1. Proof of Combinatorial Optimality.

  • The lower-bound argument applies when every bounded L-Lipschitz function can be uniformly approximated by a member of F to a fixed tolerance.Source: §B.5.1 · p. 48
  • For every sign pattern on the constructed points, an approximating function in F preserves the labeling needed for fat-shattering.Source: §B.5.1 · p. 49
  • The proof establishes matching lower and upper bounds for fat_ε(F) using Ahlfors-regular packing and the Lipschitz-class upper bound.Source: §B.5.1 · p. 49

B.6. Proof of Optimal Parameter-Dependence

This section analyzes the parameterized reconstruction formulas, establishing their approximation and stability properties alongside input regularity, realizations, and recovery consequences. It also presents example constructions and numerical experiment setups.

B.6. Proof of Optimal Parameter-Dependence.

  • For n=1, the user-selectable setting yields a minimax-optimal reconstruction formula, up to a polylog factor with sampled data and no oracle access.Source: §B.6 · p. 50

B.6.1. Step 1: Optimal Approximation with Oracle-Access to 𝒇.

  • With oracle function values on an ε-net, the midpoint of the McShane and Whitney envelopes approximates every 1-Lipschitz function within ε.The net construction uses a totally bounded space of diameter at most 1 and doubling dimension at most d.Source: §B.6.1 · pp. 50–51

B.6.2. Step 2: Stability of an Optimal Function to Parameter Map.

  • The parameter-to-function map is 1-Lipschitz on the realizable parameter set [−1,1] × X × {1} when diam(X) ≤ 1.More generally, the encoder is max{1, R, diam(X)}-Lipschitz on the stated bounded parameter domain.Source: §B.6.2 · p. 51, §B.6.4 · p. 58

B.6.3. Step 3: Identifying “Good” Lower Bounds on the Lipschitz Widths.

  • On d-Ahlfors-regular spaces, the 1-Lipschitz function class has metric entropy scaling Θ(ε^-d), and the formula matches its Lipschitz widths up to polylogarithmic factors.In the intrinsic metric-space parametrization, the design centers are fixed and the N labels are the only free real parameters.Source: §B.6.3 · pp. 52, 57, §B.6.4 · p. 57

B.6.4. Step 4: Matching the Lower Bounds.

  • The formula is optimal up to a logarithmic factor: no γ_d-Lipschitz scheme with P_N real parameters improves the stated lower bound, while the construction achieves error C_dP_N^-1/d.The lower-bound comparison is established for compact d-Ahlfors-regular metric measure spaces.Source: §B.6.4 · p. 58

B.6.5. Proof of Optimal Regularity.

  • The reconstruction formula has Lipschitz constant at most 1 as a function of the input.The proof applies the 1-Lipschitz property of the distance functions and preservation of Lipschitz bounds under minima, maxima, and averaging.Source: §B.6.5 · p. 58

B.6.6. Proofs of Parametric Optimality.

  • The formula has an exact ReLU-MLP realization of depth O(log(N)) and width and size O(N); stated p-norm approximation and Lipschitz bounds also follow.For 1 ≤ p ≤ 2 and 2 < p ≤ ∞, the proof obtains the corresponding bounds using tensor grids and the stated propositions.Source: §B.6.6 · p. 59
  • An exact ReLU-MLP realization has depth O(log N) and O_d(N) nonzero parameters, with the probabilistic uniform-recovery estimate inherited from (3.3).The realization uses N0 ≤ N.Source: §B.6.6 · p. 59

B.6.7. Proofs of Parametric Optimality.

  • Parallelized distance maps and a logarithmic-depth max network yield an exact ReLU-MLP realization of depth O(log N), width and size O(N), inheriting Theorem 3.2's probabilistic estimate.The distance maps have constant depth and O(d) nonzero parameters; the max network has depth at most ⌈log2 N⌉, width at most 3N, and size at most 16N.Source: §B.6.7 · pp. 59–60

B.7. Proofs of Examples

  • On compact (X, rho_omega), the Whitney-McShane midpoint formula approximates f within epsilon and remains 1-Lipschitz under rho_omega.It is constructed using a finite epsilon/2-net.Source: §B.7 · p. 60
  • For an injective feature map T_phi, the induced metric d_phi supports epsilon-approximation of f by an L-Lipschitz formula with an exact ReLU-MLP realization.The setting assumes (K, d_phi) is compact.Source: §B.7 · p. 60

B.1. Closed-Form Reconstruction on R: Different 𝑵train

  • The reconstruction figures show noiseless samples with the Whitney and McShane bounds and their midpoint estimator, and examples using N_train=50, 100, and 1000 with the ℓ2 metric.Figure 2.11 depicts reconstruction on [−1, 1]; Figures 2.12–2.14 describe examples on [−1, 1]^2.Source: Figure 2.11 · p. 61, Figure 2.12 · p. 62, Figure 2.13 · p. 62

B.3. Gradient Descent Recovery: 1-Dimensional Function

  • The noiseless 1-D experiment tests gradient descent initialized near theta-star at N=1000, lambda=1, eta=0.001, tracking loss, parameter error, training residual, and function error across three initialization gaps.L is chosen as a strict empirical Lipschitz upper bound estimated from training data and slightly inflated to ensure a positive empirical Lipschitz margin.Source: §B.3 · pp. 61–62

C. Deep learning architectures

The section defines MLP and multi-head transformer layers, then gives a canonical construction that realizes every ReLU MLP exactly as a transformer. The construction preserves depth and nonzero affine parameter count while bounding the transformer’s hidden width.

C. Deep learning architectures

  • A fully connected MLP applies affine maps and an activation function iteratively, with each layer’s matrix and bias determining its transformation.The affine map uses a weight matrix and bias vector, followed by component-wise activation.Source: C. Deep learning architectures · p. 63
  • A transformer layer applies a row-wise activation–bias map followed by multi-head attention, mapping an input matrix to the next layer’s representation.The transformer is formed by iterating these layers.Source: C. Deep learning architectures · pp. 63–64
  • Every depth-L ReLU MLP can be implemented exactly by a depth-L ReLU transformer with H heads, width at most W+H−1, and at most K nonzero affine parameters.Here W is the MLP hidden width and K its nonzero affine-parameter count.Source: C. Deep learning architectures · pp. 65, 67
  • The conversion adds H−1 coordinates at hidden layers and uses zero padding and zero-valued extra heads to retain the MLP’s nonzero-parameter count.The first head carries the layer’s value dimension; each remaining head has value dimension one.Source: C. Deep learning architectures · pp. 65–67
Loading 2609.03129v1…