Resolution-Consistent Greedy Neural Approximation on Infinite-Dimensional Spaces

# Resolution-Consistent Greedy Neural Approximation on Infinite-Dimensional Spaces
Source: [https://arxiv.org/html/2608.20812](https://arxiv.org/html/2608.20812)
Pablo M\. BernáAffiliation:Universidad Tecnológica Atlántico Mediterráneo – UTAMED Facultad de Empresa Digital, Tecnología y Derecho Málaga, España pablomanuel\.berna@utamed\.esAntonio FalcóAffiliation:Departamento de Matemáticas, Física y Ciencias Tecnológicas Universidad Cardenal Herrera\-CEU, CEU Universities San Bartolomé 55, Alfara del Patriarca \(Valencia\), 46115, Spain afalco@uchceu\.esDiego Mondéjar

###### Abstract

We develop constructive approximation and learning guarantees for shallow neural models with infinite\-dimensional inputs observed through finitely many coordinates\. The analysis is based on a parameter\-normalized neural dictionary and its associated weighted variation class\. Within this class, the approximation error separates into a distribution\-dependent coordinate\-truncation term and a greedy finite\-width term\. For empirical regression, a fully\-corrective greedy procedure yields population guarantees whose statistical complexity is uniform in the retained input resolution\. The same framework extends to Hilbert\-valued responses without an explicit dependence on the output dimension\. The dimension\-free statements are statistical, not computational: selecting a new neuron still requires solving a nonconvex parameter\-search problem\. The quasi\-Polish construction underlying recent infinite\-dimensional universal approximation results provides a motivating example, and synthetic experiments illustrate the predicted resolution, width, and sample\-size regimes\.

## 1Introduction

Many learning problems are naturally formulated on inputs that are not finite\-dimensional vectors\. Functional observations, trajectories, fields, probability measures, and solutions of partial differential equations are more naturally regarded as elements of infinite\-dimensional spaces\. Neural approximation in this setting raises a difficulty that is largely absent in standard finite\-dimensional learning: before a model can be trained, the input itself must usually be represented at a finite resolution\.

This leads to three distinct sources of error\. First, only finitely many coordinates or measurements of an infinite\-dimensional input can be retained\. Second, the approximating neural network has finite width\. Third, the network must be learned from finitely many observations\. A natural quantitative theory should therefore explain how approximation and learning depend simultaneously on the input resolution, the number of selected neurons, and the sample size\.

Recent work of Galimberti\[[6](https://arxiv.org/html/2608.20812#bib.bib6)\]establishes globalLpL^\{p\}universal approximation results for suitable neural architectures on infinite\-dimensional and quasi\-Polish spaces\. These results provide an important qualitative foundation: after representing the input through a countable family of scalar observables, finite neural models can approximate broad classes of target maps\. Universal approximation, however, is a density statement\. It does not by itself provide a constructive rule for choosing the neurons, a convergence rate in the network width, or a statistical guarantee when the network is trained from finite data\.

The purpose of this paper is to develop such a quantitative theory for a regularity class adapted to greedy neural approximation\. We assume that the input admits a countable coordinate representation whose magnitudes are controlled by a square\-summable envelope\. A finite\-resolution learner retains only the first finitely many coordinates\. The resulting loss of information is measured by the mean\-square size of the discarded tail under the data distribution\. This formulation is deliberately more general than the quasi\-Polish setting: the latter becomes an important application rather than an assumption of the main theory\.

To construct the approximating network, we use greedy selection\. Starting from the current residual, the algorithm repeatedly searches for a neural unit that is strongly correlated with what remains unexplained\. At the population level this leads to a direct decomposition of the approximation error into a resolution term and a finite\-width term\. At the empirical level we use a fully\-corrective version of the greedy procedure, closely related to conditional\-gradient methods, in order to keep the complexity of the successive approximants under control\.

A central role is played by a parameter\-weighted variation class\. Roughly speaking, neural units with large internal parameters are assigned a larger cost, and the target is assumed to admit a representation with finite total weighted cost\. This normalization is what allows the same regularity quantity to control both approximation under coordinate truncation and statistical complexity\. It is important, however, that this is a genuine regularity assumption\. Although normalization does not change the linear span generated by the neural units, it does change bounded variation classes\. Our results therefore provide rates for an explicit weighted neural class; they should not be interpreted as quantitative rates for every target covered by the underlying universal approximation theorem\. We make this distinction precise later and show, through a one\-dimensional threshold example, that the weighted and unweighted classes can behave very differently\.

The main statistical phenomenon is that finer input resolution does not necessarily lead to a larger estimation penalty\. A naive finite\-dimensional analysis might suggest a complexity term increasing with the number of retained coordinates\. Instead, the coordinate representations considered here remain uniformly bounded in a common Hilbert space\. Exploiting this geometry, together with the parameter normalization, gives a Rademacher complexity estimate that is uniform in the input resolution\. Consequently, the final population bound separates into three contributions:

resolution error\+finite\-width error\+statistical error,\\text\{resolution error\}\\;\+\\;\\text\{finite\-width error\}\\;\+\\;\\text\{statistical error\},where the statistical contribution has no explicit dependence on the number of retained input coordinates\. In the quasi\-Polish example motivating the paper, the first two contributions exhibit the familiar inverse\-resolution and inverse\-width behavior, while the statistical term has the standard square\-root dependence on sample size, up to logarithmic factors\.

This resolution independence is statistical rather than computational\. Selecting the next neural unit still requires solving a nonconvex optimization problem over its parameters, and the cost of that search may increase with the retained resolution\. Similar computational difficulties occur in convex infinite\-width neural formulations\[[1](https://arxiv.org/html/2608.20812#bib.bib1)\]\. The experiments in this paper therefore use a finite candidate dictionary\. Their purpose is to illustrate separately the resolution, width, and sampling effects predicted by the theory, rather than to claim an efficient solution of the continuous neuron\-selection problem\.

Our analysis builds on several established ideas\. Greedy approximation and its connection with statistical learning have a long history\[[2](https://arxiv.org/html/2608.20812#bib.bib2)\]; variation\-space formulations and conditional\-gradient methods for shallow neural networks were developed, among others, by Bach\[[1](https://arxiv.org/html/2608.20812#bib.bib1)\]; and recent work gives refined analyses of orthogonal greedy algorithms and neural variation spaces\[[17](https://arxiv.org/html/2608.20812#bib.bib17),[16](https://arxiv.org/html/2608.20812#bib.bib16)\]\. The contribution here is not a new greedy principle or a new empirical\-process inequality\. Rather, it is an end\-to\-end analysis showing how these tools interact with finite\-resolution observation of an infinite\-dimensional input\.

More specifically, the paper makes the following contributions:

1. \(i\)We formulate finite\-resolution neural approximation under minimal measurability assumptions and quantify the information lost by truncating an infinite\-dimensional coordinate representation\.
2. \(ii\)We introduce a parameter\-weighted neural variation class and prove constructive greedy approximation bounds that separate the effects of input resolution and network width\.
3. \(iii\)We prove a Rademacher complexity bound for the normalized neural dictionary that is uniform in the retained input resolution, and combine it with a fully\-corrective greedy procedure to obtain an end\-to\-end population risk guarantee\.
4. \(iv\)We quantify the additional regularity imposed by the weighted class through a Lipschitz lower bound and a sharp one\-dimensional threshold example\.
5. \(v\)We extend the statistical argument to Hilbert\-valued responses without introducing an explicit dependence on either the retained input dimension or the output dimension in the statistical term\.
6. \(vi\)We provide reproducible synthetic experiments that isolate the resolution, width, and sample\-size regimes and illustrate the distinction between weighted and unweighted variation constraints\.

The remainder of the paper is organized as follows\. Section[2](https://arxiv.org/html/2608.20812#S2)introduces the coordinate representation and the notion of resolution error\. The following sections define the weighted neural variation class and establish the deterministic greedy approximation results\. We then study empirical complexity and the fully\-corrective learning procedure, followed by the numerical experiments\. Finally, Section[10](https://arxiv.org/html/2608.20812#S10)treats Hilbert\-valued responses before the discussion and conclusion\.

## 2Minimal measurable setting

###### Assumption 2\.1\(Measurable coordinate embedding\)\.

Let\(𝒳,𝒜,μ\)\(\\mathcal\{X\},\\mathcal\{A\},\\mu\)be a probability space\. Lethj:𝒳→ℝh\_\{j\}:\\mathcal\{X\}\\to\\mathbb\{R\},j≥1j\\geq 1, be measurable and assume that there existsα=\(αj\)j≥1∈ℓ2\\alpha=\(\\alpha\_\{j\}\)\_\{j\\geq 1\}\\in\\ell^\{2\}such that

\|hj​\(x\)\|≤αjfor all​j≥1​and​x∈𝒳\.\|h\_\{j\}\(x\)\|\\leq\\alpha\_\{j\}\\qquad\\text\{for all \}j\\geq 1\\text\{ and \}x\\in\\mathcal\{X\}\.Define

H⁡\(x\):=\(h1​\(x\),h2​\(x\),…\)∈ℓ2,HN​\(x\):=PN​H​\(x\),H\(x\):=\(h\_\{1\}\(x\),h\_\{2\}\(x\),\\ldots\)\\in\\ell^\{2\},\\qquad H\_\{N\}\(x\):=P\_\{N\}H\(x\),wherePNP\_\{N\}is the orthogonal projection onto the firstNNcanonical coordinates\.

Two coordinate\-tail quantities will be useful\. The distribution\-dependent tail is

ηN​\(μ\):=\(∫𝒳‖\(I−PN\)​H​\(x\)‖ℓ22​𝑑μ​\(x\)\)1/2,\\eta\_\{N\}\(\\mu\):=\\left\(\\int\_\{\\mathcal\{X\}\}\\left\\lVert\(I\-P\_\{N\}\)H\(x\)\\right\\rVert\_\{\\ell^\{2\}\}^\{2\}\\,d\\mu\(x\)\\right\)^\{1/2\},\(1\)while the uniform tail is

ηN∞:=supx∈𝒳‖\(I−PN\)​H​\(x\)‖ℓ2\.\\eta\_\{N\}^\{\\infty\}:=\\sup\_\{x\\in\\mathcal\{X\}\}\\left\\lVert\(I\-P\_\{N\}\)H\(x\)\\right\\rVert\_\{\\ell^\{2\}\}\.\(2\)By Assumption[2\.1](https://arxiv.org/html/2608.20812#S2.Thmtheorem1),

ηN​\(μ\)≤ηN∞≤\(∑j\>Nαj2\)1/2\.\\eta\_\{N\}\(\\mu\)\\leq\\eta\_\{N\}^\{\\infty\}\\leq\\left\(\\sum\_\{j\>N\}\\alpha\_\{j\}^\{2\}\\right\)^\{1/2\}\.\(3\)
We incorporate the bias as an additional Hilbert coordinate\. Let

𝒫:=ℓ2⊕ℝ,θ=\(w,b\)∈𝒫,‖θ‖𝒫:=‖w‖ℓ22\+b2,\\mathcal\{P\}:=\\ell^\{2\}\\oplus\\mathbb\{R\},\\qquad\\theta=\(w,b\)\\in\\mathcal\{P\},\\qquad\\left\\lVert\\theta\\right\\rVert\_\{\\mathcal\{P\}\}:=\\sqrt\{\\left\\lVert w\\right\\rVert\_\{\\ell^\{2\}\}^\{2\}\+b^\{2\}\},and define

Z⁡\(x\):=\(H⁡\(x\),1\),ZN​\(x\):=\(HN​\(x\),1\)\.Z\(x\):=\(H\(x\),1\),\\qquad Z\_\{N\}\(x\):=\(H\_\{N\}\(x\),1\)\.The envelope gives the uniform radius

K:=supx‖Z⁡\(x\)‖𝒫≤1\+‖α‖ℓ22,K:=\\sup\_\{x\}\\left\\lVert Z\(x\)\\right\\rVert\_\{\\mathcal\{P\}\}\\leq\\sqrt\{1\+\\left\\lVert\\alpha\\right\\rVert\_\{\\ell^\{2\}\}^\{2\}\},\(4\)and‖ZN​\(x\)‖𝒫≤K\\left\\lVert Z\_\{N\}\(x\)\\right\\rVert\_\{\\mathcal\{P\}\}\\leq Kfor everyNN\.

### 2\.1The quasi\-Polish construction as an example

The topological assumptions used by Galimberti are not required for the estimates below\. They become relevant when one wants to connect the class to a global density theorem\. In the quasi\-Polish construction of\[[6](https://arxiv.org/html/2608.20812#bib.bib6)\], a continuous separating sequence can be scaled so that

0≤hj​\(x\)≤1j\.0\\leq h\_\{j\}\(x\)\\leq\\frac\{1\}\{j\}\.Consequently,

ηN​\(μ\)2≤\(ηN∞\)2≤∑j\>N1j2≤1N,K≤1\+π26\.\\eta\_\{N\}\(\\mu\)^\{2\}\\leq\(\\eta\_\{N\}^\{\\infty\}\)^\{2\}\\leq\\sum\_\{j\>N\}\\frac\{1\}\{j^\{2\}\}\\leq\\frac\{1\}\{N\},\\qquad K\\leq\\sqrt\{1\+\\frac\{\\pi^\{2\}\}\{6\}\}\.\(5\)The separating property is used later only to explain density of the union of weighted balls; it is not used in the quantitative proofs\.

## 3Normalized neural atoms and weighted variation

We use the bounded11\-Lipschitz activation

ρ⁡\(t\):=t\+1\+t\+,t\+:=max⁡\{t,0\}\.\\rho\(t\):=\\frac\{t\_\{\+\}\}\{1\+t\_\{\+\}\},\\qquad t\_\{\+\}:=\\max\\\{t,0\\\}\.\(6\)Thus0≤ρ≤10\\leq\\rho\\leq 1,ρ⁡\(0\)=0\\rho\(0\)=0, and\|ρ⁡\(s\)−ρ⁡\(t\)\|≤\|s−t\|\|\\rho\(s\)\-\\rho\(t\)\|\\leq\|s\-t\|\. Moreover,

limλ→∞ρ⁡\(λ​t\)=\{1,t\>0,0,t≤0,\\lim\_\{\\lambda\\to\\infty\}\\rho\(\\lambda t\)=\\begin\{cases\}1,&t\>0,\\\\ 0,&t\\leq 0,\\end\{cases\}so the associated rank\-one infinite\-dimensional activation has the separating behavior used in\[[6](https://arxiv.org/html/2608.20812#bib.bib6)\]\.

Forθ=\(w,b\)\\theta=\(w,b\)define

gθ​\(x\):=ρ⁡\(⟨θ,Z⁡\(x\)⟩𝒫\)=ρ⁡\(b\+⟨w,H⁡\(x\)⟩ℓ2\),g\_\{\\theta\}\(x\):=\\rho\(\\left\\langle\\theta,Z\(x\)\\right\\rangle\_\{\\mathcal\{P\}\}\)=\\rho\(b\+\\left\\langle w,H\(x\)\\right\\rangle\_\{\\ell^\{2\}\}\),and

gθ,N​\(x\):=ρ⁡\(⟨θ,ZN​\(x\)⟩𝒫\)\.g\_\{\\theta,N\}\(x\):=\\rho\(\\left\\langle\\theta,Z\_\{N\}\(x\)\\right\\rangle\_\{\\mathcal\{P\}\}\)\.
###### Definition 3\.1\(Parameter\-normalized atoms\)\.

Let

c⁡\(θ\):=1\+‖θ‖𝒫\.c\(\\theta\):=1\+\\left\\lVert\\theta\\right\\rVert\_\{\\mathcal\{P\}\}\.Define

ψθ​\(x\):=gθ​\(x\)c⁡\(θ\),ψθ,N​\(x\):=gθ,N​\(x\)c⁡\(θ\),\\psi\_\{\\theta\}\(x\):=\\frac\{g\_\{\\theta\}\(x\)\}\{c\(\\theta\)\},\\qquad\\psi\_\{\\theta,N\}\(x\):=\\frac\{g\_\{\\theta,N\}\(x\)\}\{c\(\\theta\)\},\(7\)and the symmetric finite\-resolution dictionary

𝒟N♯:=\{±ψθ,N:θ∈𝒫\}\.\\mathcal\{D\}\_\{N\}^\{\\sharp\}:=\\\{\\pm\\psi\_\{\\theta,N\}:\\theta\\in\\mathcal\{P\}\\\}\.\(8\)

Because0≤ρ≤10\\leq\\rho\\leq 1,

\|ψθ,N​\(x\)\|≤11\+‖θ‖𝒫≤1\.\|\\psi\_\{\\theta,N\}\(x\)\|\\leq\\frac\{1\}\{1\+\\left\\lVert\\theta\\right\\rVert\_\{\\mathcal\{P\}\}\}\\leq 1\.\(9\)The normalization preserves the linear span,

span⁡\{ψθ:θ∈𝒫\}=span⁡\{gθ:θ∈𝒫\},\\operatorname\{span\}\\\{\\psi\_\{\\theta\}:\\theta\\in\\mathcal\{P\}\\\}=\\operatorname\{span\}\\\{g\_\{\\theta\}:\\theta\\in\\mathcal\{P\}\\\},\(10\)but this fact must not be confused with preservation of fixed variation balls\.

###### Definition 3\.2\(Unweighted and weighted variation norms\)\.

Let𝔐⁡\(f\)\\mathfrak\{M\}\(f\)be the collection of finite signed Borel measuresν\\nuon𝒫\\mathcal\{P\}such that

f⁡\(x\)=∫𝒫gθ​\(x\)​𝑑ν​\(θ\)for​μ​\-a\.e\.​x\.f\(x\)=\\int\_\{\\mathcal\{P\}\}g\_\{\\theta\}\(x\)\\,d\\nu\(\\theta\)\\qquad\\text\{for \}\\mu\\text\{\-a\.e\. \}x\.\(11\)Define the unweighted variation seminorm

‖f‖ℬH:=infν∈𝔐⁡\(f\)\|ν\|​\(𝒫\),\\left\\lVert f\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}\}:=\\inf\_\{\\nu\\in\\mathfrak\{M\}\(f\)\}\|\\nu\|\(\\mathcal\{P\}\),\(12\)and the weighted norm

‖f‖ℬH♯:=infν∈𝔐⁡\(f\)∫𝒫\(1\+‖θ‖𝒫\)​d​\|ν\|​\(θ\)\.\\left\\lVert f\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\}:=\\inf\_\{\\nu\\in\\mathfrak\{M\}\(f\)\}\\int\_\{\\mathcal\{P\}\}\(1\+\\left\\lVert\\theta\\right\\rVert\_\{\\mathcal\{P\}\}\)\\,d\|\\nu\|\(\\theta\)\.\(13\)The classℬH♯\\mathcal\{B\}\_\{H\}^\{\\sharp\}consists of functions with finite weighted norm\.

Sincec⁡\(θ\)≥1c\(\\theta\)\\geq 1,

‖f‖ℬH≤‖f‖ℬH♯\.\\left\\lVert f\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}\}\\leq\\left\\lVert f\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\}\.\(14\)Thus every radius\-VVweighted ball is contained in the corresponding unweighted ball\. The normalization is therefore not free: it preserves the span but imposes additional regularity on quantitative approximation and learning statements\.

Ifν∈𝔐⁡\(f\)\\nu\\in\\mathfrak\{M\}\(f\)has finite weighted cost, define the signed measureλ\\lambdabyd​λ=c​d​νd\\lambda=c\\,d\\nuin polar form\. Then

f⁡\(x\)=∫𝒫ψθ​\(x\)​𝑑λ​\(θ\),\|λ\|​\(𝒫\)=∫c⁡\(θ\)​d​\|ν\|​\(θ\)\.f\(x\)=\\int\_\{\\mathcal\{P\}\}\\psi\_\{\\theta\}\(x\)\\,d\\lambda\(\\theta\),\\qquad\|\\lambda\|\(\\mathcal\{P\}\)=\\int c\(\\theta\)\\,d\|\\nu\|\(\\theta\)\.\(15\)This is the representation used throughout the proofs\. Related parameter\-measure and Barron\-space viewpoints are developed in, for example,\[[5](https://arxiv.org/html/2608.20812#bib.bib5)\]\.

###### Proposition 3\.3\(Weighted variation controls the embedding Lipschitz seminorm\)\.

Define the pseudometric

dH​\(x,y\):=‖H⁡\(x\)−H⁡\(y\)‖ℓ2\.d\_\{H\}\(x,y\):=\\left\\lVert H\(x\)\-H\(y\)\\right\\rVert\_\{\\ell^\{2\}\}\.Everyf∈ℬH♯f\\in\\mathcal\{B\}\_\{H\}^\{\\sharp\}admits a version satisfying

\|f⁡\(x\)−f⁡\(y\)\|≤‖f‖ℬH♯​dH​\(x,y\),x,y∈𝒳\.\|f\(x\)\-f\(y\)\|\\leq\\left\\lVert f\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\}\\,d\_\{H\}\(x,y\),\\qquad x,y\\in\\mathcal\{X\}\.\(16\)Consequently, whenever thedHd\_\{H\}\-Lipschitz seminorm of a version offfis well defined,

LipdH⁡\(f\)≤‖f‖ℬH♯\.\\operatorname\{Lip\}\_\{d\_\{H\}\}\(f\)\\leq\\left\\lVert f\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\}\.\(17\)

###### Proof\.

For every parameterθ=\(w,b\)\\theta=\(w,b\), the11\-Lipschitz property ofρ\\rhogives

\|ψθ​\(x\)−ψθ​\(y\)\|\\displaystyle\|\\psi\_\{\\theta\}\(x\)\-\\psi\_\{\\theta\}\(y\)\|≤\|⟨w,H⁡\(x\)−H⁡\(y\)⟩\|1\+‖w‖2\+b2\\displaystyle\\leq\\frac\{\|\\left\\langle w,H\(x\)\-H\(y\)\\right\\rangle\|\}\{1\+\\sqrt\{\\left\\lVert w\\right\\rVert^\{2\}\+b^\{2\}\}\}≤‖w‖1\+‖w‖2\+b2​dH​\(x,y\)≤dH​\(x,y\)\.\\displaystyle\\leq\\frac\{\\left\\lVert w\\right\\rVert\}\{1\+\\sqrt\{\\left\\lVert w\\right\\rVert^\{2\}\+b^\{2\}\}\}\\,d\_\{H\}\(x,y\)\\leq d\_\{H\}\(x,y\)\.Letf=∫ψθ​𝑑λ​\(θ\)f=\\int\\psi\_\{\\theta\}\\,d\\lambda\(\\theta\)be any normalized representation with\|λ\|​\(𝒫\)<∞\|\\lambda\|\(\\mathcal\{P\}\)<\\infty\. Then

\|f⁡\(x\)−f⁡\(y\)\|≤∫\|ψθ​\(x\)−ψθ​\(y\)\|​d\|λ\|\(θ\)≤\|λ\|​\(𝒫\)​dH​\(x,y\)\.\|f\(x\)\-f\(y\)\|\\leq\\int\|\\psi\_\{\\theta\}\(x\)\-\\psi\_\{\\theta\}\(y\)\|\\,d\|\\lambda\|\(\\theta\)\\leq\|\\lambda\|\(\\mathcal\{P\}\)d\_\{H\}\(x,y\)\.Taking the infimum over all normalized representations proves \([16](https://arxiv.org/html/2608.20812#S3.E16)\)–\([17](https://arxiv.org/html/2608.20812#S3.E17)\)\. ∎

The preceding proposition also quantifies the additional regularity imposed by the weighted variation norm\. This can be seen explicitly for the one\-dimensional threshold family used later in the numerical experiments\. As the threshold becomes sharper, its weighted variation norm necessarily grows linearly with the sharpness parameter, whereas its unweighted variation norm remains uniformly bounded\.

###### Corollary 3\.4\.

Let𝒳=\[−1,1\]\\mathcal\{X\}=\[\-1,1\]andH⁡\(x\)=xH\(x\)=x\. Forλ\>0\\lambda\>0, define

fλ​\(x\):=ρ⁡\(λ​x\)\.f\_\{\\lambda\}\(x\):=\\rho\(\\lambda x\)\.Then

λ≤‖fλ‖ℬH♯≤1\+λ\.\\lambda\\leq\\left\\lVert f\_\{\\lambda\}\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\}\\leq 1\+\\lambda\.\(18\)At the same time,

‖fλ‖ℬH≤1\.\\left\\lVert f\_\{\\lambda\}\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}\}\\leq 1\.Consequently, the weighted and unweighted fixed\-radius variation balls separate quantitatively asλ\\lambdaincreases\.

###### Proof\.

SinceH⁡\(x\)=xH\(x\)=x, the pseudometric induced by the embedding is

dH​\(x,y\)=‖H⁡\(x\)−H⁡\(y\)‖ℓ2=\|x−y\|\.d\_\{H\}\(x,y\)=\\left\\lVert H\(x\)\-H\(y\)\\right\\rVert\_\{\\ell^\{2\}\}=\|x\-y\|\.ThusLipdH⁡\(fλ\)\\operatorname\{Lip\}\_\{d\_\{H\}\}\(f\_\{\\lambda\}\)coincides with the usual Lipschitz seminorm offλf\_\{\\lambda\}on\[−1,1\]\[\-1,1\]\. We first show that

LipdH⁡\(fλ\)=λ\.\\operatorname\{Lip\}\_\{d\_\{H\}\}\(f\_\{\\lambda\}\)=\\lambda\.Becauseρ\\rhois11\-Lipschitz,

\|fλ​\(x\)−fλ​\(y\)\|\\displaystyle\|f\_\{\\lambda\}\(x\)\-f\_\{\\lambda\}\(y\)\|=\|ρ⁡\(λ​x\)−ρ⁡\(λ​y\)\|\\displaystyle=\|\\rho\(\\lambda x\)\-\\rho\(\\lambda y\)\|≤\|λ​x−λ​y\|\\displaystyle\\leq\|\\lambda x\-\\lambda y\|=λ​\|x−y\|\.\\displaystyle=\\lambda\|x\-y\|\.HenceLipdH⁡\(fλ\)≤λ\.\\operatorname\{Lip\}\_\{d\_\{H\}\}\(f\_\{\\lambda\}\)\\leq\\lambda\.To obtain the reverse inequality, takeh\>0h\>0\. Since

ρ⁡\(t\)=t1\+t,t\>0,\\rho\(t\)=\\frac\{t\}\{1\+t\},\\qquad t\>0,andρ⁡\(0\)=0\\rho\(0\)=0, we have

\|fλ​\(h\)−fλ​\(0\)\|\|h\|\\displaystyle\\frac\{\|f\_\{\\lambda\}\(h\)\-f\_\{\\lambda\}\(0\)\|\}\{\|h\|\}=ρ⁡\(λ​h\)h=1h​λ​h1\+λ​h=λ1\+λ​h\.\\displaystyle=\\frac\{\\rho\(\\lambda h\)\}\{h\}=\\frac\{1\}\{h\}\\frac\{\\lambda h\}\{1\+\\lambda h\}=\\frac\{\\lambda\}\{1\+\\lambda h\}\.Lettingh↓0h\\downarrow 0gives

limh↓0\|fλ​\(h\)−fλ​\(0\)\|\|h\|=λ\.\\lim\_\{h\\downarrow 0\}\\frac\{\|f\_\{\\lambda\}\(h\)\-f\_\{\\lambda\}\(0\)\|\}\{\|h\|\}=\\lambda\.Since the Lipschitz seminorm is the supremum of the corresponding difference quotients,LipdH⁡\(fλ\)≥λ\.\\operatorname\{Lip\}\_\{d\_\{H\}\}\(f\_\{\\lambda\}\)\\geq\\lambda\.Therefore

LipdH⁡\(fλ\)=λ\.\\operatorname\{Lip\}\_\{d\_\{H\}\}\(f\_\{\\lambda\}\)=\\lambda\.\(19\)Proposition[3\.3](https://arxiv.org/html/2608.20812#S3.Thmtheorem3)now yields

λ=LipdH⁡\(fλ\)≤‖fλ‖ℬH♯,\\lambda=\\operatorname\{Lip\}\_\{d\_\{H\}\}\(f\_\{\\lambda\}\)\\leq\\left\\lVert f\_\{\\lambda\}\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\},which proves the lower bound in \([18](https://arxiv.org/html/2608.20812#S3.E18)\)\.

For the upper bound, observe thatfλf\_\{\\lambda\}is itself represented by a single raw atom\. Indeed, taking

θλ=\(w,b\)=\(λ,0\)\\theta\_\{\\lambda\}=\(w,b\)=\(\\lambda,0\)gives

gθλ​\(x\)=ρ⁡\(0\+λ​H​\(x\)\)=ρ⁡\(λ​x\)=fλ​\(x\)\.g\_\{\\theta\_\{\\lambda\}\}\(x\)=\\rho\\bigl\(0\+\\lambda H\(x\)\\bigr\)=\\rho\(\\lambda x\)=f\_\{\\lambda\}\(x\)\.Hence the Dirac measure

ν=δθλ\\nu=\\delta\_\{\\theta\_\{\\lambda\}\}belongs to𝔐⁡\(fλ\)\\mathfrak\{M\}\(f\_\{\\lambda\}\)\. Its weighted cost is

∫𝒫\(1\+‖θ‖𝒫\)​d​\|ν\|​\(θ\)\\displaystyle\\int\_\{\\mathcal\{P\}\}\\bigl\(1\+\\left\\lVert\\theta\\right\\rVert\_\{\\mathcal\{P\}\}\\bigr\)\\,d\|\\nu\|\(\\theta\)=1\+‖θλ‖𝒫\\displaystyle=1\+\\left\\lVert\\theta\_\{\\lambda\}\\right\\rVert\_\{\\mathcal\{P\}\}=1\+λ2\+02\\displaystyle=1\+\\sqrt\{\\lambda^\{2\}\+0^\{2\}\}=1\+λ\.\\displaystyle=1\+\\lambda\.Since the weighted variation norm is the infimum over all admissible representations,

‖fλ‖ℬH♯≤1\+λ\.\\left\\lVert f\_\{\\lambda\}\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\}\\leq 1\+\\lambda\.Together with the lower bound, this proves

λ≤‖fλ‖ℬH♯≤1\+λ\.\\lambda\\leq\\left\\lVert f\_\{\\lambda\}\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\}\\leq 1\+\\lambda\.Finally, the same single\-atom representation gives

\|δθλ\|​\(𝒫\)=1\.\|\\delta\_\{\\theta\_\{\\lambda\}\}\|\(\\mathcal\{P\}\)=1\.By the definition of the unweighted variation seminorm,

‖fλ‖ℬH≤1\.\\left\\lVert f\_\{\\lambda\}\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}\}\\leq 1\.This completes the proof\. ∎

## 4Quantitative coordinate truncation

Recall from Assumption[2\.1](https://arxiv.org/html/2608.20812#S2.Thmtheorem1)thatPNP\_\{N\}denotes the orthogonal projection ofℓ2\\ell^\{2\}onto its firstNNcanonical coordinates, so thatHN​\(x\)=PN​H​\(x\)H\_\{N\}\(x\)=P\_\{N\}H\(x\)and\(I−PN\)​H​\(x\)\(I\-P\_\{N\}\)H\(x\)is the tail ofH⁡\(x\)H\(x\)beyond coordinateNN\.

###### Lemma 4\.1\(Pointwise truncation of a normalized atom\)\.

For everyθ=\(w,b\)∈𝒫\\theta=\(w,b\)\\in\\mathcal\{P\}, everyNN, and everyx∈𝒳x\\in\\mathcal\{X\},

\|ψθ​\(x\)−ψθ,N​\(x\)\|≤‖\(I−PN\)​H​\(x\)‖ℓ2\.\|\\psi\_\{\\theta\}\(x\)\-\\psi\_\{\\theta,N\}\(x\)\|\\leq\\left\\lVert\(I\-P\_\{N\}\)H\(x\)\\right\\rVert\_\{\\ell^\{2\}\}\.\(20\)Consequently,

‖ψθ−ψθ,N‖L2​\(μ\)≤ηN​\(μ\),‖ψθ−ψθ,N‖L∞≤ηN∞\.\\left\\lVert\\psi\_\{\\theta\}\-\\psi\_\{\\theta,N\}\\right\\rVert\_\{L^\{2\}\(\\mu\)\}\\leq\\eta\_\{N\}\(\\mu\),\\qquad\\left\\lVert\\psi\_\{\\theta\}\-\\psi\_\{\\theta,N\}\\right\\rVert\_\{L^\{\\infty\}\}\\leq\\eta\_\{N\}^\{\\infty\}\.

###### Proof\.

By the Lipschitz property ofρ\\rho,

\|ψθ​\(x\)−ψθ,N​\(x\)\|\\displaystyle\|\\psi\_\{\\theta\}\(x\)\-\\psi\_\{\\theta,N\}\(x\)\|≤\|⟨w,\(I−PN\)​H​\(x\)⟩\|1\+‖w‖2\+b2\\displaystyle\\leq\\frac\{\|\\left\\langle w,\(I\-P\_\{N\}\)H\(x\)\\right\\rangle\|\}\{1\+\\sqrt\{\\left\\lVert w\\right\\rVert^\{2\}\+b^\{2\}\}\}≤‖\(I−PN\)​H​\(x\)‖​‖w‖1\+‖w‖2\+b2\\displaystyle\\leq\\left\\lVert\(I\-P\_\{N\}\)H\(x\)\\right\\rVert\\frac\{\\left\\lVert w\\right\\rVert\}\{1\+\\sqrt\{\\left\\lVert w\\right\\rVert^\{2\}\+b^\{2\}\}\}≤‖\(I−PN\)​H​\(x\)‖\.\\displaystyle\\leq\\left\\lVert\(I\-P\_\{N\}\)H\(x\)\\right\\rVert\.The two norm estimates follow by integration and by taking the supremum\. ∎

###### Lemma 4\.2\(Finite\-resolution comparator\)\.

Assumeffhas a representation with weighted cost at mostVV, i\.e\.

f⁡\(x\)=∫gθ​\(x\)​𝑑ν​\(θ\),∫c⁡\(θ\)​d​\|ν\|​\(θ\)≤V\.f\(x\)=\\int g\_\{\\theta\}\(x\)\\,d\\nu\(\\theta\),\\qquad\\int c\(\\theta\)\\,d\|\\nu\|\(\\theta\)\\leq V\.\(21\)Letλ\\lambdabe the corresponding measure in \([15](https://arxiv.org/html/2608.20812#S3.E15)\) and define

fN​\(x\):=∫𝒫ψθ,N​\(x\)​𝑑λ​\(θ\)\.f\_\{N\}\(x\):=\\int\_\{\\mathcal\{P\}\}\\psi\_\{\\theta,N\}\(x\)\\,d\\lambda\(\\theta\)\.\(22\)Then, pointwise,

\|f⁡\(x\)−fN​\(x\)\|≤V⁡‖\(I−PN\)​H​\(x\)‖,\|f\(x\)\-f\_\{N\}\(x\)\|\\leq V\\left\\lVert\(I\-P\_\{N\}\)H\(x\)\\right\\rVert,\(23\)and hence

‖f−fN‖L2​\(μ\)≤V​ηN​\(μ\),‖f−fN‖L∞≤V​ηN∞\.\\left\\lVert f\-f\_\{N\}\\right\\rVert\_\{L^\{2\}\(\\mu\)\}\\leq V\\eta\_\{N\}\(\\mu\),\\qquad\\left\\lVert f\-f\_\{N\}\\right\\rVert\_\{L^\{\\infty\}\}\\leq V\\eta\_\{N\}^\{\\infty\}\.\(24\)MoreoverfNf\_\{N\}admits a normalized representation of total variation at mostVV\.

###### Proof\.

Integrate the pointwise estimate from Lemma[4\.1](https://arxiv.org/html/2608.20812#S4.Thmtheorem1)against\|λ\|\|\\lambda\|and use\|λ\|​\(𝒫\)≤V\|\\lambda\|\(\\mathcal\{P\}\)\\leq V\. ∎

## 5Population greedy approximation

Letℋ=L2​\(μ\)\\mathscr\{H\}=L^\{2\}\(\\mu\)\. For a symmetric dictionary𝒟⊂ℋ\\mathcal\{D\}\\subset\\mathscr\{H\}withsupg∈𝒟‖g‖≤1\\sup\_\{g\\in\\mathcal\{D\}\}\\left\\lVert g\\right\\rVert\\leq 1, let𝒦1​\(𝒟\)\\mathcal\{K\}\_\{1\}\(\\mathcal\{D\}\)denote the gauge of its closed absolutely convex hull inℋ\\mathscr\{H\}\. Then

\|⟨r,h⟩\|≤‖h‖𝒦1​\(𝒟\)​supg∈𝒟\|⟨r,g⟩\|\.\|\\left\\langle r,h\\right\\rangle\|\\leq\\left\\lVert h\\right\\rVert\_\{\\mathcal\{K\}\_\{1\}\(\\mathcal\{D\}\)\}\\sup\_\{g\\in\\mathcal\{D\}\}\|\\left\\langle r,g\\right\\rangle\|\.\(25\)
Starting fromf0,N=0f\_\{0,N\}=0, weak OGA selectsϕk∈𝒟N♯\\phi\_\{k\}\\in\\mathcal\{D\}\_\{N\}^\{\\sharp\}satisfying

\|⟨f−fk−1,N,ϕk⟩\|≥γ​supϕ∈𝒟N♯\|⟨f−fk−1,N,ϕ⟩\|,0<γ<1,\|\\left\\langle f\-f\_\{k\-1,N\},\\phi\_\{k\}\\right\\rangle\|\\geq\\gamma\\sup\_\{\\phi\\in\\mathcal\{D\}\_\{N\}^\{\\sharp\}\}\|\\left\\langle f\-f\_\{k\-1,N\},\\phi\\right\\rangle\|,\\qquad 0<\\gamma<1,\(26\)and letsfk,Nf\_\{k,N\}be the orthogonal projection offfonto the span of the selected atoms\.

###### Lemma 5\.1\(Recursion inversion\)\.

Letc\>0c\>0and let\(ak\)k≥0\(a\_\{k\}\)\_\{k\\geq 0\}be a sequence of nonnegative reals such that

ak≤ak−1−c​ak−12,k≥1\.a\_\{k\}\\leq a\_\{k\-1\}\-c\\,a\_\{k\-1\}^\{2\},\\qquad k\\geq 1\.\(27\)Thena1≤14​ca\_\{1\}\\leq\\dfrac\{1\}\{4c\}, and

am≤1c⁡\(m\+3\)for every integer​m≥1\.a\_\{m\}\\leq\\frac\{1\}\{c\(m\+3\)\}\\qquad\\text\{for every integer \}m\\geq 1\.\(28\)

###### Proof\.

By \([27](https://arxiv.org/html/2608.20812#S5.E27)\),ak≤ak−1a\_\{k\}\\leq a\_\{k\-1\}for everykk, so the sequence is non\-increasing andak∈\[0,a0\]a\_\{k\}\\in\[0,a\_\{0\}\]for allkk\. The real mapx↦x−c​x2x\\mapsto x\-cx^\{2\}attains its maximum overℝ\\mathbb\{R\}atx=1/\(2​c\)x=1/\(2c\)with value1/\(4​c\)1/\(4c\), so applying \([27](https://arxiv.org/html/2608.20812#S5.E27)\) withk=1k=1gives

a1≤a0−c​a02≤maxx∈ℝ⁡\(x−c​x2\)=14​c=1c⁡\(1\+3\),a\_\{1\}\\leq a\_\{0\}\-ca\_\{0\}^\{2\}\\leq\\max\_\{x\\in\\mathbb\{R\}\}\(x\-cx^\{2\}\)=\\frac\{1\}\{4c\}=\\frac\{1\}\{c\(1\+3\)\},which is exactly \([28](https://arxiv.org/html/2608.20812#S5.E28)\) atm=1m=1\.

Fork≥2k\\geq 2we haveak−1≤a1≤14​ca\_\{k\-1\}\\leq a\_\{1\}\\leq\\frac\{1\}\{4c\}, hence1−c​ak−1≥34\>01\-ca\_\{k\-1\}\\geq\\frac\{3\}\{4\}\>0\. Ifak−1=0a\_\{k\-1\}=0thenak=0a\_\{k\}=0by \([27](https://arxiv.org/html/2608.20812#S5.E27)\) and \([28](https://arxiv.org/html/2608.20812#S5.E28)\) holds trivially atm=km=kgiven that it holds atm=k−1m=k\-1\. Ifak−1\>0a\_\{k\-1\}\>0, then, using11−x≥1\+x\\frac\{1\}\{1\-x\}\\geq 1\+xforx∈\[0,1\)x\\in\[0,1\),

1ak≥1ak−1−c​ak−12=1ak−1⋅11−c​ak−1≥1ak−1​\(1\+c​ak−1\)=1ak−1\+c\.\\frac\{1\}\{a\_\{k\}\}\\geq\\frac\{1\}\{a\_\{k\-1\}\-ca\_\{k\-1\}^\{2\}\}=\\frac\{1\}\{a\_\{k\-1\}\}\\cdot\\frac\{1\}\{1\-ca\_\{k\-1\}\}\\geq\\frac\{1\}\{a\_\{k\-1\}\}\\bigl\(1\+ca\_\{k\-1\}\\bigr\)=\\frac\{1\}\{a\_\{k\-1\}\}\+c\.Telescoping this fromk=2k=2tok=mk=m\(form≥2m\\geq 2\) and usinga1≤14​ca\_\{1\}\\leq\\frac\{1\}\{4c\},

1am≥1a1\+c⁡\(m−1\)≥4​c\+c⁡\(m−1\)=c⁡\(m\+3\),\\frac\{1\}\{a\_\{m\}\}\\geq\\frac\{1\}\{a\_\{1\}\}\+c\(m\-1\)\\geq 4c\+c\(m\-1\)=c\(m\+3\),i\.e\.am≤1c⁡\(m\+3\)a\_\{m\}\\leq\\dfrac\{1\}\{c\(m\+3\)\}\. Together with the casem=1m=1already established, this proves \([28](https://arxiv.org/html/2608.20812#S5.E28)\) for everym≥1m\\geq 1\. ∎

###### Lemma 5\.2\(Robust weak OGA\)\.

For everyh∈𝒦1​\(𝒟\)h\\in\\mathcal\{K\}\_\{1\}\(\\mathcal\{D\}\),

‖f−fm‖ℋ2≤‖f−h‖ℋ2\+4γ2​m​‖h‖𝒦1​\(𝒟\)2\.\\left\\lVert f\-f\_\{m\}\\right\\rVert\_\{\\mathscr\{H\}\}^\{2\}\\leq\\left\\lVert f\-h\\right\\rVert\_\{\\mathscr\{H\}\}^\{2\}\+\\frac\{4\}\{\\gamma^\{2\}m\}\\left\\lVert h\\right\\rVert\_\{\\mathcal\{K\}\_\{1\}\(\\mathcal\{D\}\)\}^\{2\}\.\(29\)

###### Proof\.

Setrk=f−fkr\_\{k\}=f\-f\_\{k\},dk=‖rk‖2d\_\{k\}=\\left\\lVert r\_\{k\}\\right\\rVert^\{2\},e=‖f−h‖e=\\left\\lVert f\-h\\right\\rVert, andM=‖h‖𝒦1​\(𝒟\)M=\\left\\lVert h\\right\\rVert\_\{\\mathcal\{K\}\_\{1\}\(\\mathcal\{D\}\)\}\. Orthogonality gives⟨rk−1,f⟩=dk−1\\left\\langle r\_\{k\-1\},f\\right\\rangle=d\_\{k\-1\}\. Ifdk−1\>e2d\_\{k\-1\}\>e^\{2\}, then

\|⟨rk−1,h⟩\|≥dk−1−e​dk−1≥12​\(dk−1−e2\)\.\|\\left\\langle r\_\{k\-1\},h\\right\\rangle\|\\geq d\_\{k\-1\}\-e\\sqrt\{d\_\{k\-1\}\}\\geq\\frac\{1\}\{2\}\(d\_\{k\-1\}\-e^\{2\}\)\.Using \([25](https://arxiv.org/html/2608.20812#S5.E25)\) and the weak selection rule,

\|⟨rk−1,ϕk⟩\|≥γ2​M​\(dk−1−e2\)\.\|\\left\\langle r\_\{k\-1\},\\phi\_\{k\}\\right\\rangle\|\\geq\\frac\{\\gamma\}\{2M\}\(d\_\{k\-1\}\-e^\{2\}\)\.After removing the component ofϕk\\phi\_\{k\}in the previous greedy span, the new orthogonal direction has norm at most one and the same residual correlation\. Hence

dk≤dk−1−γ24​M2​\(dk−1−e2\)2\.d\_\{k\}\\leq d\_\{k\-1\}\-\\frac\{\\gamma^\{2\}\}\{4M^\{2\}\}\(d\_\{k\-1\}\-e^\{2\}\)^\{2\}\.Since orthogonal projection onto an enlarged subspace cannot increase the residual norm,dk≤dk−1d\_\{k\}\\leq d\_\{k\-1\}for everykk, soΔk:=\(dk−e2\)\+\\Delta\_\{k\}:=\(d\_\{k\}\-e^\{2\}\)\_\{\+\}is non\-increasing; combined with the last display, this givesΔk≤Δk−1−γ24​M2​Δk−12\\Delta\_\{k\}\\leq\\Delta\_\{k\-1\}\-\\frac\{\\gamma^\{2\}\}\{4M^\{2\}\}\\Delta\_\{k\-1\}^\{2\}wheneverΔk−1\>0\\Delta\_\{k\-1\}\>0, and the same inequality holds trivially whenΔk−1=0\\Delta\_\{k\-1\}=0\. Applying Lemma[5\.1](https://arxiv.org/html/2608.20812#S5.Thmtheorem1)withak=Δka\_\{k\}=\\Delta\_\{k\}andc=γ2/\(4​M2\)c=\\gamma^\{2\}/\(4M^\{2\}\)yields

Δm≤4​M2γ2​\(m\+3\)≤4​M2γ2​m,m≥1\.\\Delta\_\{m\}\\leq\\frac\{4M^\{2\}\}\{\\gamma^\{2\}\(m\+3\)\}\\leq\\frac\{4M^\{2\}\}\{\\gamma^\{2\}m\},\\qquad m\\geq 1\.\(30\)∎

###### Theorem 5\.4\(Deterministic width–resolution tradeoff\)\.

Under \([21](https://arxiv.org/html/2608.20812#S4.E21)\), weak OGA over𝒟N♯\\mathcal\{D\}\_\{N\}^\{\\sharp\}satisfies

‖f−fm,N‖L2​\(μ\)2≤V2​ηN​\(μ\)2\+4​V2γ2​m\.\\boxed\{\\left\\lVert f\-f\_\{m,N\}\\right\\rVert\_\{L^\{2\}\(\\mu\)\}^\{2\}\\leq V^\{2\}\\eta\_\{N\}\(\\mu\)^\{2\}\+\\frac\{4V^\{2\}\}\{\\gamma^\{2\}m\}\.\}\(31\)In particular,

‖f−fm,N‖L2​\(μ\)≤V⁡\(ηN​\(μ\)\+2γ​m\)\.\\left\\lVert f\-f\_\{m,N\}\\right\\rVert\_\{L^\{2\}\(\\mu\)\}\\leq V\\left\(\\eta\_\{N\}\(\\mu\)\+\\frac\{2\}\{\\gamma\\sqrt\{m\}\}\\right\)\.\(32\)

###### Proof\.

By Lemma[4\.2](https://arxiv.org/html/2608.20812#S4.Thmtheorem2),fNf\_\{N\}has atomic gauge at mostVVand‖f−fN‖2≤V​ηN​\(μ\)\\left\\lVert f\-f\_\{N\}\\right\\rVert\_\{2\}\\leq V\\eta\_\{N\}\(\\mu\)\. Apply Lemma[5\.2](https://arxiv.org/html/2608.20812#S5.Thmtheorem2)withh=fNh=f\_\{N\}\. ∎

###### Corollary 5\.5\(Quasi\-Polish envelope\)\.

If\|hj\|≤1/j\|h\_\{j\}\|\\leq 1/j, then

‖f−fm,N‖L2​\(μ\)≤V⁡\(1N\+2γ​m\)\.\\left\\lVert f\-f\_\{m,N\}\\right\\rVert\_\{L^\{2\}\(\\mu\)\}\\leq V\\left\(\\frac\{1\}\{\\sqrt\{N\}\}\+\\frac\{2\}\{\\gamma\\sqrt\{m\}\}\\right\)\.

## 6Rademacher complexity without an explicit resolution factor

For a fixed, deterministic sampleS=\(x1,…,xn\)∈𝒳nS=\(x\_\{1\},\\ldots,x\_\{n\}\)\\in\\mathcal\{X\}^\{n\}\(lower\-case points, not random variables\) and a classℱ\\mathcal\{F\}of real\-valued functions on𝒳\\mathcal\{X\}\(a*real\-valued class*\), letε=\(ε1,…,εn\)\\varepsilon=\(\\varepsilon\_\{1\},\\ldots,\\varepsilon\_\{n\}\)be i\.i\.d\. Rademacher random variables \(uniform on\{−1,\+1\}\\\{\-1,\+1\\\}\), independent ofSS, and define the empirical Rademacher complexity

ℜ^S​\(ℱ\):=𝔼ε​\[supf∈ℱ1n​∑i=1nεi​f​\(xi\)\],\\widehat\{\\mathfrak\{R\}\}\_\{S\}\(\\mathcal\{F\}\):=\\mathbb\{E\}\_\{\\varepsilon\}\\left\[\\sup\_\{f\\in\\mathcal\{F\}\}\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\varepsilon\_\{i\}f\(x\_\{i\}\)\\right\],\(33\)where𝔼ε\\mathbb\{E\}\_\{\\varepsilon\}denotes expectation overε\\varepsilonwithSSheld fixed\. Thusℜ^S​\(ℱ\)\\widehat\{\\mathfrak\{R\}\}\_\{S\}\(\\mathcal\{F\}\)is itself a deterministic number for each fixedSS; it becomes a random variable only throughSSwhen the sample is later drawn at random, as in Section[7](https://arxiv.org/html/2608.20812#S7), whereS=\(\(X1,Y1\),…,\(Xn,Yn\)\)S=\(\(X\_\{1\},Y\_\{1\}\),\\ldots,\(X\_\{n\},Y\_\{n\}\)\)is i\.i\.d\.

Every classℱ\\mathcal\{F\}appearing below \(the dyadic shell classesℱN,j\\mathcal\{F\}\_\{N,j\}, the linear classesℒj\\mathcal\{L\}\_\{j\}, and𝒟N♯\\mathcal\{D\}\_\{N\}^\{\\sharp\}itself\) is indexed by a continuum of parametersθ∈𝒫\\theta\\in\\mathcal\{P\}rather than by a countable set, sosupf∈ℱ\\sup\_\{f\\in\\mathcal\{F\}\}and, onceSSis random, quantities such assupf∈ℱn−1​∑iεi​f​\(Xi\)\\sup\_\{f\\in\\mathcal\{F\}\}n^\{\-1\}\\sum\_\{i\}\\varepsilon\_\{i\}f\(X\_\{i\}\)require a measurability justification\. Two distinct measurability questions are involved, and it is worth separating them explicitly\. The first, forSSfixed, is whether𝔼ε​\[supf∈ℱn−1​∑iεi​f​\(xi\)\]\\mathbb\{E\}\_\{\\varepsilon\}\\bigl\[\\sup\_\{f\\in\\mathcal\{F\}\}n^\{\-1\}\\sum\_\{i\}\\varepsilon\_\{i\}f\(x\_\{i\}\)\\bigr\]in \([33](https://arxiv.org/html/2608.20812#S6.E33)\) is well defined; this is immediate and requires no argument at all, sinceε=\(ε1,…,εn\)\\varepsilon=\(\\varepsilon\_\{1\},\\ldots,\\varepsilon\_\{n\}\)ranges over the*finite*set\{−1,\+1\}n\\\{\-1,\+1\\\}^\{n\}, so𝔼ε\\mathbb\{E\}\_\{\\varepsilon\}is literally a finite average over2n2^\{n\}terms, each of which is a supremum of a fixed real numbern−1​∑iεi​f​\(xi\)n^\{\-1\}\\sum\_\{i\}\\varepsilon\_\{i\}f\(x\_\{i\}\)overf∈ℱf\\in\\mathcal\{F\}– a real number \(possibly\+∞\+\\infty, though not here since\|f\|≤1\|f\|\\leq 1throughout\), not a random variable, so no measurability question aboutε\\varepsilonarises\.

The second, genuine question is whether, once the sample itself is random \(as in Section[7](https://arxiv.org/html/2608.20812#S7), withS=\(\(X1,Y1\),…,\(Xn,Yn\)\)S=\(\(X\_\{1\},Y\_\{1\}\),\\ldots,\(X\_\{n\},Y\_\{n\}\)\)i\.i\.d\.\), maps such asS↦supf∈ℱn−1​∑iεi​f​\(Xi\)S\\mapsto\\sup\_\{f\\in\\mathcal\{F\}\}n^\{\-1\}\\sum\_\{i\}\\varepsilon\_\{i\}f\(X\_\{i\}\)\(for fixedε\\varepsilon\) orS↦supu∈𝒞N,V\|Rn​\(u\)−𝔼​Rn​\(u\)\|S\\mapsto\\sup\_\{u\\in\\mathcal\{C\}\_\{N,V\}\}\|R\_\{n\}\(u\)\-\\mathbb\{E\}R\_\{n\}\(u\)\|\(in the bounded\-difference argument underlying Theorem[8\.1](https://arxiv.org/html/2608.20812#S8.Thmtheorem1)\) are measurable functions ofSS, as is implicitly required to apply McDiarmid’s inequality and the symmetrization step\. This is resolved by the standard separability argument for processes indexed by a continuous parameter \(see, e\.g\.,\[[18](https://arxiv.org/html/2608.20812#bib.bib18)\], Section 2\.1\): for every fixedx∈𝒳x\\in\\mathcal\{X\}the mapθ↦ψθ​\(x\)\\theta\\mapsto\\psi\_\{\\theta\}\(x\)is continuous on𝒫\\mathcal\{P\}\(it is a continuous function of⟨w,H⁡\(x\)⟩\\left\\langle w,H\(x\)\\right\\rangleand‖θ‖𝒫\\left\\lVert\\theta\\right\\rVert\_\{\\mathcal\{P\}\}, both continuous inθ\\theta\), and likewise forθ↦ψθ,N​\(x\)\\theta\\mapsto\\psi\_\{\\theta,N\}\(x\)and for the map\(a1,…,ak,θ1,…,θk\)↦∑jaj​ψθj,N​\(x\)\(a\_\{1\},\\ldots,a\_\{k\},\\theta\_\{1\},\\ldots,\\theta\_\{k\}\)\\mapsto\\sum\_\{j\}a\_\{j\}\\psi\_\{\\theta\_\{j\},N\}\(x\)defining a general element of𝒞N,V\\mathcal\{C\}\_\{N,V\}\. Since𝒫=ℓ2⊕ℝ\\mathcal\{P\}=\\ell^\{2\}\\oplus\\mathbb\{R\}is separable, any subsetΘ⊆𝒫\\Theta\\subseteq\\mathcal\{P\}has a countable dense subsetΘ0\\Theta\_\{0\}, and for every fixed sample the mapθ↦\(εi​fθ​\(xi\)\)i≤n\\theta\\mapsto\(\\varepsilon\_\{i\}f\_\{\\theta\}\(x\_\{i\}\)\)\_\{i\\leq n\}is continuous, sosupθ∈Θn−1​∑iεi​fθ​\(xi\)=supθ∈Θ0n−1​∑iεi​fθ​\(xi\)\\sup\_\{\\theta\\in\\Theta\}n^\{\-1\}\\sum\_\{i\}\\varepsilon\_\{i\}f\_\{\\theta\}\(x\_\{i\}\)=\\sup\_\{\\theta\\in\\Theta\_\{0\}\}n^\{\-1\}\\sum\_\{i\}\\varepsilon\_\{i\}f\_\{\\theta\}\(x\_\{i\}\)for every fixed sample: the supremum over the continuum coincides with a countable supremum\. As a function of the \(random\) sample, a countable supremum of measurable functions is measurable, soS↦supθ∈Θn−1​∑iεi​fθ​\(Xi\)S\\mapsto\\sup\_\{\\theta\\in\\Theta\}n^\{\-1\}\\sum\_\{i\}\\varepsilon\_\{i\}f\_\{\\theta\}\(X\_\{i\}\)is measurable, and likewise forsupu∈𝒞N,V\|Rn​\(u\)−𝔼​Rn​\(u\)\|\\sup\_\{u\\in\\mathcal\{C\}\_\{N,V\}\}\|R\_\{n\}\(u\)\-\\mathbb\{E\}R\_\{n\}\(u\)\|after replacing the continuum of\(a,θ\)\(a,\\theta\)\-tuples defining𝒞N,V\\mathcal\{C\}\_\{N,V\}by a countable dense subset \(which exists since𝒞N,V\\mathcal\{C\}\_\{N,V\}, as the image of a separable metric space under a continuous map, is itself separable inL2​\(μ\)L^\{2\}\(\\mu\)and in the sup norm on the sample\)\. None of the empirical\-process bounds below are affected by working with the countable dense subset in place of the continuum, so we do not restate this observation at each subsequent supremum\.

###### Lemma 6\.1\(Finite union of bounded classes\)\.

Letℱ1,…,ℱJ\\mathcal\{F\}\_\{1\},\\ldots,\\mathcal\{F\}\_\{J\}be real\-valued classes on𝒳\\mathcal\{X\}\(in the sense of \([33](https://arxiv.org/html/2608.20812#S6.E33)\)\) satisfying\|f⁡\(xi\)\|≤1\|f\(x\_\{i\}\)\|\\leq 1on the sample for everyffin every class\. Then

ℜ^S​\(⋃j=1Jℱj\)≤max1≤j≤J⁡ℜ^S​\(ℱj\)\+2​log⁡Jn\.\\widehat\{\\mathfrak\{R\}\}\_\{S\}\\\!\\left\(\\bigcup\_\{j=1\}^\{J\}\\mathcal\{F\}\_\{j\}\\right\)\\leq\\max\_\{1\\leq j\\leq J\}\\widehat\{\\mathfrak\{R\}\}\_\{S\}\(\\mathcal\{F\}\_\{j\}\)\+\\sqrt\{\\frac\{2\\log J\}\{n\}\}\.\(34\)

###### Proof\.

For fixed Rademacherε\\varepsilonsigns let

Wj​\(ε\):=supf∈ℱj1n​∑i=1nεi​f​\(xi\)\.W\_\{j\}\(\\varepsilon\):=\\sup\_\{f\\in\\mathcal\{F\}\_\{j\}\}\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\varepsilon\_\{i\}f\(x\_\{i\}\)\.Changing one sign changesWjW\_\{j\}by at most2/n2/n\. The bounded\-differences moment bound therefore makesWj−𝔼ε​WjW\_\{j\}\-\\mathbb\{E\}\_\{\\varepsilon\}W\_\{j\}sub\-Gaussian with variance proxy1/n1/n\. The standard maximal inequality forJJsub\-Gaussian variables gives

𝔼ε​maxj​Wj≤maxj⁡𝔼ε​Wj\+2​log⁡Jn,\\mathbb\{E\}\_\{\\varepsilon\}\\max\_\{j\}W\_\{j\}\\leq\\max\_\{j\}\\mathbb\{E\}\_\{\\varepsilon\}W\_\{j\}\+\\sqrt\{\\frac\{2\\log J\}\{n\}\},which is exactly \([34](https://arxiv.org/html/2608.20812#S6.E34)\)\. ∎

###### Lemma 6\.2\(Dimension\-uniform normalized\-dictionary complexity\)\.

For everyn≥2n\\geq 2, everyNN, and every sampleSS\(herelog\\logdenotes the natural logarithm\),

ℜ^S​\(𝒟N♯\)≤4n​\(K\+1\+log⁡\(2\+log⁡n\)\)\.\\boxed\{\\widehat\{\\mathfrak\{R\}\}\_\{S\}\(\\mathcal\{D\}\_\{N\}^\{\\sharp\}\)\\leq\\frac\{4\}\{\\sqrt\{n\}\}\\left\(K\+1\+\\sqrt\{\\log\(2\+\\log n\)\}\\right\)\.\}\(35\)In particular, the bound has no explicit dependence onNN, and the displayed universal constant is explicit\. The factor is chosen conservatively to account for the explicit±\\pmsymmetrization of the normalized dictionary\.

###### Proof\.

Forj≥1j\\geq 1, let

Θj:=\{θ∈𝒫:2j−1≤1\+‖θ‖𝒫<2j\},\\Theta\_\{j\}:=\\\{\\theta\\in\\mathcal\{P\}:2^\{j\-1\}\\leq 1\+\\left\\lVert\\theta\\right\\rVert\_\{\\mathcal\{P\}\}<2^\{j\}\\\},and

ℱN,j:=\{±ψθ,N:θ∈Θj\}\.\\mathcal\{F\}\_\{N,j\}:=\\\{\\pm\\psi\_\{\\theta,N\}:\\theta\\in\\Theta\_\{j\}\\\}\.OnΘj\\Theta\_\{j\},

\(1\+‖θ‖𝒫\)−1≤21−j,‖θ‖𝒫<2j\.\(1\+\\left\\lVert\\theta\\right\\rVert\_\{\\mathcal\{P\}\}\)^\{\-1\}\\leq 2^\{1\-j\},\\qquad\\left\\lVert\\theta\\right\\rVert\_\{\\mathcal\{P\}\}<2^\{j\}\.

#### Shell bound, with an explicit contraction constant\.

The linear classℒj:=\{x↦⟨θ,ZN​\(x\)⟩:‖θ‖𝒫<2j\}\\mathcal\{L\}\_\{j\}:=\\\{x\\mapsto\\left\\langle\\theta,Z\_\{N\}\(x\)\\right\\rangle:\\left\\lVert\\theta\\right\\rVert\_\{\\mathcal\{P\}\}<2^\{j\}\\\}is symmetric, whereasρ∘ℒj\\rho\\circ\\mathcal\{L\}\_\{j\}need not be symmetric becauseρ\\rhois not odd\. The shell dictionary is symmetric only because the sign±\\pmis included explicitly in its definition\. We therefore first split the absolute supremum into its two signs and then apply the one\-sided contraction principle to each sign\. In the form used below \(Ledoux and Talagrand\[[13](https://arxiv.org/html/2608.20812#bib.bib13)\], Cor\. 3\.17\): for anLL\-Lipschitzφ:ℝ→ℝ\\varphi:\\mathbb\{R\}\\to\\mathbb\{R\}withφ⁡\(0\)=0\\varphi\(0\)=0and any classℋ\\mathcal\{H\}of real functions on the sample,

𝔼ε​suph∈ℋ∑i=1nεi​φ​\(h⁡\(xi\)\)≤L​𝔼ε​suph∈ℋ∑i=1nεi​h​\(xi\)\.\\mathbb\{E\}\_\{\\varepsilon\}\\sup\_\{h\\in\\mathcal\{H\}\}\\sum\_\{i=1\}^\{n\}\\varepsilon\_\{i\}\\varphi\(h\(x\_\{i\}\)\)\\leq L\\,\\mathbb\{E\}\_\{\\varepsilon\}\\sup\_\{h\\in\\mathcal\{H\}\}\\sum\_\{i=1\}^\{n\}\\varepsilon\_\{i\}h\(x\_\{i\}\)\.\(36\)Sinceρ\\rhois11\-Lipschitz andρ⁡\(0\)=0\\rho\(0\)=0, contraction applies to each one\-sided term\. By symmetry of the Rademacher signs the positive and negative terms have the same expectation, and hence

ℜ^S​\(ℱN,j\)\\displaystyle\\widehat\{\\mathfrak\{R\}\}\_\{S\}\(\\mathcal\{F\}\_\{N,j\}\)≤21−jn​𝔼ε​supθ∈Θj\|∑i=1nεi​ρ​\(⟨θ,ZN​\(xi\)⟩\)\|\\displaystyle\\leq\\frac\{2^\{1\-j\}\}\{n\}\\mathbb\{E\}\_\{\\varepsilon\}\\sup\_\{\\theta\\in\\Theta\_\{j\}\}\\left\|\\sum\_\{i=1\}^\{n\}\\varepsilon\_\{i\}\\rho\(\\left\\langle\\theta,Z\_\{N\}\(x\_\{i\}\)\\right\\rangle\)\\right\|≤22−jn​𝔼ε​sup‖θ‖𝒫<2j∑i=1nεi​⟨θ,ZN​\(xi\)⟩\\displaystyle\\leq\\frac\{2^\{2\-j\}\}\{n\}\\mathbb\{E\}\_\{\\varepsilon\}\\sup\_\{\\left\\lVert\\theta\\right\\rVert\_\{\\mathcal\{P\}\}<2^\{j\}\}\\sum\_\{i=1\}^\{n\}\\varepsilon\_\{i\}\\left\\langle\\theta,Z\_\{N\}\(x\_\{i\}\)\\right\\rangle=22−jn⋅2j​𝔼ε​‖∑i=1nεi​ZN​\(xi\)‖𝒫=4n​𝔼ε​‖∑i=1nεi​ZN​\(xi\)‖𝒫≤4​Kn,\\displaystyle=\\frac\{2^\{2\-j\}\}\{n\}\\cdot 2^\{j\}\\,\\mathbb\{E\}\_\{\\varepsilon\}\\left\\lVert\\sum\_\{i=1\}^\{n\}\\varepsilon\_\{i\}Z\_\{N\}\(x\_\{i\}\)\\right\\rVert\_\{\\mathcal\{P\}\}=\\frac\{4\}\{n\}\\mathbb\{E\}\_\{\\varepsilon\}\\left\\lVert\\sum\_\{i=1\}^\{n\}\\varepsilon\_\{i\}Z\_\{N\}\(x\_\{i\}\)\\right\\rVert\_\{\\mathcal\{P\}\}\\leq\\frac\{4K\}\{\\sqrt\{n\}\},where the middle equality usessup‖θ‖𝒫<2j\|⟨θ,v⟩\|=2j​‖v‖𝒫\\sup\_\{\\left\\lVert\\theta\\right\\rVert\_\{\\mathcal\{P\}\}<2^\{j\}\}\|\\left\\langle\\theta,v\\right\\rangle\|=2^\{j\}\\left\\lVert v\\right\\rVert\_\{\\mathcal\{P\}\}, and the last inequality uses the Hilbert\-space Khintchine bound𝔼ε​‖∑iεi​ZN​\(xi\)‖𝒫≤\(∑i‖ZN​\(xi\)‖𝒫2\)1/2≤K​n\\mathbb\{E\}\_\{\\varepsilon\}\\left\\lVert\\sum\_\{i\}\\varepsilon\_\{i\}Z\_\{N\}\(x\_\{i\}\)\\right\\rVert\_\{\\mathcal\{P\}\}\\leq\\bigl\(\\sum\_\{i\}\\left\\lVert Z\_\{N\}\(x\_\{i\}\)\\right\\rVert\_\{\\mathcal\{P\}\}^\{2\}\\bigr\)^\{1/2\}\\leq K\\sqrt\{n\}\. The boundℜ^S​\(ℱN,j\)≤4​K/n\\widehat\{\\mathfrak\{R\}\}\_\{S\}\(\\mathcal\{F\}\_\{N,j\}\)\\leq 4K/\\sqrt\{n\}holds for everyj≥1j\\geq 1with no unspecified constant\.

#### Dyadic union\.

Choose

J:=⌈12​log2​n⌉\+1\.J:=\\left\\lceil\\frac\{1\}\{2\}\\log\_\{2\}n\\right\\rceil\+1\.By Lemma[6\.1](https://arxiv.org/html/2608.20812#S6.Thmtheorem1), since every shell class is bounded by11on the sample \(eq\. \([9](https://arxiv.org/html/2608.20812#S3.E9)\)\),

ℜ^S​\(⋃j=1JℱN,j\)≤max1≤j≤J⁡ℜ^S​\(ℱN,j\)\+2​log⁡Jn≤4​Kn\+2​log⁡Jn\.\\widehat\{\\mathfrak\{R\}\}\_\{S\}\\Bigl\(\\bigcup\_\{j=1\}^\{J\}\\mathcal\{F\}\_\{N,j\}\\Bigr\)\\leq\\max\_\{1\\leq j\\leq J\}\\widehat\{\\mathfrak\{R\}\}\_\{S\}\(\\mathcal\{F\}\_\{N,j\}\)\+\\sqrt\{\\frac\{2\\log J\}\{n\}\}\\leq\\frac\{4K\}\{\\sqrt\{n\}\}\+\\sqrt\{\\frac\{2\\log J\}\{n\}\}\.Forn≥2n\\geq 2,J≤12​log2​n\+2=12​ln⁡2​ln⁡n\+2<ln⁡n\+2J\\leq\\frac\{1\}\{2\}\\log\_\{2\}n\+2=\\frac\{1\}\{2\\ln 2\}\\ln n\+2<\\ln n\+2\(since12​ln⁡2<1\\frac\{1\}\{2\\ln 2\}<1\), solog⁡J≤log⁡\(2\+log⁡n\)\\log J\\leq\\log\(2\+\\log n\)and hence2​log⁡J/n≤2​log⁡\(2\+log⁡n\)/n\\sqrt\{2\\log J/n\}\\leq\\sqrt\{2\}\\,\\sqrt\{\\log\(2\+\\log n\)\}/\\sqrt\{n\}\.

Forj\>Jj\>J, everyϕ∈ℱN,j\\phi\\in\\mathcal\{F\}\_\{N,j\}satisfies\|ϕ\|≤2−J\|\\phi\|\\leq 2^\{\-J\}on the sample \(eq\. \([9](https://arxiv.org/html/2608.20812#S3.E9)\) together withΘj\\Theta\_\{j\}’s definition\), and2−J≤2−12​log2​n−1=12n−1/2≤n−1/22^\{\-J\}\\leq 2^\{\-\\frac\{1\}\{2\}\\log\_\{2\}n\-1\}=\\tfrac\{1\}\{2\}n^\{\-1/2\}\\leq n^\{\-1/2\}; since a class uniformly bounded byε\\varepsilonon the sample has Rademacher complexity at mostε\\varepsilonregardless of how many functions it contains, the entire tail⋃j\>JℱN,j\\bigcup\_\{j\>J\}\\mathcal\{F\}\_\{N,j\}contributes at mostn−1/2n^\{\-1/2\}toℜ^S​\(𝒟N♯\)\\widehat\{\\mathfrak\{R\}\}\_\{S\}\(\\mathcal\{D\}\_\{N\}^\{\\sharp\}\)\. Combining the head and tail contributions,

ℜ^S​\(𝒟N♯\)\\displaystyle\\widehat\{\\mathfrak\{R\}\}\_\{S\}\(\\mathcal\{D\}\_\{N\}^\{\\sharp\}\)≤4​Kn\+2​log⁡\(2\+log⁡n\)n\+1n\\displaystyle\\leq\\frac\{4K\}\{\\sqrt\{n\}\}\+\\sqrt\{2\}\\,\\frac\{\\sqrt\{\\log\(2\+\\log n\)\}\}\{\\sqrt\{n\}\}\+\\frac\{1\}\{\\sqrt\{n\}\}=1n​\(4​K\+1\+2​log⁡\(2\+log⁡n\)\)\\displaystyle=\\frac\{1\}\{\\sqrt\{n\}\}\\Bigl\(4K\+1\+\\sqrt\{2\}\\sqrt\{\\log\(2\+\\log n\)\}\\Bigr\)≤4n​\(K\+1\+log⁡\(2\+log⁡n\)\)\.\\displaystyle\\leq\\frac\{4\}\{\\sqrt\{n\}\}\\Bigl\(K\+1\+\\sqrt\{\\log\(2\+\\log n\)\}\\Bigr\)\.where the last step compares the three terms coefficient by coefficient \(4≥44\\geq 4,4≥14\\geq 1,4≥24\\geq\\sqrt\{2\}\)\. This proves \([35](https://arxiv.org/html/2608.20812#S6.E35)\); we may takeC0=4C\_\{0\}=4\. ∎

## 7Fully\-corrective empirical greedy regression

Let\(X,Y\)\(X,Y\)be distributed on𝒳×ℝ\\mathcal\{X\}\\times\\mathbb\{R\}and letS=\(\(X1,Y1\),…,\(Xn,Yn\)\)S=\(\(X\_\{1\},Y\_\{1\}\),\\ldots,\(X\_\{n\},Y\_\{n\}\)\)be i\.i\.d\. For a measurable prediction functionu:𝒳→ℝu:\\mathcal\{X\}\\to\\mathbb\{R\}, define its empirical squared\-error risk

Rn​\(u\):=1n​∑i=1n\(Yi−u⁡\(Xi\)\)2\.R\_\{n\}\(u\):=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\(Y\_\{i\}\-u\(X\_\{i\}\)\)^\{2\}\.ForV\>0V\>0define the prediction class directly through pointwise integral representations: recalling the parameter space𝒫=ℓ2⊕ℝ\\mathcal\{P\}=\\ell^\{2\}\\oplus\\mathbb\{R\}from Section[3](https://arxiv.org/html/2608.20812#S3), letλ\\lambdarange over finite signed Borel measures on𝒫\\mathcal\{P\}, with\|λ\|\|\\lambda\|its total\-variation measure and\|λ\|​\(𝒫\)\|\\lambda\|\(\\mathcal\{P\}\)the corresponding total\-variation norm \(as in Definition[3\.2](https://arxiv.org/html/2608.20812#S3.Thmtheorem2)\), and set

𝒞N,V:=\{u:u\(x\)=∫𝒫ψθ,N\(x\)dλ\(θ\),\|λ\|\(𝒫\)≤V\}\.\\mathcal\{C\}\_\{N,V\}:=\\left\\\{u:\\ u\(x\)=\\int\_\{\\mathcal\{P\}\}\\psi\_\{\\theta,N\}\(x\)\\,d\\lambda\(\\theta\),\\quad\|\\lambda\|\(\\mathcal\{P\}\)\\leq V\\right\\\}\.\(37\)NoL2L^\{2\}closure is invoked in this definition\. The class is convex, contains every±V​ψθ,N\\pm V\\psi\_\{\\theta,N\}, contains the comparator from Lemma[4\.2](https://arxiv.org/html/2608.20812#S4.Thmtheorem2), and satisfies

\|u⁡\(x\)\|≤Vfor every​u∈𝒞N,V\.\|u\(x\)\|\\leq V\\qquad\\text\{for every \}u\\in\\mathcal\{C\}\_\{N,V\}\.\(38\)
#### Fully\-corrective normalized greedy algorithm\.

Setu0=0u\_\{0\}=0and residualsrk−1,i=Yi−uk−1​\(Xi\)r\_\{k\-1,i\}=Y\_\{i\}\-u\_\{k\-1\}\(X\_\{i\}\)\. The linear minimization oracle over𝒞N,V\\mathcal\{C\}\_\{N,V\}is equivalent, up to the irrelevant factorVV, to selecting

θk∈arg​maxθ=\(w,b\)⁡\|1n​∑i=1nrk−1,i​ρ​\(b\+∑j=1Nwj​hj​\(Xi\)\)\|1\+‖w‖ℓ22\+b2\.\\theta\_\{k\}\\in\\operatorname\*\{arg\\,max\}\_\{\\theta=\(w,b\)\}\\frac\{\\left\|\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}r\_\{k\-1,i\}\\rho\\\!\\left\(b\+\\sum\_\{j=1\}^\{N\}w\_\{j\}h\_\{j\}\(X\_\{i\}\)\\right\)\\right\|\}\{1\+\\sqrt\{\\left\\lVert w\\right\\rVert\_\{\\ell^\{2\}\}^\{2\}\+b^\{2\}\}\}\.\(39\)The domainθ=\(w,b\)∈ℝN×ℝ\\theta=\(w,b\)\\in\\mathbb\{R\}^\{N\}\\times\\mathbb\{R\}in \([39](https://arxiv.org/html/2608.20812#S7.E39)\) is not compact, so existence of a maximizer is not automatic\. It does hold, by a standard coercivity argument: writeM:=supθ\(objective\)≥0M:=\\sup\_\{\\theta\}\(\\text\{objective\}\)\\geq 0\. IfM=0M=0\(the residual is uncorrelated, on the sample, with every candidate atom\), the supremum is trivially attained atθ=0\\theta=0\. IfM\>0M\>0, the objective is continuous inθ\\theta\(asρ\\rhois continuous\) and tends to00as‖θ‖𝒫→∞\\left\\lVert\\theta\\right\\rVert\_\{\\mathcal\{P\}\}\\to\\infty, because its numerator is bounded byn−1​∑i\|rk−1,i\|n^\{\-1\}\\sum\_\{i\}\|r\_\{k\-1,i\}\|while its denominator grows without bound; hence there isR\>0R\>0with objective<M/2<M/2whenever‖θ‖𝒫\>R\\left\\lVert\\theta\\right\\rVert\_\{\\mathcal\{P\}\}\>R, so every maximizing sequence eventually lies in the compact ball\{‖θ‖𝒫≤R\}\\\{\\left\\lVert\\theta\\right\\rVert\_\{\\mathcal\{P\}\}\\leq R\\\}, on which the supremum is attained by continuity\. This settles existence but not tractability: as with Proposition[7\.1](https://arxiv.org/html/2608.20812#S7.Thmtheorem1)below, the guarantees that follow assume access to an oracle that solves \([39](https://arxiv.org/html/2608.20812#S7.E39)\) exactly, and we make no claim that the underlying nonconvex selection problem can be solved efficiently in practice\.

After adding the selected signed atom, refit all active coefficients by

uk∈arg​mina1,…,ak⁡Rn​\(∑j=1kaj​ψθj,N\)subject to∑j=1k\|aj\|≤V\.u\_\{k\}\\in\\operatorname\*\{arg\\,min\}\_\{a\_\{1\},\\ldots,a\_\{k\}\}R\_\{n\}\\\!\\left\(\\sum\_\{j=1\}^\{k\}a\_\{j\}\\psi\_\{\\theta\_\{j\},N\}\\right\)\\quad\\text\{subject to\}\\quad\\sum\_\{j=1\}^\{k\}\|a\_\{j\}\|\\leq V\.\(40\)Equivalently, ifβj\\beta\_\{j\}multiplies the unnormalized atomgθj,Ng\_\{\\theta\_\{j\},N\}, then

∑j=1k\|βj\|\(1\+‖θj‖𝒫\)≤V\.\\sum\_\{j=1\}^\{k\}\|\\beta\_\{j\}\|\(1\+\\left\\lVert\\theta\_\{j\}\\right\\rVert\_\{\\mathcal\{P\}\}\)\\leq V\.This is the same measure/conditional\-gradient geometry that appears in convex neural network formulations such as\[[1](https://arxiv.org/html/2608.20812#bib.bib1)\]and in projection\-free convex optimization\[[7](https://arxiv.org/html/2608.20812#bib.bib7)\]; the full correction is used here to keep all empirical iterates inside the statistically controlled ball\. The negative result of\[[17](https://arxiv.org/html/2608.20812#bib.bib17)\]explains why an unconstrained orthogonal refit cannot generally be assumed to have this property: the population algorithm of Section[5](https://arxiv.org/html/2608.20812#S5)can afford an unconstrained orthogonal refit because coefficient growth causes no empirical\-complexity issue there, whereas in the sampled problem nearly dependent selected atoms can drive the variation\-norm coefficients arbitrarily large, so the empirical algorithm instead performs least squares under the fixed weighted budget\. The two correction steps are summarized here for reference\.

###### Proposition 7\.1\(Empirical greedy optimization error\)\.

Assume the linear oracle is solved exactly and setRn∗:=infu∈𝒞N,VRn​\(u\)R\_\{n\}^\{\*\}:=\\inf\_\{u\\in\\mathcal\{C\}\_\{N,V\}\}R\_\{n\}\(u\)\. Then

Rn​\(um\)−Rn∗≤16​V2m\+3\.R\_\{n\}\(u\_\{m\}\)\-R\_\{n\}^\{\*\}\\leq\\frac\{16V^\{2\}\}\{m\+3\}\.\(41\)

###### Proof\.

Use the empirical norm‖u‖n2=n−1​∑iu​\(Xi\)2\\left\\lVert u\\right\\rVert\_\{n\}^\{2\}=n^\{\-1\}\\sum\_\{i\}u\(X\_\{i\}\)^\{2\}\. The feasible class has radius at mostVVand diameter at most2​V2V\. LetF​\(u\)=Rn​\(u\)F\(u\)=R\_\{n\}\(u\)andΔk=F⁡\(uk\)−infu∈𝒞N,VF⁡\(u\)\\Delta\_\{k\}=F\(u\_\{k\}\)\-\\inf\_\{u\\in\\mathcal\{C\}\_\{N,V\}\}F\(u\)\. For an arbitrarily accurate minimizeru∗u^\{\*\}, the exact linear oracle producesqk∈𝒞N,Vq\_\{k\}\\in\\mathcal\{C\}\_\{N,V\}with

⟨∇F​\(uk\),qk⟩n≤⟨∇F​\(uk\),u∗⟩n\.\\left\\langle\\nabla F\(u\_\{k\}\),q\_\{k\}\\right\\rangle\_\{n\}\\leq\\left\\langle\\nabla F\(u\_\{k\}\),u^\{\*\}\\right\\rangle\_\{n\}\.By convexity,⟨∇F​\(uk\),uk−qk⟩n≥Δk\\left\\langle\\nabla F\(u\_\{k\}\),u\_\{k\}\-q\_\{k\}\\right\\rangle\_\{n\}\\geq\\Delta\_\{k\}\. Forα∈\[0,1\]\\alpha\\in\[0,1\], full correction is at least as good as the feasible segment pointuk\+α⁡\(qk−uk\)u\_\{k\}\+\\alpha\(q\_\{k\}\-u\_\{k\}\), and the quadratic loss gives

Δk\+1≤\(1−α\)​Δk\+4​V2​α2\.\\Delta\_\{k\+1\}\\leq\(1\-\\alpha\)\\Delta\_\{k\}\+4V^\{2\}\\alpha^\{2\}\.\(42\)Takingα=1\\alpha=1at the first step yieldsΔ1≤4​V2\\Delta\_\{1\}\\leq 4V^\{2\}\. IfΔk≤16​V2/\(k\+3\)\\Delta\_\{k\}\\leq 16V^\{2\}/\(k\+3\), chooseα=2/\(k\+4\)\\alpha=2/\(k\+4\)in \([42](https://arxiv.org/html/2608.20812#S7.E42)\); direct substitution givesΔk\+1≤16​V2/\(k\+4\)\\Delta\_\{k\+1\}\\leq 16V^\{2\}/\(k\+4\)\. Induction proves the claim\. ∎

## 8End\-to\-end statistical guarantee

Assume\|Y\|≤B\|Y\|\\leq Balmost surely and letf⋆​\(x\)=𝔼⁡\[Y∣X=x\]f\_\{\\star\}\(x\)=\\mathbb\{E\}\[Y\\mid X=x\]\. To avoid a spurious empirical\-population discrepancy in theY2Y^\{2\}term, work with the centered squared loss

ℓu​\(x,y\):=u​\(x\)2−2​y​u​\(x\)\.\\ell\_\{u\}\(x,y\):=u\(x\)^\{2\}\-2yu\(x\)\.\(43\)LetL⁡\(u\)=𝔼⁡\[ℓu​\(X,Y\)\]L\(u\)=\\mathbb\{E\}\[\\ell\_\{u\}\(X,Y\)\]andLn​\(u\)=n−1​∑iℓu​\(Xi,Yi\)L\_\{n\}\(u\)=n^\{\-1\}\\sum\_\{i\}\\ell\_\{u\}\(X\_\{i\},Y\_\{i\}\)\. SinceRn​\(u\)=n−1​∑iYi2\+Ln​\(u\)R\_\{n\}\(u\)=n^\{\-1\}\\sum\_\{i\}Y\_\{i\}^\{2\}\+L\_\{n\}\(u\), minimizingRnR\_\{n\}is equivalent to minimizingLnL\_\{n\}\. Moreover,

L⁡\(u\)−L⁡\(f⋆\)=‖u−f⋆‖L2​\(μ\)2\.L\(u\)\-L\(f\_\{\\star\}\)=\\left\\lVert u\-f\_\{\\star\}\\right\\rVert\_\{L^\{2\}\(\\mu\)\}^\{2\}\.\(44\)
###### Theorem 8\.1\(Dimension\-uniform empirical greedy learning\)\.

Assume\|Y\|≤B\|Y\|\\leq Balmost surely and suppose

f⋆​\(x\)=∫gθ​\(x\)​𝑑ν​\(θ\),∫\(1\+‖θ‖𝒫\)​d​\|ν\|​\(θ\)≤V\.f\_\{\\star\}\(x\)=\\int g\_\{\\theta\}\(x\)\\,d\\nu\(\\theta\),\\qquad\\int\(1\+\\left\\lVert\\theta\\right\\rVert\_\{\\mathcal\{P\}\}\)\\,d\|\\nu\|\(\\theta\)\\leq V\.\(45\)Letf^m,N=um\\widehat\{f\}\_\{m,N\}=u\_\{m\}be the fully\-corrective greedy estimator with an exact linear oracle\. Then there are universal constantsC1,C2\>0C\_\{1\},C\_\{2\}\>0such that, with probability at least1−δ1\-\\delta,

‖f^m,N−f⋆‖L2​\(μ\)2≤V2​ηN​\(μ\)2\+16​V2m\+3\+C1​\(B\+V\)​V​K\+1\+log⁡\(2\+log⁡n\)n\+C2​\(B\+V\)2​log⁡\(2/δ\)n\.\\boxed\{\\begin\{aligned\} \\left\\lVert\\widehat\{f\}\_\{m,N\}\-f\_\{\\star\}\\right\\rVert\_\{L^\{2\}\(\\mu\)\}^\{2\}\\leq\{\}&V^\{2\}\\eta\_\{N\}\(\\mu\)^\{2\}\+\\frac\{16V^\{2\}\}\{m\+3\}\\\\ &\+C\_\{1\}\(B\+V\)V\\frac\{K\+1\+\\sqrt\{\\log\(2\+\\log n\)\}\}\{\\sqrt\{n\}\}\\\\ &\+C\_\{2\}\(B\+V\)^\{2\}\\sqrt\{\\frac\{\\log\(2/\\delta\)\}\{n\}\}\.\\end\{aligned\}\}\(46\)The sampling terms contain no explicit dependence on the coordinate resolutionNN\.

###### Proof\.

LetfNf\_\{N\}be the comparator from Lemma[4\.2](https://arxiv.org/html/2608.20812#S4.Thmtheorem2)\. ThenfN∈𝒞N,Vf\_\{N\}\\in\\mathcal\{C\}\_\{N,V\}and‖fN−f⋆‖2≤V​ηN​\(μ\)\\left\\lVert f\_\{N\}\-f\_\{\\star\}\\right\\rVert\_\{2\}\\leq V\\eta\_\{N\}\(\\mu\)\. Proposition[7\.1](https://arxiv.org/html/2608.20812#S7.Thmtheorem1)gives

Ln​\(f^m,N\)≤Ln​\(fN\)\+16​V2m\+3\.L\_\{n\}\(\\widehat\{f\}\_\{m,N\}\)\\leq L\_\{n\}\(f\_\{N\}\)\+\\frac\{16V^\{2\}\}\{m\+3\}\.\(47\)
For the statistical transfer, the integral definition of𝒞N,V\\mathcal\{C\}\_\{N,V\}implies directly that

ℜ^S​\(𝒞N,V\)≤V​ℜ^S​\(𝒟N♯\)\.\\widehat\{\\mathfrak\{R\}\}\_\{S\}\(\\mathcal\{C\}\_\{N,V\}\)\\leq V\\widehat\{\\mathfrak\{R\}\}\_\{S\}\(\\mathcal\{D\}\_\{N\}^\{\\sharp\}\)\.\(48\)Indeed, a linear functional is maximized over the total\-variation ball by a signed point mass\. By Lemma[6\.2](https://arxiv.org/html/2608.20812#S6.Thmtheorem2), the right\-hand side is bounded by

C0​V​K\+1\+log⁡\(2\+log⁡n\)n\.C\_\{0\}V\\frac\{K\+1\+\\sqrt\{\\log\(2\+\\log n\)\}\}\{\\sqrt\{n\}\}\.
For\|y\|≤B\|y\|\\leq Band\|u\|≤V\|u\|\\leq V, the mapt↦t2−2​y​tt\\mapsto t^\{2\}\-2ytvanishes at zero, is2​\(B\+V\)2\(B\+V\)\-Lipschitz on\[−V,V\]\[\-V,V\], and has absolute value at most a universal multiple of\(B\+V\)2\(B\+V\)^\{2\}\. Standard symmetrization, contraction, and bounded\-difference concentration\[[3](https://arxiv.org/html/2608.20812#bib.bib3),[13](https://arxiv.org/html/2608.20812#bib.bib13)\]therefore imply that, with probability at least1−δ1\-\\delta,

supu∈𝒞N,V\|L⁡\(u\)−Ln​\(u\)\|≤C3​\(B\+V\)​V​K\+1\+log⁡\(2\+log⁡n\)n\+C4​\(B\+V\)2​log⁡\(2/δ\)n\.\\sup\_\{u\\in\\mathcal\{C\}\_\{N,V\}\}\|L\(u\)\-L\_\{n\}\(u\)\|\\leq C\_\{3\}\(B\+V\)V\\frac\{K\+1\+\\sqrt\{\\log\(2\+\\log n\)\}\}\{\\sqrt\{n\}\}\+C\_\{4\}\(B\+V\)^\{2\}\\sqrt\{\\frac\{\\log\(2/\\delta\)\}\{n\}\}\.\(49\)Apply \([49](https://arxiv.org/html/2608.20812#S8.E49)\) to bothf^m,N\\widehat\{f\}\_\{m,N\}andfNf\_\{N\}in \([47](https://arxiv.org/html/2608.20812#S8.E47)\), then use \([44](https://arxiv.org/html/2608.20812#S8.E44)\) and‖fN−f⋆‖22≤V2​ηN​\(μ\)2\\left\\lVert f\_\{N\}\-f\_\{\\star\}\\right\\rVert\_\{2\}^\{2\}\\leq V^\{2\}\\eta\_\{N\}\(\\mu\)^\{2\}\. Absorb numerical constants intoC1,C2C\_\{1\},C\_\{2\}\. ∎

###### Corollary 8\.2\(Canonical quasi\-Polish envelope\)\.

If\|hj\|≤1/j\|h\_\{j\}\|\\leq 1/j, then with probability at least1−δ1\-\\delta,

‖f^m,N−f⋆‖22≤\\displaystyle\\left\\lVert\\widehat\{f\}\_\{m,N\}\-f\_\{\\star\}\\right\\rVert\_\{2\}^\{2\}\\leq\{\}V2N\+16​V2m\+3\\displaystyle\\frac\{V^\{2\}\}\{N\}\+\\frac\{16V^\{2\}\}\{m\+3\}\+C1′​\(B\+V\)​V​1\+log⁡\(2\+log⁡n\)n\+C2​\(B\+V\)2​log⁡\(2/δ\)n\.\\displaystyle\+C\_\{1\}^\{\\prime\}\(B\+V\)V\\frac\{1\+\\sqrt\{\\log\(2\+\\log n\)\}\}\{\\sqrt\{n\}\}\+C\_\{2\}\(B\+V\)^\{2\}\\sqrt\{\\frac\{\\log\(2/\\delta\)\}\{n\}\}\.\(50\)Thus the heuristic balanceN≍m≍nN\\asymp m\\asymp\\sqrt\{n\}matches the two deterministic squared\-error contributions to the globaln−1/2n^\{\-1/2\}sampling scale, up to logarithmic factors\.

## 9Synthetic experiments

This section reports two complementary numerical illustrations, both built on finite candidate dictionaries in place of the continuous nonconvex oracle\. Section[9\.1](https://arxiv.org/html/2608.20812#S9.SS1)probes the three mechanisms separated by the end\-to\-end guarantee of Theorem[8\.1](https://arxiv.org/html/2608.20812#S8.Thmtheorem1)\(coordinate resolution, greedy width, and sample size\) one at a time\. Section[9\.2](https://arxiv.org/html/2608.20812#S9.SS2)then isolates the weighted\-versus\-unweighted contrast quantified by Corollary[3\.4](https://arxiv.org/html/2608.20812#S3.Thmtheorem4)\. Neither experiment is intended to validate theorem constants or to demonstrate that the continuous oracle is computationally tractable\.

### 9\.1Three\-regime synthetic experiment: resolution, width, and sample size

The theorem separates three mechanisms, but the continuous oracle in \([39](https://arxiv.org/html/2608.20812#S7.E39)\) is computationally nontrivial\. We therefore use a deliberately simple finite\-candidate experiment whose purpose is only to illustrate the three regimes\.

#### Data and target\.

We truncate a synthetic input at a maximal ambient dimensionD=48D=48and draw independentξj∼Unif⁡\[−1,1\]\\xi\_\{j\}\\sim\\mathrm\{Unif\}\[\-1,1\], setting

hj​\(x\)=ξjj\.h\_\{j\}\(x\)=\\frac\{\\xi\_\{j\}\}\{j\}\.Thus the canonical envelope\|hj\|≤1/j\|h\_\{j\}\|\\leq 1/jholds exactly\. The noiseless target is a finite combination of2020normalized atoms\. The absolute sum of its normalized outer coefficients is7\.367\.36, below the algorithmic budgetV=8V=8\. The candidate dictionary contains the2020target atoms plus108108independently generated distractor atoms\. Hence the experiment is favorable to the finite oracle: at full resolution the target is contained in the candidate variation ball\.

At each greedy step we maximize residual correlation over these128128candidates and then approximately solve the fully\-correctiveℓ1\\ell^\{1\}\-constrained least\-squares problem by projected accelerated gradient\. A held\-out set of60006000points is used for all reported test errors\. Curves show means and standard deviations over three repetitions\.

#### Resolution sweep\.

To isolate truncation, we use40964096noiseless training observations andm=20m=20greedy steps while varyingNN\. Figure[1](https://arxiv.org/html/2608.20812#S9.F1)shows a monotone decrease in test error as more coordinates are retained\. The dashedN−1N^\{\-1\}line is only the worst\-case squared\-error reference suggested by the canonical envelope; the theorem does not predict equality with that slope for this distribution and target\. The final sharp drop atN=48N=48reflects the finite ambient construction and the fact that all true atoms are present in the candidate pool\.

Figure 1:Resolution sweep\. Training labels are noiseless andm=20m=20is fixed\. The dashed line is anN−1N^\{\-1\}reference, not a fitted law\.
#### Width sweep\.

With full resolutionN=48N=48and40964096noiseless observations, increasing the number of greedy atoms reduces the test error by more than three orders of magnitude, as shown in Figure[2](https://arxiv.org/html/2608.20812#S9.F2)\. Because the target itself is a2020\-atom combination included in the pool, the error becomes nearly numerical atm=20m=20\. The dashedm−1m^\{\-1\}line again serves only as the theorem’s generic squared\-error reference\.

Figure 2:Width sweep at full resolution\. The finite candidate pool contains the target atoms, so the last point is intentionally an easy endpoint\.
#### Sample\-size sweep\.

Finally, fixN=48N=48andm=20m=20, and add independent bounded noise with standard deviation0\.080\.08\(uniform on\[−3​0\.08,3​0\.08\]\[\-\\sqrt\{3\}\\,0\.08,\\sqrt\{3\}\\,0\.08\]\)\. Figure[3](https://arxiv.org/html/2608.20812#S9.F3)plots test MSE against the noiseless regression function\. Across the tested range the curve is consistent with a roughlyn−1/2n^\{\-1/2\}global\-complexity scale, although no asymptotic claim is made from this small experiment\.

Figure 3:Sample\-size sweep with bounded observation noise\. The dashed line is ann−1/2n^\{\-1/2\}reference\.The experiment should therefore be read as a sanity check for the decomposition rather than evidence that the continuous oracle is tractable\. A stronger computational paper would need either a provable approximate neuron oracle or a realistic operator\-learning benchmark in which the cost of increasingNNis measured explicitly\.

### 9\.2Weighted versus unweighted variation: a numerical illustration

Corollary[3\.4](https://arxiv.org/html/2608.20812#S3.Thmtheorem4)proves in the present one\-dimensional setting thatλ≤‖fλ‖ℬH♯≤1\+λ\\lambda\\leq\\left\\lVert f\_\{\\lambda\}\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\}\\leq 1\+\\lambda, whereas‖fλ‖ℬH≤1\\left\\lVert f\_\{\\lambda\}\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}\}\\leq 1\. We complement this exact class separation with a small numerical experiment that puts the two variation classes side by side under a matched, finite representation budget\.

#### Setup\.

We work with a single coordinateh1​\(x\)=xh\_\{1\}\(x\)=x,x∈\[−1,1\]x\\in\[\-1,1\], andc=0c=0, matching Remark[3\.5](https://arxiv.org/html/2608.20812#S3.Thmtheorem5)exactly \(sop\+=μ⁡\(h1\>0\)=12p\_\{\+\}=\\mu\(h\_\{1\}\>0\)=\\tfrac\{1\}\{2\}under the uniform reference measure used for evaluation\)\. For a grid of sharpness valuesλ∈\{1,2,4,…,256\}\\lambda\\in\\\{1,2,4,\\dots,256\\\}we fit the targetfλf\_\{\\lambda\}on40004000evenly spaced test points using a finite candidate pool of130130atomsg\(w,b\)g\_\{\(w,b\)\}, built from a grid of1010slopesw∈\{0\.5,1,2,…,256\}w\\in\\\{0\.5,1,2,\\dots,256\\\}and1313thresholdsb∈\[−0\.6,0\.6\]b\\in\[\-0\.6,0\.6\]– deliberately richer than the single canonical atom, so that the weighted fit is free to combine several affordable atoms if that would let it track a sharp target more cheaply than the canonical representation\. Each target is fit twice, by the same fully\-corrective projected\-gradient scheme used in Section[9\.1](https://arxiv.org/html/2608.20812#S9.SS1)with budgetV=8V=8: once over the raw atomsg\(w,b\)g\_\{\(w,b\)\}with the classical unweighted budget∑i\|ai\|≤V\\sum\_\{i\}\|a\_\{i\}\|\\leq V, and once over the normalized atomsψ\(w,b\)=g\(w,b\)/\(1\+w2\+b2\)\\psi\_\{\(w,b\)\}=g\_\{\(w,b\)\}/\(1\+\\sqrt\{w^\{2\}\+b^\{2\}\}\)with the weighted budget∑i\|ai\|≤V\\sum\_\{i\}\|a\_\{i\}\|\\leq Vused throughout Sections[7](https://arxiv.org/html/2608.20812#S7)–[8](https://arxiv.org/html/2608.20812#S8)\. The complete code is provided with the manuscript

Figure 4:Left: test MSE againstfλf\_\{\\lambda\}under a matched budgetV=8V=8, for the unweighted \(classical\) and weighted \(ℬH♯\\mathcal\{B\}\_\{H\}^\{\\sharp\}\) variation classes\. Right: the canonical single\-atom weighted cost1\+λ1\+\\lambda, which is an upper bound on‖fλ‖ℬH♯\\left\\lVert f\_\{\\lambda\}\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\}and differs by one from the new lower boundλ\\lambdain Corollary[3\.4](https://arxiv.org/html/2608.20812#S3.Thmtheorem4); the canonical cost crossesV=8V=8atλ=7\\lambda=7\.
#### Result and relation to Corollary[3\.4](https://arxiv.org/html/2608.20812#S3.Thmtheorem4)\.

Figure[4](https://arxiv.org/html/2608.20812#S9.F4)shows a clean separation between the two fixed\-radius classes\. Corollary[3\.4](https://arxiv.org/html/2608.20812#S3.Thmtheorem4)now gives a rigorous explanation in this one\-dimensional setting:

λ≤‖fλ‖ℬH♯≤1\+λ,‖fλ‖ℬH≤1\.\\lambda\\leq\\left\\lVert f\_\{\\lambda\}\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\}\\leq 1\+\\lambda,\\qquad\\left\\lVert f\_\{\\lambda\}\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}\}\\leq 1\.Thus a fixed weighted budgetV=8V=8cannot containfλf\_\{\\lambda\}onceλ\>8\\lambda\>8, while the corresponding unweighted ball already contains the exact target for everyλ\\lambdathrough its single raw atom\. The numerical curves are consistent with this sharp theoretical distinction: the unweighted fit remains near numerical accuracy, whereas the weighted fit deteriorates rapidly asλ\\lambdapasses the fixed budget\. The right panel displays the canonical upper bound1\+λ1\+\\lambda; the new lower boundλ\\lambdadiffers from it by only one unit, so the weighted norm is pinned down to a unit\-width interval for this family\.

#### Computational caveat\.

The experiment still uses a finite candidate pool and therefore does not certify that the projected\-gradient solver finds the best continuum representation at a given budget\. This limitation concerns the numerical optimizer, not the class separation: Corollary[3\.4](https://arxiv.org/html/2608.20812#S3.Thmtheorem4)proves independently of the candidate pool thatfλf\_\{\\lambda\}lies outside the radius\-VVweighted ball wheneverλ\>V\\lambda\>V\.

## 10Hilbert\-valued targets

Let𝒴\\mathcal\{Y\}be a separable real Hilbert space \(so𝒴≅ℝd\\mathcal\{Y\}\\cong\\mathbb\{R\}^\{d\}or𝒴≅ℓ2\\mathcal\{Y\}\\cong\\ell^\{2\}\) with orthonormal basis\(sk\)k≥1\(s\_\{k\}\)\_\{k\\geq 1\}, and letF:𝒳→𝒴F:\\mathcal\{X\}\\to\\mathcal\{Y\}\. We extend the scalar atoms by an output direction,

Ψθ,v​\(x\):=ψθ​\(x\)​v,θ∈𝒫,v∈𝒴,‖v‖𝒴≤1,\\Psi\_\{\\theta,v\}\(x\):=\\psi\_\{\\theta\}\(x\)v,\\qquad\\theta\\in\\mathcal\{P\},\\quad v\\in\\mathcal\{Y\},\\ \\left\\lVert v\\right\\rVert\_\{\\mathcal\{Y\}\}\\leq 1,\(51\)so that‖Ψθ,v​\(x\)‖𝒴≤1\\left\\lVert\\Psi\_\{\\theta,v\}\(x\)\\right\\rVert\_\{\\mathcal\{Y\}\}\\leq 1pointwise, exactly as in \([9](https://arxiv.org/html/2608.20812#S3.E9)\)\.

###### Lemma 10\.1\(Linear oracle for Hilbert\-valued targets\)\.

For everyR∈L2​\(μ,𝒴\)R\\in L^\{2\}\(\\mu;\\mathcal\{Y\}\)and everyθ∈𝒫\\theta\\in\\mathcal\{P\},

sup‖v‖𝒴≤1\|⟨R,ψθ​v⟩L2​\(μ,𝒴\)\|=‖∫𝒳ψθ​\(x\)​R​\(x\)​μ​\(𝑑x\)‖𝒴,\\sup\_\{\\left\\lVert v\\right\\rVert\_\{\\mathcal\{Y\}\}\\leq 1\}\\bigl\|\\left\\langle R,\\psi\_\{\\theta\}v\\right\\rangle\_\{L^\{2\}\(\\mu;\\mathcal\{Y\}\)\}\\bigr\|=\\left\\lVert\\int\_\{\\mathcal\{X\}\}\\psi\_\{\\theta\}\(x\)R\(x\)\\,\\mu\(dx\)\\right\\rVert\_\{\\mathcal\{Y\}\},\(52\)and, when the vector on the right is nonzero, the supremum on the left is attained at its normalization\.

###### Proof\.

Writeζ⁡\(θ\):=∫𝒳ψθ​\(x\)​R​\(x\)​μ​\(𝑑x\)∈𝒴\\zeta\(\\theta\):=\\int\_\{\\mathcal\{X\}\}\\psi\_\{\\theta\}\(x\)R\(x\)\\,\\mu\(dx\)\\in\\mathcal\{Y\}\(well defined since‖ψθ‖L∞≤1\\left\\lVert\\psi\_\{\\theta\}\\right\\rVert\_\{L^\{\\infty\}\}\\leq 1andR∈L2​\(μ,𝒴\)⊂L1​\(μ,𝒴\)R\\in L^\{2\}\(\\mu;\\mathcal\{Y\}\)\\subset L^\{1\}\(\\mu;\\mathcal\{Y\}\)on the probability space\(𝒳,μ\)\(\\mathcal\{X\},\\mu\)\)\. By Fubini for the scalar pairing,

⟨R,ψθ​v⟩L2​\(μ,𝒴\)=∫𝒳ψθ​\(x\)​⟨R⁡\(x\),v⟩𝒴​μ​\(𝑑x\)=⟨ζ⁡\(θ\),v⟩𝒴\.\\left\\langle R,\\psi\_\{\\theta\}v\\right\\rangle\_\{L^\{2\}\(\\mu;\\mathcal\{Y\}\)\}=\\int\_\{\\mathcal\{X\}\}\\psi\_\{\\theta\}\(x\)\\left\\langle R\(x\),v\\right\\rangle\_\{\\mathcal\{Y\}\}\\,\\mu\(dx\)=\\left\\langle\\zeta\(\\theta\),v\\right\\rangle\_\{\\mathcal\{Y\}\}\.Hence the left side of \([52](https://arxiv.org/html/2608.20812#S10.E52)\) equalssup‖v‖≤1\|⟨ζ⁡\(θ\),v⟩\|=‖ζ⁡\(θ\)‖𝒴\\sup\_\{\\left\\lVert v\\right\\rVert\\leq 1\}\|\\left\\langle\\zeta\(\\theta\),v\\right\\rangle\|=\\left\\lVert\\zeta\(\\theta\)\\right\\rVert\_\{\\mathcal\{Y\}\}by the Riesz representation of the norm on a Hilbert space, attained atv=ζ⁡\(θ\)/‖ζ⁡\(θ\)‖v=\\zeta\(\\theta\)/\\left\\lVert\\zeta\(\\theta\)\\right\\rVertwheneverζ⁡\(θ\)≠0\\zeta\(\\theta\)\\neq 0\. ∎

Lemma[10\.1](https://arxiv.org/html/2608.20812#S10.Thmtheorem1)shows that the output direction of the linear minimization oracle \([39](https://arxiv.org/html/2608.20812#S7.E39)\) can be eliminated analytically – the greedy step still reduces to a search over the scalar parameterθ\\thetaalone, with the optimalvvread off in closed form – and that the coordinate\-truncation argument of Section[4](https://arxiv.org/html/2608.20812#S4)is unchanged, since it acts only on the scalar input atomψθ\\psi\_\{\\theta\}, not onvv\. This is a genuine computational simplification, but it says nothing yet about statistical complexity, which is where the vector\-valued case departs from the scalar one\.

###### Definition 10\.2\(Weighted vector variation class\)\.

ForF∈L2​\(μ,𝒴\)F\\in L^\{2\}\(\\mu;\\mathcal\{Y\}\), let𝔐𝒴​\(F\)\\mathfrak\{M\}\_\{\\mathcal\{Y\}\}\(F\)be the collection of pairs\(ν,w\)\(\\nu,w\)whereν\\nuis a finite nonnegative Borel measure on𝒫\\mathcal\{P\}andw:𝒫→𝒴w:\\mathcal\{P\}\\to\\mathcal\{Y\}isν\\nu\-measurable with‖w⁡\(θ\)‖𝒴≤1\\left\\lVert w\(\\theta\)\\right\\rVert\_\{\\mathcal\{Y\}\}\\leq 1forν\\nu\-a\.e\.θ\\theta, such that

F⁡\(x\)=∫𝒫ψθ​\(x\)​w​\(θ\)​ν​\(𝑑θ\)for​μ​\-a\.e\.​x\.F\(x\)=\\int\_\{\\mathcal\{P\}\}\\psi\_\{\\theta\}\(x\)\\,w\(\\theta\)\\,\\nu\(d\\theta\)\\qquad\\text\{for \}\\mu\\text\{\-a\.e\.\\ \}x\.Define

‖F‖ℬH♯​\(𝒴\):=inf\(ν,w\)∈𝔐𝒴​\(F\)ν⁡\(𝒫\)\.\\left\\lVert F\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\(\\mathcal\{Y\}\)\}:=\\inf\_\{\(\\nu,w\)\\in\\mathfrak\{M\}\_\{\\mathcal\{Y\}\}\(F\)\}\\nu\(\\mathcal\{P\}\)\.\(53\)

This mirrors theλ\\lambda\-representation \([15](https://arxiv.org/html/2608.20812#S3.E15)\) of Definition[3\.2](https://arxiv.org/html/2608.20812#S3.Thmtheorem2), not the rawν\\nu\-representation \([11](https://arxiv.org/html/2608.20812#S3.E11)\): sinceψθ\\psi\_\{\\theta\}already carries the weight1/\(1\+‖θ‖𝒫\)1/\(1\+\\left\\lVert\\theta\\right\\rVert\_\{\\mathcal\{P\}\}\), the cost of a representation is simply the total massν⁡\(𝒫\)\\nu\(\\mathcal\{P\}\), with*no*further reweighting by\(1\+‖θ‖𝒫\)\(1\+\\left\\lVert\\theta\\right\\rVert\_\{\\mathcal\{P\}\}\)– reintroducing that factor here would double\-count it\. For𝒴=ℝ\\mathcal\{Y\}=\\mathbb\{R\}\(sow:𝒫→\[−1,1\]w:\\mathcal\{P\}\\to\[\-1,1\]\), we check‖⋅‖ℬH♯​\(ℝ\)=‖⋅‖ℬH♯\\left\\lVert\\cdot\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\(\\mathbb\{R\}\)\}=\\left\\lVert\\cdot\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\}by the two inequalities that make up equality of the two infima\.

First,‖f‖ℬH♯≤‖f‖ℬH♯​\(ℝ\)\\left\\lVert f\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\}\\leq\\left\\lVert f\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\(\\mathbb\{R\}\)\}: given any\(ν,w\)∈𝔐ℝ​\(f\)\(\\nu,w\)\\in\\mathfrak\{M\}\_\{\\mathbb\{R\}\}\(f\), setd​λ:=w​d​νd\\lambda:=w\\,d\\nu, a signed measure withf=∫𝒫ψθ​𝑑λf=\\int\_\{\\mathcal\{P\}\}\\psi\_\{\\theta\}\\,d\\lambda\(a validλ\\lambda\-representation in the sense of \([15](https://arxiv.org/html/2608.20812#S3.E15)\)\) and, since\|w⁡\(θ\)\|≤1\|w\(\\theta\)\|\\leq 1pointwise andν≥0\\nu\\geq 0,\|λ\|=\|w\|​ν≤ν\|\\lambda\|=\|w\|\\,\\nu\\leq\\nuas measures – so\|λ\|​\(𝒫\)≤ν​\(𝒫\)\|\\lambda\|\(\\mathcal\{P\}\)\\leq\\nu\(\\mathcal\{P\}\): no mass is discarded, it is absorbed intoλ\\lambdaand reweighted by\|w\|\|w\|instead\. Hence‖f‖ℬH♯≤\|λ\|\(𝒫\)≤ν⁡\(𝒫\)\\left\\lVert f\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\}\\leq\|\\lambda\|\(\\mathcal\{P\}\)\\leq\\nu\(\\mathcal\{P\}\)for every\(ν,w\)∈𝔐ℝ​\(f\)\(\\nu,w\)\\in\\mathfrak\{M\}\_\{\\mathbb\{R\}\}\(f\); taking the infimum over\(ν,w\)\(\\nu,w\)gives‖f‖ℬH♯≤‖f‖ℬH♯​\(ℝ\)\\left\\lVert f\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\}\\leq\\left\\lVert f\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\(\\mathbb\{R\}\)\}\.

Second,‖f‖ℬH♯​\(ℝ\)≤‖f‖ℬH♯\\left\\lVert f\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\(\\mathbb\{R\}\)\}\\leq\\left\\lVert f\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\}: given anyλ\\lambda\-representationf=∫𝒫ψθ​𝑑λf=\\int\_\{\\mathcal\{P\}\}\\psi\_\{\\theta\}\\,d\\lambda, setν:=\|λ\|\\nu:=\|\\lambda\|andw:=sgn⁡\(λ\)w:=\\operatorname\{sgn\}\(\\lambda\)\(defined\|λ\|\|\\lambda\|\-a\.e\. and extended arbitrarily, sayw≡1w\\equiv 1, on the\|λ\|\|\\lambda\|\-null remainder, which does not affectν\\nuor the integral\)\. Then\(ν,w\)∈𝔐ℝ​\(f\)\(\\nu,w\)\\in\\mathfrak\{M\}\_\{\\mathbb\{R\}\}\(f\), sinceν≥0\\nu\\geq 0is finite,\|w\|≤1\|w\|\\leq 1ν\\nu\-a\.e\., and∫𝒫ψθ​w​𝑑ν=∫𝒫ψθ​𝑑λ=f\\int\_\{\\mathcal\{P\}\}\\psi\_\{\\theta\}w\\,d\\nu=\\int\_\{\\mathcal\{P\}\}\\psi\_\{\\theta\}\\,d\\lambda=f, at the same costν⁡\(𝒫\)=\|λ\|\(𝒫\)\\nu\(\\mathcal\{P\}\)=\|\\lambda\|\(\\mathcal\{P\}\)\. Hence‖f‖ℬH♯​\(ℝ\)≤ν⁡\(𝒫\)=\|λ\|\(𝒫\)\\left\\lVert f\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\(\\mathbb\{R\}\)\}\\leq\\nu\(\\mathcal\{P\}\)=\|\\lambda\|\(\\mathcal\{P\}\)for everyλ\\lambda\-representation; taking the infimum overλ\\lambdagives‖f‖ℬH♯​\(ℝ\)≤‖f‖ℬH♯\\left\\lVert f\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\(\\mathbb\{R\}\)\}\\leq\\left\\lVert f\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\}\.

Together,‖⋅‖ℬH♯​\(𝒴\)\\left\\lVert\\cdot\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\(\\mathcal\{Y\}\)\}reduces exactly to‖⋅‖ℬH♯\\left\\lVert\\cdot\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\}when𝒴=ℝ\\mathcal\{Y\}=\\mathbb\{R\}\.

For the statistical result it is useful to define the vector\-valued feasible class

𝒞N,V𝒴:=\{F\(x\)=∫𝒫ψθ,N\(x\)v\(θ\)ν\(dθ\):ν≥0,ν\(𝒫\)≤V,‖v\(θ\)‖𝒴≤1\}\.\\mathcal\{C\}\_\{N,V\}^\{\\mathcal\{Y\}\}:=\\left\\\{F\(x\)=\\int\_\{\\mathcal\{P\}\}\\psi\_\{\\theta,N\}\(x\)v\(\\theta\)\\,\\nu\(d\\theta\):\\nu\\geq 0,\\ \\nu\(\\mathcal\{P\}\)\\leq V,\\ \\left\\lVert v\(\\theta\)\\right\\rVert\_\{\\mathcal\{Y\}\}\\leq 1\\right\\\}\.\(54\)EveryF∈𝒞N,V𝒴F\\in\\mathcal\{C\}\_\{N,V\}^\{\\mathcal\{Y\}\}satisfies‖F⁡\(x\)‖𝒴≤V\\left\\lVert F\(x\)\\right\\rVert\_\{\\mathcal\{Y\}\}\\leq V\.

###### Lemma 10\.3\(Dimension\-uniform vector loss complexity\)\.

LetS=\(\(xi,𝐲i\)\)i=1nS=\(\(x\_\{i\},\\mathbf\{y\}\_\{i\}\)\)\_\{i=1\}^\{n\}satisfy‖𝐲i‖𝒴≤B\\left\\lVert\\mathbf\{y\}\_\{i\}\\right\\rVert\_\{\\mathcal\{Y\}\}\\leq B\. For the centered vector squared loss

ℓF​\(x,𝐲\):=‖F⁡\(x\)‖𝒴2−2​⟨𝐲,F⁡\(x\)⟩𝒴,\\ell\_\{F\}\(x,\\mathbf\{y\}\):=\\left\\lVert F\(x\)\\right\\rVert\_\{\\mathcal\{Y\}\}^\{2\}\-2\\left\\langle\\mathbf\{y\},F\(x\)\\right\\rangle\_\{\\mathcal\{Y\}\},there is a universal constantC\>0C\>0such that

ℜ^S​\(ℓ∘𝒞N,V𝒴\)≤C⁡\(V2\+B​V\)​K\+1\+log⁡\(2\+log⁡n\)n\.\\widehat\{\\mathfrak\{R\}\}\_\{S\}\\bigl\(\\ell\\circ\\mathcal\{C\}\_\{N,V\}^\{\\mathcal\{Y\}\}\\bigr\)\\leq C\\,\(V^\{2\}\+BV\)\\,\\frac\{K\+1\+\\sqrt\{\\log\(2\+\\log n\)\}\}\{\\sqrt\{n\}\}\.\(55\)The bound is independent of bothNNanddim\(𝒴\)\\dim\(\\mathcal\{Y\}\)\.

###### Proof\.

WriteAn:=K\+1\+log⁡\(2\+log⁡n\)A\_\{n\}:=K\+1\+\\sqrt\{\\log\(2\+\\log n\)\}\. For the linear part, by the integral representation and duality in𝒴\\mathcal\{Y\},

𝔼ε​supF∈𝒞N,V𝒴\|1n​∑iεi​⟨𝐲i,F⁡\(xi\)⟩\|\\displaystyle\\mathbb\{E\}\_\{\\varepsilon\}\\sup\_\{F\\in\\mathcal\{C\}\_\{N,V\}^\{\\mathcal\{Y\}\}\}\\left\|\\frac\{1\}\{n\}\\sum\_\{i\}\\varepsilon\_\{i\}\\left\\langle\\mathbf\{y\}\_\{i\},F\(x\_\{i\}\)\\right\\rangle\\right\|≤V​𝔼ε​supθ,‖v‖≤1\|1n​∑iεi​ψθ,N​\(xi\)​⟨𝐲i,v⟩\|\.\\displaystyle\\leq V\\,\\mathbb\{E\}\_\{\\varepsilon\}\\sup\_\{\\theta,\\left\\lVert v\\right\\rVert\\leq 1\}\\left\|\\frac\{1\}\{n\}\\sum\_\{i\}\\varepsilon\_\{i\}\\psi\_\{\\theta,N\}\(x\_\{i\}\)\\left\\langle\\mathbf\{y\}\_\{i\},v\\right\\rangle\\right\|\.The last display is the Rademacher complexity of the product of two classes bounded by one after dividing the second factor byBB\. A standard bounded product\-class contraction bound \(obtainable, for example, from Maurer’s vector\-contraction inequality applied to\(a,b\)↦a​b\(a,b\)\\mapsto abon\[−1,1\]2\[\-1,1\]^\{2\}\[[15](https://arxiv.org/html/2608.20812#bib.bib15)\]\) gives

ℜ^S​\(ℱ​𝒢\)≤C⁡\(ℜ^S​\(ℱ\)\+ℜ^S​\(𝒢\)\)\\widehat\{\\mathfrak\{R\}\}\_\{S\}\(\\mathcal\{F\}\\mathcal\{G\}\)\\leq C\\bigl\(\\widehat\{\\mathfrak\{R\}\}\_\{S\}\(\\mathcal\{F\}\)\+\\widehat\{\\mathfrak\{R\}\}\_\{S\}\(\\mathcal\{G\}\)\\bigr\)for\[−1,1\]\[\-1,1\]\-valued classes\. Hereℱ=𝒟N♯\\mathcal\{F\}=\\mathcal\{D\}\_\{N\}^\{\\sharp\}and𝒢=\{i↦⟨𝐲i,v⟩/B:‖v‖≤1\}\\mathcal\{G\}=\\\{i\\mapsto\\left\\langle\\mathbf\{y\}\_\{i\},v\\right\\rangle/B:\\left\\lVert v\\right\\rVert\\leq 1\\\}, while

ℜ^S​\(𝒢\)=1n​B​𝔼ε​‖∑iεi​𝐲i‖𝒴≤1n\.\\widehat\{\\mathfrak\{R\}\}\_\{S\}\(\\mathcal\{G\}\)=\\frac\{1\}\{nB\}\\mathbb\{E\}\_\{\\varepsilon\}\\left\\lVert\\sum\_\{i\}\\varepsilon\_\{i\}\\mathbf\{y\}\_\{i\}\\right\\rVert\_\{\\mathcal\{Y\}\}\\leq\\frac\{1\}\{\\sqrt\{n\}\}\.Lemma[6\.2](https://arxiv.org/html/2608.20812#S6.Thmtheorem2)therefore bounds the linear part byC​B​V​An/nCBVA\_\{n\}/\\sqrt\{n\}\.

For the quadratic part, everyF∈𝒞N,V𝒴F\\in\\mathcal\{C\}\_\{N,V\}^\{\\mathcal\{Y\}\}has a representation with mass at mostVV, and

‖F⁡\(xi\)‖2=∬ψθ,N​\(xi\)​ψθ′,N​\(xi\)​⟨v⁡\(θ\),v⁡\(θ′\)⟩​ν​\(𝑑θ\)​ν​\(d​θ′\)\.\\left\\lVert F\(x\_\{i\}\)\\right\\rVert^\{2\}=\\iint\\psi\_\{\\theta,N\}\(x\_\{i\}\)\\psi\_\{\\theta^\{\\prime\},N\}\(x\_\{i\}\)\\left\\langle v\(\\theta\),v\(\\theta^\{\\prime\}\)\\right\\rangle\\,\\nu\(d\\theta\)\\nu\(d\\theta^\{\\prime\}\)\.Hence

𝔼ε​supF\|1n​∑iεi​‖F⁡\(xi\)‖2\|≤V2​𝔼ε​supθ,θ′\|1n​∑iεi​ψθ,N​\(xi\)​ψθ′,N​\(xi\)\|\.\\mathbb\{E\}\_\{\\varepsilon\}\\sup\_\{F\}\\left\|\\frac\{1\}\{n\}\\sum\_\{i\}\\varepsilon\_\{i\}\\left\\lVert F\(x\_\{i\}\)\\right\\rVert^\{2\}\\right\|\\leq V^\{2\}\\,\\mathbb\{E\}\_\{\\varepsilon\}\\sup\_\{\\theta,\\theta^\{\\prime\}\}\\left\|\\frac\{1\}\{n\}\\sum\_\{i\}\\varepsilon\_\{i\}\\psi\_\{\\theta,N\}\(x\_\{i\}\)\\psi\_\{\\theta^\{\\prime\},N\}\(x\_\{i\}\)\\right\|\.A second application of the bounded product\-class inequality and Lemma[6\.2](https://arxiv.org/html/2608.20812#S6.Thmtheorem2)givesC​V2​An/nCV^\{2\}A\_\{n\}/\\sqrt\{n\}\. Combining the two parts proves \([55](https://arxiv.org/html/2608.20812#S10.E55)\)\. No coordinate basis of𝒴\\mathcal\{Y\}is used\. ∎

###### Theorem 10\.4\(Dimension\-uniform Hilbert\-valued greedy learning\)\.

Let\(X,𝐘\)\(X,\\mathbf\{Y\}\)be distributed on𝒳×𝒴\\mathcal\{X\}\\times\\mathcal\{Y\}with‖𝐘‖𝒴≤B\\left\\lVert\\mathbf\{Y\}\\right\\rVert\_\{\\mathcal\{Y\}\}\\leq Balmost surely, and letF⋆​\(x\)=𝔼⁡\[𝐘∣X=x\]F\_\{\\star\}\(x\)=\\mathbb\{E\}\[\\mathbf\{Y\}\\mid X=x\]\. Suppose‖F⋆‖ℬH♯​\(𝒴\)≤V\\left\\lVert F\_\{\\star\}\\right\\rVert\_\{\\mathcal\{B\}\_\{H\}^\{\\sharp\}\(\\mathcal\{Y\}\)\}\\leq V\. Run the fully\-corrective vector\-valued greedy method over𝒞N,V𝒴\\mathcal\{C\}\_\{N,V\}^\{\\mathcal\{Y\}\}, using the exact linear oracle from Lemma[10\.1](https://arxiv.org/html/2608.20812#S10.Thmtheorem1), and denote itsmmth iterate byF^m,N\\widehat\{F\}\_\{m,N\}\. Then universal constantsC1,C2\>0C\_\{1\},C\_\{2\}\>0exist such that, with probability at least1−δ1\-\\delta,

‖F^m,N−F⋆‖L2​\(μ,𝒴\)2≤\\displaystyle\\left\\lVert\\widehat\{F\}\_\{m,N\}\-F\_\{\\star\}\\right\\rVert\_\{L^\{2\}\(\\mu;\\mathcal\{Y\}\)\}^\{2\}\\leq\{\}V2​ηN​\(μ\)2\+16​V2m\+3\\displaystyle V^\{2\}\\eta\_\{N\}\(\\mu\)^\{2\}\+\\frac\{16V^\{2\}\}\{m\+3\}\(56\)\+C1​\(V2\+B​V\)​K\+1\+log⁡\(2\+log⁡n\)n\+C2​\(B\+V\)2​log⁡\(2/δ\)n\.\\displaystyle\+C\_\{1\}\(V^\{2\}\+BV\)\\frac\{K\+1\+\\sqrt\{\\log\(2\+\\log n\)\}\}\{\\sqrt\{n\}\}\+C\_\{2\}\(B\+V\)^\{2\}\\sqrt\{\\frac\{\\log\(2/\\delta\)\}\{n\}\}\.In particular the statistical terms contain no explicit dependence on the retained input resolutionNNor on the Hilbert dimension of𝒴\\mathcal\{Y\}\.

###### Proof\.

Truncate only the input atoms in a representation ofF⋆F\_\{\\star\}of mass at mostVV\. Exactly as in Lemma[4\.2](https://arxiv.org/html/2608.20812#S4.Thmtheorem2), the resulting comparatorFNF\_\{N\}belongs to𝒞N,V𝒴\\mathcal\{C\}\_\{N,V\}^\{\\mathcal\{Y\}\}and satisfies‖FN−F⋆‖L2​\(μ,𝒴\)≤V​ηN​\(μ\)\\left\\lVert F\_\{N\}\-F\_\{\\star\}\\right\\rVert\_\{L^\{2\}\(\\mu;\\mathcal\{Y\}\)\}\\leq V\\eta\_\{N\}\(\\mu\)\. The fully\-corrective optimization proof of Proposition[7\.1](https://arxiv.org/html/2608.20812#S7.Thmtheorem1)is Hilbertian and uses only that the feasible set has empirical radius at mostVV, so it gives the same16​V2/\(m\+3\)16V^\{2\}/\(m\+3\)optimization gap for vector\-valued squared loss\.

For transfer to population risk use the centered loss from Lemma[10\.3](https://arxiv.org/html/2608.20812#S10.Thmtheorem3)\. Its envelope is bounded by a universal multiple of\(B\+V\)2\(B\+V\)^\{2\}\. Symmetrization, Lemma[10\.3](https://arxiv.org/html/2608.20812#S10.Thmtheorem3), and bounded\-difference concentration yield a uniform empirical\-population deviation of the last two terms in \([56](https://arxiv.org/html/2608.20812#S10.E56)\)\. Finally,

L⁡\(F\)−L⁡\(F⋆\)=‖F−F⋆‖L2​\(μ,𝒴\)2L\(F\)\-L\(F\_\{\\star\}\)=\\left\\lVert F\-F\_\{\\star\}\\right\\rVert\_\{L^\{2\}\(\\mu;\\mathcal\{Y\}\)\}^\{2\}for Hilbert\-valued conditional expectation, so comparing the empirical greedy iterate withFNF\_\{N\}proves the result\. ∎

Banach\- and Hilbert\-valued shallow neural approximation has important antecedents, including Korolev’s two\-layer Banach\-valued theory\[[9](https://arxiv.org/html/2608.20812#bib.bib9)\]; operator\-learning error decompositions also appear in the DeepONet analysis of Lanthaler, Mishra, and Karniadakis\[[12](https://arxiv.org/html/2608.20812#bib.bib12)\], with earlier operator universal approximation due to Chen and Chen\[[4](https://arxiv.org/html/2608.20812#bib.bib4)\]\. Theorem[10\.4](https://arxiv.org/html/2608.20812#S10.Thmtheorem4)strengthens the coordinatewise reduction by exploiting the rank\-one structure of the vector atoms directly; no output truncation is required\.

## Discussion and Conclusion

#### What the result does and does not quantify\.

The fixed\-radius theorem concerns the weighted regularity classℬH♯\\mathcal\{B\}\_\{H\}^\{\\sharp\}\. The span preservation in \([10](https://arxiv.org/html/2608.20812#S3.E10)\) is useful for density, but it does not make the weighted ball equivalent to the unweighted one\. The statement is therefore a constructive approximation/learning result*inside a smoothness class*, not a rate for everyL2L^\{2\}target covered by an infinite\-dimensional UAT\. Proposition[3\.3](https://arxiv.org/html/2608.20812#S3.Thmtheorem3)makes part of this restriction explicit: the weighted norm controls the Lipschitz seminorm in the embedding pseudometric\. In the one\-dimensional threshold experiment, Corollary[3\.4](https://arxiv.org/html/2608.20812#S3.Thmtheorem4)pins the weighted norm betweenλ\\lambdaand1\+λ1\+\\lambda, while the unweighted norm stays at most one\. Thus fixed weighted balls genuinely remove increasingly sharp thresholds in that example\.

#### Distribution\-dependent resolution\.

The natural resolution quantity isηN​\(μ\)\\eta\_\{N\}\(\\mu\), not the uniform tailηN∞\\eta\_\{N\}^\{\\infty\}\. For highly concentrated input laws,ηN​\(μ\)\\eta\_\{N\}\(\\mu\)can be much smaller than the envelope bound\. This gives a direct route to data\-distribution\-dependent resolution choices without altering the statistical\-complexity argument\.

#### Computational bottleneck\.

The main unresolved issue is the nonlinear neuron oracle\. The statistical theorem is uniform inNN, but the parameter search is not\. Bach’s convex neural network analysis already emphasizes that the unit\-addition subproblem can be the computationally hard part of an infinite\-dimensional convex formulation\[[1](https://arxiv.org/html/2608.20812#bib.bib1)\]\. The synthetic experiment sidesteps this issue by replacing the continuous oracle with a finite pool\.

#### Potential operator\-learning application\.

Recent greedy operator\-learning work focuses on linear operators and kernel estimation\[[14](https://arxiv.org/html/2608.20812#bib.bib14)\]\. The present scalar theory is formulated for nonlinear regression maps of infinite\-dimensional inputs\. Combined with the vector\-valued extension of Section[10](https://arxiv.org/html/2608.20812#S10), this suggests a route toward nonlinear operator or score learning; Theorem[10\.4](https://arxiv.org/html/2608.20812#S10.Thmtheorem4)already removes explicit output\-dimension dependence from the statistical term\. A tractable nonlinear neuron oracle and realistic operator\-learning benchmarks remain necessary before making a strong application claim\. For context, nonlinear operator approximation and discretization error have a broader literature\[[4](https://arxiv.org/html/2608.20812#bib.bib4),[12](https://arxiv.org/html/2608.20812#bib.bib12),[10](https://arxiv.org/html/2608.20812#bib.bib10)\]\.

#### Conclusion\.

A parameter\-weighted variation class provides a clean setting in which three errors can be separated for greedy neural learning from infinite\-dimensional inputs: coordinate truncation, finite greedy width, and finite sampling\. The key statistical observation is that anℓ2\\ell^\{2\}coordinate embedding has a Hilbert radius bounded independently of the retained dimension, so a normalized dictionary admits a Rademacher estimate with no explicitNNfactor\. This comes at two costs that should remain visible: the weighted ball is more restrictive than the unweighted variation ball, and the nonlinear neuron oracle is not computationally dimension\-free\. The quasi\-Polish construction of Galimberti supplies a natural motivating example withηN​\(μ\)2≤N−1\\eta\_\{N\}\(\\mu\)^\{2\}\\leq N^\{\-1\}, while the main quantitative proofs need only measurable coordinates with anℓ2\\ell^\{2\}envelope\. The same argument extends to Hilbert\-valued responses without output coordinate truncation, yielding a statistical term uniform in the output Hilbert dimension\.

## References

- \[1\]F\. Bach,Breaking the curse of dimensionality with convex neural networks,*Journal of Machine Learning Research*, 18\(19\):1–53, 2017\.
- \[2\]A\. R\. Barron, A\. Cohen, W\. Dahmen, and R\. A\. DeVore,Approximation and learning by greedy algorithms,*Annals of Statistics*, 36\(1\):64–94, 2008\.
- \[3\]P\. L\. Bartlett and S\. Mendelson,Rademacher and Gaussian complexities: Risk bounds and structural results,*Journal of Machine Learning Research*, 3:463–482, 2002\.
- \[4\]T\. Chen and H\. Chen,Universal approximation to nonlinear operators by neural networks with arbitrary activation functions and its application to dynamical systems,*IEEE Transactions on Neural Networks*, 6\(4\):911–917, 1995\.
- \[5\]W\. E, C\. Ma, and L\. Wu,The Barron space and the flow\-induced function spaces for neural network models,arXiv:1906\.08039, 2019\.
- \[6\]L\. Galimberti,LpL^\{p\}approximation results for infinite dimensional Neural Networks,arXiv:2608\.08230, 2026\.
- \[7\]M\. Jaggi,Revisiting Frank–Wolfe: Projection\-free sparse convex optimization,in*Proceedings of the 30th International Conference on Machine Learning*, 2013\.
- \[8\]J\. M\. Klusowski and A\. R\. Barron,Approximation by combinations of ReLU and squared ReLU ridge functions withℓ1\\ell^\{1\}andℓ0\\ell^\{0\}controls,arXiv:1607\.07819, 2016\.
- \[9\]Y\. Korolev,Two\-layer neural networks with values in a Banach space,*SIAM Journal on Mathematical Analysis*, 54\(6\):6358–6389, 2022\.
- \[10\]N\. Kovachki, S\. Lanthaler, and S\. Mishra,On universal approximation and error bounds for Fourier Neural Operators,arXiv:2107\.07562, 2021\.
- \[11\]V\. Kůrková and M\. Sanguineti,Bounds on rates of variable\-basis and neural\-network approximation,*IEEE Transactions on Information Theory*, 47\(6\):2659–2665, 2001\.
- \[12\]S\. Lanthaler, S\. Mishra, and G\. E\. Karniadakis,Error estimates for DeepONets: a deep learning framework in infinite dimensions,*Transactions of Mathematics and Its Applications*, 6\(1\):tnac001, 2022\.
- \[13\]M\. Ledoux and M\. Talagrand,*Probability in Banach Spaces: Isoperimetry and Processes*,Springer\-Verlag, Berlin, 1991\.
- \[14\]Y\. Lin, J\. Jia, Y\.\-J\. Lee, and R\. Zhang,Orthogonal greedy algorithm for linear operator learning with shallow neural network,arXiv:2501\.02791, 2025\.
- \[15\]A\. Maurer,A vector\-contraction inequality for Rademacher complexities,in*Algorithmic Learning Theory \(ALT 2016\)*, Lecture Notes in Computer Science, vol\. 9925, Springer, 2016\.
- \[16\]J\. W\. Siegel and J\. Xu,Characterization of the variation spaces corresponding to shallow neural networks,arXiv:2106\.15002, 2021\.
- \[17\]J\. W\. Siegel and J\. Xu,Optimal convergence rates for the orthogonal greedy algorithm,arXiv:2106\.15000, 2021\.
- \[18\]A\. W\. van der Vaart and J\. A\. Wellner,*Weak Convergence and Empirical Processes: With Applications to Statistics*,Springer\-Verlag, New York, 1996\.