Introduction
We study the problem of estimating an unknown convex regression function from n n n independent, identically distributed (i.i.d) observations. Convex regression arises in a wide range of areas, including economics [2 , 36 ] , operations research [3 , 20 , 16 ] , statistical learning [37 , 24 ] , and engineering [15 ] . In economics, for example, concavity restrictions arise naturally in models of utility, consumer preferences, and production technologies. [1 , 35 , 9 , 7 , 17 , 3 ] . In financial engineering, convexity restrictions arise in option-pricing problems [2 ] . In operations research and dynamic programming, convexity or concavity of value functions and response surfaces often follows from structural assumptions on costs, transitions, or performance measures [34 , 25 ] .
Early work on convex and concave regression focused primarily on the one-dimensional setting establishing consistency, rates of convergence, and limit-distribution results [19 , 18 , 29 , 10 ] . More recent work has extended both the finite-dimensional characterization and the statistical theory of least-squares convex regression to multivariate data [33 , 27 , 26 , 14 ] . In parallel, substantial effort has been devoted to scalable optimization methods for solving the associated quadratic program whose solution serves as the natural convex regression estimator. This quadratic program minimizes the empirical squared error over the space of max-affine functions n n n subgradients, with each subgradient constraint encoded by n − 1 n-1 n − 1 inequalities, thus resulting in O ( n 2 ) O(n^2) O ( n 2 ) constraints. In this paper, we consider a less studied alternative approach where, instead of aiming to solve the full constrained problem, we analyze a reduced formulation in which o ( n 2 ) o(n^2) o ( n 2 ) constraints are retained. The central question we address is:
Under what conditions can the convex regression constraints be reduced, and by how much, while preserving the same statistical convergence rate for population risk? Our main results shows that, under reasonable assumptions, we can retain only O ~ ( n 2 ( d − 1 ) / ( 2 d − 1 ) ) \widetilde{O}(n^{2(d-1)/(2d-1)}) O ( n 2 ( d − 1 ) / ( 2 d − 1 ) ) constraints per subgradient for general convex functions and O ~ ( n ( d + 1 ) / ( d + 2 ) ) \widetilde{O}(n^{(d+1)/(d+2)}) O ( n ( d + 1 ) / ( d + 2 ) ) constraints per subgradient for strongly convex functions while achieving the same statistical convergence rate as the full convex regression estimator for d > 4 d > 4 d > 4 . Because our reduced problem relies of only keeping localized constraints from the full problem, one can substantially decrease the computational burden without sacrificing asymptotic statistical efficiency.
Related work
Convex regression belongs to the broader class of shape-restricted regression methods, which impose qualitative constraints on the regression function. Standard examples include isotonic regression, where the fitted function is constrained to be monotone with respect to a given order, and convex or concave regression, where the fitted function is constrained by a global curvature condition ([5 , 31 , 13 ] ). Isotonic regression yields estimators that are typically piecewise constant, while convex regression yields a piecewise affine estimator whose fitted values can be represented through supporting hyperplanes. Foundational work on convex and concave least-squares regression goes back to Hildreth [19 ] and Hanson and Pledger [18 ] , with later work developing consistency, limit theory, and finite-dimensional characterizations in both one-dimensional and multivariate settings ([29 , 10 , 33 , 27 ] ).
One line of work in shape-restricted regression studies the statistical complexity of the associated least-squares estimators. For isotonic and related shape-restricted problems, risk bounds and adaptation properties have been studied by Chatterjee et al. [8 ] ; Guntuboyina and Sen [13 ] . For convex regression, analogous questions require controlling the size of the class of convex functions. Metric entropy bounds provide one way to quantify this complexity, and such bounds play a central role in the empirical-process arguments used to derive statistical rates ([11 ] ). In the one-dimensional setting, Guntuboyina and Sen [12 ] prove global risk bounds and adaptation results for the convex least-squares estimator, showing that the estimator can adapt to functions that are well approximated by piecewise affine convex functions. In multiple dimensions, Lim [26 ] and Han and Wellner [14 ] study convergence rates, minimax benchmarks, and risk bounds for multivariate convex regression. Han and Wellner [14 ] study global minimax rates and risk bounds for bounded multivariate convex least-squares estimators, showing that the attainable rates depend strongly on the geometry of the support. Their analysis indicates that the bounded least square estimation problem is nearly rate-optimal only in low dimensions, motivating the use of sieved adaptive estimators in higher dimensions. Kur, Gao, Guntuboyina, and Sen [21 ] later make the high-dimensional suboptimality of the convex LSE precise, proving that for d ≥ 5 d \ge5 d ≥ 5 the least square error (LSE) has risk of order Θ ~ ( n − 2 / d ) \widetilde{\Theta}(n^{-2/d}) Θ ( n − 2/ d ) over several standard convex function classes, while the minimax rate is n − 4 / ( d + 4 ) n^{-4/(d+4)} n − 4/ ( d + 4 ) . Such a suboptimality was only true when d > 5 d > 5 d > 5 with convex regression leading to optimal estimators for d ≤ 5 d \le5 d ≤ 5 . This gap motivated the study of alternative convex estimators and more structured formulations. In this direction, Balázs, György, and Szepesvári [4 ] consider least-squares estimators over max-affine function classes, where the estimator is constrained to be the maximum of a finite number of affine functions. Under boundedness and Lipschitz assumptions, they obtain near-optimal minimax rates up to logarithmic factors, but provide no polynomial-time guarantee for the required optimization over affine partitions. In contrast, Kur and Putterman [22 ] attain near-minimax rates in polynomial time by combining local affine fits on candidate simplices and their estimated errors into a globally convex estimator.
The usual multivariate convex least-squares estimator admits a finite-dimensional formulation with one fitted value and one subgradient vector per observation, together with pairwise supporting-hyperplane constraints. This formulation is a convex quadratic program, but it contains O ( n 2 ) O(n^2) O ( n 2 ) linear inequality constraints, which makes solving the problem difficult for large samples sizes ([33 , 27 , 30 ] ). A parallel line of work in convex regression focuses on ease of computation. Lee et al. [23 ] developed more efficient algorithms for convex nonparametric least squares in production analysis. Mazumder, Choudhury, Iyengar, and Sen [30 ] propose a scalable augmented-Lagrangian and ascent descent method of multipliers (ADMM)-based frameworks for computing the multivariate convex LSE and its variants. Lin, Sun, and Toh [28 ] develop a proximal augmented-Lagrangian method combined with semismooth Newton subproblem solvers and a practical constraint-generation strategy. Bertsimas and Mundru [6 ] study sparse convex regression and develop cutting-plane methods for large-scale instances. These methods improve the computational tractability of convex regression, but they are primarily designed to solve, approximate, or regularize the full convex regression problem. Tangentially, Hannah and Dunson [16 ] constructed globally convex estimators by fitting local linear models on adaptively selected partitions and then combining them into a max-affine convex function, closely aligning with the statistical work of Balazs [4 ] .
The use of constraint localization within regression problems is a less studied phenomenon within academic literature. To the best of our knowledge, no such methods have been theoretically studied in the literature for either convex or isotonic regression. In more classical regression settings, K-nearest-neighbor regression has been used to predict new data by constructing a weighted average of the learned training outcomes of the nearest neighbors.
Setup and Framework
Notation
We use ∥ ⋅ ∥ 2 \lVert\cdot\rVert_{2} ∥ ⋅ ∥ 2 for the Euclidean norm of a vector and ∥ ⋅ ∥ F \lVert\cdot\rVert_{F} ∥ ⋅ ∥ F for the Frobenius norm of a matrix. For a function f : Ω → R f:\Omega\to\mathbb{R} f : Ω → R , we write ∥ f ∥ ∞ = sup x ∈ Ω ∣ f ( x ) ∣ \lVert f\rVert_{\infty}=\sup_{x\in\Omega}|f(x)| ∥ f ∥ ∞ = sup x ∈ Ω ∣ f ( x ) ∣ and ∥ f ∥ n 2 = n − 1 ∑ i = 1 n f ( X i ) 2 \lVert f\rVert_{n}^{2}=n^{-1}\sum_{i=1}^{n}f(X_i)^2 ∥ f ∥ n 2 = n − 1 ∑ i = 1 n f ( X i ) 2 . We denote its Lipschitz constant with respect to Euclidean distance by Lip ( f ) \operatorname{Lip}(f) Lip ( f ) . For a scalar a a a , we use [ a ] + = max { a , 0 } [a]_{+}=\max\{a,0\} [ a ] + = max { a , 0 } and [ a ] − = max { − a , 0 } [a]_{-}=\max\{-a,0\} [ a ] − = max { − a , 0 } for its positive and negative parts, respectively. For positive sequences a n , b n a_n,b_n a n , b n , the notation a n = o ( b n ) a_n=o(b_n) a n = o ( b n ) means that a n / b n → 0 a_n/b_n\to0 a n / b n → 0 and a n = O ( b n ) a_n=O(b_n) a n = O ( b n ) implies that a n / b n → C a_n/b_n\to C a n / b n → C for some constant C ≥ 0 C\ge0 C ≥ 0 . The notation O ~ ( ⋅ ) \widetilde{O}(\cdot) O ( ⋅ ) suppresses logarithmic factors in n n n .
Setting
We consider a setting where our samples are drawn uniformly on a convex compact body Ω ⊂ R d \Omega\subset\mathbb{R}^{d} Ω ⊂ R d for d ≥ 2 d\ge2 d ≥ 2 with a nonempty interior. We denote P \mathbb{P} P for the uniform probability measure on Ω \Omega Ω and denote the diameter of the convex body be denoted as D Ω D_{\Omega} D Ω . For values B , L > 0 B,L>0 B , L > 0 , we denote by F B , L ( Ω ) \mathcal{F}_{B,L}(\Omega) F B , L ( Ω ) the class of convex functions on Ω \Omega Ω with ∥ f ∥ ∞ ≤ B \lVert f\rVert_{\infty}\le B ∥ f ∥ ∞ ≤ B and Lip ( f ) ≤ L \operatorname{Lip}(f)\le L Lip ( f ) ≤ L . We assume the following assumptions on our setting:
Assumption 2.1. For n > 1 n>1 n > 1 , our observations satisfy
Y i = f 0 ( X i ) + ξ i for X i ∼ i i d P and f 0 ∈ F B , L ( Ω ) . (1) Y_i=f_0(X_i)+\xi_i\quad\text{for }X_i\mathrel{\overset{\mathrm{iid}}{\sim}}\mathbb{P}\text{ and }f_0\in\mathcal{F}_{B,L}(\Omega). \tag*{(1)} Y i = f 0 ( X i ) + ξ i for X i ∼ iid P and f 0 ∈ F B , L ( Ω ) . (1)
where the errors ξ 1 , … , ξ n \xi_1,\ldots,\xi_n ξ 1 , … , ξ n are mutually independent and are also independent of the X = ( X 1 , … , X n ) X=(X_1,\ldots,X_n) X = ( X 1 , … , X n ) .
Assumption 2.2. Each error ξ i \xi_i ξ i has mean 0 0 0 and is subgaussian with variance proxy σ 2 \sigma^2 σ 2 :
E [ e t ξ i ] ≤ e σ 2 t 2 / 2 for t ∈ R , i ≤ n , (2) \mathbb{E}[e^{t\xi_i}]\le e^{\sigma^2t^2/2}\quad\text{for }t\in\mathbb{R},\ i\le n, \tag*{(2)} E [ e t ξ i ] ≤ e σ 2 t 2 /2 for t ∈ R , i ≤ n , (2)
For a matrix of subgradients G = ( g 1 , … , g n ) ∈ R n × d G=(g_1,\ldots,g_n)\in\mathbb{R}^{n\times d} G = ( g 1 , … , g n ) ∈ R n × d and values θ = ( θ 1 , θ 2 , … , θ n ) ∈ R n \theta=(\theta_1,\theta_2,\ldots,\theta_n)\in\mathbb{R}^{n} θ = ( θ 1 , θ 2 , … , θ n ) ∈ R n , we denote a supporting hyperplane residual between X i X_i X i and X j X_j X j as
r j i ( θ , G ) = θ i − θ j − g j T ( X i − X j ) r_{ji}(\theta,G)=\theta_i-\theta_j-g_j^{\mathsf{T}}(X_i-X_j) r j i ( θ , G ) = θ i − θ j − g j T ( X i − X j )
which measures how much each value θ i \theta_i θ i is above the hyperplane generated from point X j X_j X j . We collect the function bounds in
C = { ( θ , G ) : ∣ θ i ∣ ≤ B , ∥ g i ∥ 2 ≤ L ∀ i } . \mathcal{C}=\{(\theta,G):|\theta_i|\le B,\ \lVert g_i\rVert_2\le L\ \forall i\}. C = {( θ , G ) : ∣ θ i ∣ ≤ B , ∥ g i ∥ 2 ≤ L ∀ i } .
Given an edge set W W W , we define C W \mathcal{C}_{W} C W as the subset of C \mathcal{C} C satisfying r j i ( θ , G ) ≥ 0 r_{ji}(\theta,G)\ge0 r j i ( θ , G ) ≥ 0 for every ( j , i ) ∈ W (j,i)\in W ( j , i ) ∈ W . For different edge sets W W W , this leads to different feasible sets for our least square formulation. Let the full edge set be E F = { ( j , i ) : j ≠ i } E_F=\{(j,i):j\ne i\} E F = {( j , i ) : j = i } . For a value 1 ≤ K ≤ n − 1 1\le K\le n-1 1 ≤ K ≤ n − 1 , we write N K ( j ) \mathcal{N}_{K}(j) N K ( j ) for the Euclidean K K K nearest observations to X j X_j X j and subsequently denote the KNN edge set as E K = { ( j , i ) : i ∈ N K ( j ) } E_K=\{(j,i):i\in\mathcal{N}_{K}(j)\} E K = {( j , i ) : i ∈ N K ( j )} .
To mitigate the commonly known problem of blowup of gradients near the boundary of Ω \Omega Ω present in convex regression, we introduce a regularized version of our least square objective
Φ n ( θ , G ) = 1 2 ∥ θ − Y ∥ 2 2 + μ n 2 ∥ G ∥ F 2 . \Phi_n(\theta,G)=\frac{1}{2}\lVert\theta-Y\rVert_2^2+\frac{\mu_n}{2}\lVert G\rVert_F^2. Φ n ( θ , G ) = 2 1 ∥ θ − Y ∥ 2 2 + 2 μ n ∥ G ∥ F 2 .
The full convex regression and KNN convex regression problem are subsequently defined as
( θ F , G F ) = arg min C E F Φ n , ( θ K , G K ) = arg min C E K Φ n , (3) (\theta_F,G_F)=\mathop{\arg\min}_{\mathcal{C}_{E_F}}\Phi_n,\qquad(\theta_K,G_K)=\mathop{\arg\min}_{\mathcal{C}_{E_K}}\Phi_n, \tag*{(3)} ( θ F , G F ) = arg min C E F Φ n , ( θ K , G K ) = arg min C E K Φ n , (3)
respectively. For out-of-sample prediction, we use the standard max-affine predictors defined by:
f ^ A ( x ) = max j ≤ n { θ A , j + g A , j T ( x − X j ) } . (4) \widehat{f}_A(x)=\max_{j\le n}\{\theta_{A,j}+g_{A,j}^{\mathsf{T}}(x-X_j)\}. \tag*{(4)} f A ( x ) = j ≤ n max { θ A , j + g A , j T ( x − X j )} . (4)
where A A A could denote either the full solution and KNN solution. The predictors in (4) can be seen to be globally convex. However, a key distinction between the estimators arises in out-of-sample estimation. Full constraints put every affine piece below θ F , i \theta_{F,i} θ F , i at X i X_i X i , while the i i i th piece attains that value thereby ensuring that f ^ F ( X i ) = θ F , i \widehat{f}_F(X_i)=\theta_{F,i} f F ( X i ) = θ F , i . However, an omitted KNN inequality can allow another hyperplane to rise above its assigned fitted value leading to a difference seen by:
f ^ K ( X i ) − θ K , i = max 1 ≤ j ≤ n { − r j i ( θ K , G K ) } . (5) \widehat{f}_K(X_i)-\theta_{K,i}=\max_{1\le j\le n}\{-r_{ji}(\theta_K,G_K)\}. \tag*{(5)} f K ( X i ) − θ K , i = 1 ≤ j ≤ n max { − r j i ( θ K , G K )} . (5)
For notational simplicity, we define
r n , d = { n − 4 / ( d + 4 ) , 2 ≤ d < 4 , n − 1 / 2 log n , d = 4 , n − 2 / d , d > 4. (6) r_{n,d}=
\begin{cases}
n^{-4/(d+4)}, & 2\le d<4,\\
n^{-1/2}\log n, & d=4,\\
n^{-2/d}, & d>4.
\end{cases} \tag*{(6)} r n , d = ⎩ ⎨ ⎧ n − 4/ ( d + 4 ) , n − 1/2 log n , n − 2/ d , 2 ≤ d < 4 , d = 4 , d > 4. (6)
as a reference rates for our population risk. These values are the statistical rates of convergence of the full convex regression problem ([21 ] ). To ensure that the regularization does not introduce significant bias in our estimation as the sample points grows and worsen statistical convergence rates, we further require Assumption 2.3 below.
Assumption 2.3. The regression penalty μ n > 0 \mu_n > 0 μ n > 0 satisfies μ n ≤ C μ r n , d L 2 \mu_n \le\frac{C_\mu r_{n,d}}{L^2} μ n ≤ L 2 C μ r n , d for some fixed constant C μ C_\mu C μ .
We measure the population risk of an estimator f A f_A f A with respect to a function f 0 f_0 f 0 through
R A ( f 0 ) = E f 0 [ ℓ 2 ( f ^ A , f 0 ) ] = E f 0 [ ∫ Ω ( f A ( x ) − f 0 ( x ) ) 2 d x ] . R_A(f_0)=\mathbb{E}_{f_0}[\ell^2(\widehat f_A,f_0)]=\mathbb{E}_{f_0}\left[\int_\Omega(f_A(x)-f_0(x))^2dx\right]. R A ( f 0 ) = E f 0 [ ℓ 2 ( f A , f 0 )] = E f 0 [ ∫ Ω ( f A ( x ) − f 0 ( x ) ) 2 d x ] .
For a class of functions H \mathcal{H} H , the worst case risk is subsequently defined as R A , n ( H ) = sup f 0 ∈ H E f 0 ℓ 2 ( f ^ A , f 0 ) R_{A,n}(\mathcal{H})=\sup_{f_0\in\mathcal{H}}\mathbb{E}_{f_0}\ell^2(\widehat f_A,f_0) R A , n ( H ) = sup f 0 ∈ H E f 0 ℓ 2 ( f A , f 0 ) . Here, the expectation is taken over the sampling of the points X i X_i X i and the errors ξ i \xi_i ξ i .
Subsequently, our goal is to identify neighborhood sizes K n = o ( n ) K_n=o(n) K n = o ( n ) for which the KNN estimator preserves the full estimator’s population-risk upper bound O ~ ( r n , d ) \widetilde{O}(r_{n,d}) O ( r n , d ) .
Risk Decomposition and Bounds
To separate the statistical estimation error from the effect of removing constraints, consider fixing a regression function f 0 f_0 f 0 . We can subsequently decompose the difference of f ^ K − f 0 \widehat f_K-f_0 f K − f 0 into ( f ^ F − f 0 ) + ( f ^ K − f ^ F ) (\widehat f_F-f_0)+(\widehat f_K-\widehat f_F) ( f F − f 0 ) + ( f K − f F ) . Standard algebraic manipulations yields the associated risk decomposition of
E f 0 ℓ 2 ( f ^ K , f 0 ) ≤ 2 E f 0 ℓ 2 ( f ^ F , f 0 ) + 2 E f 0 ℓ 2 ( f ^ K , f ^ F ) . (7) \mathbb{E}_{f_0}\ell^2(\widehat f_K,f_0)\le2\mathbb{E}_{f_0}\ell^2(\widehat f_F,f_0)+2\mathbb{E}_{f_0}\ell^2(\widehat f_K,\widehat f_F). \tag*{(7)} E f 0 ℓ 2 ( f K , f 0 ) ≤ 2 E f 0 ℓ 2 ( f F , f 0 ) + 2 E f 0 ℓ 2 ( f K , f F ) . (7)
Term (i) measures the error of the full estimator relative to the true regression function. Term (ii) measures the discrepancy between the KNN and full predictors fitted to the same observations. We first establish a statistical rate for term (i). Such analyses of the convex LSE typically consider the unregularized estimator under Gaussian errors, allowing the use of Gaussian projection and empirical-process arguments [21 , 14 ] . However, our assumptions allows more general subgaussian errors and our framework introduces a regularization term for the fitted subgradients. For those reasons, the corresponding risk analysis requires additional control of both features. An analysis of the risk for the full estimator leads to the following bound:
Proposition 3.1 (Full-estimator population risk). Assume that f 0 f_0 f 0 and ( X i , Y i ) (X_i,Y_i) ( X i , Y i ) follow the setup in § 2 . Further assume that we use the max affine solution f ^ F ( x ) \widehat f_F(x) f F ( x ) as defined in (4). Then, for sufficiently large n n n ,
sup f 0 ∈ F B , L ( Ω ) E f 0 ℓ 2 ( f ^ F , f 0 ) ≤ C [ ( log n ) ( r n , d + μ n L 2 + σ 2 n ) + L 2 ( log n n ) 2 / d ] . (8) \sup_{f_0\in\mathcal{F}_{B,L}(\Omega)}\mathbb{E}_{f_0}\ell^2(\widehat f_F,f_0)\le C\left[(\log n)\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2}{n}\right)+L^2\left(\frac{\log n}{n}\right)^{2/d}\right]. \tag*{(8)} f 0 ∈ F B , L ( Ω ) sup E f 0 ℓ 2 ( f F , f 0 ) ≤ C [ ( log n ) ( r n , d + μ n L 2 + n σ 2 ) + L 2 ( n log n ) 2/ d ] . (8)
Proposition 3.1 relies on controlling how strongly a feasible fitted-value vector can align with the observation noise. We first analyze the unregularized least-squares estimator over the feasible set C F C_F C F . Since the true fitted values are feasible, the optimality of the least square estimator implies that a large estimation error would require a deviation from the truth with a correspondingly large alignment with the noise. Standard metric entropy bounds for bounded Lipschitz convex functions and a subgaussian chaining argument allows us to control these alignments, yielding an empirical squared-error bound of order r n , d + σ 2 / n r_{n,d}+\sigma^2/n r n , d + σ 2 / n . We then compare the regularized and unregularized optimization problems to show that the slope penalty changes the fitted-value vector by at most μ n L 2 \mu_nL^2 μ n L 2 in Euclidean norm. To transfer our sample risk to population risk, we employ the Lipschitz bound to control the population risk for each observation’s Voronoi cell resulting in the final term of L 2 ( log n / n ) 2 / d L^2(\log n/n)^{2/d} L 2 ( log n / n ) 2/ d . We provide a complete proof in Appendix A.
Under Assumption 2.3, the penalty contribution does not exceed the full problem regression rate of r n , d r_{n,d} r n , d . We therefore obtain the population-risk upper bound of O ~ ( n − 4 / ( d + 4 ) ) \widetilde{O}(n^{-4/(d+4)}) O ( n − 4/ ( d + 4 ) ) for 2 ≤ d < 4 2\le d<4 2 ≤ d < 4 , O ~ ( n − 1 / 2 ) \widetilde{O}(n^{-1/2}) O ( n − 1/2 ) for d = 4 d=4 d = 4 , and O ~ ( n − 2 / d ) \widetilde{O}(n^{-2/d}) O ( n − 2/ d ) for d > 4 d>4 d > 4 . Our subsequent goal is to choose a value of K K K so that term (ii) does not exceed this upper bound while simultaneously ensuring K K K is o ( n ) o(n) o ( n ) . We begin by proving such a bound over the function class of convex functions and then move to the function class of strongly convex functions. For clarity in our exposition, we display the sufficient neighborhood size for every dimension regime and the associated risk bounds are presented in Table 1 where logarithmic factors have been suppressed.
Table 1. Sufficient K n K_n K n and associated MSE risk orders with logarithmic factors being suppressed suppressed.
Bounded Lipschitz Convex Truths
We first look at functions f 0 f_0 f 0 that are convex, bounded, and Lipschitz. We summarize our results in the theorem below:
Theorem 3.2 (Convex risk rate preservation). Assume that f 0 f_0 f 0 and ( X i , Y i ) (X_i,Y_i) ( X i , Y i ) follow the setup in § 2 and we use the max affine solution f ^ F ( x ) \widehat f_F(x) f F ( x ) as defined in (4).
Under Assumption 2.3, if we set
K n = min { n − 1 , ⌈ C K n d − 1 2 d − 1 ( log n ) d 2 d − 1 × r n , d − d ( d − 1 ) 2 ( 2 d − 1 ) ⌉ } . (9) K_n = \min\left\{n-1,\left\lceil C_K n^{\frac{d-1}{2d-1}}(\log n)^{\frac{d}{2d-1}} \times r_{n,d}^{-\frac{d(d-1)}{2(2d-1)}}\right\rceil\right\}. \tag*{(9)} K n = min { n − 1 , ⌈ C K n 2 d − 1 d − 1 ( log n ) 2 d − 1 d × r n , d − 2 ( 2 d − 1 ) d ( d − 1 ) ⌉ } . (9)
for sufficiently large C K C_K C K , then we have that K n = o ( n ) K_n=o(n) K n = o ( n ) and, for sufficiently large n n n ,
sup f 0 ∈ F B , L ( Ω ) E f 0 [ ℓ P 2 ( f ^ K , f 0 ) ] ≤ C r n , d log n . (10) \sup_{f_0\in\mathcal{F}_{B,L}(\Omega)}\mathbb{E}_{f_0}\left[\ell_{\mathbb{P}}^2(\hat f_K,f_0)\right]\leq Cr_{n,d}\log n. \tag*{(10)} f 0 ∈ F B , L ( Ω ) sup E f 0 [ ℓ P 2 ( f ^ K , f 0 ) ] ≤ C r n , d log n . (10)
Theorem 3.2 relies on a chaining argument where we construct paths of local edges retained in both directions from the nearest neighbor construction of edges. By combining the residual inequalities along these paths, we show that distant pairs observations satisfy the omitted inequalities up to a controlled error. Provided that the KNN optimizer almost satisfies the residual constraints of the full solution, we then focus on adjusting it so that it satisfied all of the full constraints. In particular, by linearly mixing the KNN fitted values and subgradient with those of a fixed quadratic function, we can construct a comparison point that is feasible for the full problem, Through this constructed point, first-order optimality conditions and the full estimator’s empirical-error bound to control how far the KNN fitted values can move from the full solution. Finally, we account for the KNN interpolation defect in (5) and use the same argument as in the full convex regression to transfer the fitted-value comparison to population prediction risk. We give the complete argument in Appendix B.
Bounded Lipschitz strongly convex truths
Having established bounds for K n K_n K n in the convex case, we now turn our attention specifically to functions f 0 f_0 f 0 that are strongly convex with parameter m 0 m_0 m 0 . For fixed m 0 > 0 m_0>0 m 0 > 0 , we denote the strongly convex function class by F B , L ( Ω ; m 0 ) \mathcal{F}_{B,L}(\Omega;m_0) F B , L ( Ω ; m 0 ) as the subclass of F B , L ( Ω ) \mathcal{F}_{B,L}(\Omega) F B , L ( Ω ) for which f f f is m 0 m_0 m 0 strongly-convex; i.e its members satisfy
f ( ( 1 − t ) x + t y ) ≤ ( 1 − t ) f ( x ) + t f ( y ) − m 0 2 t ( 1 − t ) ∥ x − y ∥ 2 2 . (11) f((1-t)x+ty)\leq(1-t)f(x)+tf(y)-\frac{m_0}{2}t(1-t)\lVert x-y\rVert_2^2. \tag*{(11)} f (( 1 − t ) x + t y ) ≤ ( 1 − t ) f ( x ) + t f ( y ) − 2 m 0 t ( 1 − t ) ∥ x − y ∥ 2 2 . (11)
Assumption 3.3. The true function f 0 ∈ F B , L s c ( Ω , m 0 ) f_0\in\mathcal{F}^{\mathrm{sc}}_{B,L}(\Omega,m_0) f 0 ∈ F B , L sc ( Ω , m 0 ) for a fixed constant m 0 m_0 m 0 .
Under this function class, we can prove a different bound on sufficient K K K shown in Theorem 3.4.
Theorem 3.4 (Strong convexity rate preservation). Assume that f 0 f_0 f 0 and ( X i , Y i ) (X_i,Y_i) ( X i , Y i ) follow the setup in § 2 and we use the max affine solution f ^ F ( x ) \hat f_F(x) f ^ F ( x ) as defined in (4). Under Assumption 2.3 and 3.3, if we set
K n = min { n − 1 , ⌈ C K n × ( r n , d log n ) d 2 ( d + 2 ) ⌉ } , (12) K_n=\min\left\{n-1,\left\lceil C_Kn\times(r_{n,d}\log n)^{\frac{d}{2(d+2)}}\right\rceil\right\}, \tag*{(12)} K n = min { n − 1 , ⌈ C K n × ( r n , d log n ) 2 ( d + 2 ) d ⌉ } , (12) where C K > 0 C_K>0 C K > 0 is a sufficiently large fixed constant, then we have that K n = o ( n ) K_n=o(n) K n = o ( n ) and, for all sufficiently large n n n ,
E f 0 ℓ P 2 ( f ^ K , f 0 ) ≤ C r n , d log n , (13) \mathbb{E}_{f_0}\ell_{\mathbb{P}}^2(\hat f_K,f_0)\leq Cr_{n,d}\log n, \tag*{(13)} E f 0 ℓ P 2 ( f ^ K , f 0 ) ≤ C r n , d log n , (13)
Unlike the general convex case, Theorem 3.4 instead relies on a screening argument in which we show that, with high probability, all active constraints in the full convex regression problem are from nearby observations residual constraints. We first show that f ^ F \hat f_F f ^ F approximates f 0 f_0 f 0 everywhere on Ω \Omega Ω with high probability. By employing strong convexity, we can then show that every constraint connecting observations beyond a shrinking radius is strictly slack at the ( Θ F , G F ) (\Theta_F,\mathcal{G}_F) ( Θ F , G F ) . We choose K n K_n K n large enough that the KNN graph retains all constraints within this radius, and therefore every active full constraint, with high probability. We provide the complete argument in Appendix C.
We highlight that though both Theorem 3.2 and Theorem 3.4 preserve the overall population-risk upper bound O ~ ( r n , d ) \widetilde{O}(r_{n,d}) O ( r n , d ) , they provide different guarantees for the both the size and effect of sparsification. Specifically, Theorem 3.2 allows for the estimators that produce different predictions while only enforcing E f 0 ℓ P 2 ( f ^ K , f ^ F ) = O ~ ( r n , d ) \mathbb{E}_{f_0}\ell_{\mathbb{P}}^2(\hat f_K,\hat f_F)=\widetilde{O}(r_{n,d}) E f 0 ℓ P 2 ( f ^ K , f ^ F ) = O ( r n , d ) . In particular, we only establish that the KNN estimator achieves the required statistical rate by showing that it approximates the full estimator at the same scale. On the other hand, with the additional strong convexity assumption, we demonstrate a stronger statement: the fitted values and subgradients from the KNN and full problems are exactly equal with probability at least 1 − C r n , d 2 1-Cr_{n,d}^2 1 − C r n , d 2 . Since both predictors are uniformly bounded, the complement event contributes only O ( r n , d 2 ) O(r_{n,d}^2) O ( r n , d 2 ) to the expected squared discrepancy. We therefore obtain E f 0 ℓ P 2 ( f ^ K , f ^ F ) = O ( r n , d 2 ) = o ( r n , d ) \mathbb{E}_{f_0}\ell_{\mathbb{P}}^2(\hat f_K,\hat f_F)=O(r_{n,d}^2)=o(r_{n,d}) E f 0 ℓ P 2 ( f ^ K , f ^ F ) = O ( r n , d 2 ) = o ( r n , d ) . So, while Theorem 3.2 is only able to control the sparsification discrepancy at the statistical upper-rate scale, the strongly convex theorem makes this discrepancy asymptotically negligible relative to the asymptotic rate r n , d r_{n,d} r n , d .
In terms of neighborhood sizes, for d < 4 d<4 d < 4 , typical calculations can show that Theorem 3.2 requires fewer neighbors for risk preservation while the strongly convex theorem provides the stronger recovery guarantee at the cost of larger sufficient neighborhood size. However, for d > 4 d>4 d > 4 , the assumption of strong convexity reduces the sufficient order from O ~ ( n 2 ( d − 1 ) / ( 2 d − 1 ) ) \widetilde{O}(n^{2(d-1)/(2d-1)}) O ( n 2 ( d − 1 ) / ( 2 d − 1 ) ) to O ~ ( n ( d + 1 ) / ( d + 2 ) ) \widetilde{O}(n^{(d+1)/(d+2)}) O ( n ( d + 1 ) / ( d + 2 ) ) overtaking the neighborhood size from the general convex case. As the F B , L s c ( Ω , m 0 ) \mathcal{F}^{\mathrm{sc}}_{B,L}(\Omega,m_0) F B , L sc ( Ω , m 0 ) is a subset of F B , L ( Ω , m 0 ) \mathcal{F}_{B,L}(\Omega,m_0) F B , L ( Ω , m 0 ) , the upper bounds for d < 4 d<4 d < 4 that were achieved for convex functions can be immediately applied to strongly convex functions. However, the discrepancy between the two bounds gives indication for future improvements on the risk upper bound of our constructed KNN estimator.
Numerical experiments
To validate our population risk results, we run tests on synthetic functions and data to compare the population risk of KNN convex regression with that of full convex regression. We give general details of the implementations and numerical accuracy checks in the main text and refer the readers to Appendix § 12 and the Appendix § 13 for further implementation details and experimental settings respectively.
Synthetic Data Construction
We sample points X i X_i X i uniformly on Ω = [ − 2 , 2 ] d \Omega= [-2,2]^d Ω = [ − 2 , 2 ] d with d d d ranging from 2 to 20 and selected sample sizes from n = 250 n = 250 n = 250 to n = 3000 n = 3000 n = 3000 , with 30 independent training runs per set values of n n n and d d d . For the true function f 0 f_0 f 0 , we use varying different functions listed below.
Quadratics Firstly, we include a quadratic and piecewise quadratic found in previous convex regression literature. Balázs et al. [4 ] :
f Q ( x ) = − 8 + 4 d ∥ x ∥ 2 2 , f H ( x ) = − 8 + 4 d ∥ [ x ] + ∥ 2 2 , (14) \begin{aligned}
f_{\mathrm{Q}}(x) &= -8 + \frac{4}{d}\lVert x\rVert_2^2,\\
f_{\mathrm{H}}(x) &= -8 + \frac{4}{d}\lVert[x]_+\rVert_2^2, \tag*{(14)}
\end{aligned} f Q ( x ) f H ( x ) = − 8 + d 4 ∥ x ∥ 2 2 , = − 8 + d 4 ∥[ x ] + ∥ 2 2 , (14)
The full quadratic is strongly convex with curvature 8 / d 8/d 8/ d , while the half quadratic is only generally convex due to its. These two problems have been seen to be problems where convex regression struggles in practice, motivating their choice in our experimentation.
Maximum of Affine Planes To test genuine slope discontinuities, we also use finite-plane truths
f M A ( x ) = max 1 ≤ m ≤ M { a m T x + b m } . (15) f_{\mathrm{MA}}(x) = \max_{1\le m\le M}\{a_m^\mathsf{T}x+b_m\}. \tag*{(15)} f MA ( x ) = 1 ≤ m ≤ M max { a m T x + b m } . (15)
We varied M M M in the set of { 5 , 10 , 25 , 50 } \{5, 10, 25, 50\} { 5 , 10 , 25 , 50 } , with randomly generated coefficients a m a_m a m and b m b_m b m . These coefficients held fixed across sample sizes and replicates for each value of d d d and M M M . Such function instances are convex as well as not having without any curvature arising from a quadratic term like in Eq. (14) motivating their inclusion into our dataset.
Max Affine Estimation of a Quadratic Finally, as a further stress test, we implement a piecewise-affine approximation to a quadratic. This function was motivated by the least square error lower-bound construction of Kur et al. [21 ] which demonstrated the suboptimality of convex regression. Intuitively, we expected such a hard problem in full convex regression for possibly lead to hard problems in KNN regression.
f h a r d , n ( x ) = − 8 + 4 d ∑ j = 1 d q J n ( x j ) , q J ( t ) = max 0 ≤ k < J { ( t k + t k + 1 ) t − t k t k + 1 } . (16) \begin{aligned}
f_{\mathrm{hard},n}(x) &= -8 + \frac{4}{d}\sum_{j=1}^{d}q_{J_n}(x_j),\\
q_J(t) &= \max_{0\le k<J}\{(t_k+t_{k+1})t-t_kt_{k+1}\}. \tag*{(16)}
\end{aligned} f hard , n ( x ) q J ( t ) = − 8 + d 4 j = 1 ∑ d q J n ( x j ) , = 0 ≤ k < J max {( t k + t k + 1 ) t − t k t k + 1 } . (16)
Here we use the grid points t k = − 2 + 4 k / J t_k=-2+4k/J t k = − 2 + 4 k / J . For d > 4 d>4 d > 4 , we set J n = max { 2 , ⌈ n 1 / ( 2 d ) ⌉ } J_n=\max\{2,\lceil n^{1/(2d)}\rceil\} J n = max { 2 , ⌈ n 1/ ( 2 d ) ⌉} . The truth then has M n = J n d ∼ n M_n=J_n^d\sim\sqrt{n} M n = J n d ∼ n affine regions, while its bounds remain fixed as n n n grows.
For all four families, we construct them so that they have the common bounds B = 8 B=8 B = 8 and L = 16 / d L=16/\sqrt{d} L = 16/ d . To attempt to simulate a real scenario where we do not know such bounds a priori, we set B = 10 B=10 B = 10 and L = 20 / d L=20/\sqrt{d} L = 20/ d as conservative estimates in our simulations.
After sampling functions, we added Gaussian noise according to Y i = f 0 ( X i ) + ξ i Y_i=f_0(X_i)+\xi_i Y i = f 0 ( X i ) + ξ i , with ξ i \xi_i ξ i set so that the signal to noise ratio was set to 3. After obtaining the KNN solution and full solution for our problems, we estimated the population risk R ( f ^ ) = E [ ( f ^ ( X ) − f 0 ( X ) ) 2 ] R(\hat{f})=\mathbb{E}[(\hat{f}(X)-f_0(X))^2] R ( f ^ ) = E [( f ^ ( X ) − f 0 ( X ) ) 2 ] for the max-affine predictor shown in (4) using 10,000 data points.
In order to compare to the risk of the full estimator, standard solvers such as Gurobi and MOSEK were not able to push to the limits desired to show our asymptotic convergence. To alleviate this computational burden, iterative methods such as ADMM, dual ascent, augmented Lagrangian, and constraint generation methods have been developed in previous literature. Having tested all methods, we found that a proximal augmented Lagrangian method with sub-problems solved by the semismooth Newton method developed by Lin et al. [28 ] worked exceptionally well. Further details about the method can be found in Appendix § 12 .
Results and Discussion
For each sample size n n n , dimension d d d , and problem family, we recorded the estimated population risks of the KNN and full convex regression estimators as K K K increased. Table 2 reports the ratio of these risks at n = 1500 n=1500 n = 1500 across several problems and dimensions. For small neighborhoods, such as K = 19 K=19 K = 19 , the KNN estimator typically has substantially larger risk than the full estimator, particularly in the lower- and moderate-dimensional settings. As K K K increases, however, we observe a steady decrease in this ratio, with the KNN and full risks becoming nearly indistinguishable at sufficiently large K K K . The slowest approach to the full-estimator risk occurs for the max-affine truth, where the ratio remains noticeably above one for larger values of K K K . While this behavior cannot be explained solely by the absence of strong convexity, since the half-quadratic and hard-grid benchmarks are also not globally strongly convex, it suggests that additional structural features in f 0 f_0 f 0 , particularly sharp discontinuous changes in active slopes, may influence how quickly the KNN relaxation risk approaches the full estimator risk.
Table 2. Ratio of empirical risk for KNN convex regression solution to full convex regression solution for different problems and dimensions at n = 1500 n = 1500 n = 1500 .
As a further visualization of our experimentation, Figure 1 displays the estimated population-risk ratio between the KNN solution and full solution as a function of the fraction of retained constraints, K / ( n − 1 ) K/(n-1) K / ( n − 1 ) . Each panel corresponds to a fixed benchmark family and dimension d d d , while the color gradient distinguishes sample sizes n n n . For a fixed value of n n n and d d d , our theory in Theorem 3.2 and 3.4 give us an estimation of the sufficient values K n / ( n − 1 ) K_n/(n-1) K n / ( n − 1 ) provided large enough n n n . As such a reference rate is dependent on a multiplicative constant C K C_K C K , we display corresponding vertical bands extending from 0.5 to 2 times this reference scale. We emphasize that bands are meant to illustrate a reasonable theoretical order attained from our theory though more accurate bound would require further analyzing the dependence of C K C_K C K on d d d and the other problem parameters. We observe that the risk ratio is already close to one throughout the reference bands and generally approaches this level well before the left edges of the band corroborating our theory on the sufficiency of the values of K n K_n K n . In fact, we observe that we can obtain comparable prediction accuracy while retaining substantially fewer constraints than suggested by the displayed reference scales. Such a gap suggests room to sharpen our sufficient neighborhood bounds, either through accurate constant dependence or further improvements on the sample size.
Figure 1. Risk curves for the four synthetic convex regression truths and varying dimensions. The differing colors represent different values of n n n and the vertical opaque bands represent what our theoretical limits mark as sufficient values of K n K_n K n . The risk levels converge to the full problems risk well before the predicted value of K K K .
Conclusion and future directions
We introduced KNN constraint sparsification for convex regression. We showed such a sparsification preserves full-estimator risk upper bound for bounded Lipschitz convex truths under subgaussian noise. Depending on whether the true function class is strongly convex or generally convex, the level of sparsification needed to achieve the risk upper bound varies with our proof techniques. However, in both cases, a risk bound matching that of full convex regression can be achieved with a nearest neighbor sparsification K K K that is o ( n ) o(n) o ( n ) . Experimental validation on sythetic data also validates such findings.
For future work, a natural next step we aim to look into would be to determine lower bound on the worst-case risk of our constructed KNN estimators and compare it with the minimax risk for appropriate function classes. Developing these lower bounds would illuminate for what type of functions constraint sparsification preserves or changes the statistical suboptimality of the full convex regression estimator. Finally, we plan to extend our evaluation to semi-synthetic and real-world data to test the efficiency of our algorithm.
Table 2 : Ratio of empirical risk for KNN convex regression solution to full convex regression solution for different problems and dimensions at n = 1500 n = 1500 n = 1500 . We can see the convergence of risk to 1 1 1 for sufficiently large K K K .
Table 2.
AI USE STATEMENT
In this work, we used generative AI tools for writing the code to generate our synthetic dataset, assisting in the writing of proofs, verification of our proofs, refining hypothesis, implementation of our numerical experiments, and providing feedback on our experimental design. We have not used generative AI tools for formulating our mathematical claims or providing ingredients for our proof ideas, assist with translation, clean and reformat datasets, support qualitative and thematic data analysis, or interpret results. Additionally, we used generative AI tools for creating software code. We have reviewed all AI-assisted work. All parts of proofs where AI were used were checked line by line by the authors and code was verified for correctness by comparing the generated methods with other standard solvers. We take responsibility for the final content of this work, including text, claims, or artifacts produced with the aid of generative AI.
References
CHECKLIST
For all models and algorithms presented, check if you include:
(a) A clear description of the mathematical setting, assumptions, algorithm, and/or model. [Yes/No/Not Applicable]
(b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. [Yes/No/Not Applicable]
(c) (Optional) Anonymized source code, with specification of all dependencies, including external libraries. [Yes/No/Not Applicable]
For any theoretical claim, check if you include:
(a) Statements of the full set of assumptions of all theoretical results. [Yes/No/Not Applicable]
(b) Complete proofs of all theoretical results. [Yes/No/Not Applicable]
(c) Clear explanations of any assumptions. [Yes/No/Not Applicable]
For all figures and tables that present empirical results, check if you include:
(a) The code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL). [Yes/No/Not Applicable]
(b) All the training details (e.g., data splits, hyperparameters, how they were chosen). [Yes/No/Not Applicable]
(c) A clear definition of the specific measure or statistics and error bars (e.g., with respect to the random seed after running experiments multiple times). [Yes/No/Not Applicable]
(d) A description of the computing infrastructure used. (e.g., type of GPUs, internal cluster, or cloud provider). [Yes/No/Not Applicable]
If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include:
(a) Citations of the creator If your work uses existing assets. [Yes/No/Not Applicable]
(b) The license information of the assets, if applicable. [Yes/No/Not Applicable]
(c) New assets either in the supplemental material or as a URL, if applicable. [Yes/No/Not Applicable]
(d) Information about consent from data providers/curators. [Yes/No/Not Applicable]
(e) Discussion of sensible content if applicable, e.g., personally identifiable information or offensive content. [Yes/No/Not Applicable]
If you used crowdsourcing or conducted research with human subjects, check if you include:
(a) The full text of instructions given to participants and screenshots. [Yes/No/Not Applicable]
(b) Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable. [Yes/No/Not Applicable]
(c) The estimated hourly wage paid to participants and the total amount spent on participant compensation. [Yes/No/Not Applicable]
Full-estimator statistical analysis
We prove the full-estimator bound in Proposition 3.1 . We first establish the design estimates used to transfer sample error to population error. We then analyze the unregularized fitted vector, control the change introduced by the slope penalty, and obtain both an expected population-risk bound and a high-probability bound for the screening argument in Appendix § 11 . Throughout Appendices A–C, we use the setup in § 2 and Assumption 2.3. We write ∥ v ∥ n 2 = n − 1 ∥ v ∥ 2 2 \|v\|_{n}^{2}=n^{-1}\|v\|_{2}^{2} ∥ v ∥ n 2 = n − 1 ∥ v ∥ 2 2 for vectors in R n \mathbb{R}^{n} R n and use ℓ 2 P ( f , g ) = ∫ Ω ( f − g ) 2 d P \ell_{2}^{P}(f,g)=\int_{\Omega}(f-g)^{2}\,\mathrm{d}P ℓ 2 P ( f , g ) = ∫ Ω ( f − g ) 2 d P . Constants denoted by C C C or c c c may change from line to line and depend only on the fixed model parameters; the constants in Appendix § 11 may also depend on the fixed curvature lower bound m 0 m_{0} m 0 .
The sample-to-population comparison uses how well the observations cover Ω \Omega Ω . We denote the Voronoi cell of X i X_i X i by V i V_i V i , and define ρ n = sup x ∈ Ω min i ≤ n ∥ x − X i ∥ 2 \rho_n=\sup_{x\in\Omega}\min_{i\le n}\|x-X_i\|_2 ρ n = sup x ∈ Ω min i ≤ n ∥ x − X i ∥ 2 and p max = max i ≤ n P ( V i ) p_{\max}=\max_{i\le n}\mathbb{P}(V_i) p m a x = max i ≤ n P ( V i ) . The first quantity measures the largest gap in the design; the second measures the largest portion of the domain assigned to one observation.
Lemma A.1. For independent uniform observations on the compact convex body Ω ⊂ R d \Omega\subset\mathbb{R}^{d} Ω ⊂ R d , there are constants C ρ , C p , C > 0 C_{\rho},C_{p},C>0 C ρ , C p , C > 0 such that, for n ≥ 2 n\ge2 n ≥ 2 and δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , with probability at least 1 − δ 1-\delta 1 − δ ,
ρ n ≤ C ρ ( log ( n / δ ) n ) 1 / d , p max ≤ C p log ( n / δ ) n . (17) \rho_n\le C_{\rho}\left(\frac{\log(n/\delta)}{n}\right)^{1/d},\qquad p_{\max}\le C_p\frac{\log(n/\delta)}{n}. \tag*{(17)} ρ n ≤ C ρ ( n log ( n / δ ) ) 1/ d , p m a x ≤ C p n log ( n / δ ) . (17) Moreover, E ρ n 2 ≤ C ( log n / n ) 2 / d \mathbb{E}\rho_n^2\le C(\log n/n)^{2/d} E ρ n 2 ≤ C ( log n / n ) 2/ d .
Proof. We first establish a uniform bound on the mass of balls within the domain. We then use this bound to control the covering radius. Because Ω \Omega Ω has nonempty interior, there are x ∗ ∈ Ω x_*\in\Omega x ∗ ∈ Ω and r ∗ > 0 r_*>0 r ∗ > 0 such that B ( x ∗ , r ∗ ) ⊆ Ω B(x_*,r_*)\subseteq\Omega B ( x ∗ , r ∗ ) ⊆ Ω . For a fixed x ∈ Ω x\in\Omega x ∈ Ω and 0 < r ≤ D Ω 0<r\le D_{\Omega} 0 < r ≤ D Ω , and setting t : = r D Ω + r ∗ t:=\frac{r}{D_{\Omega}+r_*} t := D Ω + r ∗ r , we have that 0 < t ≤ 1 0<t\le1 0 < t ≤ 1 . Every point of ( 1 − t ) x + t B ( x ∗ , r ∗ ) (1-t)x+tB(x_*,r_*) ( 1 − t ) x + tB ( x ∗ , r ∗ ) is a convex combination of points in Ω \Omega Ω , so it belongs to Ω \Omega Ω . Moreover, if y ∈ B ( x ∗ , r ∗ ) y\in B(x_*,r_*) y ∈ B ( x ∗ , r ∗ ) , then
∥ ( 1 − t ) x + t y − x ∥ 2 = t ∥ y − x ∥ 2 ≤ t ( ∥ x ∗ − x ∥ 2 + ∥ y − x ∗ ∥ 2 ) ≤ t ( D Ω + r ∗ ) = r . \|(1-t)x+ty-x\|_2=t\|y-x\|_2\le t(\|x_*-x\|_2+\|y-x_*\|_2)\le t(D_{\Omega}+r_*)=r. ∥ ( 1 − t ) x + t y − x ∥ 2 = t ∥ y − x ∥ 2 ≤ t ( ∥ x ∗ − x ∥ 2 + ∥ y − x ∗ ∥ 2 ) ≤ t ( D Ω + r ∗ ) = r .
It follows that
( 1 − t ) x + t B ( x ∗ , r ∗ ) ⊆ Ω ∩ B ( x , r ) . (1-t)x+tB(x_*,r_*)\subseteq\Omega\cap B(x,r). ( 1 − t ) x + tB ( x ∗ , r ∗ ) ⊆ Ω ∩ B ( x , r ) .
The set on the left is a ball of radius t r ∗ tr_* t r ∗ . Since the design distribution is uniform,
P ( B ( x , r ) ∩ Ω ) ≥ v d ( t r ∗ ) d ∣ Ω ∣ = v d r ∗ d ∣ Ω ∣ ( D Ω + r ∗ ) d r d , \mathbb{P}(B(x,r)\cap\Omega)\ge\frac{v_d(tr_*)^d}{|\Omega|}=\frac{v_dr_*^d}{|\Omega|(D_{\Omega}+r_*)^d}r^d, P ( B ( x , r ) ∩ Ω ) ≥ ∣Ω∣ v d ( t r ∗ ) d = ∣Ω∣ ( D Ω + r ∗ ) d v d r ∗ d r d ,
where v d v_d v d is the volume of a unit ball in R d \mathbb{R}^{d} R d . For the upper bound, the volume of B ( x , r ) ∩ Ω B(x,r)\cap\Omega B ( x , r ) ∩ Ω is no greater than the volume of the entire ball. We have therefore shown that there are constants c 0 , C 0 > 0 c_0,C_0>0 c 0 , C 0 > 0 , depending only on d d d and Ω \Omega Ω , such that
c 0 r d ≤ P ( B ( x , r ) ∩ Ω ) ≤ C 0 r d , x ∈ Ω , 0 < r ≤ D Ω . (18) c_0r^d\le\mathbb{P}(B(x,r)\cap\Omega)\le C_0r^d,\qquad x\in\Omega,\quad0<r\le D_{\Omega}. \tag*{(18)} c 0 r d ≤ P ( B ( x , r ) ∩ Ω ) ≤ C 0 r d , x ∈ Ω , 0 < r ≤ D Ω . (18)
We now control ρ n \rho_n ρ n . We begin by choosing a maximal collection A r ⊆ Ω \mathcal{A}_r\subseteq\Omega A r ⊆ Ω whose points are separated by more than r / 2 r/2 r /2 . Maximality makes this an r / 2 r/2 r /2 -net. The balls of radius r / 4 r/4 r /4 centered at its points are disjoint and lie inside B ( x ∗ , D Ω + r / 4 ) B(x_*,D_{\Omega}+r/4) B ( x ∗ , D Ω + r /4 ) , giving
∣ A r ∣ v d ( r / 4 ) d ≤ v d ( D Ω + r / 4 ) d ⟹ ∣ A r ∣ ≤ ( 5 D Ω r ) d . |\mathcal{A}_r|v_d(r/4)^d\le v_d(D_{\Omega}+r/4)^d\Longrightarrow|\mathcal{A}_r|\le\left(\frac{5D_{\Omega}}{r}\right)^d. ∣ A r ∣ v d ( r /4 ) d ≤ v d ( D Ω + r /4 ) d ⟹ ∣ A r ∣ ≤ ( r 5 D Ω ) d .
Suppose that every ball B ( a , r / 2 ) B(a,r/2) B ( a , r /2 ) centered at a net point a ∈ A r a\in\mathcal{A}_r a ∈ A r contains at least one observation. For any x ∈ Ω x\in\Omega x ∈ Ω , we can first find a net point within r / 2 r/2 r /2 of x x x and then an observation within r / 2 r/2 r /2 of that net point. The triangle inequality places this observation within distance r r r of x x x . Consequently, ρ n ≤ r \rho_n\le r ρ n ≤ r on this event. Consider the complement of that event. By independence of the observations and (18),
P ( ρ n > r ) ≤ ∑ a ∈ A r P ( X i ∉ B ( a , r / 2 ) for every i ) = ∑ a ∈ A r ( 1 − P ( B ( a , r / 2 ) ∩ Ω ) ) n ≤ ∑ a ∈ A r ( 1 − c 0 ( r 2 ) d ) n ≤ C 1 r − d exp ( − c 1 n r d ) . \mathbb{P}(\rho_n > r) \le\sum_{a\in A_r} \mathbb{P}(X_i \notin B(a,r/2)\text{ for every }i)
= \sum_{a\in A_r} \left(1-\mathbb{P}(B(a,r/2)\cap\Omega)\right)^n
\le\sum_{a\in A_r}\left(1-c_0\left(\frac{r}{2}\right)^d\right)^n
\le C_1r^{-d}\exp(-c_1nr^d). P ( ρ n > r ) ≤ a ∈ A r ∑ P ( X i ∈ / B ( a , r /2 ) for every i ) = a ∈ A r ∑ ( 1 − P ( B ( a , r /2 ) ∩ Ω ) ) n ≤ a ∈ A r ∑ ( 1 − c 0 ( 2 r ) d ) n ≤ C 1 r − d exp ( − c 1 n r d ) .
for sufficiently large constants C 1 , c 1 > 0 C_1,c_1>0 C 1 , c 1 > 0 . We set a = log ( n / δ ) a=\log(n/\delta) a = log ( n / δ ) and r n , δ = ( A a / n ) 1 / d r_{n,\delta}=(Aa/n)^{1/d} r n , δ = ( A a / n ) 1/ d . When r n , δ ≥ D Ω r_{n,\delta}\ge D_\Omega r n , δ ≥ D Ω , the bound ρ n ≤ r n , δ \rho_n\le r_{n,\delta} ρ n ≤ r n , δ is automatic. Otherwise, the preceding estimate gives
P ( ρ n > r n , δ ) ≤ C 1 n A a exp ( − c 1 A a ) . \mathbb{P}(\rho_n>r_{n,\delta})\le\frac{C_1n}{Aa}\exp(-c_1Aa). P ( ρ n > r n , δ ) ≤ A a C 1 n exp ( − c 1 A a ) .
Since a ≥ log 2 a\ge\log2 a ≥ log 2 , we set A = max { 2 c 1 , C 1 log 2 } A=\max\left\{\frac{2}{c_1},\frac{C_1}{\log2}\right\} A = max { c 1 2 , l o g 2 C 1 } , so that C 1 / ( A log 2 ) ≤ 1 C_1/(A\log2)\le1 C 1 / ( A log 2 ) ≤ 1 and c 1 A ≥ 2 c_1A\ge2 c 1 A ≥ 2 . The right-hand side is then at most n e − 2 a = δ 2 / n ≤ δ ne^{-2a}=\delta^2/n\le\delta n e − 2 a = δ 2 / n ≤ δ . This proves the covering-radius bound with C ρ = A 1 / d C_\rho=A^{1/d} C ρ = A 1/ d .
To control the cell masses, note that x ∈ V i x\in V_i x ∈ V i implies ∥ x − X i ∥ 2 ≤ ρ n \lVert x-X_i\rVert_2\le\rho_n ∥ x − X i ∥ 2 ≤ ρ n . Hence
V i ⊆ B ( X i , ρ n ) ∩ Ω . V_i\subseteq B(X_i,\rho_n)\cap\Omega. V i ⊆ B ( X i , ρ n ) ∩ Ω.
Because ρ n ≤ D Ω \rho_n\le D_\Omega ρ n ≤ D Ω , the upper bound in (18) gives P ( V i ) ≤ C 0 ρ n d \mathbb{P}(V_i)\le C_0\rho_n^d P ( V i ) ≤ C 0 ρ n d . Therefore, on the event of ρ n ≤ r n , δ \rho_n\le r_{n,\delta} ρ n ≤ r n , δ ,
p max ≤ C 0 r n , δ d = C 0 A log ( n / δ ) n . p_{\max}\le C_0r_{n,\delta}^d=C_0A\frac{\log(n/\delta)}{n}. p m a x ≤ C 0 r n , δ d = C 0 A n log ( n / δ ) .
Taking C p = C 0 A C_p=C_0A C p = C 0 A proves the bound on p max p_{\max} p m a x occurs with probability 1 − δ 1-\delta 1 − δ .
The covering-radius bound gives P ( ρ n > s n ) ≤ n − 3 \mathbb{P}(\rho_n>s_n)\le n^{-3} P ( ρ n > s n ) ≤ n − 3 . Since ρ n ≤ D Ω \rho_n\le D_\Omega ρ n ≤ D Ω for every sample,
E ρ n 2 = E [ ρ n 2 1 { ρ n ≤ s n } ] + E [ ρ n 2 1 { ρ n > s n } ] ≤ s n 2 + D Ω 2 n − 3 ≤ C ρ 2 ( 4 log n n ) 2 / d + D Ω 2 n − 3 . \mathbb{E}\rho_n^2=\mathbb{E}\left[\rho_n^2\mathbf{1}_{\{\rho_n\le s_n\}}\right]+\mathbb{E}\left[\rho_n^2\mathbf{1}_{\{\rho_n>s_n\}}\right]
\le s_n^2+D_\Omega^2n^{-3}
\le C_\rho^2\left(\frac{4\log n}{n}\right)^{2/d}+D_\Omega^2n^{-3}. E ρ n 2 = E [ ρ n 2 1 { ρ n ≤ s n } ] + E [ ρ n 2 1 { ρ n > s n } ] ≤ s n 2 + D Ω 2 n − 3 ≤ C ρ 2 ( n 4 log n ) 2/ d + D Ω 2 n − 3 .
Since d ≥ 1 d\ge1 d ≥ 1 , we have 2 / d ≤ 2 < 3 2/d\le2<3 2/ d ≤ 2 < 3 , and hence n − 3 n^{-3} n − 3 is bounded by a constant multiple of ( log n / n ) 2 / d (\log n/n)^{2/d} ( log n / n ) 2/ d for all n ≥ 2 n\ge2 n ≥ 2 . The result follows for sufficiently large C C C .
Lemma A.2. For n ≥ 2 n\ge2 n ≥ 2 , δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , and a deterministic radius R ∈ [ 0 , D Ω ] R\in[0,D_\Omega] R ∈ [ 0 , D Ω ] , with probability at least 1 − δ 1-\delta 1 − δ ,
max j ≤ n # { i ≠ j : ∥ X i − X j ∥ 2 ≤ R } ≤ C N ( n R d + log ( n / δ ) ) . (19) \max_{j\le n}\#\{i\ne j:\lVert X_i-X_j\rVert_2\le R\}\le C_N\left(nR^d+\log(n/\delta)\right). \tag*{(19)} j ≤ n max # { i = j : ∥ X i − X j ∥ 2 ≤ R } ≤ C N ( n R d + log ( n / δ ) ) . (19) where C N C_N C N depends only on d d d and Ω \Omega Ω .
Proof. We write N j ( R ) = ∑ i ≠ j 1 { ∥ X i − X j ∥ 2 ≤ R } N_j(R)=\sum_{i\ne j}\mathbf{1}\{\lVert X_i-X_j\rVert_2\le R\} N j ( R ) = ∑ i = j 1 {∥ X i − X j ∥ 2 ≤ R } . As j j j is fixed, the indicators are independent Bernoulli variables with common success probability p j = P ( B ( X j , R ) ∩ Ω ≤ C 0 R d p_j=\mathbb{P}(B(X_j,R)\cap\Omega\le C_0R^d p j = P ( B ( X j , R ) ∩ Ω ≤ C 0 R d using (18). It follows that
E ( e Z j ∣ X j ) = ( 1 + p j ( e − 1 ) ) n − 1 ≤ exp ( ( n − 1 ) p j ( e − 1 ) ) ≤ exp ( ( e − 1 ) C 0 n R d ) . \mathbb{E}(e^{Z_j}\mid X_j)=(1+p_j(e-1))^{n-1}
\le\exp((n-1)p_j(e-1))
\le\exp((e-1)C_0nR^d). E ( e Z j ∣ X j ) = ( 1 + p j ( e − 1 ) ) n − 1 ≤ exp (( n − 1 ) p j ( e − 1 )) ≤ exp (( e − 1 ) C 0 n R d ) .
Applying Markov’s inequality at the threshold T = ( e − 1 ) C 0 n R d + log ( n δ ) T=(e-1)C_0 n R^d+\log\left(\frac{n}{\delta}\right) T = ( e − 1 ) C 0 n R d + log ( δ n ) therefore gives
P ( Z j > T ∣ X j ) ≤ e − T E ( e Z j ∣ X j ) ≤ e − log ( n δ ) = δ n . \begin{aligned}
\mathbb{P}(Z_j>T\mid X_j)\le e^{-T}\mathbb{E}(e^{Z_j}\mid X_j) \\
&\le e^{-\log\left(\frac{n}{\delta}\right)}=\frac{\delta}{n}.
\end{aligned} P ( Z j > T ∣ X j ) ≤ e − T E ( e Z j ∣ X j ) ≤ e − l o g ( δ n ) = n δ .
Taking a union bound over all possible j j j gives us:
P ( max j ≤ n Z j > ( e − 1 ) C 0 n R d + log ( n δ ) ) ≤ δ . \mathbb{P}\left(\max_{j\le n}Z_j>(e-1)C_0nR^d+\log\left(\frac{n}{\delta}\right)\right)\le\delta. P ( j ≤ n max Z j > ( e − 1 ) C 0 n R d + log ( δ n ) ) ≤ δ .
implying that the radius R R R neighborhood around any points X j X_j X j contains at most C N ( n R d + log ( n / δ ) ) C_N(nR^d+\log(n/\delta)) C N ( n R d + log ( n / δ )) holds with probability at least 1 − δ 1-\delta 1 − δ .
The next lemma transfers error at the observations to population error. Lipschitz continuity bounds the change in error between an observation and the points in its Voronoi cell.
Lemma A.3 (Sample-to-population comparison). For any two L L L -Lipschitz functions f , g f,g f , g on Ω \Omega Ω ,
ℓ P 2 ( f , g ) ≤ 2 p max ∑ i = 1 n ( f ( X i ) − g ( X i ) ) 2 + 8 L 2 ρ n 2 . (20) \ell_{\mathbb{P}}^2(f,g)\le2p_{\max}\sum_{i=1}^{n}(f(X_i)-g(X_i))^2+8L^2\rho_n^2. \tag*{(20)} ℓ P 2 ( f , g ) ≤ 2 p m a x i = 1 ∑ n ( f ( X i ) − g ( X i ) ) 2 + 8 L 2 ρ n 2 . (20) Proof. Because both f f f and g g g are L L L -Lipschitz, their difference is 2 L 2L 2 L -Lipschitz. For every x ∈ V i x\in V_i x ∈ V i , the definition of the Voronoi cell gives ∥ x − X i ∥ 2 ≤ ρ n \lVert x-X_i\rVert_2\le\rho_n ∥ x − X i ∥ 2 ≤ ρ n . Therefore, by setting h = f − g h=f-g h = f − g
∣ h ( x ) ∣ ≤ ∣ h ( X i ) ∣ + ∣ h ( x ) − h ( X i ) ∣ ≤ ∣ h ( X i ) ∣ + 2 L ρ n . |h(x)|\le|h(X_i)|+|h(x)-h(X_i)|\le|h(X_i)|+2L\rho_n. ∣ h ( x ) ∣ ≤ ∣ h ( X i ) ∣ + ∣ h ( x ) − h ( X i ) ∣ ≤ ∣ h ( X i ) ∣ + 2 L ρ n . Squaring this inequality and using ( a + b ) 2 ≤ 2 a 2 + 2 b 2 (a+b)^2\le2a^2+2b^2 ( a + b ) 2 ≤ 2 a 2 + 2 b 2 , we obtain h ( x ) 2 ≤ 2 h ( X i ) 2 + 8 L 2 ρ n 2 h(x)^2\le2h(X_i)^2+8L^2\rho_n^2 h ( x ) 2 ≤ 2 h ( X i ) 2 + 8 L 2 ρ n 2 , for x ∈ V i x\in V_i x ∈ V i . Integration over V i V_i V i yields
∫ V i h ( x ) 2 d P ( x ) ≤ 2 P ( V i ) h ( X i ) 2 + 8 L 2 ρ n 2 P ( V i ) . \int_{V_i}h(x)^2\,\mathrm{d}\mathbb{P}(x)\le2\mathbb{P}(V_i)h(X_i)^2+8L^2\rho_n^2\mathbb{P}(V_i). ∫ V i h ( x ) 2 d P ( x ) ≤ 2 P ( V i ) h ( X i ) 2 + 8 L 2 ρ n 2 P ( V i ) . The cells partition Ω \Omega Ω , and their probability masses sum to one. Summing the last inequality over all cells consequently gives
∫ Ω h ( x ) 2 d P ( x ) ≤ 2 ∑ i = 1 n P ( V i ) h ( X i ) 2 + 8 L 2 ρ n 2 . \int_{\Omega}h(x)^2\,\mathrm{d}\mathbb{P}(x)\le2\sum_{i=1}^{n}\mathbb{P}(V_i)h(X_i)^2+8L^2\rho_n^2. ∫ Ω h ( x ) 2 d P ( x ) ≤ 2 i = 1 ∑ n P ( V i ) h ( X i ) 2 + 8 L 2 ρ n 2 . The first term is at most 2 p max ∑ i h ( X i ) 2 2p_{\max}\sum_i h(X_i)^2 2 p m a x ∑ i h ( X i ) 2 completing the lemma.
Analyzing the statistical rate term (i)
We now bound the full estimator’s error at the observations. We begin with the unregularized problem so that the least-squares optimality condition directly relates estimation error to the noise. The reference sequence r n , d r_{n,d} r n , d is defined in (6) .
Feasible fitted values and the least-squares projection
We first recall the supporting-subgradient result used to show that the true fitted values are feasible.
Theorem A.4 (Rockafellar [32 ] , Theorem 23.4). For a finite convex function f f f on an open convex set U ⊆ R d U\subseteq\mathbb{R}^d U ⊆ R d , every x ∈ U x\in U x ∈ U admits a vector g ∈ R d g\in\mathbb{R}^d g ∈ R d such that f ( y ) ≥ f ( x ) + g ⊤ ( y − x ) f(y)\ge f(x)+g^\top(y-x) f ( y ) ≥ f ( x ) + g ⊤ ( y − x ) for all $y\in U.
The following lemma establishes existence of the estimators and the prediction properties needed throughout the risk analysis.
Lemma A.5. For every design in Ω \Omega Ω and every W ⊆ E F W\subseteq E_F W ⊆ E F , the set C W C_W C W is nonempty, compact, and convex. Additionally, the objective Φ n \Phi_n Φ n has a unique minimizer on this set for regularization parameter μ n > 0 \mu_n>0 μ n > 0 . The fitted-value set Θ n = { θ ∈ R n : ∃ G , ( θ , G ) ∈ C E F } \Theta_n=\{\theta\in\mathbb{R}^n:\exists G,(\theta,G)\in C_{E_F}\} Θ n = { θ ∈ R n : ∃ G , ( θ , G ) ∈ C E F } is also nonempty, compact, and convex, and contains the true values θ 0 = ( f 0 ( X 1 ) , … , f 0 ( X n ) ) \theta^0=(f_0(X_1),\ldots,f_0(X_n)) θ 0 = ( f 0 ( X 1 ) , … , f 0 ( X n )) almost surely. Every ( θ , G ) ∈ C W (\theta,G)\in C_W ( θ , G ) ∈ C W defines a convex, L L L -Lipschitz out-of-sample predictor bounded in absolute value on Ω \Omega Ω by B f = B + L D Ω B_f=B+LD_\Omega B f = B + L D Ω . Additionally, for the out of sample predictor f ^ θ F , G F \widehat{f}_{\theta_F,G_F} f θ F , G F arising from full solution ( θ F , G F ) (\theta_F,G_F) ( θ F , G F ) , we have that f ^ θ F , G F ( X i ) = θ F , i \widehat{f}_{\theta_F,G_F}(X_i)=\theta_{F,i} f θ F , G F ( X i ) = θ F , i for every i i i .
Proof. We observe that ( 0 , 0 ) ∈ C W (0,0) \in C_W ( 0 , 0 ) ∈ C W proving nonemptiness. The linear inequalities and hard bounds make the set closed, bounded, and convex. The uniqueness of the minimizer of Φ n \Phi_n Φ n comes directly from the strong convexity of the function along with the convexity of C W C_W C W .
The set Θ n \Theta_n Θ n is the image of C E F C_{EF} C E F under the continuous linear map ( θ , G ) ↦ θ (\theta,G) \mapsto\theta ( θ , G ) ↦ θ , so it maintains the properties of being nonempty, compact, and convex.
To show that θ 0 \theta^0 θ 0 is contained within Θ n \Theta_n Θ n , note that the observations lie on the interior of Ω \Omega Ω with probability 1. On that event, Theorem A.4 ensures that there exists a supporting vector g j 0 g_j^0 g j 0 at each X j X_j X j . Using points X j X_j X j and X i X_i X i ensure the hyperplane constraints are satisfied. We now must show that the bounded and Lipschitz constraints are satisfied. For g j 0 ≠ 0 g_j^0 \ne0 g j 0 = 0 , we can look at a new point y = X j + t g j 0 / ∥ g j 0 ∥ 2 y = X_j + tg_j^0/\lVert g_j^0\rVert_2 y = X j + t g j 0 / ∥ g j 0 ∥ 2 with t > 0 t > 0 t > 0 small enough that y y y is still in int ( Ω ) \operatorname{int}(\Omega) int ( Ω ) . The supporting inequality and the Lipschitz bound subsequently give us that t ∥ g j 0 ∥ 2 ≤ f 0 ( y ) − f 0 ( X j ) ≤ L t t\lVert g_j^0\rVert_2 \le f_0(y)-f_0(X_j) \le Lt t ∥ g j 0 ∥ 2 ≤ f 0 ( y ) − f 0 ( X j ) ≤ L t . Thus ∥ g j 0 ∥ 2 ≤ L \lVert g_j^0\rVert_2 \le L ∥ g j 0 ∥ 2 ≤ L even when g j 0 = 0 g_j^0 = 0 g j 0 = 0 . Our function class assumption gives us that ∣ f 0 ( X i ) ∣ ≤ B |f_0(X_i)| \le B ∣ f 0 ( X i ) ∣ ≤ B thereby proving that ( θ 0 , G 0 ) (\theta^0,G^0) ( θ 0 , G 0 ) is feasible for the full problem and that θ 0 ∈ Θ n \theta^0 \in\Theta_n θ 0 ∈ Θ n .
For the out-of-sample prediction, each affine piece a j ( x ) = θ j + g j ⊤ ( x − X j ) a_j(x) = \theta_j + g_j^\top(x-X_j) a j ( x ) = θ j + g j ⊤ ( x − X j ) is L L L -Lipschitz and bounded by ∥ θ j ∥ 2 + ∥ g j ∥ 2 ⋅ ∥ x − X j ∥ 2 ≤ B + L D Ω \lVert\theta_j\rVert_2 + \lVert g_j\rVert_2 \cdot\lVert x-X_j\rVert_2 \le B+LD_\Omega ∥ θ j ∥ 2 + ∥ g j ∥ 2 ⋅ ∥ x − X j ∥ 2 ≤ B + L D Ω . The maximum of these affine pieces is convex and satisfies the same bounds, since ∣ f θ , G ( X i ) − f θ , G ( X j ) ∣ = max j ∣ a j ( x ) − max j a j ( y ) ∣ ≤ max j ∣ a j ( x ) − a j ( y ) ∣ ≤ L ∥ x − y ∥ 2 |f_{\theta,G}(X_i)-f_{\theta,G}(X_j)| = \max_j|a_j(x)-\max_j a_j(y)| \le\max_j|a_j(x)-a_j(y)| \le L\lVert x-y\rVert_2 ∣ f θ , G ( X i ) − f θ , G ( X j ) ∣ = max j ∣ a j ( x ) − max j a j ( y ) ∣ ≤ max j ∣ a j ( x ) − a j ( y ) ∣ ≤ L ∥ x − y ∥ 2 .
By definition, the full solution ( θ F , G F ) (\theta_F,G_F) ( θ F , G F ) has an out of sample solution f F ( X i ) = max j { θ F , j + g F , j ⊤ ( X i − X j ) } f_F(X_i) = \max_j\{\theta_{F,j}+g_{F,j}^\top(X_i-X_j)\} f F ( X i ) = max j { θ F , j + g F , j ⊤ ( X i − X j )} and also satisfies the supporting hyperplane inequalities of θ F , i ≥ θ F , j + g F , i ⊤ ( X i − X j ) \theta_{F,i} \ge\theta_{F,j}+g_{F,i}^\top(X_i-X_j) θ F , i ≥ θ F , j + g F , i ⊤ ( X i − X j ) for all j j j . Therefore, θ ^ ( X i ) ≤ θ F , i \hat{\theta}(X_i) \le\theta_{F,i} θ ^ ( X i ) ≤ θ F , i . However, θ F , i + g F , i ⊤ ( X i − X i ) = θ F , i \theta_{F,i}+g_{F,i}^\top(X_i-X_i)=\theta_{F,i} θ F , i + g F , i ⊤ ( X i − X i ) = θ F , i , ensuring equality. The result follows. □
Localization Argument
Our goal within the proceeding subsections is to show that ∥ θ ^ L S − θ 0 ∥ n \lVert\hat{\theta}_{LS}-\theta^0\rVert_n ∥ θ ^ L S − θ 0 ∥ n is sufficiently small with high probability. We can relate the least square objective error of ∥ θ − Y ∥ 2 \lVert\theta-Y\rVert_2 ∥ θ − Y ∥ 2 to the true objective error ∥ θ 0 − Y ∥ 2 \lVert\theta^0-Y\rVert_2 ∥ θ 0 − Y ∥ 2 by substituting Y = θ 0 + ξ Y=\theta^0+\xi Y = θ 0 + ξ and expanding:
1 2 n ∥ θ − Y ∥ 2 2 − 1 2 n ∥ θ 0 − Y ∥ 2 2 = 1 2 n ( ∥ ( θ − θ 0 ) − ξ ∥ 2 2 − ∥ ξ ∥ 2 2 ) = 1 2 ∥ θ − θ 0 ∥ n 2 − 1 n ξ ⊤ ( θ − θ 0 ) . (21) \frac{1}{2n}\lVert\theta-Y\rVert_2^2-\frac{1}{2n}\lVert\theta^0-Y\rVert_2^2
=\frac{1}{2n}\left(\lVert(\theta-\theta^0)-\xi\rVert_2^2-\lVert\xi\rVert_2^2\right)
=\frac{1}{2}\lVert\theta-\theta^0\rVert_n^2-\frac{1}{n}\xi^\top(\theta-\theta^0). \tag*{(21)} 2 n 1 ∥ θ − Y ∥ 2 2 − 2 n 1 ∥ θ 0 − Y ∥ 2 2 = 2 n 1 ( ∥( θ − θ 0 ) − ξ ∥ 2 2 − ∥ ξ ∥ 2 2 ) = 2 1 ∥ θ − θ 0 ∥ n 2 − n 1 ξ ⊤ ( θ − θ 0 ) . (21)
For the purpose of proving a bound, for a design θ 0 ∈ Θ n \theta^0 \in\Theta_n θ 0 ∈ Θ n , we define T s = { θ ∈ Θ n : ∥ θ − θ 0 ∥ n ≤ s } T_s=\{\theta\in\Theta_n:\lVert\theta-\theta^0\rVert_n \le s\} T s = { θ ∈ Θ n : ∥ θ − θ 0 ∥ n ≤ s } and the quantities
Z θ = 1 n ξ ⊤ ( θ − θ 0 ) , U X ( s ) = sup θ ∈ T s ∣ Z θ ∣ . (22) Z_\theta=\frac{1}{n}\xi^\top(\theta-\theta^0),\qquad U_X(s)=\sup_{\theta\in T_s}|Z_\theta|. \tag*{(22)} Z θ = n 1 ξ ⊤ ( θ − θ 0 ) , U X ( s ) = θ ∈ T s sup ∣ Z θ ∣. (22)
The next lemma shows it is enough to control U X ( s ) U_X(s) U X ( s ) to prove that our estimator belongs to T s T_s T s .
Lemma A.6. For every design with θ 0 ∈ Θ n \theta^0 \in\Theta_n θ 0 ∈ Θ n ,
1 2 ∥ θ ^ L S − θ 0 ∥ n 2 ≤ 1 n ξ ⊤ ( θ ^ L S − θ 0 ) . (23) \frac{1}{2}\lVert\hat{\theta}_{LS}-\theta^0\rVert_n^2 \le\frac{1}{n}\xi^\top(\hat{\theta}_{LS}-\theta^0). \tag*{(23)} 2 1 ∥ θ ^ L S − θ 0 ∥ n 2 ≤ n 1 ξ ⊤ ( θ ^ L S − θ 0 ) . (23) Moreover, for every s > 0 s>0 s > 0 ,
{ ∥ θ ^ L S − θ 0 ∥ n > s } ⊆ { U X ( s ) > s 2 / 2 } . (24) \{\lVert\hat{\theta}_{LS}-\theta^0\rVert_n>s\}\subseteq\{U_X(s)>s^2/2\}. \tag*{(24)} {∥ θ ^ L S − θ 0 ∥ n > s } ⊆ { U X ( s ) > s 2 /2 } . (24)
Proof. By Lemma (A.5), the truth θ 0 \theta_0 θ 0 is feasible, so ∥ θ ^ L S − Y ∥ 2 2 ≤ ∥ θ 0 − Y ∥ 2 2 \lVert\hat{\theta}_{LS}-Y\rVert_2^2 \le\lVert\theta^0-Y\rVert_2^2 ∥ θ ^ L S − Y ∥ 2 2 ≤ ∥ θ 0 − Y ∥ 2 2 . We therefore have that
0 ≤ 1 2 n ∥ θ ^ L S − Y ∥ 2 2 − 1 2 n ∥ θ 0 − Y ∥ 2 2 (25) 0\le\frac{1}{2n}\lVert\hat{\theta}_{LS}-Y\rVert_2^2-\frac{1}{2n}\lVert\theta^0-Y\rVert_2^2 \tag*{(25)} 0 ≤ 2 n 1 ∥ θ ^ L S − Y ∥ 2 2 − 2 n 1 ∥ θ 0 − Y ∥ 2 2 (25)
= 1 2 n ( ∥ ( θ − θ 0 ) − ξ ∥ 2 2 − ∥ ξ ∥ 2 2 ) (26) =\frac{1}{2n}\left(\lVert(\theta-\theta^0)-\xi\rVert_2^2-\lVert\xi\rVert_2^2\right) \tag*{(26)} = 2 n 1 ( ∥( θ − θ 0 ) − ξ ∥ 2 2 − ∥ ξ ∥ 2 2 ) (26)
= 1 2 ∥ θ ^ L S − θ 0 ∥ n 2 − 1 n ξ ⊤ ( θ ^ L S − θ 0 ) . (27) =\frac{1}{2}\lVert\hat{\theta}_{LS}-\theta^0\rVert_n^2-\frac{1}{n}\xi^\top(\hat{\theta}_{LS}-\theta^0). \tag*{(27)} = 2 1 ∥ θ ^ L S − θ 0 ∥ n 2 − n 1 ξ ⊤ ( θ ^ L S − θ 0 ) . (27)
For a realization with R = ∥ θ ^ L S − θ 0 ∥ n > s R = \|\hat{\theta}_{\mathrm{LS}}-\theta^0\|_n>s R = ∥ θ ^ LS − θ 0 ∥ n > s , consider setting θ s = θ 0 + ( s / R ) ( θ ^ L S − θ 0 ) \theta_s=\theta^0+(s/R)(\hat{\theta}_{\mathrm{LS}}-\theta^0) θ s = θ 0 + ( s / R ) ( θ ^ LS − θ 0 ) . Convexity of Θ n \Theta_n Θ n makes this vector feasible, and ∥ θ s − θ 0 ∥ n = s \|\theta_s-\theta^0\|_n=s ∥ θ s − θ 0 ∥ n = s , so θ s ∈ T s \theta_s\in T_s θ s ∈ T s . Calculations gives
Z θ s = s R Z θ ^ L S ≥ s R R 2 2 = s R 2 > s 2 2 . Z_{\theta_s}=\frac{s}{R}Z_{\hat{\theta}_{\mathrm{LS}}}\geq\frac{s}{R}\frac{R^2}{2}=\frac{sR}{2}>\frac{s^2}{2}. Z θ s = R s Z θ ^ LS ≥ R s 2 R 2 = 2 s R > 2 s 2 .
where the inequality is from using equation (23) . Since U X ( s ) ≥ ∣ Z θ s ∣ U_X(s)\geq|Z_{\theta_s}| U X ( s ) ≥ ∣ Z θ s ∣ , the event inclusion follows.
Taking the complement of the set tells us that { U X ( s ) < s 2 / 2 } ⊆ { ∥ θ ^ L S − θ 0 ∥ n < s } \{U_X(s)<s^2/2\}\subseteq\{\|\hat{\theta}_{\mathrm{LS}}-\theta^0\|_n<s\} { U X ( s ) < s 2 /2 } ⊆ { ∥ θ ^ LS − θ 0 ∥ n < s } . Therefore a high concentration probability bound on U X ( s ) U_X(s) U X ( s ) would also be a high concentration bound on ∥ θ ^ L S − θ 0 ∥ n \|\hat{\theta}_{\mathrm{LS}}-\theta^0\|_n ∥ θ ^ LS − θ 0 ∥ n .
Entropy of the localized fitted-value set
We now bound the number of representatives needed to approximate T s T_s T s . For notation, we write N ( ϵ , S , ∥ ⋅ ∥ ) N(\epsilon,S,\|\cdot\|) N ( ϵ , S , ∥ ⋅ ∥ ) to denote the smallest number of ϵ \epsilon ϵ balls covering S S S using distance metric ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ . The centers of those balls are an ϵ \epsilon ϵ cover. We use the following covering theorem for convex functions and then evaluate its representatives at the observations.
Theorem A.7 (Guntuboyina and Sen [11 ] , Theorem III.2). For a rectangle Q = ∏ k = 1 d [ a k , b k ] Q=\prod_{k=1}^{d}[a_k,b_k] Q = ∏ k = 1 d [ a k , b k ] with a k < b k a_k<b_k a k < b k and fixed positive numbers M , Γ 1 , … , Γ d M,\Gamma_1,\ldots,\Gamma_d M , Γ 1 , … , Γ d , we denote by C ( Q ; M , Γ ) C(Q;M,\Gamma) C ( Q ; M , Γ ) the class of convex functions h : Q → R h:Q\to\mathbb{R} h : Q → R that are bounded by M M M and have ∣ h ( x ) − h ( y ) ∣ ≤ Γ k ∣ x k − y k ∣ |h(x)-h(y)|\leq\Gamma_k|x_k-y_k| ∣ h ( x ) − h ( y ) ∣ ≤ Γ k ∣ x k − y k ∣ whenever x , y x,y x , y agree in all coordinates other than the k k k th. Then, there are constants c d , ϵ d > 0 c_d,\epsilon_d>0 c d , ϵ d > 0 , depending only on d d d , such that
log N ( ϵ , C ( Q ; M , Γ ) , ∥ ⋅ ∥ ∞ ) ≤ c d ( M + ∑ k = 1 d Γ k ( b k − a k ) ϵ ) d / 2 , 0 < ϵ ≤ ϵ d ( M + ∑ k = 1 d Γ k ( b k − a k ) ) . (28) \log N\left(\epsilon,C(Q;M,\Gamma),\|\cdot\|_\infty\right)\leq c_d\left(\frac{M+\sum_{k=1}^{d}\Gamma_k(b_k-a_k)}{\epsilon}\right)^{d/2},\qquad0<\epsilon\leq\epsilon_d\left(M+\sum_{k=1}^{d}\Gamma_k(b_k-a_k)\right). \tag*{(28)} log N ( ϵ , C ( Q ; M , Γ ) , ∥ ⋅ ∥ ∞ ) ≤ c d ( ϵ M + ∑ k = 1 d Γ k ( b k − a k ) ) d /2 , 0 < ϵ ≤ ϵ d ( M + k = 1 ∑ d Γ k ( b k − a k ) ) . (28) Here ∥ h ∥ ∞ , Q = sup x ∈ Q ∣ h ( x ) ∣ \|h\|_{\infty,Q}=\sup_{x\in Q}|h(x)| ∥ h ∥ ∞ , Q = sup x ∈ Q ∣ h ( x ) ∣ .
Using this theorem gives us the associated bound below.
Lemma A.8. There are constants C , ϵ 0 > 0 C,\epsilon_0>0 C , ϵ 0 > 0 such that for every design with θ 0 ∈ Θ n \theta^0\in\Theta_n θ 0 ∈ Θ n and every s > 0 s>0 s > 0 ,
log N ( ϵ , T s , ∥ ⋅ ∥ n ) ≤ C ϵ − d / 2 , 0 < ϵ ≤ ϵ 0 , (29) \log N(\epsilon,T_s,\|\cdot\|_n)\leq C\epsilon^{-d/2},\qquad0<\epsilon\leq\epsilon_0, \tag*{(29)} log N ( ϵ , T s , ∥ ⋅ ∥ n ) ≤ C ϵ − d /2 , 0 < ϵ ≤ ϵ 0 , (29) with covering centers chosen in T s T_s T s .
Proof. We choose a fixed rectangle Q = ∏ k = 1 d [ a k , b k ] Q=\prod_{k=1}^{d}[a_k,b_k] Q = ∏ k = 1 d [ a k , b k ] such that Ω ⊆ Q \Omega\subseteq Q Ω ⊆ Q . For each θ ∈ T s \theta\in T_s θ ∈ T s , there exists a matrix of subgradients G G G that gives a function f ^ θ , G \hat{f}_{\theta,G} f ^ θ , G which interpolates θ \theta θ and is convex and L L L -Lipschitz on Q Q Q . For x ∈ Q x\in Q x ∈ Q , we have that satisfies ∣ θ j + g j T ( x − X j ) ∣ ≤ B Q : = B + L diam ( Q ) |\theta_j+g_j^{\mathsf{T}}(x-X_j)|\leq B_Q:=B+L\operatorname{diam}(Q) ∣ θ j + g j T ( x − X j ) ∣ ≤ B Q := B + L diam ( Q ) . therefore f ^ θ , G \hat{f}_{\theta,G} f ^ θ , G has the same absolute bound on Q Q Q . We apply Theorem A.7 with M = B Q M=B_Q M = B Q and Γ k = L \Gamma_k=L Γ k = L at radius ϵ / 2 \epsilon/2 ϵ /2 giving us covering functions h 1 , … , h J h_1,\ldots,h_J h 1 , … , h J with log J ≤ c d ( 2 H Q / ϵ ) d / 2 \log J\leq c_d(2H_Q/\epsilon)^{d/2} log J ≤ c d ( 2 H Q / ϵ ) d /2 for sufficiently small ϵ \epsilon ϵ . By evaluating the covering functions at the sample points, we can construct v j = ( h j ( X 1 ) , … , h j ( X n ) ) v_j=(h_j(X_1),\ldots,h_j(X_n)) v j = ( h j ( X 1 ) , … , h j ( X n )) which covers T s T_s T s at radius ϵ / 2 \epsilon/2 ϵ /2 using distance metric ∥ ⋅ ∥ n \|\cdot\|_n ∥ ⋅ ∥ n since
∥ θ − v j ∥ n 2 = 1 n ∑ i = 1 n ∣ f θ , G ( X i ) − h j ( X i ) ∣ 2 ≤ ( ϵ / 2 ) 2 . \|\theta-v_j\|_n^2=\frac{1}{n}\sum_{i=1}^{n}|f_{\theta,G}(X_i)-h_j(X_i)|^2\leq(\epsilon/2)^2. ∥ θ − v j ∥ n 2 = n 1 i = 1 ∑ n ∣ f θ , G ( X i ) − h j ( X i ) ∣ 2 ≤ ( ϵ /2 ) 2 .
For each covering ball that intersects with T s T_s T s , we choose a point u j u_j u j in that intersection. A vector θ \theta θ covered by the original ball satisfies ∥ θ − u j ∥ n ≤ ϵ \|\theta-u_j\|_n\leq\epsilon ∥ θ − u j ∥ n ≤ ϵ . So, the points u j u_j u j form an ϵ \epsilon ϵ -cover of T s T_s T s . Taking ϵ 0 = ϵ d H Q \epsilon_0=\epsilon_dH_Q ϵ 0 = ϵ d H Q and adjusting the constant C C C appropriate proves the lemma.
We now aim to use the entropy bound to control U X ( s ) U_X(s) U X ( s ) through a Gaussian chaining argument. Each difference between two successive representatives is a linear function of the noise. We recall the following elementary properties of subgaussian matrices.
Lemma A.9. Assume that ξ \xi ξ satisfies Assumption (1). Then, for every vector a ∈ R n a\in\mathbb{R}^n a ∈ R n and sample points X X X ,
E [ e t a T ξ ∣ X ] ≤ e σ 2 t 2 ∥ a ∥ 2 2 / 2 , t ∈ R . (30) \mathbb{E}[e^{t a^{\mathsf{T}}\xi}\mid X]\leq e^{\sigma^2t^2\|a\|_2^2/2},\qquad t\in\mathbb{R}. \tag*{(30)} E [ e t a T ξ ∣ X ] ≤ e σ 2 t 2 ∥ a ∥ 2 2 /2 , t ∈ R . (30)
P ( ∣ a T ξ ∣ > σ ∥ a ∥ 2 t ∣ X ) ≤ 2 e − t . (31) \mathbb{P}(|a^{\mathsf{T}}\xi|>\sigma\|a\|\sqrt{2t}\mid X)\le2e^{-t}. \tag*{(31)} P ( ∣ a T ξ ∣ > σ ∥ a ∥ 2 t ∣ X ) ≤ 2 e − t . (31)
E [ ξ i 2 ∣ X ] ≤ σ 2 (32) \mathbb{E}[\xi_i^2\mid X]\le\sigma^2 \tag*{(32)} E [ ξ i 2 ∣ X ] ≤ σ 2 (32)
P ( ∥ ξ ∥ 2 > 2 σ n log 3 + t ∣ X ) ≤ e − t for t > 0. (33) \mathbb{P}(\|\xi\|_2>2\sigma\sqrt{n\log3+t}\mid X)\le e^{-t}\quad\text{for }t>0. \tag*{(33)} P ( ∥ ξ ∥ 2 > 2 σ n log 3 + t ∣ X ) ≤ e − t for t > 0. (33)
Proof. Independence of ξ \xi ξ along with the sub-gaussianity gives
E [ e t a T ξ ∣ X ] = ∏ i E [ e t a i ξ i ∣ X ] ≤ ∏ i e σ 2 t 2 a i 2 / 2 = e σ 2 t 2 ∥ a ∥ 2 2 / 2 . \mathbb{E}[e^{ta^{\mathsf{T}}\xi}\mid X]=\prod_i\mathbb{E}[e^{ta_i\xi_i}\mid X]\le\prod_i e^{\sigma^2t^2a_i^2/2}=e^{\sigma^2t^2\|a\|_2^2/2}. E [ e t a T ξ ∣ X ] = i ∏ E [ e t a i ξ i ∣ X ] ≤ i ∏ e σ 2 t 2 a i 2 /2 = e σ 2 t 2 ∥ a ∥ 2 2 /2 .
For a ≠ 0 a\ne0 a = 0 and u > 0 u>0 u > 0 , Markov’s inequality gives
P ( a T ξ > u ∣ X ) ≤ inf t > 0 exp { − t u + σ 2 t 2 ∥ a ∥ 2 2 / 2 } = exp { − u 2 / ( 2 σ 2 ∥ a ∥ 2 2 ) } . \mathbb{P}(a^{\mathsf{T}}\xi>u\mid X)\le\inf_{t>0}\exp\{-tu+\sigma^2t^2\|a\|_2^2/2\}=\exp\{-u^2/(2\sigma^2\|a\|_2^2)\}. P ( a T ξ > u ∣ X ) ≤ t > 0 inf exp { − t u + σ 2 t 2 ∥ a ∥ 2 2 /2 } = exp { − u 2 / ( 2 σ 2 ∥ a ∥ 2 2 )} .
by setting t = u / ( σ 2 ∥ a ∥ 2 2 ) t=u/(\sigma^2\|a\|_2^2) t = u / ( σ 2 ∥ a ∥ 2 2 ) . Applying the same bound to − a -a − a and applying a union bound gives (31) .
For the second moment bound, we note that e u + e − u ≥ 2 + u 2 e^u+e^{-u}\ge2+u^2 e u + e − u ≥ 2 + u 2
1 + t 2 2 E [ ξ i 2 ∣ X ] ≤ E [ e t ξ i ∣ X ] + E [ e − t ξ i ∣ X ] 1+\frac{t^2}{2}\mathbb{E}[\xi_i^2\mid X]\le\mathbb{E}[e^{t\xi_i}\mid X]+\mathbb{E}[e^{-t\xi_i}\mid X] 1 + 2 t 2 E [ ξ i 2 ∣ X ] ≤ E [ e t ξ i ∣ X ] + E [ e − t ξ i ∣ X ]
implying that E [ ξ i 2 ∣ X ] ≤ 2 e σ 2 t 2 / 2 − 2 t 2 \mathbb{E}[\xi_i^2\mid X]\le\frac{2e^{\sigma^2t^2/2}-2}{t^2} E [ ξ i 2 ∣ X ] ≤ t 2 2 e σ 2 t 2 /2 − 2 . By sending t ⇒ 0 t\Rightarrow0 t ⇒ 0 bounds this by σ 2 \sigma^2 σ 2 as desired.
For the norm bound, equation (31) implies P ( e ξ i 2 / ( 4 σ 2 ) > v ∣ X ) ≤ 2 v − 2 \mathbb{P}(e^{\xi_i^2/(4\sigma^2)}>v\mid X)\le2v^{-2} P ( e ξ i 2 / ( 4 σ 2 ) > v ∣ X ) ≤ 2 v − 2 for v ≥ 1 v\ge1 v ≥ 1 . Integration along with independence gives
E [ e ξ i 2 / ( 4 σ 2 ) ∣ X ] ≤ 1 + 2 ∫ 1 ∞ v − 2 d v = 3. ⟹ E [ e ∥ ξ ∥ 2 2 / ( 4 σ 2 ) ∣ X ] ≤ 3 n \mathbb{E}[e^{\xi_i^2/(4\sigma^2)}\mid X]\le1+2\int_1^\infty v^{-2}\,dv=3.
\quad\Longrightarrow\quad
\mathbb{E}[e^{\|\xi\|_2^2/(4\sigma^2)}\mid X]\le3^n E [ e ξ i 2 / ( 4 σ 2 ) ∣ X ] ≤ 1 + 2 ∫ 1 ∞ v − 2 d v = 3. ⟹ E [ e ∥ ξ ∥ 2 2 / ( 4 σ 2 ) ∣ X ] ≤ 3 n
An application of Markov inequality proves the result. (33).
For an increment Z v − Z w = n − 1 ξ T ( v − w ) Z_v-Z_w=n^{-1}\xi^{\mathsf{T}}(v-w) Z v − Z w = n − 1 ξ T ( v − w ) , Lemma (A.9) gives a scale proportional to σ ∥ v − w ∥ n / n \sigma\|v-w\|_n/\sqrt{n} σ ∥ v − w ∥ n / n . We now bound the relevant U X ( s ) U_X(s) U X ( s ) .
Lemma A.10. For 0 < s ≤ 2 B 0<s\le2B 0 < s ≤ 2 B , 0 < β ≤ s / 2 0<\beta\le s/2 0 < β ≤ s /2 , and t ≥ 0 t\ge0 t ≥ 0 , with probability at least 1 − 2 e − t 1-2e^{-t} 1 − 2 e − t ,
U X ( s ) ≤ C σ [ β + J d ( s , β ) n + s t + 1 n ] . (34) U_X(s)\le C\sigma\left[\beta+\frac{J_d(s,\beta)}{\sqrt{n}}+s\sqrt{\frac{t+1}{n}}\right]. \tag*{(34)} U X ( s ) ≤ C σ [ β + n J d ( s , β ) + s n t + 1 ] . (34) where
J d ( s , β ) = { s 1 − d / 4 , 2 ≤ d < 4 , 1 + log ( s / β ) , d = 4 , β 1 − d / 4 , d > 4. J_d(s,\beta)=
\begin{cases}
s^{1-d/4}, & 2\le d<4,\\
1+\log(s/\beta), & d=4,\\
\beta^{1-d/4}, & d>4.
\end{cases} J d ( s , β ) = ⎩ ⎨ ⎧ s 1 − d /4 , 1 + log ( s / β ) , β 1 − d /4 , 2 ≤ d < 4 , d = 4 , d > 4. Proof. We write N i n t N_{\mathrm{int}} N int to denote the covering numbers with centers in T s T_s T s . Through Lemma A.8, we have log N i n t ( u , T s , ∥ ⋅ ∥ n ) ≤ A 0 u − d / 2 \log N_{\mathrm{int}}(u,T_s,\|\cdot\|_n)\le A_0u^{-d/2} log N int ( u , T s , ∥ ⋅ ∥ n ) ≤ A 0 u − d /2 for all 0 < u ≤ ϵ 0 0<u\le\epsilon_0 0 < u ≤ ϵ 0 . If ϵ 0 > 2 B \epsilon_0>2B ϵ 0 > 2 B , we can set the inequality to 0 < u ≤ 2 B 0< u\le2B 0 < u ≤ 2 B . If not, for u > ϵ 0 u>\epsilon_0 u > ϵ 0 , we have that log N i n t ( u , T s , ∥ ⋅ ∥ n ) ≤ log N i n t ( ϵ 0 , T s , ∥ ⋅ ∥ n ) ≤ A 0 ϵ 0 − d / 2 \log N_{\mathrm{int}}(u,T_s,\|\cdot\|_n)\le\log N_{\mathrm{int}}(\epsilon_0,T_s,\|\cdot\|_n)\le A_0\epsilon_0^{-d/2} log N int ( u , T s , ∥ ⋅ ∥ n ) ≤ log N int ( ϵ 0 , T s , ∥ ⋅ ∥ n ) ≤ A 0 ϵ 0 − d /2 . By choosing A = A 0 max { 1 , ( 2 B / ϵ 0 ) d / 2 } A=A_0\max\{1,(2B/\epsilon_0)^{d/2}\} A = A 0 max { 1 , ( 2 B / ϵ 0 ) d /2 } , we have that log N i n t ( u , T s , ∥ ⋅ ∥ n ) \log N_{\mathrm{int}}(u,T_s,\|\cdot\|_n) log N int ( u , T s , ∥ ⋅ ∥ n ) for all 0 < u ≤ 2 B 0<u\le2B 0 < u ≤ 2 B .
We set successively finer radii of the form r j = 2 − j s r_j=2^{-j}s r j = 2 − j s and the smallest integer J J J with r J ≤ β r_J\le\beta r J ≤ β , so that β / 2 < r J ≤ β \beta/2<r_J\le\beta β /2 < r J ≤ β . For each value of j j j , we take an r j r_j r j -cover T j T_j T j of size M j M_j M j satisfying log M j ≤ A r j − d / 2 \log M_j\le Ar_j^{-d/2} log M j ≤ A r j − d /2 . We set T 0 = { θ 0 } T_0=\{\theta^0\} T 0 = { θ 0 } and M 0 = 1 M_0=1 M 0 = 1 . For θ ∈ T s \theta\in T_s θ ∈ T s , we select a representative π j θ ∈ T j \pi_j\theta\in T_j π j θ ∈ T j such that ∥ θ − π j θ ∥ n ≤ r j \|\theta-\pi_j\theta\|_n\le r_j ∥ θ − π j θ ∥ n ≤ r j and define π 0 θ = θ 0 \pi_0\theta=\theta^0 π 0 θ = θ 0 . Since Z θ 0 = 0 Z_{\theta^0}=0 Z θ 0 = 0 ,
Z θ = ∑ j = 1 J ( Z π j θ − Z π j − 1 θ ) + ( Z θ − Z π J θ ) . Z_\theta=\sum_{j=1}^{J}(Z_{\pi_j\theta}-Z_{\pi_{j-1}\theta})+(Z_\theta-Z_{\pi_J\theta}). Z θ = j = 1 ∑ J ( Z π j θ − Z π j − 1 θ ) + ( Z θ − Z π J θ ) . We now control the finite sum and its remainder separately.
The triangle inequality gives ∥ π j θ − π j − 1 θ ∥ n ≤ 3 r j \lVert\pi_j\theta-\pi_{j-1}\theta\rVert_n \le3r_j ∥ π j θ − π j − 1 θ ∥ n ≤ 3 r j . For any fixed pair v , w v,w v , w at this distance, Equation (31) with a = ( v − w ) / n a=(v-w)/n a = ( v − w ) / n yields
P ( ∣ Z v − Z w ∣ > 3 σ r j n 2 z | X ) ≤ 2 e − z . \mathbb{P}\left(\left|Z_v-Z_w\right|>\frac{3\sigma r_j}{\sqrt{n}}\sqrt{2z}\,\middle|\,X\right)\le2e^{-z}. P ( ∣ Z v − Z w ∣ > n 3 σ r j 2 z X ) ≤ 2 e − z .
At level j j j , at most M j M j − 1 M_jM_{j-1} M j M j − 1 pairs can be used as successive representatives to θ \theta θ which tells us that
P ( ∃ ( v , w ) such that ∣ Z v − Z w ∣ > 3 σ r j n 2 z | X ) ≤ 2 M j M j − 1 e − z . \mathbb{P}\left(\exists(v,w)\text{ such that }\left|Z_v-Z_w\right|>\frac{3\sigma r_j}{\sqrt{n}}\sqrt{2z}\,\middle|\,X\right)\le2M_jM_{j-1}e^{-z}. P ( ∃ ( v , w ) such that ∣ Z v − Z w ∣ > n 3 σ r j 2 z X ) ≤ 2 M j M j − 1 e − z .
By choosing z j = t + log ( 4 M j M j − 1 ) + 2 log ( j + 1 ) z_j=t+\log(4M_jM_{j-1})+2\log(j+1) z j = t + log ( 4 M j M j − 1 ) + 2 log ( j + 1 ) , we get that
P ( ∃ ( v , w ) such that ∣ Z v − Z w ∣ > 3 σ r j n 2 z | X ) ≤ e − t 2 ( j + 1 ) 2 . \mathbb{P}\left(\exists(v,w)\text{ such that }\left|Z_v-Z_w\right|>\frac{3\sigma r_j}{\sqrt{n}}\sqrt{2z}\,\middle|\,X\right)\le\frac{e^{-t}}{2(j+1)^2}. P ( ∃ ( v , w ) such that ∣ Z v − Z w ∣ > n 3 σ r j 2 z X ) ≤ 2 ( j + 1 ) 2 e − t .
Applying another union bound over all j j j , we have that
P ( ∃ ( j , v , w ) such that ∣ Z v − Z w ∣ > 3 σ r j n 2 z | X ) ≤ e − t \mathbb{P}\left(\exists(j,v,w)\text{ such that }\left|Z_v-Z_w\right|>\frac{3\sigma r_j}{\sqrt{n}}\sqrt{2z}\,\middle|\,X\right)\le e^{-t} P ( ∃ ( j , v , w ) such that ∣ Z v − Z w ∣ > n 3 σ r j 2 z X ) ≤ e − t
where we used that ∑ j = 1 J 1 ( j + 1 ) 2 ≤ ∑ j = 1 J 1 j ( j + 1 ) = 1 − 1 J + 1 < 1 \sum_{j=1}^{J}\frac{1}{(j+1)^2}\le\sum_{j=1}^{J}\frac{1}{j(j+1)}=1-\frac{1}{J+1}<1 ∑ j = 1 J ( j + 1 ) 2 1 ≤ ∑ j = 1 J j ( j + 1 ) 1 = 1 − J + 1 1 < 1 . Therefore, with probability 1 − e − t 1-e^{-t} 1 − e − t , we have that every relevant pair Z v − Z w Z_v-Z_w Z v − Z w at every level is appropriately bounded. On such an event, we have that for all θ ∈ T s \theta\in T_s θ ∈ T s , consecutive pairs ( π j θ , π j − 1 θ ) (\pi_j\theta,\pi_{j-1}\theta) ( π j θ , π j − 1 θ )
∣ ∑ j = 1 J ( Z π j θ − Z π j − 1 θ ) ∣ ≤ 3 2 σ n ∑ j = 1 J r j z j . \left|\sum_{j=1}^{J}(Z_{\pi_j\theta}-Z_{\pi_{j-1}\theta})\right|\le\frac{3\sqrt{2}\sigma}{\sqrt{n}}\sum_{j=1}^{J}r_j\sqrt{z_j}. j = 1 ∑ J ( Z π j θ − Z π j − 1 θ ) ≤ n 3 2 σ j = 1 ∑ J r j z j .
The two cover sizes satisfy log ( M j M j − 1 ) < 2 A r j − d / 2 \log(M_jM_{j-1})<2Ar_j^{-d/2} log ( M j M j − 1 ) < 2 A r j − d /2 , so z j ≤ 2 A r j − d / 2 + t + log 4 + 2 log ( j + 1 ) z_j\le\sqrt{2}Ar_j^{-d/2}+t+\log4+2\log(j+1) z j ≤ 2 A r j − d /2 + t + log 4 + 2 log ( j + 1 ) . By noting that x + y ≤ x + y \sqrt{x+y}\le\sqrt{x}+\sqrt{y} x + y ≤ x + y , we get that
∑ j = 1 J r j z j ≤ C A ∑ j = 1 J r j 1 − d / 4 + C ∑ j = 1 J r j t + 1 + 2 log ( j + 1 ) . \sum_{j=1}^{J}r_j\sqrt{z_j}\le C_A\sum_{j=1}^{J}r_j^{1-d/4}+C\sum_{j=1}^{J}r_j\sqrt{t+1+2\log(j+1)}. j = 1 ∑ J r j z j ≤ C A j = 1 ∑ J r j 1 − d /4 + C j = 1 ∑ J r j t + 1 + 2 log ( j + 1 ) .
We first handle the second term. We have that
∑ j = 1 J r j t + 1 + 2 log ( j + 1 ) ≤ s t + log 4 ∑ j = 1 J 2 − j + 2 s ∑ j = 1 J 2 − j log ( j + 1 ) ≤ s t + 4 + 2 2 s . \begin{aligned}
\sum_{j=1}^{J}r_j\sqrt{t+1+2\log(j+1)}
\le s\sqrt{t+\log4}\sum_{j=1}^{J}2^{-j}+\sqrt{2}s\sum_{j=1}^{J}2^{-j}\sqrt{\log(j+1)} \\
&\le s\sqrt{t+4+2\sqrt{2}s}.
\end{aligned} j = 1 ∑ J r j t + 1 + 2 log ( j + 1 ) ≤ s t + log 4 j = 1 ∑ J 2 − j + 2 s j = 1 ∑ J 2 − j log ( j + 1 ) ≤ s t + 4 + 2 2 s .
where we used that log ( j + 1 ) ≤ j \log(j+1)\le j log ( j + 1 ) ≤ j for j ≥ 1 j\ge1 j ≥ 1 . We therefore have that this can be bounded by C t + 1 C\sqrt{t+1} C t + 1 for large enough constants C C C .
For the first term, we have that β 2 ≤ r J ≤ β \frac{\beta}{2}\le r_J\le\beta 2 β ≤ r J ≤ β . For 2 ≤ d < 4 2\le d<4 2 ≤ d < 4 , we have that ∑ j = 1 J r j 1 − d / 4 ≤ s 1 − d / 4 1 − 2 1 − d / 4 ≤ C d s 1 − d / 4 \sum_{j=1}^{J}r_j^{1-d/4}\le\frac{s^{1-d/4}}{1-2^{1-d/4}}\le C_ds^{1-d/4} ∑ j = 1 J r j 1 − d /4 ≤ 1 − 2 1 − d /4 s 1 − d /4 ≤ C d s 1 − d /4 from a geometric series sum. For d = 4 d=4 d = 4 , we have that ∑ j = 1 J r j 1 − d / 4 = J ≤ C ( 1 + log ( s / β ) ) \sum_{j=1}^{J}r_j^{1-d/4}=J\le C(1+\log(s/\beta)) ∑ j = 1 J r j 1 − d /4 = J ≤ C ( 1 + log ( s / β )) . When d = 4 d=4 d = 4 ,
∑ j = 1 J r j 1 − d / 4 ≤ r 1 1 − d / 4 1 − 2 1 − d / 4 . \sum_{j=1}^{J}r_j^{1-d/4}\le\frac{r_1^{1-d/4}}{1-2^{1-d/4}}. j = 1 ∑ J r j 1 − d /4 ≤ 1 − 2 1 − d /4 r 1 1 − d /4 .
Since r J > β 2 r_J>\frac{\beta}{2} r J > 2 β , the top term simplifies to 2 d / 4 − 1 β 1 − d / 4 2^{d/4-1}\beta^{1-d/4} 2 d /4 − 1 β 1 − d /4 giving us a bound of C d β 1 − d / 4 C_d\beta^{1-d/4} C d β 1 − d /4 . Hence, the telescoping sum satisfies
∑ j = 1 J ( Z π j θ − Z π j − 1 θ ) ≤ C σ [ J d ( s , β ) n + s t + 1 n ] . \sum_{j=1}^{J}(Z_{\pi_j\theta}-Z_{\pi_{j-1}\theta})\le C\sigma\left[\frac{J_d(s,\beta)}{\sqrt{n}}+s\sqrt{\frac{t+1}{n}}\right]. j = 1 ∑ J ( Z π j θ − Z π j − 1 θ ) ≤ C σ [ n J d ( s , β ) + s n t + 1 ] .
For the remainder term, note that since r J < β r_J<\beta r J < β ,
∣ Z θ − Z π J θ ∣ ≤ 1 n ∥ ξ ∥ 2 ∥ θ − π J θ ∥ 2 ≤ β ∥ ξ ∥ n . \left|Z_\theta-Z_{\pi_J\theta}\right|\le\frac{1}{n}\lVert\xi\rVert_2\lVert\theta-\pi_J\theta\rVert_2\le\beta\lVert\xi\rVert_n. ∣ Z θ − Z π J θ ∣ ≤ n 1 ∥ ξ ∥ 2 ∥ θ − π J θ ∥ 2 ≤ β ∥ ξ ∥ n .
By Lemma (A.9), outside an event of conditional probability at most e − t e^{-t} e − t , this is bounded by
2 σ β log 3 + t / n ≤ C σ β + C σ s ( t + 1 ) / n . 2\sigma\beta\sqrt{\log3+t/n}\le C\sigma\beta+C\sigma s\sqrt{(t+1)/n}. 2 σ β log 3 + t / n ≤ C σ β + C σ s ( t + 1 ) / n .
Combining the two events proves the bound on U X ( s ) U_X(s) U X ( s ) .
An important note in Lemma (A.10) is that for 2 < d < 4 2<d<4 2 < d < 4 , we have that sending β \beta β to 0 0 0 does not change the failure probability allowing us to remove the first term.
Conversion to a high probability bound
Lemma (A.6) reduces the estimation problem to choosing s s s for which the upper bound on U X U_X U X is smaller than s 2 / 2 s^2/2 s 2 /2 . We now appropriately choose the radii r n , d r_{n,d} r n , d so that the bound from Lemma (A.10) is satisfied.
Proposition A.11. There are constants C , n 0 > 0 C,n_0>0 C , n 0 > 0 such that, for n ≥ n 0 n\ge n_0 n ≥ n 0 , t ≥ 0 t\ge0 t ≥ 0 , f 0 ∈ F B , L ( Ω ) f_0\in\mathcal{F}_{B,L}(\Omega) f 0 ∈ F B , L ( Ω ) and for almost all set of points X 1 , … , X n X_1,\ldots,X_n X 1 , … , X n ,
P f 0 ( ∥ θ ^ L S − θ 0 ∥ n 2 > C ( r n , d + σ 2 ( t + 1 ) n ) ∣ X ) ≤ 2 e − t . (35) \mathbb{P}_{f_0}\left(\left\|\widehat{\theta}_{\mathrm{LS}}-\theta^0\right\|_n^2>C\left(r_{n,d}+\frac{\sigma^2(t+1)}{n}\right)\mathrel{\Big|}X\right)\le2e^{-t}. \tag*{(35)} P f 0 ( θ LS − θ 0 n 2 > C ( r n , d + n σ 2 ( t + 1 ) ) X ) ≤ 2 e − t . (35) where r n , d r_{n,d} r n , d was defined in (6). Consequently,
E f 0 [ ∥ θ ^ L S − θ 0 ∥ n 2 ∣ X ] ≤ C ( r n , d + σ 2 n ) . (36) \mathbb{E}_{f_0}\left[\left\|\widehat{\theta}_{\mathrm{LS}}-\theta^0\right\|_n^2\mid X\right]\le C\left(r_{n,d}+\frac{\sigma^2}{n}\right). \tag*{(36)} E f 0 [ θ LS − θ 0 n 2 ∣ X ] ≤ C ( r n , d + n σ 2 ) . (36)
Proof. Using Lemma (A.6) and (A.10), our goal is to choose s s s and β \beta β so that
C σ [ β + J d ( s , β ) n + s t + 1 n ] < s 2 4 . C\sigma\left[\beta+\frac{J_d(s,\beta)}{\sqrt{n}}+s\sqrt{t+1}\sqrt{n}\right]<\frac{s^2}{4}. C σ [ β + n J d ( s , β ) + s t + 1 n ] < 4 s 2 .
For a given t ≥ 0 t\ge0 t ≥ 0 , consider the value of s = ( A ( r n , d + σ 2 ( t + 1 ) / n ) ) 1 / 2 s=(A(r_{n,d}+\sigma^2(t+1)/n))^{1/2} s = ( A ( r n , d + σ 2 ( t + 1 ) / n ) ) 1/2 , where A A A is a sufficiently large fixed constant. Firstly, note that both θ i \theta_i θ i and f ( X i ) f(X_i) f ( X i ) are bounded by B B B , so the error cannot exceed s s s when s ≥ 2 B s\ge2B s ≥ 2 B . We therefore consider the case where s < 2 B s<2B s < 2 B .
The last term in Eq. (34) satisfies
C σ s ( t + 1 ) / n s 2 ≤ C A , \frac{C\sigma s\sqrt{(t+1)/n}}{s^2}\le\frac{C}{\sqrt{A}}, s 2 C σ s ( t + 1 ) / n ≤ A C ,
since s 2 ≥ A σ 2 ( t + 1 ) / n s^2\ge A\sigma^2(t+1)/n s 2 ≥ A σ 2 ( t + 1 ) / n . Choosing A A A large enough makes this contribution at most s 2 / 8 s^2/8 s 2 /8 .
When 2 ≤ d < 4 2\le d<4 2 ≤ d < 4 , we remove the β \beta β term and focus on the second term C σ s 1 − d / 4 n C\sigma\frac{s^{1-d/4}}{\sqrt{n}} C σ n s 1 − d /4 . Since s ≥ A r n , d 1 / 2 = A n − 2 / ( d + 4 ) s\ge\sqrt{A}r_{n,d}^{1/2}=\sqrt{A}n^{-2/(d+4)} s ≥ A r n , d 1/2 = A n − 2/ ( d + 4 ) , we get
C σ n − 1 / 2 s 1 − d / 4 s 2 = C σ n − 1 / 2 s − ( 1 + d / 4 ) ≤ C σ A − ( d + 4 ) / 8 . \frac{C\sigma n^{-1/2}s^{1-d/4}}{s^2}=C\sigma n^{-1/2}s^{-(1+d/4)}\le C\sigma A^{-(d+4)/8}. s 2 C σ n − 1/2 s 1 − d /4 = C σ n − 1/2 s − ( 1 + d /4 ) ≤ C σ A − ( d + 4 ) /8 .
When d = 4 d=4 d = 4 , we can set β = n − 1 / 2 \beta=n^{-1/2} β = n − 1/2 . The lower bound s 2 ≥ A n − 1 / 2 log n s^2\ge An^{-1/2}\log n s 2 ≥ A n − 1/2 log n ensures β ≤ s / 2 \beta\le s/2 β ≤ s /2 for all sufficiently large n n n . Since s < 2 B s<2B s < 2 B , we have 1 + log ( s / β ) ≤ 1 + log ( 2 B n ) ≤ C B log n 1+\log(s/\beta)\le1+\log(2B\sqrt{n})\le C_B\log n 1 + log ( s / β ) ≤ 1 + log ( 2 B n ) ≤ C B log n . Therefore,
C σ [ β + 1 + log ( s / β ) n ] ≤ C ′ σ n − 1 / 2 log n = C ′ σ r n , d ≤ C ′ A σ 2 s 2 . C\sigma\left[\beta+\frac{1+\log(s/\beta)}{\sqrt{n}}\right]\le C'\sigma n^{-1/2}\log n=C'\sigma r_{n,d}\le\frac{C'}{A}\sigma^2s^2. C σ [ β + n 1 + log ( s / β ) ] ≤ C ′ σ n − 1/2 log n = C ′ σ r n , d ≤ A C ′ σ 2 s 2 .
When d > 4 d>4 d > 4 , we can set β = n − 2 / d \beta=n^{-2/d} β = n − 2/ d . As s 2 A > r n , d \frac{s^2}{A}>r_{n,d} A s 2 > r n , d , we have that β ≤ s / 2 \beta\le s/2 β ≤ s /2 for large enough A A A and n n n , since s ≥ A r n , d 1 / 2 s\ge\sqrt{A}r_{n,d}^{1/2} s ≥ A r n , d 1/2 and r n , d → 0 r_{n,d}\to0 r n , d → 0 . We then get that
C σ [ β + β 1 − d / 4 n ] ≤ C ′ σ n − 2 / d ≤ C ′ σ r n , d ≤ C ′ A σ 2 s 2 . C\sigma\left[\beta+\frac{\beta^{1-d/4}}{\sqrt{n}}\right]\le C'\sigma n^{-2/d}\le C'\sigma r_{n,d}\le\frac{C'}{A}\sigma^2s^2. C σ [ β + n β 1 − d /4 ] ≤ C ′ σ n − 2/ d ≤ C ′ σ r n , d ≤ A C ′ σ 2 s 2 .
In all three cases, we can make this at most s 2 / 8 s^2/8 s 2 /8 for sufficiently large A A A .
Combining, we have that with probability at least 1 − 2 e − t 1-2e^{-t} 1 − 2 e − t , we have U X ( s ) ≤ s 2 / 4 U_X(s) \le s^2/4 U X ( s ) ≤ s 2 /4 . This proves the concentration bound.
For the expectation, we have the objective we care about is positive giving us that
E [ ∥ θ ^ L S − θ 0 ∥ n 2 ∣ X ] = ∫ 0 ∞ P ( ∥ θ ^ L S − θ 0 ∥ n 2 > C ( r n , d + σ 2 ( t + 1 ) n ) ) ≤ C ( r n , d + σ 2 ( t + 1 ) n ) + ∫ 0 ∞ P ( V > C ( r n , d + σ 2 ( t + 1 ) n ) + u ∣ X ) d u ≤ C ( r n , d + σ 2 ( t + 1 ) n ) + C σ 2 n ∫ 0 ∞ 2 e − t d t ≤ C ′ ( r n , d + σ 2 n ) . \begin{aligned}
\mathbb{E}[\|\widehat{\theta}_{\mathrm{LS}}-\theta^0\|_n^2\mid X]
&=\int_0^\infty\mathbb{P}\left(\|\widehat{\theta}_{\mathrm{LS}}-\theta^0\|_n^2>C\left(r_{n,d}+\frac{\sigma^2(t+1)}{n}\right)\right)\\
&\le C\left(r_{n,d}+\frac{\sigma^2(t+1)}{n}\right)+\int_0^\infty\mathbb{P}\left(V>C\left(r_{n,d}+\frac{\sigma^2(t+1)}{n}\right)+u\mid X\right)\,du\\
&\le C\left(r_{n,d}+\frac{\sigma^2(t+1)}{n}\right)+\frac{C\sigma^2}{n}\int_0^\infty2e^{-t}\,dt
\le C'\left(r_{n,d}+\frac{\sigma^2}{n}\right).
\end{aligned} E [ ∥ θ LS − θ 0 ∥ n 2 ∣ X ] = ∫ 0 ∞ P ( ∥ θ LS − θ 0 ∥ n 2 > C ( r n , d + n σ 2 ( t + 1 ) ) ) ≤ C ( r n , d + n σ 2 ( t + 1 ) ) + ∫ 0 ∞ P ( V > C ( r n , d + n σ 2 ( t + 1 ) ) + u ∣ X ) d u ≤ C ( r n , d + n σ 2 ( t + 1 ) ) + n C σ 2 ∫ 0 ∞ 2 e − t d t ≤ C ′ ( r n , d + n σ 2 ) .
The preceding proposition concerns the unregularized fitted vector. We now compare it with the regularized full fit. The hard slope bound limits how much objective improvement can be obtained from reducing the slope penalty, and the quadratic loss converts this limitation into a bound on the movement of the fitted values.
Lemma A.12. For every realized design and response vector,
∥ θ F − θ ^ L S ∥ n 2 ≤ μ n L 2 . (37) \|\theta_F-\widehat{\theta}_{\mathrm{LS}}\|_n^2\le\mu_nL^2. \tag*{(37)} ∥ θ F − θ LS ∥ n 2 ≤ μ n L 2 . (37) Proof. Consider a subgradient matrix G L S G_{\mathrm{LS}} G LS for θ ^ L S \widehat{\theta}_{\mathrm{LS}} θ LS so that ( θ ^ L S , G L S ) ∈ C E F (\widehat{\theta}_{\mathrm{LS}},G_{\mathrm{LS}})\in\mathcal{C}_{EF} ( θ LS , G LS ) ∈ C E F . The bounds of the gradients give ∥ G L S ∥ F 2 ≤ n L 2 \|G_{\mathrm{LS}}\|_F^2\le nL^2 ∥ G LS ∥ F 2 ≤ n L 2 . The projection optimality condition is ( θ ^ L S − Y ) ⊤ ( θ F − θ ^ L S ) ≥ 0 (\widehat{\theta}_{\mathrm{LS}}-Y)^\top(\theta_F-\widehat{\theta}_{\mathrm{LS}})\ge0 ( θ LS − Y ) ⊤ ( θ F − θ LS ) ≥ 0 . We can then note that
1 2 ∥ θ F − θ ^ L S ∥ n 2 ≤ 1 2 ∥ θ F − Y ∥ n 2 − 1 2 ∥ θ ^ L S − Y ∥ n 2 . (38) \frac{1}{2}\|\theta_F-\widehat{\theta}_{\mathrm{LS}}\|_n^2\le\frac{1}{2}\|\theta_F-Y\|_n^2-\frac{1}{2}\|\widehat{\theta}_{\mathrm{LS}}-Y\|_n^2. \tag*{(38)} 2 1 ∥ θ F − θ LS ∥ n 2 ≤ 2 1 ∥ θ F − Y ∥ n 2 − 2 1 ∥ θ LS − Y ∥ n 2 . (38) Since ( θ F , G F ) (\theta_F,G_F) ( θ F , G F ) optimizes our regularized objective functions, we have that
μ n 2 ( ∥ G L S ∥ F 2 − ∥ G F ∥ F 2 ) ≤ μ n n L 2 2 . \frac{\mu_n}{2}\left(\|G_{\mathrm{LS}}\|_F^2-\|G_F\|_F^2\right)\le\frac{\mu_n nL^2}{2}. 2 μ n ( ∥ G LS ∥ F 2 − ∥ G F ∥ F 2 ) ≤ 2 μ n n L 2 . Dividing by n / 2 n/2 n /2 gives us the desired result.
Combining this regularization limit with the concentration bounds of the LS solution gives the following corollary.
Corollary A.13 (Regularized empirical error). For all sufficiently large n n n , every δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , and almost every design,
P f 0 ( ∥ θ F − θ 0 ∥ n 2 > C ( r n , d + μ n L 2 + σ 2 log ( 2 / δ ) n ) | X ) ≤ δ , (39) \mathbb{P}_{f_0}\left(\|\theta_F-\theta^0\|_n^2>C\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2\log(2/\delta)}{n}\right)\middle|X\right)\le\delta, \tag*{(39)} P f 0 ( ∥ θ F − θ 0 ∥ n 2 > C ( r n , d + μ n L 2 + n σ 2 log ( 2/ δ ) ) X ) ≤ δ , (39) and
E f 0 [ ∥ θ F − θ 0 ∥ n 2 ∣ X ] ≤ C ( r n , d + μ n L 2 + σ 2 n ) . (40) \mathbb{E}_{f_0}[\|\theta_F-\theta^0\|_n^2\mid X]\le C\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2}{n}\right). \tag*{(40)} E f 0 [ ∥ θ F − θ 0 ∥ n 2 ∣ X ] ≤ C ( r n , d + μ n L 2 + n σ 2 ) . (40) Proof. We decompose our desired term into
∥ θ F − θ 0 ∥ n 2 ≤ 2 ∥ θ F − θ ^ L S ∥ n 2 + 2 ∥ θ ^ L S − θ 0 ∥ n 2 . \|\theta_F-\theta^0\|_n^2\le2\|\theta_F-\widehat{\theta}_{\mathrm{LS}}\|_n^2+2\|\widehat{\theta}_{\mathrm{LS}}-\theta^0\|_n^2. ∥ θ F − θ 0 ∥ n 2 ≤ 2∥ θ F − θ LS ∥ n 2 + 2∥ θ LS − θ 0 ∥ n 2 . Lemma (A.12) bounds the first term by μ n L 2 \mu_nL^2 μ n L 2 . For the second term, an application of Proposition (A.11) with t = log ( 2 / δ ) t=\log(2/\delta) t = log ( 2/ δ ) and noting that log ( 2 / δ ) + 1 ≤ ( 1 + 1 log 2 ) log ( 2 / δ ) \log(2/\delta)+1\le\left(1+\frac{1}{\log2}\right)\log(2/\delta) log ( 2/ δ ) + 1 ≤ ( 1 + l o g 2 1 ) log ( 2/ δ ) , The expectation bound immediately follows fomr the decomposition.
We now convert this to a population bound. For the remaining appendices, we define δ = r n , d 2 \delta=r_{n,d}^2 δ = r n , d 2 . For sufficiently large n n n , we have that δ n ∈ ( 0 , 1 ) \delta_n\in(0,1) δ n ∈ ( 0 , 1 ) . Through the definition of r n , d r_{n,d} r n , d , it is easy to check that:
log ( 1 / δ n ) = O ( log n ) , log ( 2 n / δ n ) = O ( log n ) . (41) \log(1/\delta_n)=O(\log n),\qquad\log(2n/\delta_n)=O(\log n). \tag*{(41)} log ( 1/ δ n ) = O ( log n ) , log ( 2 n / δ n ) = O ( log n ) . (41)
Proposition A.14 (Full risk and population confidence bound). For all sufficiently large n n n and for any f 0 ∈ F B , L ( Ω ) f_0 \in\mathcal{F}_{B,L}(\Omega) f 0 ∈ F B , L ( Ω ) ,
E f 0 ℓ P 2 ( f ^ F , f 0 ) ≤ C [ ( log n ) ( r n , d + μ n L 2 + σ 2 n ) + L 2 ( log n n ) 2 / d ] . (42) \mathbb{E}_{f_0}\ell_{\mathbb{P}}^2(\widehat{f}_F,f_0) \le C\left[(\log n)\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2}{n}\right)+L^2\left(\frac{\log n}{n}\right)^{2/d}\right]. \tag*{(42)} E f 0 ℓ P 2 ( f F , f 0 ) ≤ C [ ( log n ) ( r n , d + μ n L 2 + n σ 2 ) + L 2 ( n log n ) 2/ d ] . (42) For every δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , we have that
P ( ℓ P 2 ( f ^ F , f 0 ) ≤ C [ log ( 4 n δ ) ( r n , d + μ n L 2 + σ 2 log ( 4 / δ ) n ) + L 2 ( log ( 4 n / δ ) n ) 2 / d ] ) ≤ δ . (43) \mathbb{P}\left(\ell_{\mathbb{P}}^2(\widehat{f}_F,f_0)\le C\left[\log\left(\frac{4n}{\delta}\right)\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2\log(4/\delta)}{n}\right)+L^2\left(\frac{\log(4n/\delta)}{n}\right)^{2/d}\right]\right)\le\delta. \tag*{(43)} P ( ℓ P 2 ( f F , f 0 ) ≤ C [ log ( δ 4 n ) ( r n , d + μ n L 2 + n σ 2 log ( 4/ δ ) ) + L 2 ( n log ( 4 n / δ ) ) 2/ d ] ) ≤ δ . (43)
Proof. By taking expectation over sample points X X X in (40) gives us that
E f 0 ∥ θ F − θ 0 ∥ n 2 ≤ C ( r n , d + μ n L 2 + σ 2 n ) , (44) \mathbb{E}_{f_0}\|\theta_F-\theta^0\|_n^2\le C\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2}{n}\right), \tag*{(44)} E f 0 ∥ θ F − θ 0 ∥ n 2 ≤ C ( r n , d + μ n L 2 + n σ 2 ) , (44)
Lemma A.3 gives us that
ℓ P 2 ( f ^ F , f 0 ) ≤ 2 n p max ∥ θ F − θ 0 ∥ n 2 + 8 L 2 ρ n 2 . \ell_{\mathbb{P}}^2(\widehat{f}_F,f_0)\le2np_{\max}\|\theta_F-\theta^0\|_n^2+8L^2\rho_n^2. ℓ P 2 ( f F , f 0 ) ≤ 2 n p m a x ∥ θ F − θ 0 ∥ n 2 + 8 L 2 ρ n 2 .
We apply Lemma A.1 with failure probability δ n \delta_n δ n and denote its event by V n \mathcal{V}_n V n . Equation (41) yields
n p max ≤ C log n , ρ n 2 ≤ C ( log n / n ) 2 / d , P ( V n c ) ≤ δ n . (45) np_{\max}\le C\log n,\qquad\rho_n^2\le C(\log n/n)^{2/d},\qquad\mathbb{P}(\mathcal{V}_n^c)\le\delta_n. \tag*{(45)} n p m a x ≤ C log n , ρ n 2 ≤ C ( log n / n ) 2/ d , P ( V n c ) ≤ δ n . (45)
Both p max p_{\max} p m a x and V n \mathcal{V}_n V n have no dependence on X X X , so conditioning on X X X and using (40) gives
E [ ℓ P 2 ( f ^ F , f 0 ) ] = E [ ℓ P 2 ( f ^ F , f 0 ) 1 V n ] + E [ ℓ P 2 ( f ^ F , f 0 ) 1 V n c ] ≤ 2 E [ n p max 1 V n E [ ∥ θ F − θ 0 ∥ n 2 ] ] + 8 L 2 E [ ρ n 2 1 V n ] + E [ ℓ P 2 ( f ^ F , f 0 ) 1 V n c ] ≤ C [ ( log n ) ( r n , d + μ n L 2 + σ 2 n ) + L 2 ( log n / n ) 2 / d ] + E [ ℓ P 2 ( f ^ F , f 0 ) 1 V n c ] . \begin{aligned}
\mathbb{E}\left[\ell_{\mathbb{P}}^2(\widehat{f}_F,f_0)\right]
&=\mathbb{E}\left[\ell_{\mathbb{P}}^2(\widehat{f}_F,f_0)1_{\mathcal{V}_n}\right]+\mathbb{E}\left[\ell_{\mathbb{P}}^2(\widehat{f}_F,f_0)1_{\mathcal{V}_n^c}\right]\\
&\le2\mathbb{E}\left[np_{\max}1_{\mathcal{V}_n}\mathbb{E}[\|\theta_F-\theta^0\|_n^2]\right]+8L^2\mathbb{E}[\rho_n^2 1_{\mathcal{V}_n}]+\mathbb{E}\left[\ell_{\mathbb{P}}^2(\widehat{f}_F,f_0)1_{\mathcal{V}_n^c}\right]\\
&\le C\left[(\log n)\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2}{n}\right)+L^2(\log n/n)^{2/d}\right]+\mathbb{E}\left[\ell_{\mathbb{P}}^2(\widehat{f}_F,f_0)1_{\mathcal{V}_n^c}\right].
\end{aligned} E [ ℓ P 2 ( f F , f 0 ) ] = E [ ℓ P 2 ( f F , f 0 ) 1 V n ] + E [ ℓ P 2 ( f F , f 0 ) 1 V n c ] ≤ 2 E [ n p m a x 1 V n E [ ∥ θ F − θ 0 ∥ n 2 ] ] + 8 L 2 E [ ρ n 2 1 V n ] + E [ ℓ P 2 ( f F , f 0 ) 1 V n c ] ≤ C [ ( log n ) ( r n , d + μ n L 2 + n σ 2 ) + L 2 ( log n / n ) 2/ d ] + E [ ℓ P 2 ( f F , f 0 ) 1 V n c ] .
On V n c \mathcal{V}_n^c V n c , the ℓ P 2 ( f ^ , f ^ 0 ) ≤ ( B f + B ) 2 \ell_{\mathbb{P}}^2(\widehat{f},\widehat{f}_0)\le(B_f+B)^2 ℓ P 2 ( f , f 0 ) ≤ ( B f + B ) 2 by Lemma A.5. The second term is therefore at most ( B f + B ) 2 δ n (B_f+B)^2\delta_n ( B f + B ) 2 δ n . Since δ n ≤ r n , d \delta_n\le r_{n,d} δ n ≤ r n , d eventually, this contribution is absorbed into (42).
For the confidence bound, we apply Corollary A.13 and Lemma 17 with failure probability of δ 2 \frac{\delta}{2} 2 δ . Intersecting both events,
∥ θ F − θ 0 ∥ n 2 ≤ C ( r n , d + μ n L 2 + σ 2 log ( 4 / δ ) n ) , n p max ≤ C log ( 4 n / δ ) , ρ n 2 ≤ C ( log ( 4 n / δ ) n ) 2 / d . \|\theta_F-\theta^0\|_n^2\le C\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2\log(4/\delta)}{n}\right),\qquad np_{\max}\le C\log(4n/\delta),\qquad\rho_n^2\le C\left(\frac{\log(4n/\delta)}{n}\right)^{2/d}. ∥ θ F − θ 0 ∥ n 2 ≤ C ( r n , d + μ n L 2 + n σ 2 log ( 4/ δ ) ) , n p m a x ≤ C log ( 4 n / δ ) , ρ n 2 ≤ C ( n log ( 4 n / δ ) ) 2/ d .
with probability 1 − δ 1-\delta 1 − δ . Substitutions prove (43).
With Assumption (2.3), we have that μ n L 2 ≤ C μ r n , d \mu_nL^2\le C_\mu r_{n,d} μ n L 2 ≤ C μ r n , d . In each fixed dimension, log n / n ≲ r n , d \log n/n\lesssim r_{n,d} log n / n ≲ r n , d , so r n , d + μ n L 2 + σ 2 log n n ≤ C r n , d r_{n,d}+\mu_nL^2+\frac{\sigma^2\log n}{n}\le Cr_{n,d} r n , d + μ n L 2 + n σ 2 l o g n ≤ C r n , d . Standard calculations show that ( log n n ) 2 / d ≤ r n , d log n \left(\frac{\log n}{n}\right)^{2/d}\le r_{n,d}\log n ( n l o g n ) 2/ d ≤ r n , d log n . Thus
( log n ) ( r n , d + μ n L 2 + σ 2 log n n ) + L 2 ( log n n ) 2 / d ≤ C r n , d log n , sup f 0 ∈ F B , L ( Ω ) E f 0 ℓ P 2 ( f ^ F , f 0 ) ≤ C r n , d log n . (46) (\log n)\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2\log n}{n}\right)+L^2\left(\frac{\log n}{n}\right)^{2/d}\le Cr_{n,d}\log n,\qquad\sup_{f_0\in\mathcal{F}_{B,L}(\Omega)}\mathbb{E}_{f_0}\ell_{\mathbb{P}}^2(\widehat{f}_F,f_0)\le Cr_{n,d}\log n. \tag*{(46)} ( log n ) ( r n , d + μ n L 2 + n σ 2 log n ) + L 2 ( n log n ) 2/ d ≤ C r n , d log n , f 0 ∈ F B , L ( Ω ) sup E f 0 ℓ P 2 ( f F , f 0 ) ≤ C r n , d log n . (46)
General convex functions
We now compare the KNN and full estimators fitted to the same sample points X X X . The proof first shows that short KNN constraints control every omitted inequality up to a small residual. We use these residual bounds to construct a full-feasible comparison point, and then apply the optimality conditions of the two problems to bound the movement of the fitted values. The final step accounts for the possibility of KNN interpolation defect and subsequently transfers the comparison to population risk.
We retain δ n = r n , d 2 \delta_n = r_{n,d}^{2} δ n = r n , d 2 and define the notation
ℓ n = log ( 8 n 2 δ n ) , v n , K = ( n K ) 1 / d ( ℓ n K ) 1 / ( d − 1 ) . (47) \ell_n = \log\left(\frac{8n^2}{\delta_n}\right), \quad v_{n,K} = \left(\frac{n}{K}\right)^{1/d}\left(\frac{\ell_n}{K}\right)^{1/(d-1)}. \tag*{(47)} ℓ n = log ( δ n 8 n 2 ) , v n , K = ( K n ) 1/ d ( K ℓ n ) 1/ ( d − 1 ) . (47)
The quantity a n a_n a n is the empirical-error scale from Appendix A, whereas intuitively v n , K v_{n,K} v n , K aims to measure the error accumulated along local paths. For fixed d d d , we have ℓ n ≍ log n \ell_n \asymp\log n ℓ n ≍ log n and, under the Assumption 2.3,
( r n , d + μ n L 2 + σ 2 n ) 1 / 2 , ≤ C r n , d 1 / 2 . \left(r_{n,d}+\mu_nL^2+\frac{\sigma^2}{n}\right)^{1/2}, \leq Cr_{n,d}^{1/2}. ( r n , d + μ n L 2 + n σ 2 ) 1/2 , ≤ C r n , d 1/2 .
We prove a more general bound.
Theorem B.1. Under the setup of Section 2 and Assumption 2.3, there are constants C 0 , c 0 , C > 0 C_0,c_0,C>0 C 0 , c 0 , C > 0 such that, for all sufficiently large n n n and every deterministic integer K K K satisfying C 0 ℓ n ≤ K ≤ c 0 n C_0\ell_n \leq K \leq c_0n C 0 ℓ n ≤ K ≤ c 0 n ,
sup f 0 ∈ F B , L ( Ω ) E f 0 ℓ 2 ( f ^ K , f ^ F ) ≤ C [ ℓ n ( v n , K ( r n , d + μ n L 2 + σ 2 n ) 1 / 2 + v n , K 2 ) + ( ℓ n n ) 2 / d + δ n ] . (48) \sup_{f_0\in\mathcal{F}_{B,L}(\Omega)}\mathbb{E}_{f_0}\ell^2(\widehat{f}_K,\widehat{f}_F) \leq C\left[\ell_n\left(v_{n,K}\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2}{n}\right)^{1/2}+v_{n,K}^{2}\right)+\left(\frac{\ell_n}{n}\right)^{2/d}+\delta_n\right]. \tag*{(48)} f 0 ∈ F B , L ( Ω ) sup E f 0 ℓ 2 ( f K , f F ) ≤ C [ ℓ n ( v n , K ( r n , d + μ n L 2 + n σ 2 ) 1/2 + v n , K 2 ) + ( n ℓ n ) 2/ d + δ n ] . (48)
We then appropriately choose K n K_n K n so that the right-hand side is no larger than the full-estimator benchmark.
Directional coverage by short KNN edges
In order for a KNN chain to be useful between two far points X i X_i X i and X j X_j X j , we must intuitively satisfy two conditions: (i) its edges must be short enough to be retained by the KNN, and (ii) each step must point approximately toward the target. Lemma A.6 allows us to handle the first requirement. For the second conditions, we show that a thin sector pointing toward any other point in Ω \Omega Ω has enough probability mass to contain an observation.
Lemma B.2. For 0 < h ≤ D Ω 0<h\leq D_\Omega 0 < h ≤ D Ω , 0 < α ≤ 1 / 4 0<\alpha\leq1/4 0 < α ≤ 1/4 , and x , y ∈ Ω x,y\in\Omega x , y ∈ Ω with ∥ y − x ∥ 2 > h \lVert y-x\rVert_2>h ∥ y − x ∥ 2 > h , we set u = ( y − x ) / ∥ y − x ∥ 2 u=(y-x)/\lVert y-x\rVert_2 u = ( y − x ) / ∥ y − x ∥ 2 and
S h , α ( x , u ) = { z ∈ Ω : h / 4 ≤ ∥ z − x ∥ 2 ≤ h / 2 , ∥ z − x ∥ z − x ∥ 2 − u ∥ 2 ≤ α } . S_{h,\alpha}(x,u)=\left\{z\in\Omega:h/4\leq\lVert z-x\rVert_2\leq h/2,\ \left\lVert\frac{z-x}{\lVert z-x\rVert_2}-u\right\rVert_2\leq\alpha\right\}. S h , α ( x , u ) = { z ∈ Ω : h /4 ≤ ∥ z − x ∥ 2 ≤ h /2 , ∥ z − x ∥ 2 z − x − u 2 ≤ α } . There is a constant c Ω > 0 c_\Omega>0 c Ω > 0 such that
P ( S h , α ( x , u ) ) ≥ c Ω h d α d − 1 . (49) \mathbb{P}(S_{h,\alpha}(x,u))\geq c_\Omega h^d\alpha^{d-1}. \tag*{(49)} P ( S h , α ( x , u )) ≥ c Ω h d α d − 1 . (49)
Proof. We construct a cylinder contained within S h , α ( x , u ) S_{h,\alpha}(x,u) S h , α ( x , u ) look at its volume. Consider an interior ball B ( x ∗ , r ∗ ) ⊆ Ω B(x_*,r_*)\subseteq\Omega B ( x ∗ , r ∗ ) ⊆ Ω . For t ∈ [ h / 3 , 5 h / 12 ] t\in[h/3,5h/12] t ∈ [ h /3 , 5 h /12 ] , the point z t = x + t u z_t=x+tu z t = x + t u lies on [ x , y ] [x,y] [ x , y ] . By setting λ = h α / ( 64 D Ω ) \lambda=h\alpha/(64D_\Omega) λ = h α / ( 64 D Ω ) . We consider all points w t + v w_t+v w t + v with v ⊥ u v\perp u v ⊥ u and ∥ v ∥ 2 ≤ λ r ∗ \lVert v\rVert_2\leq\lambda r_* ∥ v ∥ 2 ≤ λ r ∗ . Each such point belongs to Ω \Omega Ω , because
w t + v = ( 1 − λ ) z t + λ ( x ∗ + v λ ) . w_t+v=(1-\lambda)z_t+\lambda\left(x_*+\frac{v}{\lambda}\right). w t + v = ( 1 − λ ) z t + λ ( x ∗ + λ v ) .
These points form a thin cylinder and it can be shown that lies in the desired sector. Since r ∗ ≤ D Ω r_*\leq D_\Omega r ∗ ≤ D Ω ,
∥ w t + v − z t ∥ 2 = ∥ λ ( x ∗ − z t ) + v ∥ 2 ≤ λ ∥ x ∗ − z t ∥ 2 + ∥ v ∥ 2 ≤ λ ( D Ω + r ∗ ) ≤ h α 32 . \lVert w_t+v-z_t\rVert_2=\lVert\lambda(x_*-z_t)+v\rVert_2
\leq\lambda\lVert x_*-z_t\rVert_2+\lVert v\rVert_2
\leq\lambda(D_\Omega+r_*)\leq\frac{h\alpha}{32}. ∥ w t + v − z t ∥ 2 = ∥ λ ( x ∗ − z t ) + v ∥ 2 ≤ λ ∥ x ∗ − z t ∥ 2 + ∥ v ∥ 2 ≤ λ ( D Ω + r ∗ ) ≤ 32 h α .
Thus every cylinder point is within distance h α / 32 h\alpha/32 h α /32 of the corresponding point z t z_t z t on the original segment.
Because ∥ z t − x ∥ 2 = t \lVert z_t-x\rVert_2=t ∥ z t − x ∥ 2 = t , the triangle inequality gives
t − h α 32 ≤ ∥ w t + v − x ∥ 2 ≤ t + h α 32 . t-\frac{h\alpha}{32}\leq\lVert w_t+v-x\rVert_2\leq t+\frac{h\alpha}{32}. t − 32 h α ≤ ∥ w t + v − x ∥ 2 ≤ t + 32 h α .
The interval [ h / 3 , 5 h / 12 ] [h/3,5h/12] [ h /3 , 5 h /12 ] lies inside [ h / 4 , h / 2 ] [h/4,h/2] [ h /4 , h /2 ] with a margin of h / 12 h/12 h /12 at each end. Since h α / 32 ≤ h / 128 < h / 12 h\alpha/32\leq h/128<h/12 h α /32 ≤ h /128 < h /12 , it follows that
h 4 ≤ ∥ w t + v − x ∥ 2 ≤ h 2 . (50) \frac{h}{4}\leq\lVert w_t+v-x\rVert_2\leq\frac{h}{2}. \tag*{(50)} 4 h ≤ ∥ w t + v − x ∥ 2 ≤ 2 h . (50)
We apply this with a = w t + v − x a = w_t + v - x a = w t + v − x and b = z t − x = t u b = z_t - x = tu b = z t − x = t u . Since t ≥ h / 3 t \ge h/3 t ≥ h /3 , we obtain
∥ w t + v − x ∥ w t + v − x ∥ 2 − u ∥ 2 ≤ 2 ∥ w t + v − z t ∥ 2 t ≤ 2 ( h α / 32 ) h / 3 = 3 α 16 ≤ α . \left\| \frac{w_t + v - x}{\|w_t + v - x\|_2} - u \right\|_2 \le\frac{2\|w_t + v - z_t\|_2}{t} \le\frac{2(h\alpha/32)}{h/3} = \frac{3\alpha}{16} \le\alpha. ∥ w t + v − x ∥ 2 w t + v − x − u 2 ≤ t 2∥ w t + v − z t ∥ 2 ≤ h /3 2 ( h α /32 ) = 16 3 α ≤ α .
Thus the cylinder lies in S h , α ( x , u ) S_{h,\alpha}(x,u) S h , α ( x , u ) which has length ( 1 − λ ) h / 12 ≥ h / 24 (1-\lambda)h/12 \ge h/24 ( 1 − λ ) h /12 ≥ h /24 and cross-sectional radius λ r ∗ = h α r ∗ / ( 64 D Ω ) \lambda r_* = h\alpha r_*/(64D_\Omega) λ r ∗ = h α r ∗ / ( 64 D Ω ) . Its volume is therefore at least a fixed positive multiple of h ( h α ) d − 1 h(h\alpha)^{d-1} h ( h α ) d − 1 , giving us our result. □ \square □
We choose the values of
h n = c h ( K / n ) 1 / d , α n = C α ( ℓ n / K ) 1 / ( d − 1 ) . (51) h_n = c_h(K/n)^{1/d}, \qquad\alpha_n = C_\alpha(\ell_n/K)^{1/(d-1)}. \tag*{(51)} h n = c h ( K / n ) 1/ d , α n = C α ( ℓ n / K ) 1/ ( d − 1 ) . (51)
with appropriate values of c h c_h c h and C α C_\alpha C α to apply our result on
Lemma B.3. There exists constants c h , C α , C 0 , c 0 c_h,C_\alpha,C_0,c_0 c h , C α , C 0 , c 0 so that, for all sufficiently large n n n and C 0 ℓ n ≤ K ≤ c 0 n C_0\ell_n \le K \le c_0n C 0 ℓ n ≤ K ≤ c 0 n , there exists G n , K \mathcal{G}_{n,K} G n , K with P ( G n , K c ) ≤ δ n \mathbb{P}(\mathcal{G}_{n,K}^c) \le\delta_n P ( G n , K c ) ≤ δ n and every edge of length at most h n h_n h n is retained in C E K C_E^K C E K , and every ordered pair ( X j , X i ) (X_j,X_i) ( X j , X i ) with distance greater than h n h_n h n has another observation in S h n , α n ( X j , ( X i − X j ) / ∥ X i − X j ∥ 2 ) S_{h_n,\alpha_n}(X_j,(X_i-X_j)/\|X_i-X_j\|_2) S h n , α n ( X j , ( X i − X j ) /∥ X i − X j ∥ 2 ) . On G n , K \mathcal{G}_{n,K} G n , K , n p max ≤ C ℓ n np_{\max} \le C\ell_n n p m a x ≤ C ℓ n and ρ n 2 ≤ C ( ℓ n / n ) 2 / d \rho_n^2 \le C(\ell_n/n)^{2/d} ρ n 2 ≤ C ( ℓ n / n ) 2/ d .
Proof. By applying Lemma A.2 at radius h n h_n h n with probability δ n / 4 \delta_n/4 δ n /4 which gives us that { i ≠ j : ∥ X i − X j ∥ 2 ≤ h n } \{i \ne j : \|X_i-X_j\|_2 \le h_n\} { i = j : ∥ X i − X j ∥ 2 ≤ h n } is less than C N ( n h n d + ℓ n ) = C N c h d K + C N ℓ n C_N(nh_n^d+\ell_n)=C_Nc_h^dK+C_N\ell_n C N ( n h n d + ℓ n ) = C N c h d K + C N ℓ n . By choosing c h c_h c h so that C N c h d ≤ 1 / 2 C_Nc_h^d \le1/2 C N c h d ≤ 1/2 , and choosing C 0 ≥ 2 C N ⟹ ℓ n ≤ K C 0 ≤ K 2 C N C_0 \ge2C_N \implies\ell_n \le\frac{K}{C_0} \le\frac{K}{2C_N} C 0 ≥ 2 C N ⟹ ℓ n ≤ C 0 K ≤ 2 C N K , allowing the local count to be bounded by K K K at every source with probability 1 − δ / 4 1-\delta/4 1 − δ /4 . Therefore every observation within distance h n h_n h n belongs to that source’s K K K nearest neighbors. Applying the same conclusion at the other endpoint retains both directions of each such edge.
Now, suppose that we have ( X j , X i ) (X_j,X_i) ( X j , X i ) with ∥ X j − X i ∥ 2 > h n \|X_j-X_i\|_2 > h_n ∥ X j − X i ∥ 2 > h n . Lemma B.2 bounds the probability that the remaining n − 2 n-2 n − 2 observations miss the sector by exp ( − c Ω ( n − 2 ) h n d α n d − 1 ) \exp(-c_\Omega(n-2)h_n^d\alpha_n^{d-1}) exp ( − c Ω ( n − 2 ) h n d α n d − 1 ) . Our choices for h n h_n h n and α n \alpha_n α n make n h n d α n d − 1 = c h d c α d − 1 ℓ n nh_n^d\alpha_n^{d-1}=c_h^dc_\alpha^{d-1}\ell_n n h n d α n d − 1 = c h d c α d − 1 ℓ n . Choosing C α C_\alpha C α large enough that c Ω c h d C α d − 1 / 2 ≥ 1 c_\Omega c_h^d C_\alpha^{d-1}/2 \ge1 c Ω c h d C α d − 1 /2 ≥ 1 and using that n − 2 ≥ n / 2 n-2 \ge n/2 n − 2 ≥ n /2 for n ≥ 4 n \ge4 n ≥ 4 , the preceding probability is then at most e − ℓ n e^{-\ell_n} e − ℓ n . A union bound over at most n 2 n^2 n 2 ordered pairs gives that the probability any such sector is empty has probability n 2 e − ℓ n = δ n 8 n^2e^{-\ell_n}=\frac{\delta_n}{8} n 2 e − ℓ n = 8 δ n .
To apply Lemma A.2 and Lemma B.2, we need to ensure α n ≤ 1 4 \alpha_n \le\frac14 α n ≤ 4 1 and h n ≤ D Ω h_n \le D_\Omega h n ≤ D Ω . We further increase C 0 C_0 C 0 so that C 0 ≥ ( 4 C α ) d − 1 C_0 \ge(4C_\alpha)^{d-1} C 0 ≥ ( 4 C α ) d − 1 , which ensures α n ≤ 1 / 4 \alpha_n \le1/4 α n ≤ 1/4 . We choose c 0 c_0 c 0 small enough that h n = c h c 0 1 / d ≤ D Ω h_n=c_hc_0^{1/d}\le D_\Omega h n = c h c 0 1/ d ≤ D Ω . These choices make all preceding estimates applicable.
Finally, Lemma A.1 with probability δ n / 4 \delta_n/4 δ n /4 gives the desired remaining properties. Intersecting its event with the count and occupancy events above proves the lemma through a union bound. □ \square □
On the event G n , K \mathcal{G}_{n,K} G n , K , Lemma B.3 allows us to repeatedly take a short step pointing toward a target observation. The next lemma controls the number of steps and the amount by which consecutive directions turn.s
Lemma B.4. On G n , K \mathcal{G}_{n,K} G n , K , every pair at distance R = ∥ X i − X j ∥ 2 > h n R=\|X_i-X_j\|_2>h_n R = ∥ X i − X j ∥ 2 > h n can be joined by a path x 0 = X j , x 1 , … , x N = X i x_0=X_j,x_1,\ldots,x_N=X_i x 0 = X j , x 1 , … , x N = X i of retained bidirectional edges. With s k = ∥ x k + 1 − x k ∥ 2 s_k=\|x_{k+1}-x_k\|_2 s k = ∥ x k + 1 − x k ∥ 2 and u k = ( x k + 1 − x k ) / s k u_k=(x_{k+1}-x_k)/s_k u k = ( x k + 1 − x k ) / s k , we have
N ≤ C R / h n , ∑ k = 0 N − 1 s k ≤ C R , (52) N \le CR/h_n,\qquad\sum_{k=0}^{N-1}s_k \le CR, \tag*{(52)} N ≤ C R / h n , k = 0 ∑ N − 1 s k ≤ C R , (52) with
∥ u k + 1 − u k ∥ 2 ≤ C α n , 0 ≤ k ≤ N − 2. (53) \|u_{k+1}-u_k\|_2 \le C\alpha_n,\qquad0 \le k \le N-2. \tag*{(53)} ∥ u k + 1 − u k ∥ 2 ≤ C α n , 0 ≤ k ≤ N − 2. (53) Proof. We start at x 0 = X j x_0=X_j x 0 = X j . While the remaining distance to X i X_i X i is greater than h n h_n h n , we can choose an observation in the S h n , α n ( X j , ( X i − X j ) / ∥ X i − X j ∥ 2 ) S_{h_n,\alpha_n}(X_j,(X_i-X_j)/\|X_i-X_j\|_2) S h n , α n ( X j , ( X i − X j ) /∥ X i − X j ∥ 2 ) from Lemma B.3. Once the remaining distance is at most h n h_n h n , we take the final directed edge. For a given step, we write D k = ∥ X i − x k ∥ 2 D_k=\|X_i-x_k\|_2 D k = ∥ X i − x k ∥ 2 and e k = ( X i − x k ) / D k e_k=(X_i-x_k)/D_k e k = ( X i − x k ) / D k . The selected edge satisfies h n / 4 ≤ s k ≤ h n / 2 h_n/4 \le s_k \le h_n/2 h n /4 ≤ s k ≤ h n /2 and ∥ u k − e k ∥ 2 ≤ α n \|u_k-e_k\|_2 \le\alpha_n ∥ u k − e k ∥ 2 ≤ α n . Hence
D k + 1 = ∥ D k e k − s k u k ∥ 2 ≤ D k − s k + s k ∥ e k − u k ∥ 2 ≤ D k − ( 1 − α n ) s k . D_{k+1}=\|D_ke_k-s_ku_k\|_2
\le D_k-s_k+s_k\|e_k-u_k\|_2
\le D_k-(1-\alpha_n)s_k. D k + 1 = ∥ D k e k − s k u k ∥ 2 ≤ D k − s k + s k ∥ e k − u k ∥ 2 ≤ D k − ( 1 − α n ) s k .
implying that D k − D k + 1 ≥ ( 1 − α n ) s k ≥ 3 h n 16 D_k-D_{k+1}\ge(1-\alpha_n)s_k\ge\frac{3h_n}{16} D k − D k + 1 ≥ ( 1 − α n ) s k ≥ 16 3 h n since α n ≤ 1 4 \alpha_n\le\frac{1}{4} α n ≤ 4 1 and s k ≥ h n / 4 s_k\ge h_n/4 s k ≥ h n /4 . So, Each nonfinal step decreases the remaining distance by at least 3 h n / 16 3h_n/16 3 h n /16 , proving termination and N ≤ C R / h n N\le CR/h_n N ≤ C R / h n . Additionally, s k ≤ D k − D k + 1 1 − α n s_k\le\frac{D_k-D_{k+1}}{1-\alpha_n} s k ≤ 1 − α n D k − D k + 1 implying that
s N − 1 + ∑ k = 1 N − 2 s k ≤ s N − 1 + 1 1 − α n ∑ k = 0 N − 2 ( D k − D k + 1 ) = s N − 1 D 0 − D N − 1 1 − α n ≤ s N − 1 + R 1 − α n ≤ s N − 1 + 4 3 R ≤ 7 3 R s_{N-1}+\sum_{k=1}^{N-2}s_k\le s_{N-1}+\frac{1}{1-\alpha_n}\sum_{k=0}^{N-2}(D_k-D_{k+1})=s_{N-1}\frac{D_0-D_{N-1}}{1-\alpha_n}\le s_{N-1}+\frac{R}{1-\alpha_n}\le s_{N-1}+\frac{4}{3}R\le\frac{7}{3}R s N − 1 + k = 1 ∑ N − 2 s k ≤ s N − 1 + 1 − α n 1 k = 0 ∑ N − 2 ( D k − D k + 1 ) = s N − 1 1 − α n D 0 − D N − 1 ≤ s N − 1 + 1 − α n R ≤ s N − 1 + 3 4 R ≤ 3 7 R
To control direction changes, we apply the inequality ∥ a ∥ a ∥ 2 − b ∥ b ∥ 2 ∥ 2 ≤ 2 ∥ a − b ∥ 2 ∥ b ∥ 2 \left\|\frac{a}{\lVert a\rVert_2}-\frac{b}{\lVert b\rVert_2}\right\|_2\le2\frac{\lVert a-b\rVert_2}{\lVert b\rVert_2} ∥ a ∥ 2 a − ∥ b ∥ 2 b 2 ≤ 2 ∥ b ∥ 2 ∥ a − b ∥ 2 to D k e k − s k u k D_ke_k-s_ku_k D k e k − s k u k and ( D k − s k ) e k (D_k-s_k)e_k ( D k − s k ) e k . Since s k < D k / 2 s_k<D_k/2 s k < D k /2 , we obtain
∥ e k + 1 − e k ∥ 2 ≤ 2 s k ∥ u k − e k ∥ 2 D k − s k ≤ 2 α n . \lVert e_{k+1}-e_k\rVert_2\le\frac{2s_k\lVert u_k-e_k\rVert_2}{D_k-s_k}\le2\alpha_n. ∥ e k + 1 − e k ∥ 2 ≤ D k − s k 2 s k ∥ u k − e k ∥ 2 ≤ 2 α n .
A nonfinal edge direction differs from the current target direction by at most α n \alpha_n α n , and the final edge has exactly the target direction. So, we have that
∥ u k + 1 − u k ∥ 2 ≤ ∥ u k + 1 − e k + 1 ∥ 2 + ∥ e k + 1 − e k ∥ 2 + ∥ e k − u k ∥ 2 ≤ α n + 2 α n + α n ≤ 4 α n \lVert u_{k+1}-u_k\rVert_2\le\lVert u_{k+1}-e_{k+1}\rVert_2+\lVert e_{k+1}-e_k\rVert_2+\lVert e_k-u_k\rVert_2\le\alpha_n+2\alpha_n+\alpha_n\le4\alpha_n ∥ u k + 1 − u k ∥ 2 ≤ ∥ u k + 1 − e k + 1 ∥ 2 + ∥ e k + 1 − e k ∥ 2 + ∥ e k − u k ∥ 2 ≤ α n + 2 α n + α n ≤ 4 α n
Every edge has length at most h n h_n h n , so both of its directed constraints are retained.
As our path of chained constraints is only approximately straight, we develop a bound for the residual value of the missing constraint.
Lemma B.5. On G n , K G_{n,K} G n , K , every ( θ , G ) ∈ C E K (\theta,G)\in\mathcal{C}_{E_K} ( θ , G ) ∈ C E K satisfies, for all pairs,
r j i ( θ , G ) ≥ − κ n , K ∥ X i − X j ∥ 2 2 , κ n , K = C L α n h n ≤ C v n , K . (54) r_{ji}(\theta,G)\ge-\kappa_{n,K}\lVert X_i-X_j\rVert_2^2,\qquad\kappa_{n,K}=\frac{CL\alpha_n}{h_n}\le Cv_{n,K}. \tag*{(54)} r j i ( θ , G ) ≥ − κ n , K ∥ X i − X j ∥ 2 2 , κ n , K = h n C L α n ≤ C v n , K . (54)
Proof. Retained constraints already have nonnegative residuals. For an omitted pair, R = ∥ X i − X j ∥ 2 > h n R=\lVert X_i-X_j\rVert_2>h_n R = ∥ X i − X j ∥ 2 > h n , and we use the path from Lemma B.4. We write ϑ k \vartheta_k ϑ k and γ k \gamma_k γ k for the KNN fitted values and slopes at point x k x_k x k . We have the point the KNN solution will maintain the residual inequality from x k x_k x k to x k + 1 x_{k+1} x k + 1 and from x k + 1 x_{k+1} x k + 1 to x k x_k x k . Therefore, ϑ k + 1 ≥ ϑ k + γ k T ( x k + 1 − x k ) \vartheta_{k+1}\ge\vartheta_k+\gamma_k^{\mathsf{T}}(x_{k+1}-x_k) ϑ k + 1 ≥ ϑ k + γ k T ( x k + 1 − x k ) which implies that
ϑ k + 1 − ϑ k ∥ x k + 1 − x k ∥ 2 ≥ γ k T ( x k + 1 − x k ) ∥ x k + 1 − x k ∥ 2 . \frac{\vartheta_{k+1}-\vartheta_k}{\lVert x_{k+1}-x_k\rVert_2}\ge\gamma_k^{\mathsf{T}}\frac{(x_{k+1}-x_k)}{\lVert x_{k+1}-x_k\rVert_2}. ∥ x k + 1 − x k ∥ 2 ϑ k + 1 − ϑ k ≥ γ k T ∥ x k + 1 − x k ∥ 2 ( x k + 1 − x k ) .
Defining s k s_k s k and u k u_k u k just as in Lemma 51 and also performing simular calculations between x k + 1 x_{k+1} x k + 1 and x k x_k x k , we get
γ k T u k ≤ ϑ k + 1 − ϑ k s k ≤ γ k + 1 T u k . (55) \gamma_k^{\mathsf{T}}u_k\le\frac{\vartheta_{k+1}-\vartheta_k}{s_k}\le\gamma_{k+1}^{\mathsf{T}}u_k. \tag*{(55)} γ k T u k ≤ s k ϑ k + 1 − ϑ k ≤ γ k + 1 T u k . (55)
In particular, ( γ k + 1 − γ k ) T u k ≥ 0 (\gamma_{k+1}-\gamma_k)^{\mathsf{T}}u_k\ge0 ( γ k + 1 − γ k ) T u k ≥ 0 .
We define b k = ( γ k − γ 0 ) T u k b_k=(\gamma_k-\gamma_0)^{\mathsf{T}}u_k b k = ( γ k − γ 0 ) T u k , so b 0 = 0 b_0=0 b 0 = 0 . For consecutive edge directions,
b k + 1 − b k = ( γ k + 1 − γ k ) T u k + ( γ k + 1 − γ 0 ) T ( u k + 1 − u k ) ≥ − 2 L ∥ u k + 1 − u k ∥ 2 ≥ − C L α n . b_{k+1}-b_k=(\gamma_{k+1}-\gamma_k)^{\mathsf{T}}u_k+(\gamma_{k+1}-\gamma_0)^{\mathsf{T}}(u_{k+1}-u_k)
\ge-2L\lVert u_{k+1}-u_k\rVert_2\ge-CL\alpha_n. b k + 1 − b k = ( γ k + 1 − γ k ) T u k + ( γ k + 1 − γ 0 ) T ( u k + 1 − u k ) ≥ − 2 L ∥ u k + 1 − u k ∥ 2 ≥ − C L α n .
Thus b k ≥ − C L k α n b_k\ge-CLk\alpha_n b k ≥ − C L k α n . We telescope the forward inequalities to obtain
r j i ( θ , G ) = ∑ k = 0 N − 1 [ ϑ k + 1 − ϑ k − γ 0 T ( x k + 1 − x k ) ] ≥ ∑ k = 0 N − 1 s k b k ≥ − C L α n ∑ k = 0 N − 1 k s k ≥ − C L α n N ∑ k = 0 N − 1 s k ≥ − C L α n h n R 2 . \begin{aligned}
r_{ji}(\theta,G)=\sum_{k=0}^{N-1}\left[\vartheta_{k+1}-\vartheta_k-\gamma_0^{\mathsf{T}}(x_{k+1}-x_k)\right] \\
&\ge\sum_{k=0}^{N-1}s_kb_k\ge-CL\alpha_n\sum_{k=0}^{N-1}ks_k \\
&\ge-CL\alpha_nN\sum_{k=0}^{N-1}s_k\ge-CL\frac{\alpha_n}{h_n}R^2.
\end{aligned} r j i ( θ , G ) = k = 0 ∑ N − 1 [ ϑ k + 1 − ϑ k − γ 0 T ( x k + 1 − x k ) ] ≥ k = 0 ∑ N − 1 s k b k ≥ − C L α n k = 0 ∑ N − 1 k s k ≥ − C L α n N k = 0 ∑ N − 1 s k ≥ − C L h n α n R 2 .
Substituting (50) gives α n / h n = ( C α / c h ) v n , K \alpha_n/h_n=(C_\alpha/c_h)v_{n,K} α n / h n = ( C α / c h ) v n , K , proving the claim.
Quadratic restoration of full feasibility
Having analyzed the residual failure of the KNN solution, we next turn a KNN-feasible pair into a full-feasible comparison point. The idea is that an appropriately small quadratic has supporting residuals proportional to squared distance, matching the form of the possible negative residuals in (54) . A single convex-combination weight can therefore properly offset all of them.
We choose x ∗ ∈ Ω x_\ast\in\Omega x ∗ ∈ Ω and define γ ∗ = min { B / D Ω 2 , L / ( 2 D Ω ) } \gamma_\ast= \min\{B/D_\Omega^2,L/(2D_\Omega)\} γ ∗ = min { B / D Ω 2 , L / ( 2 D Ω )} and q ( x ) = γ ∗ ∥ x − x ∗ ∥ 2 2 / 2 q(x)=\gamma_\ast\lVert x-x_\ast\rVert_2^2/2 q ( x ) = γ ∗ ∥ x − x ∗ ∥ 2 2 /2 . Its sampled values and slopes are θ ˉ i = q ( X i ) \bar{\theta}_i=q(X_i) θ ˉ i = q ( X i ) and g ˉ i = γ ∗ ( X i − x ∗ ) \bar{g}_i=\gamma_\ast(X_i-x_\ast) g ˉ i = γ ∗ ( X i − x ∗ ) . We write z ˉ = ( θ ˉ , G ˉ ) \bar{z}=(\bar{\theta},\bar{G}) z ˉ = ( θ ˉ , G ˉ ) and c ∗ = γ ∗ / 2 > 0 c_\ast=\gamma_\ast/2>0 c ∗ = γ ∗ /2 > 0 .
Lemma B.6. The pair z ˉ \bar{z} z ˉ is full-feasible and satisfies
r j i ( θ ˉ , G ˉ ) = c ∗ ∥ X i − X j ∥ 2 2 . (56) r_{ji}(\bar{\theta},\bar{G})=c_\ast\lVert X_i-X_j\rVert_2^2. \tag*{(56)} r j i ( θ ˉ , G ˉ ) = c ∗ ∥ X i − X j ∥ 2 2 . (56) For any z = ( θ , G ) ∈ C z=(\theta,G)\in C z = ( θ , G ) ∈ C satisfying r j i ( z ) ≥ − κ ∥ X i − X j ∥ 2 2 r_{ji}(z)\ge-\kappa\lVert X_i-X_j\rVert_2^2 r j i ( z ) ≥ − κ ∥ X i − X j ∥ 2 2 for all pairs, with κ ≥ 0 \kappa\ge0 κ ≥ 0 , the pair
z r e p = ( 1 − t ) z + t z ˉ , t = κ κ + c ∗ , (57) z^{\mathrm{rep}}=(1-t)z+t\bar{z},\qquad t=\frac{\kappa}{\kappa+c_\ast}, \tag*{(57)} z rep = ( 1 − t ) z + t z ˉ , t = κ + c ∗ κ , (57) then belongs to C E F C_{\mathrm{EF}} C EF .
Proof. The choice of γ ∗ \gamma_\ast γ ∗ gives 0 ≤ θ ˉ i ≤ γ ∗ D Ω 2 / 2 ≤ B / 2 0\le\bar{\theta}_i\le\gamma_\ast D_\Omega^2/2\le B/2 0 ≤ θ ˉ i ≤ γ ∗ D Ω 2 /2 ≤ B /2 and ∥ g ˉ i ∥ 2 ≤ γ ∗ D Ω ≤ L / 2 \lVert\bar{g}_i\rVert_2\le\gamma_\ast D_\Omega\le L/2 ∥ g ˉ i ∥ 2 ≤ γ ∗ D Ω ≤ L /2 . For a = X j − x ∗ a=X_j-x_\ast a = X j − x ∗ and Δ = X i − X j \Delta=X_i-X_j Δ = X i − X j , expansion gives
r j i ( θ ˉ , G ˉ ) = γ ∗ 2 ( ∥ a + Δ ∥ 2 2 − ∥ a ∥ 2 2 ) − γ ∗ a T Δ = γ ∗ 2 ∥ Δ ∥ 2 2 . \begin{aligned}
r_{ji}(\bar{\theta},\bar{G})&=\frac{\gamma_\ast}{2}\left(\lVert a+\Delta\rVert_2^2-\lVert a\rVert_2^2\right)-\gamma_\ast a^\mathsf{T}\Delta\\
&=\frac{\gamma_\ast}{2}\lVert\Delta\rVert_2^2.
\end{aligned} r j i ( θ ˉ , G ˉ ) = 2 γ ∗ ( ∥ a + Δ ∥ 2 2 − ∥ a ∥ 2 2 ) − γ ∗ a T Δ = 2 γ ∗ ∥ Δ ∥ 2 2 .
This proves (56) and feasibility of the comparison pair.
The common bound set C C C is convex, so z r e p z^{\mathrm{rep}} z rep satisfies the value and slope bounds. Each residual is linear in ( θ , G ) (\theta,G) ( θ , G ) , and hence
r j i ( z r e p ) = ( 1 − t ) r j i ( z ) + t r j i ( z ˉ ) ≥ [ − ( 1 − t ) κ + t c ∗ ] ∥ X i − X j ∥ 2 2 = 0. r_{ji}(z^{\mathrm{rep}})=(1-t)r_{ji}(z)+tr_{ji}(\bar{z})\ge[-(1-t)\kappa+tc_\ast]\lVert X_i-X_j\rVert_2^2=0. r j i ( z rep ) = ( 1 − t ) r j i ( z ) + t r j i ( z ˉ ) ≥ [ − ( 1 − t ) κ + t c ∗ ] ∥ X i − X j ∥ 2 2 = 0.
Therefore z r e p z^{\mathrm{rep}} z rep is feasible for the full problem.
We apply this lemma with κ = κ n , K \kappa=\kappa_{n,K} κ = κ n , K to the KNN optimizer. We use the restored pair as a feasible direction in the full problem’s optimality condition.
First-order optimality and fitted-value stability
For notational simplicity, we write z F = ( θ F , G F ) z_F=(\theta_F,G_F) z F = ( θ F , G F ) , z K = ( θ K , G K ) z_K=(\theta_K,G_K) z K = ( θ K , G K ) , z ˉ = ( θ ˉ , g ˉ ) \bar{z}=(\bar{\theta},\bar{g}) z ˉ = ( θ ˉ , g ˉ ) and H n = diag ( I n , μ n I n d ) H_n=\operatorname{diag}(I_n,\mu_n I_{nd}) H n = diag ( I n , μ n I n d ) after stacking the slopes.
Lemma B.7. On G n , K \mathcal{G}_{n,K} G n , K ,
∥ θ K − θ F ∥ 2 2 + μ n ∥ G K − G F ∥ F 2 ≤ κ n , K c ∗ S n , (58) \lVert\theta_K-\theta_F\rVert_2^2+\mu_n\lVert G_K-G_F\rVert_F^2\le\frac{\kappa_{n,K}}{c_\ast}S_n, \tag*{(58)} ∥ θ K − θ F ∥ 2 2 + μ n ∥ G K − G F ∥ F 2 ≤ c ∗ κ n , K S n , (58) where S n = ⟨ ∇ Φ n ( z F ) , z ˉ − z F ⟩ ≥ 0 S_n=\langle\nabla\Phi_n(z_F),\bar{z}-z_F\rangle\ge0 S n = ⟨ ∇ Φ n ( z F ) , z ˉ − z F ⟩ ≥ 0 .
Proof. We put Δ = z K − z F \Delta=z_K-z_F Δ = z K − z F . Because z F ∈ C E K z_F\in C_{E_K} z F ∈ C E K , KNN optimality gives ⟨ ∇ Φ n ( z K ) , z F − z K ⟩ ≥ 0 \langle\nabla\Phi_n(z_K),z_F-z_K\rangle\ge0 ⟨ ∇ Φ n ( z K ) , z F − z K ⟩ ≥ 0 . Using ∇ Φ n ( z K ) = ∇ Φ n ( z F ) + H n Δ \nabla\Phi_n(z_K)=\nabla\Phi_n(z_F)+H_n\Delta ∇ Φ n ( z K ) = ∇ Φ n ( z F ) + H n Δ , we obtain
Δ T H n Δ ≤ − ⟨ ∇ Φ n ( z F ) , Δ ⟩ . (59) \Delta^\mathsf{T}H_n\Delta\le-\langle\nabla\Phi_n(z_F),\Delta\rangle. \tag*{(59)} Δ T H n Δ ≤ − ⟨ ∇ Φ n ( z F ) , Δ ⟩ . (59)
The quadratic pair is feasible, so full optimality implies S n ≥ 0 S_n\ge0 S n ≥ 0 . The restored pair z K r e p = ( 1 − t ) z K + t z ˉ z_K^{\mathrm{rep}}=(1-t)z_K+t\bar{z} z K rep = ( 1 − t ) z K + t z ˉ is also full-feasible. Thus
0 ≤ ⟨ ∇ Φ n ( z F ) , z K r e p − z F ⟩ = ( 1 − t ) ⟨ ∇ Φ n ( z F ) , Δ ⟩ + t S n . \begin{aligned}
0&\le\langle\nabla\Phi_n(z_F),z_K^{\mathrm{rep}}-z_F\rangle\\
&=(1-t)\langle\nabla\Phi_n(z_F),\Delta\rangle+tS_n.
\end{aligned} 0 ≤ ⟨ ∇ Φ n ( z F ) , z K rep − z F ⟩ = ( 1 − t ) ⟨ ∇ Φ n ( z F ) , Δ ⟩ + t S n .
Since t / ( 1 − t ) = κ n , K / c ∗ t/(1-t)=\kappa_{n,K}/c_\ast t / ( 1 − t ) = κ n , K / c ∗ ,
− ⟨ ∇ Φ n ( z F ) , Δ ⟩ ≤ κ n , K c ∗ S n . -\langle\nabla\Phi_n(z_F),\Delta\rangle\le\frac{\kappa_{n,K}}{c_\ast}S_n. − ⟨ ∇ Φ n ( z F ) , Δ ⟩ ≤ c ∗ κ n , K S n .
Combining this with (59) proves our result.
The remaining comparison quantity S n S_n S n depends on the full optimizer, whose empirical error has already been bounded. We expand it around the true fitted vector to use that bound.
Lemma B.8 (Expected comparison cost). For all sufficiently large n n n ,
E f 0 S n ≤ C n ( r n , d + μ n L 2 + σ 2 n ) 1 / 2 . (60) \mathbb{E}_{f_0} S_n \le Cn\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2}{n}\right)^{1/2}. \tag*{(60)} E f 0 S n ≤ C n ( r n , d + μ n L 2 + n σ 2 ) 1/2 . (60) Consequently, on the event G n , K \mathcal{G}_{n,K} G n , K ,
E f 0 [ ∥ θ K − θ F ∥ n 2 1 G n , K ] ≤ C v n , K ( r n , d + μ n L 2 + σ 2 n ) 1 / 2 . (61) \mathbb{E}_{f_0}\left[\|\theta_K-\theta_F\|_n^2\mathbf{1}_{\mathcal{G}_{n,K}}\right]\le C v_{n,K}\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2}{n}\right)^{1/2}. \tag*{(61)} E f 0 [ ∥ θ K − θ F ∥ n 2 1 G n , K ] ≤ C v n , K ( r n , d + μ n L 2 + n σ 2 ) 1/2 . (61)
Proof. Recall that
S n = ⟨ ∇ Φ n ( θ F , G F ) , ( θ ˉ , G ˉ ) − ( θ F , G F ) ⟩ . S_n=\left\langle\nabla\Phi_n(\theta_F,G_F),(\bar{\theta},\bar{G})-(\theta_F,G_F)\right\rangle. S n = ⟨ ∇ Φ n ( θ F , G F ) , ( θ ˉ , G ˉ ) − ( θ F , G F ) ⟩ .
Since Y = θ 0 + ξ Y=\theta^0+\xi Y = θ 0 + ξ , we can expand this quantity as
S n = ( θ F − θ 0 − ξ ) T ( θ ˉ − θ F ) + μ n ⟨ G F , G ˉ − G F ⟩ = ( θ F − θ 0 ) T ( θ ˉ − θ 0 ) − ∥ θ F − θ 0 ∥ 2 2 − ξ T ( θ ˉ − θ 0 ) + ξ T ( θ F − θ 0 ) + μ n ⟨ G F , G ˉ − G F ⟩ . \begin{aligned}
S_n&=(\theta_F-\theta^0-\xi)^\mathsf{T}(\bar{\theta}-\theta_F)+\mu_n\langle G_F,\bar{G}-G_F\rangle\\
&=(\theta_F-\theta^0)^\mathsf{T}(\bar{\theta}-\theta^0)-\|\theta_F-\theta^0\|_2^2\\
&\quad-\xi^\mathsf{T}(\bar{\theta}-\theta^0)+\xi^\mathsf{T}(\theta_F-\theta^0)+\mu_n\langle G_F,\bar{G}-G_F\rangle.
\end{aligned} S n = ( θ F − θ 0 − ξ ) T ( θ ˉ − θ F ) + μ n ⟨ G F , G ˉ − G F ⟩ = ( θ F − θ 0 ) T ( θ ˉ − θ 0 ) − ∥ θ F − θ 0 ∥ 2 2 − ξ T ( θ ˉ − θ 0 ) + ξ T ( θ F − θ 0 ) + μ n ⟨ G F , G ˉ − G F ⟩ .
We first control the terms involving the fitted values. Since θ ˉ \bar{\theta} θ ˉ and θ 0 \theta^0 θ 0 are functions of the design X X X , and the noise is conditionally centered,
E f 0 [ ξ T ( θ ˉ − θ 0 ) ] = 0. \mathbb{E}_{f_0}\left[\xi^\mathsf{T}(\bar{\theta}-\theta^0)\right]=0. E f 0 [ ξ T ( θ ˉ − θ 0 ) ] = 0.
Moreover, the bounds ∣ θ ˉ i ∣ ≤ B |\bar{\theta}_i|\le B ∣ θ ˉ i ∣ ≤ B and ∣ θ i 0 ∣ ≤ B |\theta_i^0|\le B ∣ θ i 0 ∣ ≤ B give us ∥ θ ˉ − θ 0 ∥ 2 ≤ 2 B n \|\bar{\theta}-\theta^0\|_2\le2B\sqrt{n} ∥ θ ˉ − θ 0 ∥ 2 ≤ 2 B n . We know from Proposition A.14 that
E f 0 ∥ θ F − θ 0 ∥ 2 2 ≤ C n ( r n , d + μ n L 2 + σ 2 n ) . \mathbb{E}_{f_0}\|\theta_F-\theta^0\|_2^2\le Cn\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2}{n}\right). E f 0 ∥ θ F − θ 0 ∥ 2 2 ≤ C n ( r n , d + μ n L 2 + n σ 2 ) .
Therefore, Cauchy–Schwarz yields
E f 0 [ ( θ F − θ 0 ) T ( θ ˉ − θ 0 ) ] ≤ ( E f 0 ∥ θ F − θ 0 ∥ 2 2 ) 1 / 2 ( E f 0 ∥ θ ˉ − θ 0 ∥ 2 2 ) 1 / 2 ≤ C n ( r n , d + μ n L 2 + σ 2 n ) 1 / 2 . \begin{aligned}
\mathbb{E}_{f_0}\left[(\theta_F-\theta^0)^\mathsf{T}(\bar{\theta}-\theta^0)\right]
&\le\left(\mathbb{E}_{f_0}\|\theta_F-\theta^0\|_2^2\right)^{1/2}\left(\mathbb{E}_{f_0}\|\bar{\theta}-\theta^0\|_2^2\right)^{1/2}\\
&\le Cn\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2}{n}\right)^{1/2}.
\end{aligned} E f 0 [ ( θ F − θ 0 ) T ( θ ˉ − θ 0 ) ] ≤ ( E f 0 ∥ θ F − θ 0 ∥ 2 2 ) 1/2 ( E f 0 ∥ θ ˉ − θ 0 ∥ 2 2 ) 1/2 ≤ C n ( r n , d + μ n L 2 + n σ 2 ) 1/2 .
Similarly, Lemma A.9 gave us E ∥ ξ ∥ 2 2 ≤ n σ 2 \mathbb{E}\|\xi\|_2^2\le n\sigma^2 E ∥ ξ ∥ 2 2 ≤ n σ 2 . Another application of Cauchy Schwartz then says that
E f 0 [ ξ T ( θ F − θ 0 ) ] ≤ ( E ∥ ξ ∥ 2 2 ) 1 / 2 ( E f 0 ∥ θ F − θ 0 ∥ 2 2 ) 1 / 2 ≤ C σ n ( r n , d + μ n L 2 + σ 2 n ) 1 / 2 . \mathbb{E}_{f_0}\left[\xi^\mathsf{T}(\theta_F-\theta^0)\right]\le\left(\mathbb{E}\|\xi\|_2^2\right)^{1/2}\left(\mathbb{E}_{f_0}\|\theta_F-\theta^0\|_2^2\right)^{1/2}\le C\sigma n\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2}{n}\right)^{1/2}. E f 0 [ ξ T ( θ F − θ 0 ) ] ≤ ( E ∥ ξ ∥ 2 2 ) 1/2 ( E f 0 ∥ θ F − θ 0 ∥ 2 2 ) 1/2 ≤ C σ n ( r n , d + μ n L 2 + n σ 2 ) 1/2 .
For the regularization term, the slope bounds give
μ n ⟨ G F , G ˉ − G F ⟩ ≤ 2 μ n n L 2 . \mu_n\langle G_F,\bar{G}-G_F\rangle\le2\mu_n nL^2. μ n ⟨ G F , G ˉ − G F ⟩ ≤ 2 μ n n L 2 .
We can also discard the nonpositive term − ∥ θ F − θ 0 ∥ 2 2 -\|\theta_F-\theta^0\|_2^2 − ∥ θ F − θ 0 ∥ 2 2 . Combining these estimates gives
E f 0 S n ≤ C n ( 1 + σ ) ( r n , d + μ n L 2 + σ 2 n ) 1 / 2 + 2 μ n n L 2 . \mathbb{E}_{f_0}S_n\le Cn(1+\sigma)\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2}{n}\right)^{1/2}+2\mu_n nL^2. E f 0 S n ≤ C n ( 1 + σ ) ( r n , d + μ n L 2 + n σ 2 ) 1/2 + 2 μ n n L 2 .
By Assumption 2.3, μ n L 2 ≤ C μ r n , d \mu_nL^2\le C_\mu r_{n,d} μ n L 2 ≤ C μ r n , d . Since r n , d → 0 r_{n,d}\to0 r n , d → 0 , for all sufficiently large n n n ,
μ n L 2 ≤ C ( r n , d + μ n L 2 + σ 2 n ) 1 / 2 . \mu_nL^2\le C\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2}{n}\right)^{1/2}. μ n L 2 ≤ C ( r n , d + μ n L 2 + n σ 2 ) 1/2 .
Absorbing fixed constants into C C C establishes (59). Finally, Eq. (58) gives that on G n , K \mathcal{G}_{n,K} G n , K ,
∥ θ K − θ F ∥ 2 ≤ κ n , K c ∗ S n . \lVert\theta_K-\theta_F\rVert^2 \le\frac{\kappa_{n,K}}{c_*}S_n. ∥ θ K − θ F ∥ 2 ≤ c ∗ κ n , K S n .
Since κ n , K ≤ C v n , K \kappa_{n,K}\le Cv_{n,K} κ n , K ≤ C v n , K , we can divide by n n n , multiply by 1 G n , K \mathbf{1}_{\mathcal{G}_{n,K}} 1 G n , K , and take expectations to obtain
E f 0 [ ∥ θ K − θ F ∥ n 2 1 G n , K ] ≤ C v n , K n E f 0 [ S n 1 G n , K ] . \mathbb{E}_{f_0}\left[\lVert\theta_K-\theta_F\rVert_n^2\mathbf{1}_{\mathcal{G}_{n,K}}\right]\le\frac{Cv_{n,K}}{n}\mathbb{E}_{f_0}\left[S_n\mathbf{1}_{\mathcal{G}_{n,K}}\right]. E f 0 [ ∥ θ K − θ F ∥ n 2 1 G n , K ] ≤ n C v n , K E f 0 [ S n 1 G n , K ] .
Because S n ≥ 0 S_n\ge0 S n ≥ 0 by first-order optimality of the full estimator, we have
E f 0 [ S n 1 G n , K ] ≤ E f 0 S n . \mathbb{E}_{f_0}\left[S_n\mathbf{1}_{\mathcal{G}_{n,K}}\right]\le\mathbb{E}_{f_0}S_n. E f 0 [ S n 1 G n , K ] ≤ E f 0 S n .
Substituting (59) proves (60).
Population comparison and the neighborhood choice
The fitted-value comparison is not yet a prediction comparison: other affine pieces can place f ^ K ( X i ) \widehat{f}_K(X_i) f K ( X i ) above θ K , i \theta_{K,i} θ K , i . Thankfully, the omitted-residual estimate also controls this interpolation defect, allowing us to complete the proof.
Proof of Theorem B.1. We define the interpolation defect M i = f ^ K ( X i ) − θ K , i = max j { − r j i ( θ K , G K ) } M_i=\widehat{f}_K(X_i)-\theta_{K,i}=\max_j\{-r_{ji}(\theta_K,G_K)\} M i = f K ( X i ) − θ K , i = max j { − r j i ( θ K , G K )} . By (5) and Lemma B.5, on G n , K \mathcal{G}_{n,K} G n , K ,
0 ≤ M i ≤ κ n , K D i 2 , 1 n ∑ i M i 2 ≤ C v n , K 2 . 0\le M_i\le\kappa_{n,K}D_i^2,\qquad\frac{1}{n}\sum_i M_i^2\le Cv_{n,K}^2. 0 ≤ M i ≤ κ n , K D i 2 , n 1 i ∑ M i 2 ≤ C v n , K 2 .
For the full convex regression problem, we have that f F ( X i ) = θ F , i f_F(X_i)=\theta_{F,i} f F ( X i ) = θ F , i , implying that f ^ K ( X i ) − f ^ F ( X i ) = ( θ K , i − θ F , i ) + M i \widehat{f}_K(X_i)-\widehat{f}_F(X_i)=(\theta_{K,i}-\theta_{F,i})+M_i f K ( X i ) − f F ( X i ) = ( θ K , i − θ F , i ) + M i . Using ( a + b ) 2 ≤ 2 a 2 + 2 b 2 (a+b)^2\le2a^2+2b^2 ( a + b ) 2 ≤ 2 a 2 + 2 b 2 and (60), we obtain
E f 0 [ 1 n ∑ i ( f ^ K ( X i ) − f ^ F ( X i ) ) 2 1 G n , K ] ≤ C ( v n , K ( r n , d + μ n L 2 + σ 2 n ) 1 / 2 + v n , K 2 ) . (62) \mathbb{E}_{f_0}\left[\frac{1}{n}\sum_i\left(\widehat{f}_K(X_i)-\widehat{f}_F(X_i)\right)^2\mathbf{1}_{\mathcal{G}_{n,K}}\right]\le C\left(v_{n,K}\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2}{n}\right)^{1/2}+v_{n,K}^2\right). \tag*{(62)} E f 0 [ n 1 i ∑ ( f K ( X i ) − f F ( X i ) ) 2 1 G n , K ] ≤ C ( v n , K ( r n , d + μ n L 2 + n σ 2 ) 1/2 + v n , K 2 ) . (62)
Both predictors are L L L -Lipschitz. On G n , K \mathcal{G}_{n,K} G n , K , Lemma A.3 and the bounds for p max p_{\max} p m a x and ρ n \rho_n ρ n therefore give
E f 0 [ ℓ p 2 ( f ^ K , f ^ F ) 1 G n , K ] ≤ C [ ℓ n ( v n , K ( r n , d + μ n L 2 + σ 2 n ) 1 / 2 + v n , K 2 ) + ( ℓ n / n ) 2 / d ] . \mathbb{E}_{f_0}\left[\ell_p^2(\widehat{f}_K,\widehat{f}_F)\mathbf{1}_{\mathcal{G}_{n,K}}\right]
\le C\left[\ell_n\left(v_{n,K}\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2}{n}\right)^{1/2}+v_{n,K}^2\right)+(\ell_n/n)^{2/d}\right]. E f 0 [ ℓ p 2 ( f K , f F ) 1 G n , K ] ≤ C [ ℓ n ( v n , K ( r n , d + μ n L 2 + n σ 2 ) 1/2 + v n , K 2 ) + ( ℓ n / n ) 2/ d ] .
On the complementary event, the squared discrepancy is at most 4 B f 2 4B_f^2 4 B f 2 , and the event has probability at most δ n \delta_n δ n . Adding this contribution proves (48), for any f 0 f_0 f 0 in the function class.
We now balance the terms in B.1 through our choice of K K K .
Corollary B.9. For a sufficiently large fixed constant C C C , the deterministic choice
K n = ⌈ C n d − 1 2 d − 1 ℓ n d 2 d − 1 r n , d − d ( d − 1 ) 2 ( 2 d − 1 ) ⌉ (63) K_n=\left\lceil Cn^{\frac{d-1}{2d-1}}\ell_n^{\frac{d}{2d-1}}r_{n,d}^{-\frac{d(d-1)}{2(2d-1)}}\right\rceil \tag*{(63)} K n = ⌈ C n 2 d − 1 d − 1 ℓ n 2 d − 1 d r n , d − 2 ( 2 d − 1 ) d ( d − 1 ) ⌉ (63)
satisfies K n = o ( n ) K_n=o(n) K n = o ( n ) and, for all sufficiently large n n n ,
sup f 0 ∈ F B , L ( Ω ) E f 0 [ ℓ p 2 ( f ^ K , f 0 ) ] ≤ C r n , d log n . (64) \sup_{f_0\in\mathcal{F}_{B,L}(\Omega)}\mathbb{E}_{f_0}\left[\ell_p^2(\widehat{f}_K,f_0)\right]\le Cr_{n,d}\log n. \tag*{(64)} f 0 ∈ F B , L ( Ω ) sup E f 0 [ ℓ p 2 ( f K , f 0 ) ] ≤ C r n , d log n . (64)
Additionally,
sup f 0 ∈ F B , L ( Ω ) E f 0 [ ℓ p 2 ( f ^ K , f ^ F ) ] ≤ C r n , d log n . (65) \sup_{f_0\in\mathcal{F}_{B,L}(\Omega)}\mathbb{E}_{f_0}\left[\ell_p^2(\widehat{f}_K,\widehat{f}_F)\right]\le Cr_{n,d}\log n. \tag*{(65)} f 0 ∈ F B , L ( Ω ) sup E f 0 [ ℓ p 2 ( f K , f F ) ] ≤ C r n , d log n . (65)
Proof. Assumption 2.3 gives us that ( r n , d + μ n L 2 + σ 2 n ) ≤ C r n , d \left(r_{n,d}+\mu_nL^2+\frac{\sigma^2}{n}\right)\leq Cr_{n,d} ( r n , d + μ n L 2 + n σ 2 ) ≤ C r n , d . Properly expanding our v n , K v_{n,K} v n , K gives us that:
v n , K = n 1 / d ℓ n 1 / ( d − 1 ) K − ( 2 d − 1 ) / [ d ( d − 1 ) ] . v_{n,K}=n^{1/d}\ell_n^{1/(d-1)}K^{-(2d-1)/[d(d-1)]}. v n , K = n 1/ d ℓ n 1/ ( d − 1 ) K − ( 2 d − 1 ) / [ d ( d − 1 )] .
Thus v n , K ≤ c r n , d 1 / 2 v_{n,K}\leq cr_{n,d}^{1/2} v n , K ≤ c r n , d 1/2 is obtained by taking a sufficiently large constant in (62). For this choice,
ℓ n ( v n , K ( r n , d + μ n L 2 + σ 2 n ) + v n , K 2 ) ≤ C r n , d log n \ell_n\left(v_{n,K}\left(r_{n,d}+\mu_nL^2+\frac{\sigma^2}{n}\right)+v_{n,K}^2\right)\leq Cr_{n,d}\log n ℓ n ( v n , K ( r n , d + μ n L 2 + n σ 2 ) + v n , K 2 ) ≤ C r n , d log n
We now need to establish that ( ℓ n / n ) 2 / d ≤ C r n , d log n (\ell_n/n)^{2/d}\leq Cr_{n,d}\log n ( ℓ n / n ) 2/ d ≤ C r n , d log n . Noting that ℓ n \ell_n ℓ n is on the same order as log n \log n log n and checking each dimension suffices to prove this.
Finally, we need to verify that our chosen values of K n K_n K n satisfy the condition of C 0 ℓ n ≤ K n ≤ c 0 n C_0\ell_n\leq K_n\leq c_0n C 0 ℓ n ≤ K n ≤ c 0 n . Since ℓ n ≍ log n \ell_n\asymp\log n ℓ n ≍ log n , substituting the expressions for r n , d r_{n,d} r n , d gives us
K n ≍ { n ( d − 1 ) ( 3 d + 4 ) ( 2 d − 1 ) ( d + 4 ) ( log n ) d 2 d − 1 , 2 ≤ d < 4 , n 6 / 7 ( log n ) − 2 / 7 , d = 4 , n 2 ( d − 1 ) 2 d − 1 ( log n ) d 2 d − 1 , d > 4. (66) K_n\asymp
\begin{cases}
n^{\frac{(d-1)(3d+4)}{(2d-1)(d+4)}}(\log n)^{\frac{d}{2d-1}}, & 2\leq d<4,\\
n^{6/7}(\log n)^{-2/7}, & d=4,\\
n^{\frac{2(d-1)}{2d-1}}(\log n)^{\frac{d}{2d-1}}, & d>4.
\end{cases} \tag*{(66)} K n ≍ ⎩ ⎨ ⎧ n ( 2 d − 1 ) ( d + 4 ) ( d − 1 ) ( 3 d + 4 ) ( log n ) 2 d − 1 d , n 6/7 ( log n ) − 2/7 , n 2 d − 1 2 ( d − 1 ) ( log n ) 2 d − 1 d , 2 ≤ d < 4 , d = 4 , d > 4. (66)
In the first case, the polynomial exponent equals 5 / 9 5/9 5/9 for d = 2 d=2 d = 2 and 26 / 35 26/35 26/35 for d = 3 d=3 d = 3 . For d = 4 d=4 d = 4 , it equals 6 / 7 6/7 6/7 , while for d > 4 d>4 d > 4 it is 2 ( d − 1 ) / ( 2 d − 1 ) < 1 2(d-1)/(2d-1)<1 2 ( d − 1 ) / ( 2 d − 1 ) < 1 . Thus, in every fixed dimension d ≥ 2 d\geq2 d ≥ 2 , the neighborhood size has the form K n ≍ n p ( log n ) q K_n\asymp n^p(\log n)^q K n ≍ n p ( log n ) q for some 0 < p < 1 0<p<1 0 < p < 1 and fixed q ∈ R q\in\mathbb{R} q ∈ R .
It follows that
K n ℓ n ≍ n p ( log n ) q − 1 ⟶ ∞ , K n n ≍ n p − 1 ( log n ) q ⟶ 0 , \frac{K_n}{\ell_n}\asymp n^p(\log n)^{q-1}\longrightarrow\infty,\qquad\frac{K_n}{n}\asymp n^{p-1}(\log n)^q\longrightarrow0, ℓ n K n ≍ n p ( log n ) q − 1 ⟶ ∞ , n K n ≍ n p − 1 ( log n ) q ⟶ 0 ,
We then have that E f 0 ℓ P 2 ( f ^ K , f ^ F ) ≤ C r n , d log n \mathbb{E}_{f_0}\ell_{\mathbb{P}}^2(\widehat{f}_K,\widehat{f}_F)\leq Cr_{n,d}\log n E f 0 ℓ P 2 ( f K , f F ) ≤ C r n , d log n . Finally, the risk decomposition with Proposition (A.14) gives
E f 0 ℓ P 2 ( f ^ K , f 0 ) ≤ 2 E f 0 ℓ P 2 ( f ^ K , f ^ F ) + 2 E f 0 ℓ P 2 ( f ^ F , f 0 ) ≤ C r n , d log n . \mathbb{E}_{f_0}\ell_{\mathbb{P}}^2(\widehat{f}_K,f_0)\leq2\mathbb{E}_{f_0}\ell_{\mathbb{P}}^2(\widehat{f}_K,\widehat{f}_F)+2\mathbb{E}_{f_0}\ell_{\mathbb{P}}^2(\widehat{f}_F,f_0)\leq Cr_{n,d}\log n. E f 0 ℓ P 2 ( f K , f 0 ) ≤ 2 E f 0 ℓ P 2 ( f K , f F ) + 2 E f 0 ℓ P 2 ( f F , f 0 ) ≤ C r n , d log n .
where C C C is appropriately increased in the last inequality
Strongly Convex Case
We move onto the more specific case of strongly convex functions. We prove Theorem 3.4 by identifying a radius that contains every active constraint of the full problem. We first strengthen the full estimator’s population-error control to an error bound holding everywhere on Ω \Omega Ω . Strong convexity then makes every sufficiently distant constraint strictly slack. Therefore, a KNN graph retaining all shorter constraints has the same optimizer as the full problem completing our proof.
We begin by showing that Lipschitzness gives us a way to bound uniform approximation from L 2 L_2 L 2 error.
Lemma C.1. For an A A A -Lipschitz function h : Ω → R h:\Omega\to\mathbb{R} h : Ω → R ,
∥ h ∥ ∞ ≤ C Ω [ ( ∫ Ω h 2 d P ) 1 / 2 + A d / ( d + 2 ) ( ∫ Ω h 2 d P ) 1 / ( d + 2 ) ] . (67) \lVert h\rVert_\infty\leq C_\Omega\left[\left(\int_\Omega h^2\,\mathrm{d}\mathbb{P}\right)^{1/2}+A^{d/(d+2)}\left(\int_\Omega h^2\,\mathrm{d}\mathbb{P}\right)^{1/(d+2)}\right]. \tag*{(67)} ∥ h ∥ ∞ ≤ C Ω [ ( ∫ Ω h 2 d P ) 1/2 + A d / ( d + 2 ) ( ∫ Ω h 2 d P ) 1/ ( d + 2 ) ] . (67)
Proof. If ∥ h ∥ ∞ = 0 \lVert h\rVert_\infty=0 ∥ h ∥ ∞ = 0 , the conclusion is immediate. If A = 0 A=0 A = 0 , then h h h is constant on Ω \Omega Ω , so ∥ h ∥ ∞ = ( ∫ Ω h 2 d P ) 1 / 2 \lVert h\rVert_\infty=\left(\int_\Omega h^2\,\mathrm{d}\mathbb{P}\right)^{1/2} ∥ h ∥ ∞ = ( ∫ Ω h 2 d P ) 1/2 . We therefore assume that ∥ h ∥ ∞ > 0 \lVert h\rVert_\infty>0 ∥ h ∥ ∞ > 0 and A > 0 A>0 A > 0 .
Since Ω \Omega Ω is compact and h h h is continuous, there exists x 0 ∈ Ω x_0\in\Omega x 0 ∈ Ω such that ∣ h ( x 0 ) ∣ = ∥ h ∥ ∞ \lvert h(x_0)\rvert=\lVert h\rVert_\infty ∣ h ( x 0 )∣ = ∥ h ∥ ∞ . By Lipschitz continuity, for every x ∈ Ω x\in\Omega x ∈ Ω ,
∣ h ( x ) ∣ ≥ ∣ h ( x 0 ) ∣ − ∣ h ( x ) − h ( x 0 ) ∣ ≥ ∥ h ∥ ∞ − A ∥ x − x 0 ∥ 2 . \lvert h(x)\rvert\geq\lvert h(x_0)\rvert-\lvert h(x)-h(x_0)\rvert\geq\lVert h\rVert_\infty-A\lVert x-x_0\rVert_2. ∣ h ( x )∣ ≥ ∣ h ( x 0 )∣ − ∣ h ( x ) − h ( x 0 )∣ ≥ ∥ h ∥ ∞ − A ∥ x − x 0 ∥ 2 .
In particular, whenever ∥ x − x 0 ∥ 2 ≤ ∥ h ∥ ∞ / ( 2 A ) \lVert x-x_0\rVert_2 \le\lVert h\rVert_\infty/(2A) ∥ x − x 0 ∥ 2 ≤ ∥ h ∥ ∞ / ( 2 A ) , we have ∣ h ( x ) ∣ ≥ ∥ h ∥ ∞ / 2 |h(x)| \ge\lVert h\rVert_\infty/2 ∣ h ( x ) ∣ ≥ ∥ h ∥ ∞ /2 .
We first consider the case ∥ h ∥ ∞ / ( 2 A ) ≤ D Ω \lVert h\rVert_\infty/(2A) \le D_\Omega ∥ h ∥ ∞ / ( 2 A ) ≤ D Ω . Applying the ball-mass bound (18) , we obtain
∫ Ω h 2 d P ≥ ∫ B ( x 0 , ∥ h ∥ ∞ / ( 2 A ) ) ∩ Ω h 2 d P ≥ ∥ h ∥ ∞ 2 4 P ( B ( x 0 , ∥ h ∥ ∞ 2 A ) ∩ Ω ) ≥ c Ω ∥ h ∥ ∞ 2 4 ( ∥ h ∥ ∞ 2 A ) d = c Ω 2 d + 2 ∥ h ∥ ∞ d + 2 A d . \begin{aligned}
\int_\Omega h^2\,\mathrm{d}\mathbb{P}
&\ge\int_{B(x_0,\lVert h\rVert_\infty/(2A))\cap\Omega} h^2\,\mathrm{d}\mathbb{P}\\
&\ge\frac{\lVert h\rVert_\infty^2}{4}\mathbb{P}\left(B\left(x_0,\frac{\lVert h\rVert_\infty}{2A}\right)\cap\Omega\right)\\
&\ge c_\Omega\frac{\lVert h\rVert_\infty^2}{4}\left(\frac{\lVert h\rVert_\infty}{2A}\right)^d\\
&=\frac{c_\Omega}{2^{d+2}}\frac{\lVert h\rVert_\infty^{d+2}}{A^d}.
\end{aligned} ∫ Ω h 2 d P ≥ ∫ B ( x 0 , ∥ h ∥ ∞ / ( 2 A )) ∩ Ω h 2 d P ≥ 4 ∥ h ∥ ∞ 2 P ( B ( x 0 , 2 A ∥ h ∥ ∞ ) ∩ Ω ) ≥ c Ω 4 ∥ h ∥ ∞ 2 ( 2 A ∥ h ∥ ∞ ) d = 2 d + 2 c Ω A d ∥ h ∥ ∞ d + 2 .
Rearranging yields ∥ h ∥ ∞ ≤ C Ω A d / ( d + 2 ) ( ∫ Ω h 2 d P ) 1 / ( d + 2 ) \lVert h\rVert_\infty\le C_\Omega A^{d/(d+2)}\left(\int_\Omega h^2\,\mathrm{d}\mathbb{P}\right)^{1/(d+2)} ∥ h ∥ ∞ ≤ C Ω A d / ( d + 2 ) ( ∫ Ω h 2 d P ) 1/ ( d + 2 ) .
We next consider the case ∥ h ∥ ∞ / ( 2 A ) > D Ω \lVert h\rVert_\infty/(2A)>D_\Omega ∥ h ∥ ∞ / ( 2 A ) > D Ω . Since ∥ x − x 0 ∥ 2 ≤ D Ω \lVert x-x_0\rVert_2\le D_\Omega ∥ x − x 0 ∥ 2 ≤ D Ω for every x ∈ Ω x\in\Omega x ∈ Ω , the Lipschitz inequality gives
∣ h ( x ) ∣ ≥ ∥ h ∥ ∞ − A D Ω > ∥ h ∥ ∞ 2 |h(x)|\ge\lVert h\rVert_\infty-AD_\Omega>\frac{\lVert h\rVert_\infty}{2} ∣ h ( x ) ∣ ≥ ∥ h ∥ ∞ − A D Ω > 2 ∥ h ∥ ∞
for all x ∈ Ω x\in\Omega x ∈ Ω .
Consequently, ∫ Ω h 2 d P ≥ ∥ h ∥ ∞ 2 / 4 \int_\Omega h^2\,\mathrm{d}\mathbb{P}\ge\lVert h\rVert_\infty^2/4 ∫ Ω h 2 d P ≥ ∥ h ∥ ∞ 2 /4 , ⟹ ∥ h ∥ ∞ ≤ 2 ( ∫ Ω h 2 d P ) 1 / 2 \Longrightarrow\lVert h\rVert_\infty\le2\left(\int_\Omega h^2\,\mathrm{d}\mathbb{P}\right)^{1/2} ⟹ ∥ h ∥ ∞ ≤ 2 ( ∫ Ω h 2 d P ) 1/2 .
Combining the two cases and increasing C Ω C_\Omega C Ω if necessary, we conclude that
∥ h ∥ ∞ ≤ C Ω [ ( ∫ Ω h 2 d P ) 1 / 2 + A d / ( d + 2 ) ( ∫ Ω h 2 d P ) 1 / ( d + 2 ) ] . \lVert h\rVert_\infty\le C_\Omega\left[\left(\int_\Omega h^2\,\mathrm{d}\mathbb{P}\right)^{1/2}+A^{d/(d+2)}\left(\int_\Omega h^2\,\mathrm{d}\mathbb{P}\right)^{1/(d+2)}\right]. ∥ h ∥ ∞ ≤ C Ω [ ( ∫ Ω h 2 d P ) 1/2 + A d / ( d + 2 ) ( ∫ Ω h 2 d P ) 1/ ( d + 2 ) ] .
We apply this deterministic lemma to the error f ^ F − f 0 \widehat f_F-f_0 f F − f 0 , which is 2 L 2L 2 L -Lipschitz. The population confidence bound from Appendix § 9 then provides a single event on which the full predictor is accurate at every point, including the midpoints used in the screening argument.
Lemma C.2 (Uniform approximation of the full predictor). For a sufficiently large fixed constant C C C and all sufficiently large n n n ,
sup f 0 ∈ F B , L ( Ω ) P f 0 { ∥ f ^ F − f 0 ∥ ∞ > ϵ n } ≤ δ n , (68) \sup_{f_0\in\mathcal{F}_{B,L}(\Omega)}\mathbb{P}_{f_0}\left\{\lVert\widehat f_F-f_0\rVert_\infty>\epsilon_n\right\}\le\delta_n, \tag*{(68)} f 0 ∈ F B , L ( Ω ) sup P f 0 { ∥ f F − f 0 ∥ ∞ > ϵ n } ≤ δ n , (68) where ϵ n = C ( r n , d log n ) 1 / ( d + 2 ) \epsilon_n=C(r_{n,d}\log n)^{1/(d+2)} ϵ n = C ( r n , d log n ) 1/ ( d + 2 ) , and δ n = r n , d 2 \delta_n=r_{n,d}^2 δ n = r n , d 2 .
Proof. We apply the population confidence bound (43) probability of δ n \delta_n δ n . Since δ n = r n , d 2 \delta_n=r_{n,d}^2 δ n = r n , d 2 and log ( n / δ n ) ≤ C log n \log(n/\delta_n)\le C\log n log ( n / δ n ) ≤ C log n for all sufficiently large n n n , we get
sup f 0 ∈ F B , L ( Ω ) P f 0 { ℓ P 2 ( f ^ F , f 0 ) > C r n , d log n } ≤ δ n . \sup_{f_0\in\mathcal{F}_{B,L}(\Omega)}\mathbb{P}_{f_0}\left\{\ell_{\mathbb{P}}^2(\widehat f_F,f_0)>Cr_{n,d}\log n\right\}\le\delta_n. f 0 ∈ F B , L ( Ω ) sup P f 0 { ℓ P 2 ( f F , f 0 ) > C r n , d log n } ≤ δ n .
Both f ^ F \widehat f_F f F and f 0 f_0 f 0 are L L L -Lipschitz, so their difference is 2 L 2L 2 L -Lipschitz. So, on the event where ℓ P 2 ( f ^ F , f 0 ) ≤ C r n , d log n \ell_{\mathbb{P}}^2(\widehat f_F,f_0)\le Cr_{n,d}\log n ℓ P 2 ( f F , f 0 ) ≤ C r n , d log n , Lemma C.1 gives
∥ f ^ F − f 0 ∥ ∞ ≤ C Ω [ ( C r n , d log n ) 1 / 2 + ( 2 L ) d / ( d + 2 ) ( C r n , d log n ) 1 / ( d + 2 ) ] ≤ C ( r n , d log n ) 1 / ( d + 2 ) . \begin{aligned}
\lVert\widehat f_F-f_0\rVert_\infty\le C_\Omega\left[(Cr_{n,d}\log n)^{1/2}+(2L)^{d/(d+2)}(Cr_{n,d}\log n)^{1/(d+2)}\right] \\
&\le C(r_{n,d}\log n)^{1/(d+2)}.
\end{aligned} ∥ f F − f 0 ∥ ∞ ≤ C Ω [ ( C r n , d log n ) 1/2 + ( 2 L ) d / ( d + 2 ) ( C r n , d log n ) 1/ ( d + 2 ) ] ≤ C ( r n , d log n ) 1/ ( d + 2 ) .
The last inequality follows because r n , d log n → 0 r_{n,d}\log n\to0 r n , d log n → 0 and 1 / ( d + 2 ) < 1 / 2 1/(d+2)<1/2 1/ ( d + 2 ) < 1/2 , so
( r n , d log n ) 1 / 2 ≤ ( r n , d log n ) 1 / ( d + 2 ) (r_{n,d}\log n)^{1/2}\le(r_{n,d}\log n)^{1/(d+2)} ( r n , d log n ) 1/2 ≤ ( r n , d log n ) 1/ ( d + 2 )
for all sufficiently large n n n .
Choosing the constant in ϵ n \epsilon_n ϵ n sufficiently large establishes (67), uniformly over f 0 ∈ F B , L ( Ω ) f_0\in\mathcal{F}_{B,L}(\Omega) f 0 ∈ F B , L ( Ω ) .
Screening active supporting constraints
We now assume f 0 ∈ F B , L s c ( Ω ; m 0 ) f_0 \in\mathcal{F}^{\mathrm{sc}}_{B,L}(\Omega;m_0) f 0 ∈ F B , L sc ( Ω ; m 0 ) for a fixed m 0 > 0 m_0 > 0 m 0 > 0 . A full constraint is active when its residual is zero: the affine piece based at X j X_j X j then agrees with the full predictor at both X j X_j X j and X i X_i X i . Strong convexity of the truth creates a definite midpoint gap between distant observations. If the full predictor uniformly approximates the truth, that gap prevents a distant constraint from remaining active.
Lemma C.3. On the event ∥ f ^ F − f 0 ∥ ∞ ≤ ϵ n \|\widehat{f}_F-f_0\|_\infty\le\epsilon_n ∥ f F − f 0 ∥ ∞ ≤ ϵ n ,
r j i ( θ F , G F ) ≥ m 0 4 ∥ X i − X j ∥ 2 2 − 4 ϵ n , i ≠ j . (69) r_{ji}(\theta_F,G_F) \ge\frac{m_0}{4}\|X_i-X_j\|_2^2-4\epsilon_n,\qquad i\ne j. \tag*{(69)} r j i ( θ F , G F ) ≥ 4 m 0 ∥ X i − X j ∥ 2 2 − 4 ϵ n , i = j . (69) Consequently, every active full constraint has length at most
R n = 4 ϵ n / m 0 . (70) R_n=4\sqrt{\epsilon_n/m_0}. \tag*{(70)} R n = 4 ϵ n / m 0 . (70) Proof. We set h = f ^ F h=\widehat{f}_F h = f F , x = X j x=X_j x = X j , y = X i y=X_i y = X i , and z = ( x + y ) / 2 z=(x+y)/2 z = ( x + y ) /2 . Since we are looking at the full solution of the convex problem, the j j j th affine piece is a supporting plane of h h h at x x x . Evaluating it at the midpoint gives h ( z ) ≥ h ( x ) + g F , j T ( y − x ) / 2 h(z)\ge h(x)+g_{F,j}^{\mathsf{T}}(y-x)/2 h ( z ) ≥ h ( x ) + g F , j T ( y − x ) /2 . Therefore,
r j i ( θ F , G F ) = h ( y ) − h ( x ) − g F , j T ( y − x ) ≥ h ( y ) + h ( x ) − 2 h ( z ) ≥ f 0 ( y ) + f 0 ( x ) − 2 f 0 ( z ) − 4 ϵ n . \begin{aligned}
r_{ji}(\theta_F,G_F)&=h(y)-h(x)-g_{F,j}^{\mathsf{T}}(y-x)\\
&\ge h(y)+h(x)-2h(z)\\
&\ge f_0(y)+f_0(x)-2f_0(z)-4\epsilon_n.
\end{aligned} r j i ( θ F , G F ) = h ( y ) − h ( x ) − g F , j T ( y − x ) ≥ h ( y ) + h ( x ) − 2 h ( z ) ≥ f 0 ( y ) + f 0 ( x ) − 2 f 0 ( z ) − 4 ϵ n . Using the definition of strong convexity at the midpoints (t = 1 / 2 t=1/2 t = 1/2 ) in gives
f 0 ( y ) + f 0 ( x ) − 2 f 0 ( ( x + y ) / 2 ) ≥ m 0 4 ∥ y − x ∥ 2 2 . f_0(y)+f_0(x)-2f_0((x+y)/2)\ge\frac{m_0}{4}\|y-x\|_2^2. f 0 ( y ) + f 0 ( x ) − 2 f 0 (( x + y ) /2 ) ≥ 4 m 0 ∥ y − x ∥ 2 2 . This proves (69) . If ∥ y − x ∥ 2 > R n \|y-x\|_2>R_n ∥ y − x ∥ 2 > R n , its right-hand side is positive, so the constraint is strictly slack. Every active constraint must therefore have length at most R n R_n R n .
Once all potentially active constraints have been retained, a separate deterministic fact completes the optimization argument. Removing only inequalities that are strictly slack at the full optimizer leaves that optimizer unchanged.
Exact recovery and population-risk transfer
The radius R n R_n R n is deterministic and tends to zero. The local-count lemma bounds how many observations can lie within this radius of any source. So our strategy is to choose K n K_n K n to retain them all. On the resulting event, the preceding lemmas give exact agreement; bounded losses then control the contribution from the exceptional datasets.
Theorem C.4 (Strongly convex sparsification preserves the full-estimator rate). Under the setup of § 2 and Assumption 2.3, we consider a nonempty class F B , L s c ( Ω ; m 0 ) \mathcal{F}^{\mathrm{sc}}_{B,L}(\Omega;m_0) F B , L sc ( Ω ; m 0 ) with fixed m 0 > 0 m_0>0 m 0 > 0 . For all sufficiently large n n n , any deterministic integer 1 ≤ K n ≤ n − 1 1\le K_n\le n-1 1 ≤ K n ≤ n − 1 satisfying
K n ≥ C [ n m 0 − d / 2 ( r n , d log n ) d d + 2 + log n ] (71) K_n\ge C\left[nm_0^{-d/2}(r_{n,d}\log n)^{\frac{d}{d+2}}+\log n\right] \tag*{(71)} K n ≥ C [ n m 0 − d /2 ( r n , d log n ) d + 2 d + log n ] (71) for a sufficiently large fixed constant C C C satisfies
sup f 0 ∈ F B , L s c ( Ω ; m 0 ) P f 0 { ( θ K , G K ) ≠ ( θ F , G F ) } ≤ C r n , d 2 (72) \sup_{f_0\in\mathcal{F}^{\mathrm{sc}}_{B,L}(\Omega;m_0)}
\mathbb{P}_{f_0}\{(\theta_K,G_K)\ne(\theta_F,G_F)\}\le Cr_{n,d}^2 \tag*{(72)} f 0 ∈ F B , L sc ( Ω ; m 0 ) sup P f 0 {( θ K , G K ) = ( θ F , G F )} ≤ C r n , d 2 (72) and
sup f 0 ∈ F B , L s c ( Ω ; m 0 ) E f 0 ℓ 2 ( f ^ K , f ^ F ) ≤ C r n , d 2 . (73) \sup_{f_0\in\mathcal{F}^{\mathrm{sc}}_{B,L}(\Omega;m_0)}
\mathbb{E}_{f_0}\ell^2(\widehat{f}_K,\widehat{f}_F)\le Cr_{n,d}^2. \tag*{(73)} f 0 ∈ F B , L sc ( Ω ; m 0 ) sup E f 0 ℓ 2 ( f K , f F ) ≤ C r n , d 2 . (73) We also have
∣ R K , n − R F , n ∣ ≤ C r n , d 2 , (74) |\mathcal{R}_{K,n}-\mathcal{R}_{F,n}|\le Cr_{n,d}^2, \tag*{(74)} ∣ R K , n − R F , n ∣ ≤ C r n , d 2 , (74) and consequently
R K , n ≤ C r n , d log n . (75) \mathcal{R}_{K,n}\le Cr_{n,d}\log n. \tag*{(75)} R K , n ≤ C r n , d log n . (75) There are choices satisfying (71) with K n = o ( n ) K_n=o(n) K n = o ( n ) .
Proof. Keeping the same definitions for ϵ n \epsilon_n ϵ n and R n R_n R n from Lemma C.2 and Lemma C.3 , we consider the event U n = { ∥ f ^ F − f 0 ∥ ∞ ≤ ϵ n } U_n = \{\|\widehat f_F-f_0\|_\infty\le\epsilon_n\} U n = { ∥ f F − f 0 ∥ ∞ ≤ ϵ n } . Lemma C.2 gives sup f 0 ∈ F B , L s c ( Ω ; m 0 ) P f 0 ( U n c ) ≤ r n , d 2 \sup_{f_0\in\mathcal{F}^{\mathrm{sc}}_{B,L}(\Omega;m_0)}\mathbb{P}_{f_0}(U_n^c)\le r_{n,d}^2 sup f 0 ∈ F B , L sc ( Ω ; m 0 ) P f 0 ( U n c ) ≤ r n , d 2 . On U n U_n U n , Lemma C.3 shows that every active full supporting-hyperplane constraint has length at most R n R_n R n .
Since r n , d log n → 0 r_{n,d}\log n\to0 r n , d log n → 0 , we have ϵ n → 0 \epsilon_n\to0 ϵ n → 0 and hence R n → 0 R_n\to0 R n → 0 . Thus R n ≤ D Ω R_n\le D_\Omega R n ≤ D Ω for all sufficiently large n n n . We apply Lemma A.2 at the deterministic radius R n R_n R n , with failure probability r n , d 2 r_{n,d}^2 r n , d 2 . On the resulting event G n G_n G n ,
max j ≤ n # { i ≠ j : ∥ X i − X j ∥ 2 ≤ R n } ≤ C N [ n R n d + log ( n r n , d 2 ) ] . \max_{j\le n}\#\{i\ne j:\|X_i-X_j\|_2\le R_n\}\le C_N\left[nR_n^d+\log\left(\frac{n}{r_{n,d}^2}\right)\right]. j ≤ n max # { i = j : ∥ X i − X j ∥ 2 ≤ R n } ≤ C N [ n R n d + log ( r n , d 2 n ) ] .
Since log ( n / r n , d 2 ) ≤ C log n \log(n/r_{n,d}^2)\le C\log n log ( n / r n , d 2 ) ≤ C log n for all sufficiently large n n n , and
n R n d = 4 d n m 0 − d / 2 ϵ n d / 2 ≤ C n m 0 − d / 2 ( r n , d log n ) d d + 2 , \begin{aligned}
nR_n^d=4^d n m_0^{-d/2}\epsilon_n^{d/2} \\
&\le C n m_0^{-d/2}(r_{n,d}\log n)^{\frac{d}{d+2}},
\end{aligned} n R n d = 4 d n m 0 − d /2 ϵ n d /2 ≤ C n m 0 − d /2 ( r n , d log n ) d + 2 d ,
condition (71) ensures that every observation within distance R n R_n R n of any X j X_j X j belongs to its K n K_n K n nearest neighbors. Consequently, on U n ∩ G n U_n\cap G_n U n ∩ G n , the KNN graph retains every active constraint of the full problem. Every omitted full constraint is therefore strictly slack at ( θ F , G F ) (\theta_F,G_F) ( θ F , G F ) and removing these constraints does not change the optimizer, giving us
( θ K , G K ) = ( θ F , G F ) on U n ∩ G n . (76) (\theta_K,G_K)=(\theta_F,G_F)\qquad\text{on }U_n\cap G_n. \tag*{(76)} ( θ K , G K ) = ( θ F , G F ) on U n ∩ G n . (76)
The union bound gives
sup f 0 ∈ F B , L s c ( Ω ; m 0 ) P f 0 ( ( U n ∩ G n ) c ) ≤ 2 r n , d 2 , \sup_{f_0\in\mathcal{F}^{\mathrm{sc}}_{B,L}(\Omega;m_0)}
\mathbb{P}_{f_0}\bigl((U_n\cap G_n)^c\bigr)\le2r_{n,d}^2, f 0 ∈ F B , L sc ( Ω ; m 0 ) sup P f 0 ( ( U n ∩ G n ) c ) ≤ 2 r n , d 2 ,
which proves (72) . On the U n ∩ G n U_n\cap G_n U n ∩ G n , the predictors coincide everywhere. On its complement, both predictors are uniformly bounded by B f = B + L D Ω B_f=B+LD_\Omega B f = B + L D Ω , so ℓ P 2 ( f ^ K , f ^ F ) ≤ 4 B f 2 \ell_P^2(\widehat f_K,\widehat f_F)\le4B_f^2 ℓ P 2 ( f K , f F ) ≤ 4 B f 2 . Therefore,
E f 0 ℓ P 2 ( f ^ K , f ^ F ) ≤ 4 B f 2 P f 0 ( ( U n ∩ G n ) c ) \mathbb{E}_{f_0}\ell_P^2(\widehat f_K,\widehat f_F)\le4B_f^2\mathbb{P}_{f_0}\bigl((U_n\cap G_n)^c\bigr) E f 0 ℓ P 2 ( f K , f F ) ≤ 4 B f 2 P f 0 ( ( U n ∩ G n ) c )
≤ 8 B f 2 r n , d 2 . \le8B_f^2r_{n,d}^2. ≤ 8 B f 2 r n , d 2 .
Taking the supremum over the truth class establishes (73) .
We next compare the population risks against f 0 f_0 f 0 . On the agreement event, the two predictors and hence their squared population losses coincide. On the complementary event, both losses are bounded by ( B f + B ) 2 (B_f+B)^2 ( B f + B ) 2 . Thus,
∣ E f 0 ℓ P 2 ( f ^ K , f 0 ) − E f 0 ℓ P 2 ( f ^ F , f 0 ) ∣ ≤ ( B f + B ) 2 P f 0 ( ( U n ∩ G n ) c ) \left|\mathbb{E}_{f_0}\ell_P^2(\widehat f_K,f_0)-\mathbb{E}_{f_0}\ell_P^2(\widehat f_F,f_0)\right|
\le(B_f+B)^2\mathbb{P}_{f_0}\bigl((U_n\cap G_n)^c\bigr) E f 0 ℓ P 2 ( f K , f 0 ) − E f 0 ℓ P 2 ( f F , f 0 ) ≤ ( B f + B ) 2 P f 0 ( ( U n ∩ G n ) c )
≤ 2 ( B f + B ) 2 r n , d 2 . \le2(B_f+B)^2r_{n,d}^2. ≤ 2 ( B f + B ) 2 r n , d 2 .
Taking the supremum over the truth class and using
∣ sup f a f − sup f b f ∣ ≤ sup f ∣ a f − b f ∣ \left|\sup_f a_f-\sup_f b_f\right|\le\sup_f|a_f-b_f| f sup a f − f sup b f ≤ f sup ∣ a f − b f ∣
proves (74) . Combining this bound with Proposition A.14 gives
R K , n ≤ R F , n + C r n , d 2 ≤ C r n , d log n , \mathcal{R}_{K,n}\le\mathcal{R}_{F,n}+Cr_{n,d}^2\le Cr_{n,d}\log n, R K , n ≤ R F , n + C r n , d 2 ≤ C r n , d log n ,
which establishes (75) . Finally, we verify that the neighborhood condition admits sublinear choices. Since r n , d log n → 0 r_{n,d}\log n\to0 r n , d log n → 0 ,
m 0 − d / 2 ( r n , d log n ) d 2 ( d + 2 ) + log n n ⟶ 0. m_0^{-d/2}(r_{n,d}\log n)^{\frac{d}{2(d+2)}}+\frac{\log n}{n}\longrightarrow0. m 0 − d /2 ( r n , d log n ) 2 ( d + 2 ) d + n log n ⟶ 0.
Thus, taking K n K_n K n to be the ceiling of a sufficiently large constant multiple of the right-hand side of (71) gives K n / n → 0 K_n/n\to0 K n / n → 0 .
Plugging in the values of r n , d r_{n,d} r n , d then gives us that
Corollary C.5. For fixed m 0 > 0 m_0 > 0 m 0 > 0 , sufficiently large constant multiples of the following scales, rounded upward and capped at n − 1 n-1 n − 1 , satisfy Theorem C.4 for all sufficiently large n n n :
K n = { n 1 − 2 d ( d + 4 ) ( d + 2 ) ( log n ) d 2 ( d + 2 ) , 2 ≤ d < 4 , n 5 / 6 ( log n ) 2 / 3 , d = 4 , n d + 1 d + 2 ( log n ) d 2 ( d + 2 ) , d > 4. (77) K_n =
\begin{cases}
n^{1-\frac{2d}{(d+4)(d+2)}}(\log n)^{\frac{d}{2(d+2)}}, & 2 \le d < 4,\\
n^{5/6}(\log n)^{2/3}, & d = 4,\\
n^{\frac{d+1}{d+2}}(\log n)^{\frac{d}{2(d+2)}}, & d > 4.
\end{cases} \tag*{(77)} K n = ⎩ ⎨ ⎧ n 1 − ( d + 4 ) ( d + 2 ) 2 d ( log n ) 2 ( d + 2 ) d , n 5/6 ( log n ) 2/3 , n d + 2 d + 1 ( log n ) 2 ( d + 2 ) d , 2 ≤ d < 4 , d = 4 , d > 4. (77)
For these choices,
R K , n ≤ C r n , d log n , ∣ R K , n − R F , n ∣ ≤ C r n , d 2 , n K n = o ( n 2 ) . (78) R_{K,n} \le Cr_{n,d}\log n,\qquad\lvert R_{K,n}-R_{F,n}\rvert\le Cr_{n,d}^{2},\qquad nK_n=o(n^2). \tag*{(78)} R K , n ≤ C r n , d log n , ∣ R K , n − R F , n ∣ ≤ C r n , d 2 , n K n = o ( n 2 ) . (78)
Proof. The fixed factor m 0 − d / 2 m_0^{-d/2} m 0 − d /2 is included in that constant.
For 2 ≤ d < 4 2 \le d < 4 2 ≤ d < 4 , the leading term becomes
n ( n − 4 / ( d + 4 ) log n ) d / [ 2 ( d + 2 ) ] = n 1 − 2 d ( d + 4 ) ( d + 2 ) ( log n ) d 2 ( d + 2 ) . n\left(n^{-4/(d+4)}\log n\right)^{d/[2(d+2)]}
= n^{1-\frac{2d}{(d+4)(d+2)}}(\log n)^{\frac{d}{2(d+2)}}. n ( n − 4/ ( d + 4 ) log n ) d / [ 2 ( d + 2 )] = n 1 − ( d + 4 ) ( d + 2 ) 2 d ( log n ) 2 ( d + 2 ) d .
For d = 4 d=4 d = 4 , it is n { n − 1 / 2 ( log n ) 2 } 1 / 3 = n 5 / 6 ( log n ) 2 / 3 n\{n^{-1/2}(\log n)^2\}^{1/3}=n^{5/6}(\log n)^{2/3} n { n − 1/2 ( log n ) 2 } 1/3 = n 5/6 ( log n ) 2/3 . For d > 4 d>4 d > 4 , it is
n ( n − 2 / d log n ) d / [ 2 ( d + 2 ) ] = n d + 1 d + 2 ( log n ) d 2 ( d + 2 ) . n\left(n^{-2/d}\log n\right)^{d/[2(d+2)]}
= n^{\frac{d+1}{d+2}}(\log n)^{\frac{d}{2(d+2)}}. n ( n − 2/ d log n ) d / [ 2 ( d + 2 )] = n d + 2 d + 1 ( log n ) 2 ( d + 2 ) d .
Each polynomial exponent is strictly between zero and one, so the additive log n \log n log n is lower order and each choice has K n = o ( n ) K_n=o(n) K n = o ( n ) .
Optimization Procedures
We gives the relevant optimization formulation, our used numerical method, and the stopping rules used in our experiments. The same method handles the full and KNN estimators. We first define the problem and augmented Lagrangian, then explain the inner Newton solves, acceptance tests, and continuation between problems. The final algorithm summarizes these steps.
Regression problem and notation
Given observations ( X i , Y i ) ∈ R d × R (X_i,Y_i)\in\mathbb{R}^d\times\mathbb{R} ( X i , Y i ) ∈ R d × R , i = 1 , … , n i=1,\ldots,n i = 1 , … , n , write Y = ( Y 1 , … , Y n ) ⊤ Y=(Y_1,\ldots,Y_n)^\top Y = ( Y 1 , … , Y n ) ⊤ and let W W W be a set of directed pairs ( j , i ) (j,i) ( j , i ) with j ≠ i j\ne i j = i . The source j j j specifies a supporting plane and the target i i i specifies where it is constrained. Collect the unknown fitted values in θ = ( θ 1 , … , θ n ) ⊤ \theta=(\theta_1,\ldots,\theta_n)^\top θ = ( θ 1 , … , θ n ) ⊤ and slopes in G = ( g 1 , … , g n ) G=(g_1,\ldots,g_n) G = ( g 1 , … , g n ) , with g i ∈ R d g_i\in\mathbb{R}^d g i ∈ R d . We solve
min θ , G Φ n ( θ , G ) = 1 2 ∑ i = 1 n ( θ i − Y i ) 2 + μ n 2 ∑ i = 1 n ∥ g i ∥ 2 , \min_{\theta,G}\quad\Phi_n(\theta,G)=\frac{1}{2}\sum_{i=1}^{n}(\theta_i-Y_i)^2+\frac{\mu_n}{2}\sum_{i=1}^{n}\lVert g_i\rVert^2, θ , G min Φ n ( θ , G ) = 2 1 i = 1 ∑ n ( θ i − Y i ) 2 + 2 μ n i = 1 ∑ n ∥ g i ∥ 2 ,
subject to θ j − θ i + g j ⊤ ( X i − X j ) ≤ 0 , ( j , i ) ∈ W , \text{subject to}\quad\theta_j-\theta_i+g_j^\top(X_i-X_j)\le0,\quad(j,i)\in W, subject to θ j − θ i + g j ⊤ ( X i − X j ) ≤ 0 , ( j , i ) ∈ W ,
∣ θ i ∣ ≤ B , ∥ g i ∥ 2 ≤ L , i = 1 , … , n . (79) \lvert\theta_i\rvert\le B,\quad\lVert g_i\rVert_2\le L,\quad i=1,\ldots,n. \tag*{(79)} ∣ θ i ∣ ≤ B , ∥ g i ∥ 2 ≤ L , i = 1 , … , n . (79)
For notational simplicity, we stack the column vectors as w = ( θ ⊤ , g 1 ⊤ , … , g n ⊤ ) ⊤ ∈ R p w=(\theta^\top,g_1^\top,\ldots,g_n^\top)^\top\in\mathbb{R}^p w = ( θ ⊤ , g 1 ⊤ , … , g n ⊤ ) ⊤ ∈ R p , with p = n ( d + 1 ) p=n(d+1) p = n ( d + 1 ) , and define
t = ( Y , 0 ) , H = diag ( I n , μ n I n d ) , ( C W w ) j i = θ j − θ i + g j ⊤ ( X i − X j ) . t=(Y,0),\qquad H=\operatorname{diag}(I_n,\mu_n I_{nd}),\qquad(C_Ww)_{ji}=\theta_j-\theta_i+g_j^\top(X_i-X_j). t = ( Y , 0 ) , H = diag ( I n , μ n I n d ) , ( C W w ) j i = θ j − θ i + g j ⊤ ( X i − X j ) .
Here I q I_q I q is the q × q q\times q q × q identity, t t t appends n d nd n d zeros to Y Y Y , and C W C_W C W is a linear map from R p \mathbb{R}^p R p to R ∣ W ∣ \mathbb{R}^{\lvert W\rvert} R ∣ W ∣ . Then, we can write our objection function Φ n ( w ) = 1 2 ( w − t ) ⊤ H ( w − t ) \Phi_n(w)=\frac{1}{2}(w-t)^\top H(w-t) Φ n ( w ) = 2 1 ( w − t ) ⊤ H ( w − t ) ; C W w C_Ww C W w are residual inequalities. Let C = { w : ∣ θ i ∣ ≤ B , ∥ g i ∥ 2 ≤ L } C=\{w:\lvert\theta_i\rvert\le B,\ \lVert g_i\rVert_2\le L\} C = { w : ∣ θ i ∣ ≤ B , ∥ g i ∥ 2 ≤ L } . Its Euclidean projection Π C \Pi_C Π C clips each fitted value to [ − B , B ] [-B,B] [ − B , B ] and maps each slope g i g_i g i to g i min { 1 , L / ∥ g i ∥ 2 } g_i\min\{1,L/\lVert g_i\rVert_2\} g i min { 1 , L / ∥ g i ∥ 2 } , leaving zero slopes unchanged.
Augmented Lagrangian updates
We introduce an auxiliary edge vector z ∈ R ∣ W ∣ z \in\mathbb{R}^{|W|} z ∈ R ∣ W ∣ and a copy v ∈ R p v \in\mathbb{R}^{p} v ∈ R p of the fitted values and slopes. Write R − ∣ W ∣ = { z : z e ≤ 0 for every e } \mathbb{R}^{|W|}_{-} = \{z : z_e \le0 \text{ for every } e\} R − ∣ W ∣ = { z : z e ≤ 0 for every e } , and let δ S ( u ) \delta_S(u) δ S ( u ) equal zero when u ∈ S u \in S u ∈ S and + ∞ +\infty + ∞ otherwise. The convex regression problem is equivalently
min w , z , v Φ n ( w ) + δ R − ∣ W ∣ ( z ) + δ C ( v ) subject to C W w − z = 0 , w − v = 0. (80) \min_{w,z,v}\ \Phi_n(w) + \delta_{\mathbb{R}^{|W|}_{-}}(z) + \delta_C(v)\quad\text{subject to}\quad C_Ww-z=0,\quad w-v=0. \tag*{(80)} w , z , v min Φ n ( w ) + δ R − ∣ W ∣ ( z ) + δ C ( v ) subject to C W w − z = 0 , w − v = 0. (80)
The two auxiliary variables separate the simple sign and bound constraints from the linear equalities linking them to w w w .
For equality multipliers λ ∈ R ∣ W ∣ \lambda\in\mathbb{R}^{|W|} λ ∈ R ∣ W ∣ and ν ∈ R p \nu\in\mathbb{R}^{p} ν ∈ R p , and penalty σ > 0 \sigma> 0 σ > 0 , define
L σ ( w , z , v ; λ , ν ) = Φ n ( w ) + δ R − ∣ W ∣ ( z ) + δ C ( v ) + λ T ( C W w − z ) + ν T ( w − v ) + σ 2 ∥ C W w − z ∥ 2 2 + σ 2 ∥ w − v ∥ 2 2 . (81) \begin{aligned}
\mathcal{L}_{\sigma}(w,z,v;\lambda,\nu)
&= \Phi_n(w) + \delta_{\mathbb{R}^{|W|}_{-}}(z) + \delta_C(v) \\
&\quad+ \lambda^{\mathsf{T}}(C_Ww-z) + \nu^{\mathsf{T}}(w-v) \\
&\quad+ \frac{\sigma}{2}\lVert C_Ww-z\rVert_2^2 + \frac{\sigma}{2}\lVert w-v\rVert_2^2. \tag*{(81)}
\end{aligned} L σ ( w , z , v ; λ , ν ) = Φ n ( w ) + δ R − ∣ W ∣ ( z ) + δ C ( v ) + λ T ( C W w − z ) + ν T ( w − v ) + 2 σ ∥ C W w − z ∥ 2 2 + 2 σ ∥ w − v ∥ 2 2 . (81)
At outer iteration k k k , we hold λ k , ν k , σ k \lambda^k,\nu^k,\sigma_k λ k , ν k , σ k fixed and minimize
L σ k ( w , z , v ; λ k , ν k ) + η 2 σ k ∥ w − w k ∥ 2 2 , \mathcal{L}_{\sigma_k}(w,z,v;\lambda^k,\nu^k) + \frac{\eta}{2\sigma_k}\lVert w-w^k\rVert_2^2, L σ k ( w , z , v ; λ k , ν k ) + 2 σ k η ∥ w − w k ∥ 2 2 ,
for a set η \eta η . For any fixed w w w , the minimizing z z z and v v v are available explicitly. For example, completing the square gives
( λ k ) T ( C W w − z ) + σ k 2 ∥ C W w − z ∥ 2 2 = σ k 2 ∥ C W w + λ k / σ k − z ∥ 2 2 − ∥ λ k ∥ 2 2 2 σ k . (\lambda^k)^{\mathsf{T}}(C_Ww-z) + \frac{\sigma_k}{2}\lVert C_Ww-z\rVert_2^2
= \frac{\sigma_k}{2}\lVert C_Ww+\lambda^k/\sigma_k-z\rVert_2^2-\frac{\lVert\lambda^k\rVert_2^2}{2\sigma_k}. ( λ k ) T ( C W w − z ) + 2 σ k ∥ C W w − z ∥ 2 2 = 2 σ k ∥ C W w + λ k / σ k − z ∥ 2 2 − 2 σ k ∥ λ k ∥ 2 2 .
Thus minimizing over z ≤ 0 z \le0 z ≤ 0 is a projection onto the negative orthant; the same calculation for v ∈ C v \in C v ∈ C gives
z k ( w ) = min { C W w + λ k / σ k , 0 } , v k ( w ) = Π C ( w + ν k / σ k ) , (82) \begin{aligned}
z_k(w) &= \min\{C_Ww+\lambda^k/\sigma_k,0\},\\
v_k(w) &= \Pi_C(w+\nu^k/\sigma_k), \tag*{(82)}
\end{aligned} z k ( w ) v k ( w ) = min { C W w + λ k / σ k , 0 } , = Π C ( w + ν k / σ k ) , (82)
where the minimum is componentwise. By denoting dist ( u , C ) = ∥ u − Π C u ∥ 2 \operatorname{dist}(u,C)=\lVert u-\Pi_Cu\rVert_2 dist ( u , C ) = ∥ u − Π C u ∥ 2 . Substituting these exact minimizers leaves the following subproblem in w w w alone:
ψ k ( w ) = Φ n ( w ) + ∥ [ λ k + σ k C W w ] + ∥ 2 2 2 σ k + σ k 2 dist 2 ( w + ν k / σ k , C ) + η 2 σ k ∥ w − w k ∥ 2 2 . (83) \begin{aligned}
\psi_k(w)
&= \Phi_n(w) + \frac{\lVert[\lambda^k+\sigma_kC_Ww]_+\rVert_2^2}{2\sigma_k}
+ \frac{\sigma_k}{2}\operatorname{dist}^2(w+\nu^k/\sigma_k,C)
+ \frac{\eta}{2\sigma_k}\lVert w-w^k\rVert_2^2. \tag*{(83)}
\end{aligned} ψ k ( w ) = Φ n ( w ) + 2 σ k ∥[ λ k + σ k C W w ] + ∥ 2 2 + 2 σ k dist 2 ( w + ν k / σ k , C ) + 2 σ k η ∥ w − w k ∥ 2 2 . (83)
The omitted constant is − ( ∥ λ k ∥ 2 2 + ∥ ν k ∥ 2 2 ) / ( 2 σ k ) -(\lVert\lambda^k\rVert_2^2+\lVert\nu^k\rVert_2^2)/(2\sigma_k) − (∥ λ k ∥ 2 2 + ∥ ν k ∥ 2 2 ) / ( 2 σ k ) , which has no effect on the minimizing w w w . The proximal term stabilizes the iteration around w k w^k w k ; it does not change the regression objective. Semismooth Newton is used to minimize this reduced function ψ k \psi_k ψ k .
Updating the multipliers. Minimizing (82) gives us a new update w k + 1 w^{k+1} w k + 1 . We then update v k + 1 v^{k+1} v k + 1 , λ k + 1 \lambda^{k+1} λ k + 1 , and ν k + 1 \nu^{k+1} ν k + 1 with:
v k + 1 = Π C ( w k + 1 + ν k / σ k ) , λ k + 1 = [ λ k + σ k C W w k + 1 ] + , ν k + 1 = ν k + σ k ( w k + 1 − v k + 1 ) . (84) \begin{aligned}
v^{k+1} &= \Pi_C(w^{k+1}+\nu^k/\sigma_k),\\
\lambda^{k+1} &= [\lambda^k+\sigma_kC_Ww^{k+1}]_+,\\
\nu^{k+1} &= \nu^k+\sigma_k(w^{k+1}-v^{k+1}). \tag*{(84)}
\end{aligned} v k + 1 λ k + 1 ν k + 1 = Π C ( w k + 1 + ν k / σ k ) , = [ λ k + σ k C W w k + 1 ] + , = ν k + σ k ( w k + 1 − v k + 1 ) . (84)
The projection formula makes λ k + 1 \lambda^{k+1} λ k + 1 nonnegative, even though equality multipliers are unrestricted in the split formulation. The vector v k + 1 v^{k+1} v k + 1 supplies the current bound-constrained model. To adjust the penalty, define
r k + 1 2 = ∥ λ k + 1 − λ k ∥ 2 2 σ k 2 + ∥ w k + 1 − v k + 1 ∥ 2 2 , r 0 = ∞ . r_{k+1}^2=\frac{\lVert\lambda^{k+1}-\lambda^k\rVert_2^2}{\sigma_k^2}+\lVert w^{k+1}-v^{k+1}\rVert_2^2,\qquad r_0=\infty. r k + 1 2 = σ k 2 ∥ λ k + 1 − λ k ∥ 2 2 + ∥ w k + 1 − v k + 1 ∥ 2 2 , r 0 = ∞.
If r k + 1 > 0.7 r k r_{k+1}>0.7r_k r k + 1 > 0.7 r k , we set σ k + 1 = min { 2 σ k , 10 5 } \sigma_{k+1}=\min\{2\sigma_k,10^5\} σ k + 1 = min { 2 σ k , 1 0 5 } ; otherwise we retain σ k \sigma_k σ k . This residual controls penalty adjustment. Final acceptance uses the objective or risk prediction tests below.
Objective and prediction stopping rules
We define the stopping of our algorithm with two procedures:
Objective convergence. Let Φ n ∗ ( W ) \Phi_n^*(W) Φ n ∗ ( W ) denote the minimum objective in (79) . For any λ ≥ 0 \lambda\ge0 λ ≥ 0 , define the bounded Lagrangian value
q W ( λ ) = min u ∈ C { Φ n ( u ) + λ ⊤ C W u } . q_W(\lambda)=\min_{u\in C}\{\Phi_n(u)+\lambda^\top C_Wu\}. q W ( λ ) = u ∈ C min { Φ n ( u ) + λ ⊤ C W u } .
At any feasible u u u , the multiplier term is nonpositive, so q W ( λ ) ≤ Φ n ∗ ( W ) q_W(\lambda)\le\Phi_n^*(W) q W ( λ ) ≤ Φ n ∗ ( W ) . Completing the square gives its minimizer and value explicitly:
w ( λ ) = Π C ( t − H − 1 C W ⊤ λ ) , q W ( λ ) = Φ n ( w ( λ ) ) + λ ⊤ C W w ( λ ) . (85) \begin{aligned}
w(\lambda)&=\Pi_C(t-H^{-1}C_W^\top\lambda),\\
q_W(\lambda)&=\Phi_n(w(\lambda))+\lambda^\top C_Ww(\lambda). \tag*{(85)}
\end{aligned} w ( λ ) q W ( λ ) = Π C ( t − H − 1 C W ⊤ λ ) , = Φ n ( w ( λ )) + λ ⊤ C W w ( λ ) . (85)
The Euclidean projection in the first equality is valid because H H H is scalar on each value and slope block. We retain the largest encountered value D = q W ( λ ) D=q_W(\lambda) D = q W ( λ ) and the smallest objective U = Φ n ( w f e a s ) U=\Phi_n(w^{\mathrm{feas}}) U = Φ n ( w feas ) of a model satisfying every target constraint. Thus D ≤ Φ n ∗ ( W ) ≤ U D\le\Phi_n^*(W)\le U D ≤ Φ n ∗ ( W ) ≤ U . Initially D = q W ( 0 ) D=q_W(0) D = q W ( 0 ) and U = Φ n ( 0 ) U=\Phi_n(0) U = Φ n ( 0 ) ; subsequently we keep the best bound of each kind, together with its generating multiplier or model. After each completed outer update, we define our algorithm to have objective convergence if
( U − D ) / n ≤ 10 − 4 . (86) (U-D)/n\le10^{-4}. \tag*{(86)} ( U − D ) / n ≤ 1 0 − 4 . (86)
Risk convergence. A second stopping route addresses our prediction comparison directly. We used m = 4096 m=4096 m = 4096 independent monitoring points Z j Z_j Z j drawn from the design distribution and their noiseless truth values f 0 ( Z j ) f_0(Z_j) f 0 ( Z j ) . This sample is fixed throughout a fit and is independent of training and final testing. After each completed outer update of our augmented Lagrangian method, we evaluate the candidate predictor f ℓ f_\ell f ℓ and its monitoring risk
R ^ ℓ = 1 m ∑ j = 1 m ( f ℓ ( Z j ) − f 0 ( Z j ) ) 2 . \widehat{R}_\ell=\frac{1}{m}\sum_{j=1}^{m}(f_\ell(Z_j)-f_0(Z_j))^2. R ℓ = m 1 j = 1 ∑ m ( f ℓ ( Z j ) − f 0 ( Z j ) ) 2 .
Let I ℓ \mathcal{I}_\ell I ℓ index the latest five consecutive valid checks, and set R ~ ℓ = median a ∈ I ℓ R ^ a \widetilde{R}_\ell=\operatorname{median}_{a\in\mathcal{I}_\ell}\widehat{R}_a R ℓ = median a ∈ I ℓ R a and T ℓ = 10 − 8 + 10 − 4 R ~ ℓ T_\ell=10^{-8}+10^{-4}\widetilde{R}_\ell T ℓ = 1 0 − 8 + 1 0 − 4 R ℓ . We risk convergence, we require both
max a ∈ I ℓ R ^ a − min a ∈ I ℓ R ^ a ≤ T ℓ , max a , b ∈ I ℓ 1 m ∑ j ( f a ( Z j ) − f b ( Z j ) ) 2 ≤ T ℓ . (87) \max_{a\in\mathcal{I}_\ell}\widehat{R}_a-\min_{a\in\mathcal{I}_\ell}\widehat{R}_a\le T_\ell,\qquad
\max_{a,b\in\mathcal{I}_\ell}\frac{1}{m}\sum_j(f_a(Z_j)-f_b(Z_j))^2\le T_\ell. \tag*{(87)} a ∈ I ℓ max R a − a ∈ I ℓ min R a ≤ T ℓ , a , b ∈ I ℓ max m 1 j ∑ ( f a ( Z j ) − f b ( Z j ) ) 2 ≤ T ℓ . (87)
Upon success we return the lowest-monitoring-risk model in the final five-check window, breaking exact ties in favor of the most recent model.
Algorithm summary
Algorithm 1 summarizes the solve for a fixed edge set W W W . All its updates and acceptance tests are defined above. For a full fit using constraint generation, this algorithm solves each working-set problem; the wrapper applies the full-target checks before accepting the full fit.
Detailed experimental design
We specifies our experimental procedures in this appendix
Synthetic truth families
The primary domain is Ω = [ − 2 , 2 ] d \Omega=[-2,2]^d Ω = [ − 2 , 2 ] d , with independent uniform designs in dimensions d ∈ { 2 , 3 , 4 , 5 , 6 , 8 , 10 } d\in\{2,3,4,5,6,8,10\} d ∈ { 2 , 3 , 4 , 5 , 6 , 8 , 10 } . The benchmark amplitude is A = 8 A=8 A = 8 ; we use the symbol A A A here to distinguish the prescribed truth scale from the optimization bound B B B . All four families below use the fixed common optimization bounds A = 8 A=8 A = 8 with B = 10 B=10 B = 10 and L = 2 B / d = 20 / d L=2B/\sqrt{d}=20/\sqrt{d} L = 2 B / d = 20/ d for each fixed dimension.
Algorithm 1 Augmented Lagrangian with semismooth Newton subproblems
Require: X , Y , W , B , L , μ n X,Y,W,B,L,\mu_n X , Y , W , B , L , μ n ; data { ( Z j , f 0 ( Z j ) ) } j = 1 n \{(Z_j,f_0(Z_j))\}_{j=1}^n {( Z j , f 0 ( Z j )) } j = 1 n .
Initialize w 0 , λ 0 , ν 0 , σ 0 w^0,\lambda^0,\nu^0,\sigma_0 w 0 , λ 0 , ν 0 , σ 0 as above, or warm-start.
for k = 0 , 1 , … k=0,1,\ldots k = 0 , 1 , … do
Approximately minimize ψ k \psi_k ψ k using semismooth Newton and backtracking.
If the inner accuracy test fails, stop with an unresolved status.
Update v k + 1 , λ k + 1 , ν k + 1 v^{k+1},\lambda^{k+1},\nu^{k+1} v k + 1 , λ k + 1 , ν k + 1 by (83).
Update the feasible upper bound U U U and dual lower bound D D D .
Check the objective gap and risk convergence.
If accepted, return the selected predictor and its convergence label.
Adjust σ k + 1 \sigma_{k+1} σ k + 1 using r k + 1 r_{k+1} r k + 1 and r k r_k r k .
end for
If no acceptance test passes, record an unresolved fit.
The full and half quadratics
The functions in Balázs et al. [4 ] are
f Q ( x ) = − A + A 2 d ∑ j = 1 d x j 2 , f H ( x ) = − A + A 2 d ∑ j = 1 d max { x j , 0 } 2 . (88) f_{\mathrm{Q}}(x)=-A+\frac{A}{2d}\sum_{j=1}^{d}x_j^2,\qquad f_{\mathrm{H}}(x)=-A+\frac{A}{2d}\sum_{j=1}^{d}\max\{x_j,0\}^2. \tag*{(88)} f Q ( x ) = − A + 2 d A j = 1 ∑ d x j 2 , f H ( x ) = − A + 2 d A j = 1 ∑ d max { x j , 0 } 2 . (88)
For x ∈ [ − 2 , 2 ] d x\in[-2,2]^d x ∈ [ − 2 , 2 ] d , both sums in (88) lie between zero and 4 d 4d 4 d , so both truths lie in [ − A , A ] [-A,A] [ − A , A ] . The full quadratic has
∇ f Q ( x ) = A d x , ∇ 2 f Q ( x ) = A d I d . \nabla f_{\mathrm{Q}}(x)=\frac{A}{d}x,\qquad\nabla^2 f_{\mathrm{Q}}(x)=\frac{A}{d}I_d. ∇ f Q ( x ) = d A x , ∇ 2 f Q ( x ) = d A I d .
It is therefore ( A / d ) (A/d) ( A / d ) -strongly convex, with Lipschitz constant at most ( A / d ) 2 d = 2 A / d (A/d)2\sqrt{d}=2A/\sqrt{d} ( A / d ) 2 d = 2 A / d on the cube. Since d d d is fixed in each asymptotic experiment, m 0 = A / d m_0=A/d m 0 = A / d is a fixed positive curvature floor.
The scalar function t ↦ max { t , 0 } 2 t\mapsto\max\{t,0\}^2 t ↦ max { t , 0 } 2 is continuously differentiable, with derivative 2 max { t , 0 } 2\max\{t,0\} 2 max { t , 0 } . Its derivative is nondecreasing, so the scalar function is convex. We sum coordinatewise to obtain convexity of f H f_{\mathrm{H}} f H and
∇ f H ( x ) = A d x + , ∥ ∇ f H ( x ) ∥ 2 ≤ 2 A d . \nabla f_{\mathrm{H}}(x)=\frac{A}{d}x_+,\qquad\|\nabla f_{\mathrm{H}}(x)\|_2\le\frac{2A}{\sqrt{d}}. ∇ f H ( x ) = d A x + , ∥∇ f H ( x ) ∥ 2 ≤ d 2 A .
On ( − 2 , 0 ) d (-2,0)^d ( − 2 , 0 ) d it is identically − A -A − A , ruling out any positive global strong-convexity constant. It has a change in curvature at coordinate hyperplanes, but its gradient is continuous; it should not be described as a max-affine slope kink.
A fixed finite collection of planes
For M ∈ { 5 , 10 , 25 , 50 } M\in\{5,10,25,50\} M ∈ { 5 , 10 , 25 , 50 } , we use
f M A ( x ) = max 1 ≤ m ≤ M { a m T x + b m } . f_{\mathrm{MA}}(x)=\max_{1\le m\le M}\{a_m^\mathsf{T}x+b_m\}. f MA ( x ) = 1 ≤ m ≤ M max { a m T x + b m } .
We generate coefficients before drawing any regression data and save them. To actually generate the coefficients, we draw independent directions uniformly on the Euclidean unit sphere, sets a m a_m a m to 2 / d 2/\sqrt{d} 2/ d times the direction, and draws b m b_m b m uniformly on [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] . Each coefficient realization is held fixed across the sample-size sweep and all training replications for that realization.
For every generated piece,
∣ a m T x + b m ∣ ≤ 2 d ( 2 d ) + 1 = 5 , ∥ a m ∥ 2 = 2 d . |a_m^\mathsf{T}x+b_m|\le\frac{2}{\sqrt{d}}(2\sqrt{d})+1=5,\qquad\|a_m\|_2=\frac{2}{\sqrt{d}}. ∣ a m T x + b m ∣ ≤ d 2 ( 2 d ) + 1 = 5 , ∥ a m ∥ 2 = d 2 .
Thus ∣ f M A ∣ ≤ 5 ≤ B |f_{\mathrm{MA}}|\le5\le B ∣ f MA ∣ ≤ 5 ≤ B and Lip ( f M A ) ≤ 2 / d ≤ L \operatorname{Lip}(f_{\mathrm{MA}})\le2/\sqrt{d}\le L Lip ( f MA ) ≤ 2/ d ≤ L . The maximum is convex, and it is not strongly convex because at least one full-dimensional affine region has nonempty interior. Due to the generation procedure, it is possible that some generated pieces we completely inactive, but we do not resolve this issue.
The quadratic-interpolation hard family
The random-design lower-bound construction of Kur et al. [21 ] uses piecewise-affine interpolation of a quadratic, with approximation scale k − 2 / d k^{-2/d} k − 2/ d and a complexity parameter of order n \sqrt{n} n at fixed noise level. For an integer J ≥ 2 J \ge2 J ≥ 2 , we let
h J = 4 / J , t k = − 2 + k h J ( k = 0 , … , J ) , h_J = 4/J,\qquad t_k = -2 + kh_J\quad(k = 0,\ldots,J), h J = 4/ J , t k = − 2 + k h J ( k = 0 , … , J ) ,
and define
q J ( t ) = max 0 ≤ k < J { ( t k + t k + 1 ) t − t k t k + 1 } , − 2 ≤ t ≤ 2. (89) q_J(t) = \max_{0 \le k < J}\left\{(t_k+t_{k+1})t-t_kt_{k+1}\right\},\qquad-2 \le t \le2. \tag*{(89)} q J ( t ) = 0 ≤ k < J max { ( t k + t k + 1 ) t − t k t k + 1 } , − 2 ≤ t ≤ 2. (89)
The k k k th affine term is the chord joining ( t k , t k 2 ) (t_k,t_k^2) ( t k , t k 2 ) and ( t k + 1 , t k + 1 2 ) (t_{k+1},t_{k+1}^2) ( t k + 1 , t k + 1 2 ) . Consecutive slopes increase by 2 h J 2h_J 2 h J , and the k k k th term is active on [ t k , t k + 1 ] [t_k,t_{k+1}] [ t k , t k + 1 ] . This follows directly by subtracting two adjacent terms: the ( k + 1 ) (k+1) ( k + 1 ) st term minus the k k k th term is 2 h J ( t − t k + 1 ) 2h_J(t-t_{k+1}) 2 h J ( t − t k + 1 ) . The maximum in (89) is therefore the ordinary convex linear interpolant of t 2 t^2 t 2 .
We define
f h a r d , J ( x ) = − A + A 2 d ∑ j = 1 d q J ( x j ) , A = 8. (90) f_{\mathrm{hard},J}(x)=-A+\frac{A}{2d}\sum_{j=1}^{d}q_J(x_j),\qquad A=8. \tag*{(90)} f hard , J ( x ) = − A + 2 d A j = 1 ∑ d q J ( x j ) , A = 8. (90)
The sum of the coordinatewise maxima can be written as a single maximum of J d J^d J d affine functions:
f h a r d , J ( x ) = max k ∈ { 0 , … , J − 1 } d { − A + A 2 d ∑ j = 1 d [ ( t k j + t k j + 1 ) x j − t k j t k j + 1 ] } . f_{\mathrm{hard},J}(x)=\max_{k\in\{0,\ldots,J-1\}^{d}}\left\{-A+\frac{A}{2d}\sum_{j=1}^{d}\left[(t_{k_j}+t_{k_j+1})x_j-t_{k_j}t_{k_j+1}\right]\right\}. f hard , J ( x ) = k ∈ { 0 , … , J − 1 } d max { − A + 2 d A j = 1 ∑ d [ ( t k j + t k j + 1 ) x j − t k j t k j + 1 ] } .
Each open grid cube has one distinct active affine function. The truth agrees with f Q f_Q f Q at all grid vertices and is affine throughout every grid cube, hence on any simplicial subdivision of those cubes. It is thus a concrete cube realization of the quadratic-interpolation construction, with explicitly verified convexity. It is an interpolating secant construction, not an arbitrary maximum of supporting tangent planes.
For t ∈ [ t k , t k + 1 ] t\in[t_k,t_{k+1}] t ∈ [ t k , t k + 1 ] , direct subtraction gives
q J ( t ) − t 2 = ( t − t k ) ( t k + 1 − t ) . q_J(t)-t^2=(t-t_k)(t_{k+1}-t). q J ( t ) − t 2 = ( t − t k ) ( t k + 1 − t ) .
The product is nonnegative and at most h J 2 / 4 h_J^2/4 h J 2 /4 . We sum over coordinates to obtain
0 ≤ f h a r d , J ( x ) − f Q ( x ) ≤ A h J 2 8 = h J 2 = 16 J 2 . (91) 0\le f_{\mathrm{hard},J}(x)-f_Q(x)\le\frac{Ah_J^2}{8}=h_J^2=\frac{16}{J^2}. \tag*{(91)} 0 ≤ f hard , J ( x ) − f Q ( x ) ≤ 8 A h J 2 = h J 2 = J 2 16 . (91)
The interpolation values lie in [ 0 , 4 ] [0,4] [ 0 , 4 ] and ∣ t k + t k + 1 ∣ ≤ 4 \lvert t_k+t_{k+1}\rvert\le4 ∣ t k + t k + 1 ∣ ≤ 4 , so f h a r d , J ∈ [ − A , A ] f_{\mathrm{hard},J}\in[-A,A] f hard , J ∈ [ − A , A ] and every affine slope has norm at most 2 A / d 2A/\sqrt{d} 2 A / d . These bounds hold uniformly in J J J . Since the function is affine on nonempty open cells, it has no positive global curvature floor.
For the principal high-dimensional stress test, we use
J n = max { 2 , ⌈ n 1 / ( 2 d ) ⌉ } , f 0 , n = f h a r d , J n , M n = J n d . J_n=\max\left\{2,\left\lceil n^{1/(2d)}\right\rceil\right\},\qquad f_{0,n}=f_{\mathrm{hard},J_n},\qquad M_n=J_n^d. J n = max { 2 , ⌈ n 1/ ( 2 d ) ⌉ } , f 0 , n = f hard , J n , M n = J n d .
Then M n ≍ n M_n\asymp\sqrt{n} M n ≍ n , the sup-norm approximation error to f Q f_Q f Q is O ( n − 1 / d ) O(n^{-1/d}) O ( n − 1/ d ) , and its squared population discrepancy from f Q f_Q f Q is O ( n − 2 / d ) O(n^{-2/d}) O ( n − 2/ d ) . Integer rounding makes J n J_n J n piecewise constant at accessible sample sizes, especially in large dimension, so record the actual pair ( J n , M n ) (J_n,M_n) ( J n , M n ) in every run. A fixed-grid experiment with J J J held constant is a distinct, fixed-truth control. Both designs choose the truth independently of all regression observations.
This changing-truth family is valid for our uniform upper theorem: for every n n n , f 0 , n f_{0,n} f 0 , n belongs to the same fixed class F B , L ( Ω ) \mathcal{F}_{B,L}(\Omega) F B , L ( Ω ) . Its observed risk curve is not a pointwise asymptotic curve for one fixed truth. The lower-bound result in the cited paper concerns its specified LSEs and appropriately chosen construction constants; we do not transfer that lower bound to our regularized programs or claim that every finite grid is least favorable. The experiment probes the mechanism of that construction and the full/KNN comparison.
Sample sizes, regularization, and neighborhood grids
For each fixed dimension, we use independent training replications at
n = { 250 , 300 , 400 , 500 , 600 , 700 , 800 , 900 , 1000 , 1500 , 2000 , 2500 , 3000 } (92) n = \{250,300,400,500,600,700,800,900,1000,1500,2000,2500,3000\} \tag*{(92)} n = { 250 , 300 , 400 , 500 , 600 , 700 , 800 , 900 , 1000 , 1500 , 2000 , 2500 , 3000 } (92)
with 30 replications as the research configuration. Matching our assumption from 2.3, we set our penalty to
μ n = c μ r n , d / L 2 , c μ = 0.2 , \mu_n = c_\mu r_{n,d}/L^2,\quad c_\mu= 0.2, μ n = c μ r n , d / L 2 , c μ = 0.2 ,
with c μ ∈ { 0.05 , 0.2 , 1 } c_\mu\in\{0.05,0.2,1\} c μ ∈ { 0.05 , 0.2 , 1 } as separately reported sensitivity settings. The values B B B , L L L , d d d , and c μ c_\mu c μ are held fixed within a sample-size sweep. At each n n n , the full and every KNN problem use exactly the same μ n \mu_n μ n ; it is not retuned as K K K changes. Fixed-plane coefficients are generated independently of the training data and reused for all n n n and all replications. The hard family instead uses its explicitly prescribed J n J_n J n and is labelled as a changing-truth experiment.
We denote s ( n , d ) s(n,d) s ( n , d ) denote the sufficient neighborhood schedule found in Theorem 3.2 and 3.4 before multiplying by the constant C K C_K C K . The full quadratic uses s s c s_{\mathrm{sc}} s sc ; the other families use s g e n s_{\mathrm{gen}} s gen . The study grid is the union of n − 1 n-1 n − 1 , ⌈ c × s ( n , d ) ⌉ \lceil c \times s(n,d)\rceil ⌈ c × s ( n , d )⌉ for c ∈ { 0.05 , 0.1 , 0.25 , 0.5 , 1 , 2 } c \in\{0.05,0.1,0.25,0.5,1,2\} c ∈ { 0.05 , 0.1 , 0.25 , 0.5 , 1 , 2 } , and ⌈ n α ⌉ \lceil n^\alpha\rceil ⌈ n α ⌉ for α ∈ { 0.4 , 0.6 , 0.8 , 0.85 , 0.9 , 0.95 } \alpha\in\{0.4,0.6,0.8,0.85,0.9,0.95\} α ∈ { 0.4 , 0.6 , 0.8 , 0.85 , 0.9 , 0.95 } .
Empirical risk-transition experiment
For each truth specification, fixed n n n , d d d , and training replicate b ∈ { 1 , … , R } b \in\{1,\ldots,R\} b ∈ { 1 , … , R } , we use the same training observations for the full estimator and every KNN fit. We evaluate the numerical predictors f ^ b , K \widehat{f}_{b,K} f b , K and f ^ b , F \widehat{f}_{b,F} f b , F at an independent common test set Z b , 1 , … , Z b , M t e s t Z_{b,1},\ldots,Z_{b,M_{\mathrm{test}}} Z b , 1 , … , Z b , M test , using the known noiseless truth. For a completed fit, the final test risk is
L b , K = 1 M t e s t ∑ j = 1 M t e s t ( f ^ b , K ( Z b , j ) − f 0 ( Z b , j ) ) 2 . (93) L_{b,K} = \frac{1}{M_{\mathrm{test}}}\sum_{j=1}^{M_{\mathrm{test}}}\left(\widehat{f}_{b,K}(Z_{b,j})-f_0(Z_{b,j})\right)^2. \tag*{(93)} L b , K = M test 1 j = 1 ∑ M test ( f b , K ( Z b , j ) − f 0 ( Z b , j ) ) 2 . (93)
The same test points are used across K K K within replicate b b b . We then compare the ratio of the KNN and full test risk against K K K .