Bridging Root-$n$ and Non-standard Asymptotics: Adaptive Inference in M-Estimation

Bridging Root-$n$ and Non-standard Asymptotics: Adaptive Inference in M-Estimation

Introduction

The present study examines the inference for the parameter defined as the solution to an optimization problem, commonly referred to as M-estimation, which arises in broad statistical applications. Let $\mathcal{P}$ be a set of probability measures on a measurable space $(\Omega, \mathcal{S})$ with a $\sigma$-algebra $\mathcal{S}$. Let $Z_1, \ldots, Z_n \in \mathcal{Z}$ be a sequence of identically distributed random variables, following an unknown data-generating distribution $P \in\mathcal{P}$. We emphasize that independence is not assumed unless explicitly stated otherwise. Given a metric space $(\Theta, \|\cdot\|)$ and a “criterion” function $\operatorname{\mathbb{M}}: \Theta \times \mathcal{P} \mapsto \mathbb{R}$, the goal of an M-estimation problem is to identify an element $\theta(P) \in \Theta$, which minimizes (or maximizes) the mapping $\theta \mapsto \operatorname{\mathbb{M}}(\theta, P)$. Equivalently, the aim is to estimate

The uniqueness of the solution has not yet been assumed, and $\theta(P)$ in (ref) denotes the set of minimizers. The primary objective of this manuscript is the construction of an honest confidence set Li1989, Ptscher2002Lower for the $P$-dependent minimizer such that

where $\mathbb{P}_P(\cdot)$ denotes the probability of an event under distribution $P$. A finite-sample guarantee such as (ref) is impossible without very strong assumptions on the class of distributions $\mathcal{P}$ bahadur1956nonexistence. One may instead follow the convention in large sample theory and aim for the alternative asymptotic validity guarantee:

In what follows, to reduce notational burden, we use the following convention: \[ \mathbb{P}_P(\theta(P)\in\widehat{\mathrm{CI}}_{n,\alpha}) ~:=~ \inf_{\theta^*\in\theta(P)}\,\mathbb{P}_P(\theta^*\in\widehat{\mathrm{CI}}_{n,\alpha}). \] The method studied in this article satisfies the asymptotic validity guarantee (ref) and additionally retains validity regardless of the dimension/complexity of the functional $\theta(P)$, including the cases where the dimension is comparable to the sample size. This property is termed dimension-agnostic by kim2020dimension.

Commonly used confidence set procedures include (1) the Wald methods based on the limiting distribution of a studied estimator, and (2) the resampling approaches. Both methods require an estimator $\widehat{\theta}_n$ such that for a suitable rate of convergence $r_n$, diverging to $\infty$, $r_n(\widehat{\theta}_n - \theta(P))$ converges in distribution. The Wald methods assume a parametric structure on the limiting distribution and use the quantiles of the estimated parametric limiting distribution to construct the confidence sets. The second (resampling) approach non-parametrically estimates the limiting distribution by resampling the available data. From the extensive study of both approaches in the literature, we know of numerous settings in which the corresponding confidence sets might not satisfy the guarantee of honest inference (ref). In particular, if the weak convergence of the normalized estimator is not “continuous” in $P$, the honest validity guarantee may fail for both Wald and resampling techniques Andrews2000, andrews2010asymptotic, cattaneo2020bootstrap, cattaneo2023bootstrap. An example of such “continuity” condition is the regularity of an estimator van2000asymptotic. We refer to the settings where such “continuity” condition fails (or equivalently, the estimator is ill-behaved) as irregular problems. It may be helpful to clarify that we consider cases where the functional $\theta(P)$ or estimator $\widehat{\theta}_n$ considered is ill-behaved to be irregular.

Inference for M-estimation problems that induce non-standard or irregular asymptotics is a particularly active area of research in econometrics geyer1994asymptotics, Ketz2018,Horowitz2019, Hsieh2022, Li2024. This list is far from exhaustive. To the best of our knowledge, existing methods typically are tailored to specific classes of regularities. For instance, Li2024 proposed a general inferential framework for stochastic optimization, allowing for potentially nonsmooth and non-convex objective functions; however, their approach requires knowledge of the estimator's convergence rate, which depends on unknown regularity, and the quantile of a complex random object must be estimated. vogel2008universal proposes a method closely related to the one in this manuscript; however, their corresponding confidence set often requires stronger regularity assumptions for validity, particularly, with respect to the complexity of $\Theta$. dey2024anytime and park2023robust consider inferential procedures based on the sample-splitting; however, they both require stronger assumptions than those in this manuscript for validity.

This manuscript proposes a simpler approach to inference based on the defining property of the functional and sample-splitting. Sample-splitting has seen renewed interest in recent times for complicated inference problems in several works Robins2006, chakravarti2019gaussian, wasserman2020universal, park2023robust, kim2020dimension, dey2024anytime. By the defining property, we mean (ref), which yields the functional as a minimizer of some population quantity. The method studied at an intuitive level can be derived in two steps as follows: (1) Because $\theta(P)$ minimizes $\theta\mapsto \mathbb{M}(\theta, P)$, we know that $\theta(P)$ is contained in $\{\theta:\, \mathbb{M}(\theta, P) \le \mathbb{M}(\widehat{\theta}, P)\}$ for any $\widehat{\theta}$ in the parameter space; (2) if $\theta\mapsto\widehat{\mathbb{M}}_n(\theta)$ is an estimator of $\mathbb{M}(\theta, P)$, then it is reasonable to expect that $\theta(P)$ would also be contained in $\{\theta:\, \widehat{\mathbb{M}}_n(\theta) \le \widehat{\mathbb{M}}_n(\widehat{\theta}_n) + \gamma_n\}$ for some “appropriate” $\gamma_n$. See Section (ref) for a precise description of the method.

This idea is not new and can be found, for example, in Robins2006 and vogel2008universal; see Section (ref) for some historical developments of this idea. Our contribution to this idea is two-fold. First, we provide a systematic way to obtain a dimension/complexity-agnostic validity guarantee; this is made possible by constructing $\widehat{\mathbb{M}}_n(\cdot)$ and $\widehat{\theta}_n$ on two independent datasets. Second, we analyze the width/diameter of the proposed confidence set under mild conditions and use the general result to prove the rate adaptivity in some examples. The conditions we adopt for width analysis are comparable to those employed in studying the convergence rate of the M-estimator. We believe these results represent a significant advancement in the field of honest and adaptive inference.

The proposed approach offers great flexibility and robustness compared to traditional methods of inference. First, the validity of the method is agnostic to the choice of the initial estimator $\widehat\theta_n$, and more importantly, it does not require any guarantees on its convergence rate or the existence of a limiting distribution. Second, the proposed method does not require knowledge of the convergence rate of the estimator. This is a significant improvement over traditional methods because in irregular problems the rate of convergence is impossible to estimate uniformly consistently. Third, it can accommodate constrained parameter spaces or (data-independent) regularization penalties with no additional modifications; this is because the proposed method is based on thresholding the (real-valued) objective function. Note that the limiting distributions of constrained M-estimators can be significantly complicated wang1996asymptotics.

This flexibility and generality come with a price in two aspects. Although we provide conditions under which the proposed confidence set shrinks to a singleton at the optimal rate adaptively, the proposed confidence set can be larger than the traditional ones due to sample splitting. Moreover, the shape of the confidence set is controlled by the shape of the objective function. Unlike traditional methods that control the shape of the confidence set by considering an appropriate statistic, the proposed confidence set can be non-convex or even disconnected depending on the (estimated) objective function. It might be worth pointing out that, in regular cases, the proposed confidence set will approximately be an ellipsoid in similarity to the likelihood ratio confidence set. Furthermore, we note that the universal inference procedure of wasserman2020universal also shares the same drawbacks.

In summary, the confidence set proposed in this manuscript remains valid even in high-dimensional or irregular problems where the standard approach exhibits non-standard asymptotics. The following statistical problems are a few examples in which inference remains difficult to date and the proposed confidence set provides a simple solution.

While we prove the confidence set shrinks at an adaptive rate, it may not be the best set in terms of constants. Given the level of generality achieved, we do not know if one procedure can be adaptive and also be sharp in constants. We leave this aspect for the future research.

The remainder of this manuscript is organized as follows. Section (ref) formally defines the proposed procedure within a general optimization framework. Section (ref) establishes the foundational theorems on the validity and width of the proposed confidence set. Section (ref) provides an analysis of the confidence set proposed in statistical applications whose inference has been considered challenging. Section (ref) provides numerical results. We end the manuscript with a few concluding remarks in Section (ref).

\paragraph{Notation.} We adopt the following convention. For two real numbers $a$ and $b$, we set $a \vee b = \max\{a, b\}$ and $a \wedge b = \min\{a, b\}$. For $x \in \mathbb{R}^d$, we write $\|x\|_2 = \sqrt{x^\top x}$. In particular, we define the unit sphere with respect to $\|\cdot\|_2$ such that $\mathbb{S}^{d-1} = \{u \in \mathbb{R}^d \, : \, \|u\|_2 =1\}$. Given a square matrix $A \in \mathbb{R}^{d\times d}$, its trace, the smallest and the largest eigenvalues are denoted by $\mathrm{tr}(A)$, $\lambda_{\min}(A)$ and $\lambda_{\max}(A)$ respectively. For a real-valued function $f : \Omega \mapsto \mathbb{R}$, its supremum norm is denoted by $\|f\|_\infty := \sup_{x \in\Omega}|f(x)|$. A standard indicator function is denoted by $\mathbf{1}\{\cdot\}$, i.e., $\mathbf{1}\{x\in A\} = 1$ if $x\in A$ and $0$ if $x\notin A$. For any deterministic sequences $\{x_n\}_{n \ge 1}$ and $\{r_n\}_{n \ge 1}$, we denote $x_n = O(r_n)$ if there exists a universal constant $C>0$ such that $|x_n| \le C|r_n|$ for all $n$ larger than some $N$. Similarly, we denote $x_n = O_P(r_n)$ if, for any $\varepsilon>0$, there exists a constant $C_\varepsilon>0$ such that $\mathbb{P}(|x_n| \le C_\varepsilon|r_n|) \le \varepsilon$ for all $n$ larger than some $N_\varepsilon$. We denote $x_n = o(r_n)$ if $x_n/r_n \to 0$ and $x_n = o_p(r_n)$ if $x_n/r_n \overset{p}{\to} 0$ where $\overset{p}{\to}$ denotes convergence in probability.

Construction of the Confidence Set

Given an identically, but not necessarily independently, distributed observation $Z_1, \ldots, Z_N$, we construct two sets of observations $D_1:= \{Z_i: i \in \mathcal{I}_1\}$ and $D_2:= \{Z_i : i \in \mathcal{I}_2\}$, where $\mathcal{I}_1$ and $\mathcal{I}_2$ are the disjoint partitions of $\{1, \ldots, N\}$. First, we construct any estimator of $\theta(P)$ using $D_1$, defining $\widehat \theta_1 := \widehat \theta_1(D_1) \in \Theta$. We use the first data only to obtain an initial estimator and remain agnostic to the choice of $\widehat \theta_1$. Given this estimator $\widehat \theta_1$, we construct a confidence set using the second data $D_2$. Throughout the manuscript, we denote by $n$ the cardinality of $D_2$ as we primarily use $D_2$ for the inferential task.

As stated in Section (ref), the proposed confidence set is based on the defining property of $\theta(P)$. An ideal (unactionable) confidence set is \[ \widetilde{\mathrm{CI}} := \left\{\theta\in\Theta:\, \mathbb{M}(\theta, P) - \mathbb{M}(\widehat{\theta}_1, P) \le 0\right\}. \] From this, it might be tempting to consider the set

where $\theta\mapsto\widehat{\mathbb{M}}_n(\theta)$ is an estimator of $\mathbb{M}(\theta, P)$ based on $D_2$. If $\widehat{\theta}_1$ is consistent for $\theta(P)$, then the confidence set in (ref) may not have valid coverage, and if $\widehat{\theta}_1$ is not consistent for $\theta(P)$, then this confidence set may not shrink to a singleton as the sample size increases. Nevertheless, we can prove the following result on the coverage validity of the confidence set in (ref), and this can be useful to find a “small” set that contains $\theta(P)$. To state the result, for any $\theta, \theta'\in\Theta$, consider

The quantity $\mathbb{C}_P(\theta)$ represents the curvature of the M-estimation problem. It quantifies the hardness of “estimating” $\theta(P)$. Note that $\mathbb{V}_P(\theta, \theta')$ and $\mathbb{C}_P(\theta)$ are defined for non-stochastic $\theta, \theta'\in\Theta$ and if evaluated at a random point $\widehat{\theta}_1\in\Theta$, these should be considered as random variables.

The proof of Theorem (ref) is provided in Section (ref) and is based on Cantelli's inequality pinelis2010between. Observe that uniqueness of $\theta(P)$ is not required in Theorem (ref). Moreover, the miscoverage bound depends naturally on two aspects of the M-estimation problem: (1) the estimation error of $\widehat{\mathbb{M}}_n(\cdot)$ captured by the mean squared error $\mathbb{V}_P(\cdot, \cdot)$; and (2) the curvature of the problem $\mathbb{C}_P(\cdot)$. Note that, by the definition of $\theta(P)$, $\mathbb{C}_P(\theta) \ge 0$ for all $\theta\in\Theta$. The miscoverage bound is non-decreasing in the estimation error and non-increasing in the curvature of the problem. Because the definition of the confidence set does not depend on any target coverage, the confidence set provides an agnostic bound. To understand the behavior of the miscoverage bound, consider the case when $\mathbb{M}(\theta, P) = \mathbb{E}_P[m_{\theta}(Z)]$ for a loss function $m_{\theta}(Z)$ and $\widehat{\mathbb{M}}_n(\theta) = \sum_{i=1}^n m_{\theta}(Z_i)/n$, $\mathbb{V}_P(\theta, \theta') = \mbox{Var}(m_{\theta}(Z) - m_{\theta'}(Z))/n$. If $n\mathbb{C}_P^2(\widehat{\theta}_1)$ diverges to infinity in probability, while $\mbox{Var}(m_{\theta}(Z) - m_{\widehat{\theta}_1}(Z)|\widehat{\theta}_1)$ is bounded away from zero as $n\to\infty$, then the confidence set in (ref) has an asymptotic confidence of 1. For the special case of loss functions satisfying the so-called Bernstein condition bartlett2006empirical with parameters $(\beta, B)$ with $\beta\in(0, 1]$, i.e., $\mathbb{E}_P[(m_{\theta}(Z) - m_{\theta(P)}(Z))^2] \le B(\mathbb{C}_P(\theta))^{\beta}$, this divergence condition is satisfied if $(n/B)^{1/(2-\beta)}\mathbb{C}_P(\widehat{\theta}_1)$ diverges to infinity in probability as $n\to\infty.$ Note that this divergence condition can be trivially satisfied by taking an inconsistent estimator $\widehat{\theta}_1$ of $\theta(P)$, and the resulting confidence set would be a (non-shrinking) bounded set, in most cases.

For finer control on the coverage guarantee, we modify the confidence set in (ref) as follows. Define random mappings $\theta \mapsto L_{n,\alpha_1}(\theta, \widehat \theta_1; D_2)$ and $\theta \mapsto U_{n,\alpha_2}(\theta, \widehat \theta_1; D_2)$ based on the dataset $D_2$, satisfying the following properties:

and

for any $n\ge 1$ and $\alpha_1, \alpha_2 \in (0,1)$. The final confidence set for $\theta(P)$ is defined as:

where $\alpha := (\alpha_1, \alpha_2)$. In particular, if $\alpha_2 = 0$, then $U_{n,\alpha_2}(\theta(P), \widehat{\theta}_1; D_2)$ can be taken to be zero because the definition of $\theta(P)$ implies $-\mathbb{C}_P(\widehat{\theta}_1) \le 0$ almost surely, and this yields

The following theorem establishes the validity guarantee for the proposed confidence set.

The proof of Theorem (ref) can be found in Section (ref). In situations where constructing a confidence set for $\theta(P)$ seems challenging, it may initially appear puzzling that the proposed approach involves building a (lower) confidence bound for $-\mathbb{C}_P(\widehat{\theta}_1) = \mathbb{M}(\theta(P), P) - \mathbb{M}(\widehat{\theta}_1, P)$. However, recognizing that the confidence set (ref) relies on the random mapping $\theta \mapsto L_{n,\alpha_1}(\theta, \widehat{\theta}_1; D_2)$, it is helpful to reinterpret condition (ref) as

In other words, we need to construct a lower confidence bound for $\mathbb{M}(\theta, P) - \mathbb{M}(\theta', P)$ for every (non-stochastic) pair $\theta, \theta'\in\Theta$. For instance, if $\mathbb{M}(\theta, P) = \mathbb{E}_P[m_{\theta}(Z)]$, then $\mathbb{M}(\theta, P) - \mathbb{M}(\theta', P) = \mathbb{E}_P[m_{\theta}(Z) - m_{\theta'}(Z)]$ for which lower confidence bound can be constructed by the central limit theorem. Because the mapping $\theta \mapsto \operatorname{\mathbb{M}}(\theta, P) - \operatorname{\mathbb{M}}(\widehat \theta_1, P)$ is always real-valued regardless of the complexity of $\Theta$, it is conceivable that the lower confidence limit in (ref) can be constructed without any reference to the complexity of $\Theta$. This is in stark contrast to the “classical” inferential approach based on the weak convergence of $r_n(\widehat \theta_1-\theta(P))$ to some limit process, which often depends heavily on the complexity of $\Theta$.

Comparing the definitions of $\widehat{\mathrm{CI}}_{n}^{\dagger}$ in (ref) and $\widehat{\mathrm{CI}}_{n,\alpha}$ in (ref), one can interpret the naive confidence set in (ref) as using the estimator $\widehat{\mathbb{M}}_n(\theta) - \widehat{\mathbb{M}}_n(\widehat{\theta}_1)$ as $L_{n,\alpha}(\theta, \widehat{\theta}_1; D_2)$. This, in general, does not satisfy the guarantee (ref). In the following section, we consider two methods for constructing lower confidence bounds satisfying (ref): one based on concentration inequalities under the assumption of bounded loss function and the other based on central limit theorem. Both lower bounds are of the form \[ L_{n,\alpha}(\theta, \widehat{\theta}_1; D_2) = \widehat{\mathbb{M}}_n(\theta) - \widehat{\mathbb{M}}_n(\widehat{\theta}_1) - t(\alpha, \theta, \theta'), \] for some non-negative function $t(\cdot, \cdot, \cdot)$. With such non-negativity, it is clear that $\widehat{\mathrm{CI}}_{n,\alpha} \supseteq \widehat{\mathrm{CI}}_{n}^{\dagger}$.

Construction of Lower Confidence Bounds

Section (ref) establishes that the inference on $\theta(P)$, as defined in (ref), can be reduced to the construction of the upper and lower confidence bounds, satisfying (ref) and (ref). Furthermore, Remark (ref) suggests that a valid confidence set can be obtained without estimating the upper confidence bound as the upper bound only plays a role in improving the statistical power. Therefore, the primary focus is on constructing the lower confidence bound, which is essential for ensuring validity. This section presents two general approaches for developing the lower confidence bounds.

Throughout, we introduce an additional structure to the M-estimation shared by many problems such that $\operatorname{\mathbb{M}}(\theta, P)$ corresponds to the expectation of some “loss" function. Formally, we define a measurable function $m_\theta : \mathcal{Z} \mapsto \mathbb{R}$ indexed by $\theta \in \Theta$. We consider the minimization of $m_\theta$ under the expectation with respect to $P$ such that

For example, taking $m_{\theta}(Y,X) := (Y-\theta^\top X)^2$ with $\Theta \equiv \mathbb{R}^d$ corresponds to linear regression while taking $m_{\theta}(Z) := -\log P(Z; \theta)$ for a parametrized family of likelihood functions $P(Z; \theta)$ yields maximum likelihood estimation. This definition arises in many popular situations; however, it does exclude certain classes of M-estimation problems. For example, there are problems when $\operatorname{\mathbb{M}}(\theta, P)$ is defined as U-statistics or higher-order U-statistics bose2018u, diciccio2022clt, U-quantile choudhury1988generalized, and other problems where $\operatorname{\mathbb{M}}(\theta, P)$ involves nuisance parameters, such as Cox proportional hazard models cox1972regression. Although the general results in Section (ref) still apply to these problems, detailed investigations of these applications are left for future research.

We introduce the definitions and notation that we frequently refer to. For any $n \in \mathbb{N}$ and the identically distributed observation $Z_1, \ldots, Z_n \in D_2$, the empirical measure is defined as $\mathbb{P}_n := n^{-1}\sum_{i=1}^n \delta_{Z_i}$ where $\delta_z$ is the Dirac measure at $z$. For any measure $P$ and $P$-integrable function, we set $Pf = \int f dP$. In particular, $\mathbb{P}_n f$ means $n^{-1} \sum_{i=1}^n f(Z_i)$. The empirical process is defined as the centered and normalized process, which is denoted by $ \mathbb{G}_n f := n^{1/2}(\mathbb{P}_n-P)f$. For notational convenience, we also denote by $\operatorname{\mathbb{E}}_P[\cdot]$ the expectation under $P$. Given an arbitrary initial estimator $\widehat\theta_1$, it follows that

Construction by concentration inequalities

As discussed in Section (ref), we can derive the lower confidence bound by concentration inequalities. In particular, replacing $\operatorname{\mathbb{M}}(\theta, P)$ with $P m_{\theta}$ and $\widehat{\mathbb{M}}_n(\theta)$ with $\mathbb{P}_n m_{\theta}$, it suffices to establish the following inequality:

There is a wide range of concentration inequalities for this purpose. We refer to Boucheron2013Concentration for a glossary of classical results and hao2019bootstrapping, ramdas2023randomized, waudby2024estimating, bates2021distribution for more recent developments. As an illustration, we may consider the one-sided empirical Bernstein inequality maurer2009empirical, established below:

The validity of the confidence set can be established without any additional assumptions, as shown in the following theorem.

This theorem is a simple corollary of Theorem (ref). The conditional probability $\mathbb{P}_P(\cdot|D_1)$ is replaced by the marginal probability $\mathbb{P}_P(\cdot)$ since the lower bound no longer depends on $D_1$.

Next, we establish the rate at which the confidence set shrinks. As discussed in Remark (ref), the convergence rate of the set requires the uniqueness of the optimizer $\theta(P)$. Below, we assume that $\theta(P)$ is a unique point in $\Theta$ such that the following assumptions hold:

The parameter $\beta$ in (ref) links the optimization problem at hand to the curvature within the parameter space. This condition also implies that $\theta(P)$ is a strong global minimizer of $\theta\mapsto\mathbb{M}(\theta, P)$ drusvyatskiy2013tilt. The modulus $\phi_n$ in (ref) quantifies the complexity of the parameter space $\Theta$ and serves as an upper bound on the variance of the loss function near $\theta(P)$. In particular, the first part of inequality (ref) is known in the literature as the maximal inequality with its upper bound $\phi_n(\cdot)$ reflecting the complexity of $\Theta$. Finally, (ref) pertains to the rate of convergence of the initial estimator. The convergence rate of the proposed confidence set depends on all these terms; such geometric structures are commonly used to establish the convergence rates of M-estimators, as discussed in Theorem 3.2.5 of van1996weak. These conditions are also used in kim1990cube in the estimation context to explain the differences between M-estimators in the regular and irregular cases.

We now establish a bound on the diameter of the confidence set. For any set $A$ equipped with a metric $\|\cdot\|$, the diameter of $A$ is denoted by $\mathrm{Diam}_{\|\cdot\|}(A) := \sup\{\|a-b\|\, :\, a, b\in A\}$. The following theorem provides the high probability bound on the diameter of the proposed confidence set constructed using a concentration inequality-based lower confidence bound.

The proof is provided in Section (ref) of the supplement. In summary, Theorem (ref) states that the diameter of the set $\widehat{\mathrm{CI}}^{\mathrm{E.B.}}_{n,\alpha}$ depends on four key factors: (1) the curvature of the optimization problem, (2) the complexity of $\Theta$, (3) the variance of the loss function near $\theta(P)$, and (4) the quality of $\widehat \theta_1$.

Construction by the central limit theorem

This section discusses an alternative approach to construct the lower confidence bound, given by (ref), based on the central limit theorem (CLT). Let $\widehat \sigma^{2}_{\theta(P), \widehat\theta_1}$ be the sample variance of $(m_{\theta(P)}-m_{\widehat \theta_1})(Z_i)$, given by (ref), and $\Phi(t)$ be the cumulative distribution function of the standard normal random variable. We define the Kolmogorov-Smirnov distance as

We will shortly discuss the upper bound for $\Delta_{n,P}$ based on the Berry–Esseen bound for studentized statistics bentkus1996berry, Bentkus1996. The lower confidence bound is defined as

where $z_{\alpha}$ is the $1-\alpha$-th quantile of a standard normal distribution. The corresponding confidence set is given by

The validity of this set follows immediately in view of (ref) and Theorem (ref).

The proof is provided in Section (ref) of the supplement. Comparing two expressions (ref) and (ref), we can observe that the CLT-based method always yields a smaller confidence set, since the leading constant for the $n^{-1/2}$ term in (ref) is $\sqrt{2\log(2/\alpha)} > z_{\alpha}$ for any $\alpha \in (0,1)$. This shows a strong practical advantage of the CLT-based confidence set. However, the CLT-based method compromises the validity for a finite sample size because $\sup_{P\in\mathcal{P}}\Delta_{n,P}$ might at best be close to zero as $n\to\infty$. In the following, we discuss sufficient conditions, based on katz1963note, bentkus1996berry, and Bentkus1996, under which $\sup_{P\in\mathcal{P}}\Delta_{n,P}$ converges to zero.

This result is a direct consequence of Corollary 1.1 of bentkus1996berry. To ensure the validity of the proposal, we require that the right-hand term of (ref) converge to zero.

This theorem is an immediate consequence of combining Theorem (ref) and Lemma (ref). In particular, the conditional probability $\mathbb{P}_P(\cdot | D_1)$ can be replaced by the marginal probability $\mathbb{P}_P(\cdot)$ because $\Delta_{n,P}$ can be bounded by the minimum of one and the left-hand side of (ref). Section (ref) provides a further discussion on condition (ref).

We now establish bounds on the diameter of the CLT-based confidence set. First, we introduce an additional assumption to allow for unbounded loss functions.

Assumption (ref) resembles (ref), but instead, quantifies the growth rate of the expectation of the localized squared empirical processes. As $m_{\theta}$ is unbounded, the growth rates of the moduli $\phi_n$ and $\omega_n$ may depend on the concentration properties of $(m_\theta - m_{\theta(P)})(Z_i)$, characterized through, for instance, sub-Weibull tails or the number of the available moments. Such arguments often require specific case-by-case analysis. Following Section 3.2 of van1996weak, we present the general result in terms of the growth rate of $\omega_n$, allowing for the theorem to apply without specific conditions on $m_\theta - m_{\theta(P)}$. The theorem is provided as follows:

The proof is provided in Section (ref) of the supplement.

On the validity of the CLT-based method

Section (ref) outlines the construction of the confidence set based on the CLT whose (asymptotic) validity is guaranteed so long as the Gaussian approximation tends to zero as $n \to \infty$. Verification of (ref) can be difficult when $\widehat{\theta}_1$ is consistent for $\theta(P)$ because the variance $B^2$ in Lemma (ref) converges to zero under consistency of $\widehat{\theta}_1$. This section provides sufficient conditions for the validity to hold. The results of this section are frequently used in the statistical applications presented in Section (ref).

For any real-valued random variable $X$, we write $\|X\|_p = (\mathbb{E}[|X|^p])^{1/p}$ for any $p > 0$.

Importantly, the uniform Lindeberg condition does not require strong moment assumptions on $Q$ such as the finite third moments. The proposition below provides the first-order approximation result, which becomes useful for many statistical applications.

The proof is provided in Section (ref) of the supplement. Intuitively, the random variable $H_1$ serves as the gradient of $W_1$ with respect to $\theta$ (evaluated at $\theta(P)$) so that $W_1 \approx \langle \theta - \theta(P), H_1 \rangle$. The approximation defined in (ref) is a quantitative version of the quadratic mean differentiability van1996weak, which is weaker than the pointwise differentiability. The role of the uniform Lindeberg condition is clearer in this context: when the first-order approximation in the sense of (ref) is available, it suffices to verify the uniform Lindeberg condition for the random sequence $\{H_i\}_{i=1}^n$ instead of directly inspecting $\{W_i\}_{i=1}^n$. The upper bound of this proposition no longer involves conditioning on $D_1$, but instead, requires the consistency of the initial estimator $\widehat \theta_1$. Although this aspect may be stringent compared to the confidence set based on concentration inequalities, which remained valid even when $\widehat\theta_1$ is not consistent, such consistency is not a necessary condition for the validity of the CLT-based confidence sets---see Remark (ref) in this regard. The following proposition provides sufficient conditions under which uniform Lindeberg condition is satisfied.

Proposition (ref) is standard in the CLT literature, and for the reader's convenience, we provide proof in Section (ref) of the supplement.

Statistical Applications

In this section, we present statistical applications of the proposed method and provide sufficient conditions for validity, along with the convergence rates of the corresponding confidence sets. For simplicity, we focus on the upper confidence bound $U_{n,\alpha_2}(\theta(P), \widehat{\theta}_1; D_2) = 0$ with $\alpha_2 = 0$. As discussed in Remark (ref), this choice does not affect the validity of the confidence sets. The width analysis provided here demonstrates that the simple choice of $U_{n,\alpha_2}(\theta(P), \widehat{\theta}_1; D_2) = 0$ is sufficient for rate-optimality, while alternative choices for $U_{n,\alpha_2}(\theta(P), \widehat{\theta}_1; D_2) < 0$ will only improve upon the constant factor. For each application, we specify the choice of the loss function $m_\theta$. Once such $m_\theta$ is defined, the confidence set derived from the following expression will be referred to as the empirical Bernstein-based confidence set:

where $B_0$ and $\widehat \sigma^2_{\theta, \widehat\theta_1}$ are defined in Example (ref). We similarly define the following set as the CLT-based confidence set:

Throughout this section, the $N$ observations are split into two sets $D_1$ and $D_2$ such that there exist $c$ and $C$ with $0 < c < |D_1|/|D_2| \le C < \infty$. All relevant proofs are provided in Section (ref) of the supplement.

High-dimensional mean estimation

Consider an IID observation $X_1, \ldots, X_N \in \mathbb{R}^d$ generated from $P \in \mathcal{P}$. The dimension $d$ is allowed to grow with $N$. In this problem, the inference of interest is the expectation of $X$ under $P$, which can be also written as

The covariance matrix of $X$ is denoted by $\Sigma := \operatorname{\mathbb{E}}_P(X-\operatorname{\mathbb{E}}_P[X])(X-\operatorname{\mathbb{E}}_P[X])^\top$. Although this problem may seem trivial, mean estimation and inference in growing dimensions under weak distributional assumptions remains an active area of research lugosi2019mean. We provide results under assumptions, requiring only the existence of the covariance matrix and the uniform Lindeberg condition (ref). Below, we denote by $\widehat{\mathrm{CI}}_{n,\alpha}^{\mathrm{mean}}$ the CLT-based confidence set (ref) with $m_{\theta}(x) = \|x-\theta\|_2^2$. We now provide the validity statement for this confidence set.

Next, we demonstrate the convergence rate of the confidence set in $L_2$-norm.

The requirement (ref) is satisfied when $\widehat{\theta}_1$ is the sample mean. We emphasize that Theorem (ref) imposes no restrictions on the dimension $d$---hence it is typically called dimension agnostic. The dependency on $\sqrt{\mathrm{tr}(\Sigma)/n}$ is, in fact, not improvable since this is the exact risk of the mean estimation under a multivariate Gaussian distribution; see the formal minimax argument in Section 5 of lee2022optimal.

The results in this subsection can be extended to inference for the Fr\'{e}chet mean where $\Theta$ is a general metric space. In the literature, assumption (ref) is referred to as a growth condition, or variance inequality. The quadruple condition studied in Schotz2019convergence can be used to establish (ref). We anticipate that the proposed confidence set for this problem will yield a width that shrinks at a rate determined by the growth of the entropy bounds on the space $\Theta$. A detailed exploration of this extension is deferred to future work.

Misspecified linear regression

Consider an IID observation $(Y_1, X_1^\top)^\top, \ldots, (Y_N, X_N^\top)^\top \in \mathbb{R}\times\mathbb{R}^d$ generated from the following model:

We assume that the gram matrix $\Gamma_P := \operatorname{\mathbb{E}}_P[XX^\top]$ is invertible such that $\theta_P \in \mathbb{R}^d$ exists even when the regression function $\operatorname{\mathbb{E}}_P[Y_i| X_i]$ is not linear. In this problem, the inference of interest is $\theta_P$, which can be also written as

without making the linearity assumption for $\operatorname{\mathbb{E}}_P[Y_i| X_i]$. Below, we denote by $\widehat{\mathrm{CI}}_{n,\alpha}^{\mathrm{LR}}$ the CLT-based confidence set (ref) with $m_{\theta}(y,x) = (y-\theta^\top x)^2$. We introduce the following assumptions for the validity statement:

(ref) requires the $L_{q_x}$-$L_2$ norm equivalence on $X$---see Remark (ref). (ref) ensures that the error variables $\xi$ do not become degenerate or possess infinite variance.

The following result is obtained:

Next, we provide the width of the confidence set in terms of the matrix-norm $\|\cdot\|_{\Gamma_P}$:

The requirement (ref) is satisfied when $\widehat{\theta}_1$ is the ordinary least squares (OLS). The dependency on $\overline{\sigma}^2 d/n$ in the rate is minimax optimal as shown by Theorem 1 of mourtada2022exact. Recently, chang2024confidence provided confidence sets for high-dimensional OLS under similar conditions as above. Their proposal is based on the formulation of the OLS as the root of an estimating equation, or $Z$-estimation. Theorem 10 of chang2024confidence establishes that their proposed confidence set converges at the optimal rate of $\sqrt{d/n}$; however, they require $d = o(n^{1/2})$ under the equivalent condition as (ref). chang2023inference provides a method based on one-step bias-correction, which requires $d = o(n^{2/3})$. On the other hand, Theorem (ref) holds as long as $C d(\log d)^{2} \le n$ (when $q_x = 4$) for some constant $C$ depending on $P$ but not on $n$ or $d$.

Manski's discrete choice model

Consider an IID observation $(Y_1, X_1^\top)^\top, \ldots (Y_N, X_N^\top)^\top \in \{-1,1\} \times \mathbb{R}^d$ generated from the following binary response model:

Here, the error variable $\varepsilon_i$ has zero conditional median given covariates, i.e., $\mathrm{med}(\varepsilon_i | X_i)=0$, but otherwise allowed to depend on $X_i$. In this problem, the inference of interest is $\theta_P$, which can be also written as

A popular estimator for $\theta_P$ is defined as the following maximum score estimator, proposed by manski1975maximum, which solves

The asymptotic behavior of $\widehat \theta_n$ exhibits a non-standard limit, studied by manski1985semiparametric, kim1990cube. The inference for this problem is known to be challenging, and cattaneo2020bootstrap proposes a bootstrap-based approach. By the fact that $Y_i\, \mathrm{sgn}(\theta^\top _i X_i)$ is uniformly bounded by one, we can use the confidence set based on the concentration inequality with $B_0 = 2$. Below, we denote by $\widehat{\mathrm{CI}}^{\mathrm{Manski}}_{n,\alpha}$ the empirical-Bernstein-based confidence set (ref) with $m_{\theta}(x,y) = -y\cdot\mathrm{sgn}(\theta^\top x)$. We now provide the validity statement for this confidence set.

Next, we demonstrate the width of the confidence set in $L_2$-norm. Below, we introduce additional assumptions on the joint distribution on $X$ and $\varepsilon$. Both assumptions are standard in the literature.

Both assumptions are identical to those considered in mukherjee2019nonstandard, mukherjee2021optimal. (ref) is often called the low noise (the margin) assumption in the classification literature mammen1999smooth, tsybakov2004optimal. This condition quantifies the deviation of the conditional class probability from $1/2$ near the decision boundary of the Bayes' classifier, i.e., $\mathbb{P}_P(Y=1|X)\ge 1/2$. As $\beta \to 0$, the decision boundary becomes bounded away from $1/2$, representing the most favorable situation for the classification. (ref) was introduced to relate the distribution of covariates $X$ to the underlying geometry in the parameter space $\mathbb{S}^{d-1}$. See mukherjee2021optimal for further discussion.

We provide the width of the confidence set in terms of the $L_2$-norm:

Theorem 3.2 of mukherjee2019nonstandard shows that the rate requirement (ref) is satisfied by the standard maximum score estimator defined as (ref). The rate of convergence matches that of the minimax lower bound up to the logarithmic factor (See Theorem 3.4 of mukherjee2019nonstandard).

Quantile estimation without positive densities

Consider an IID observation $X_1, \ldots, X_N \in \mathbb{R}$ generated from $P \in \mathcal{P}$ where the inference of interest is the $\gamma$-quantile defined as

and $F_P(t) := \mathbb{P}_P(X\le t)$. It is well-known that $\theta(P)$ minimizes the following “quantile" loss:

where $(t)_+ = \max(t, 0)$. The sample quantile centered at $\theta(P)$ converges to a Gaussian distribution when scaled by $n^{1/2}$ if the distribution of $X$ has a strictly positive density at $\theta(P)$. If the density at $\theta(P)$ is zero or non-existent, however, the sample quantile converges at a rate depending on the H\"{o}lder smoothness of the $F_P(t)$ in the neighborhood of $\theta(P)$. In this case, the limiting distribution is no longer Gaussian and also depends on the H\"{o}lder smoothness of the $F_P(t)$ in the neighborhood of $\theta(P)$ smirnov1952limit. Although finite-sample valid, distribution-free confidence intervals for quantiles already exist scheffe1945non, we present this result to illustrate the behavior of the proposed method in irregular settings.

Below, we construct the CLT-based confidence set (ref) with $m_{\theta}(x) = \gamma(x-\theta)_+ + (1-\gamma)(\theta-x)_+$, and denote the corresponding set by $\widehat{\mathrm{CI}}_{n,\alpha}^{\gamma}$. We quantity the smoothness of the $F_P(t)$ near $\theta(P)$ as follows:

The H\"{o}lder smoothness as described in (ref) should be compared to knight1998limiting. When $\beta=1$, this assumption becomes equivalent to requiring that the density at the true $\gamma$-quantile is bounded away from zero. We now proceed to the validity statement.

The result of Theorem (ref) allows for $\gamma \equiv \gamma_n$ to depend on the sample size $n$. When there exist constants $c$ and $C$ such that $0 < c \le \gamma_n \le C < 1$ for all $n$, the validity holds under the consistency of the initial estimator. When $\gamma_n \to 0$ or $\gamma_n \to 1$, then there is a restriction on how quickly $\gamma_n$ can tend to these extreme values depending on $\beta$ and the convergence rate of $\widehat{\theta}_1$. This requirement may be relaxed under the alternative, but possibly stronger, assumptions on $P$---see Remark (ref). Finally, the width of the confidence set is obtained as follows:

The requirement in (ref) is satisfied when $\widehat{\theta}_1$ is the sample quantile. The convergence rate of the confidence set indicated by Theorem (ref) matches that of the sample quantile under (ref) as given by Example 1 of knight1998limiting. In fact, knight1998limiting provides the limiting distribution of the sample quantile under (ref); however, the traditional approach requires prior knowledge of $\beta$ to perform asymptotic inference. The proposed confidence set of this manuscript, in contrast, converges at the rate $n^{-1/(2\beta)}$ automatically without the knowledge of $\beta$. In the special case of $\beta=1$, i.e., the density is bounded away from zero at the $\gamma$-quantile, and the confidence shrinks at the parametric rate of $n^{-1/2}$.

Discrete argmin inference

This application is motivated by the recent manuscript of zhang2024winners, which studies a prototypical problem in general model selection. The result in this subsection can be extended to constructing a confidence set that contains the best “predictor" minimizing the population risk among $\{f_1,\ldots, f_d\}$ where $f_i$ corresponds to machine learning methods developed from the same data, and consequently $f_i$ and $f_j$ for $i\neq j$ can be highly correlated.

Consider an IID observation $X_1, \ldots, X_N \in \mathbb{R}^d$ generated from $P \in \mathcal{P}$ where $d$ may grow with $N$. In this problem, the inference of interest is the index of the coordinate corresponding to the minimum marginal mean. In other words, the population parameter is defined as

Following zhang2024winners, we do not assume uniqueness of $\theta(P)$, allowing the proposed confidence set to accommodate ties. Below, we denote by $\widehat{\mathrm{CI}}_{n,\alpha}^{\mathrm{argmin}}$ the CLT-based confidence set (ref) with $m_{\theta}(x) = e_\theta^\top x$ for $\theta \in \{1, \ldots, d\}$. We introduce the following assumption to the class of distributions $\mathcal{P}$:

zhang2024winners establish the validity of their method under the assumption that the smallest eigenvalue of the covariance matrix of $X$ is bounded away from zero (See Theorem 3.1 of zhang2024winners). However, as pointed out in their work, this assumption may be violated in practice when the components of $X$ are highly correlated, such as in model selection for LASSO (see Section 6.2 of zhang2024winners). In contrast, (ref) avoids imposing a condition on the smallest eigenvalue, thereby allowing for scenarios where the components of $X$ are strongly correlated. Additionally, zhang2024winners develop their theoretical results under the assumption that $e_j^\top X_i$ is almost surely uniformly bounded for all $1\le j \le d$ and $1 \le i \le n$ for some constant. Once such a constant becomes available, we can construct a confidence set based on concentration inequalities where the finite-sample validity can be established without assuming (ref).

We now establish the validity of this confidence set.

The corresponding width analysis requires a new framework, as the parameter space $\Theta$ is discrete and not continuous. One potential approach to establish the convergence rate is through the analysis of the non-central t-statistic Bentkus2007Limiting. Interestingly, the limiting law of the non-central t-statistic can be highly non-standard, depending on the underlying moment assumptions and the rate at which the population mean decays (See Theorems 2.4 and 2.5 of Bentkus2007Limiting). Using these results, one may be able to establish a result akin to Theorem 4.1 of zhang2024winners, where the confidence set's rejection probability is analyzed under different rates at which the curvature $\mathbb{C}_P(\widehat \theta_1)$ converges to zero.

Numerical Illustration

This section provides an empirical illustration of the proposed method for inference in high-dimensional settings. The aim of this section is to demonstrate the robust coverage of the proposed methods in high dimensions, where Wald intervals may be anti-conservative. Additionally, we compare the volume of the proposed confidence set with that of the Wald intervals, highlighting that the improved robustness comes at a minor constant-factor cost.

The scenario under consideration is identical to the high-dimensional mean estimation setup from subsection (ref). For $N=500$ and $2 \le d \le 100$, independent observations $X_i \in \mathbb{R}^d$, $1 \le i \le N$ are generated from a multivariate Normal distribution: $X_i \sim N(0_d, I_d)$. We compare three methods. The first method, Asymptotic, corresponds to the Wald interval based on the asymptotic distribution. Formally, the confidence set is defined as

where $\overline X_N$ is the sample mean and $\widehat\Sigma_N$ is the sample covariance matrix computed from the $N$ observations. The cutoff value $\chi^2_{d,\alpha}$ represents the ($1-\alpha$)th-quantile of the chi-square distribution with $d$ degrees of freedom. The second method, Sample split, corresponds to the proposed approach theoretically analyzed in subsection (ref). To recall, we split the observations into two parts \[D_1 := \{X_i \, : \, 1\le i \le \lfloor N/2\rfloor \} \text{ and } D_2 := \{X_i \, : \, \lfloor N/2\rfloor + 1 \le i \le N\}.\] Let $\widehat \theta_1$ denote the sample mean computed from $D_1$, and denote $n = |D_2|$. The confidence set, Sample split, is then given by

where $\widehat \sigma_{\theta, \widehat \theta_1}$ is the sample standard deviation of $\|X_i -\theta\|^2 - \|X_i -\widehat \theta_1\|^2$ computed using $D_2$. The final method slightly modifies the sample-splitting approach by incorporating the upper bound from (ref). In particular, for mean estimation, it holds that $-\mathbb{C}_P(\widehat{\theta}_1) = -\|\widehat{\theta}_1 - \theta(P)\|^2$ and thus

The confidence set, Sample split + Upper bound, is obtained by the expression (ref):

Figure (ref) displays the empirical coverage of the $95\%$ confidence sets, calculated from $1000$ replications. We observe that the coverage accuracy of the Wald intervals deteriorates as the dimension increases. By $d \approx 100$, the average coverage of the $95\%$ confidence set drops to approximately $50\%$. In contrast, the proposed sample-splitting methods remain their validity across all dimensions we investigated. The simulation results further highlight the empirical advantages of estimating the upper bounds of the curvature $-\mathbb{C}_P(\widehat\theta_1)$. While the confidence set $\widehat{\mathrm{CI}}^{\mathrm{SS}}_{N,\alpha}$, analyzed in subsection (ref) to show the optimal shrinkage rate, its empirical coverage suggests that the method is conservative in practice. Meanwhile, incorporating the upper bound significantly improves coverage accuracy, bringing it close to the nominal $95\%$ level across all dimensions.

Next, we analyze the size of the proposed confidence set in comparison to the Wald intervals. As illustrated in Figure (ref) in the supplement, the proposed confidence set is non-convex and the exact computation of the volume is challenging. To address this, we adopt the following approximation. First, we can establish that there exists a random variable $r \in \mathbb{R}_+$ such that

Meanwhile, Lemma (ref) in Section (ref) of the supplement implies that the volume of the Wald interval is given by

Here, $\Gamma$ denotes the Euler's gamma functions and $\lambda_{k}(\widehat \Sigma_N)$ denotes the $k$th smallest eigenvalue of the sample covariance matrix $\widehat \Sigma_N$ computed from all $N$ observations. Then, it is straightforward to see that

The final expression represents the ratio between the radius $r$ and the geometric mean of the ellipsoid's radii $(r_1, \ldots, r_d)$. A detailed derivation is provided in Section (ref) of the supplement. Figure (ref) presents the average ratio of the radii computed from $1000$ replications across different dimensions. The results roughly state that the proposed confidence set enlarges the Wald intervals in each of the $d$-dimensional axes by at most a factor of $2$. We emphasize that this is an upper bound of the ratio and two confidence sets can be much closer in size in practice. See Figure (ref) in the supplement for visual illustration. This enlargement is expected since the proposed methods employ sample-splitting, which reduces sample efficiency but enhances the validity of inference in high-dimensional settings.

Concluding Remarks

This manuscript introduces a general approach to constructing confidence sets for M-estimation, addressing longstanding challenges in statistical inference due to inherent irregularities in these tasks. The proposed method employs sample splitting, facilitating validity across regular and irregular settings. In particular, the method offers a dimension-agnostic solution that is particularly valuable for high-dimensional problems where inferential tools are currently limited or unavailable. The general framework is illustrated through two approaches: one based on concentration inequalities and the other on the central limit theorem (CLT). The manuscript provides foundational theorems for each case that guarantee validity and characterize their convergence rates.

The theoretical properties of the proposed methods are demonstrated through statistical applications where inference is challenging. The first application considers mean estimation and misspecified linear regression in growing dimensions. The proposed methods remain valid even when the dimension $d$ exceeds $n^{1/2}$, a regime where many existing inferential tools fail. The convergence rates of the proposed method are also dimension-agnostic and match those of the known minimax lower bounds---these properties have been previously established in estimation but have been less known for inference. The second application extends the proposed methods to irregular settings, such as cube-root asymptotic, whose convergence rates are shown to adapt to the underlying geometry of the optimization problem at hand.

The authors are currently exploring several directions for extending the proposed method. One key area is the constrained optimization problems, where similar irregularities emerge when the solution lies on the boundary of the constrained set. This issue includes problems involving shape constraints and sparsity. In particular, there is a lack of inferential tools for LASSO and Dantzig selectors candes2007dantzig despite their widespread use, making the investigation in this area of significant interest.

Several open problems remain where the proposed methods may be extended. First, inference for generalized linear models in growing dimensions, including logistic regression and Poisson regression, remains underdeveloped. Second, the extension to the Cox proportional hazard model may be interesting. This problem involves nuisance parameters, requiring the optimization in the form of $\operatorname{\mathbb{M}}(\theta, \eta, P)$ for some unknown $\eta \in \mathcal{H}$, where $\mathcal{H}$ can be a nonparametric class of functions. Achieving efficiency in estimating $\operatorname{\mathbb{M}}(\theta, \eta, P)$ will likely require the first-order bias correction from the estimation error of $\eta$, which is an interesting area to investigate. Third, the manuscript did not focus on optimization problems involving U-statistics or U-quantiles. Given that the CLT for U-statistics is well-established, we anticipate the general framework to be applicable to these problems as well. Finally, this manuscript considered scenarios where the sample size $n$ is fixed and not data-dependent. We envision extending this framework to data-dependent stopping rules, or anytime-valid inference, can be achieved when the loss function is equipped with certain concentration properties, such as sub-Gaussian tails schreuder2020nonasymptotic or under the asymptotic confidence sequence framework formalized by waudby2024time. Pursuing these extensions will require considerable additional effort and represent substantial methodological advances.

Acknowledgements

The first author gratefully acknowledges Woonyoung Chang for the series of helpful discussions. We also thank Christof Sch\"{o}tz for providing us comments on the proof of Theorem (ref) in the initial manuscript and informing us of the application to Fr\'{e}chet means.

\setcounter{section}{0} \setcounter{equation}{0} \setcounter{figure}{0}

Review of History

This section summarizes the historical developments of the key idea behind the content of this manuscript.

Research on adaptive confidence sets for nonparametric models was particularly active from the 1990s to the 2010s. These studies generally relied on concentration inequalities to establish validity, requiring precise error quantification for adaptive nonparametric estimators. Additional historical developments can be found in Chapter 8.4 of gine2021mathematical.

Proof of Theorem (ref)

We denote by $\operatorname{\mathbb{M}}(\theta) \equiv \operatorname{\mathbb{M}}(\theta, P)$ for any $\theta \in \Theta$. Note that

where the last inequality follows from Cantelli's inequality pinelis2010between.

Proof of Theorem (ref)

Let $P$ be an arbitrary distribution in $\mathcal{P}$. Conditioning on $D_1$, such that $\widehat \theta_1$ is considered deterministic, we define following events:

We further observe that

The last event has probability zero under $\mathbb{P}_{P}( \cdot | D_1)$ since $\theta(P)$ is the minimizer of $\theta \mapsto \mathbb{M}(\theta, P)$ and thus $\mathbb{M}(\theta(P), P) \le \mathbb{M}(\theta, P)$ holds $P$-almost surely for any $\theta \in \Theta$. When $U_{n,\alpha_2}(\theta(P), \widehat \theta_1; D_2) < 0$, the probability under $\mathbb{P}_{P}(\cdot | D_1)$ remains zero after taking the intersection with $\mathcal{B}_n$. Hence, we have

Finally, we conclude the claim by the fact that $\mathbb{P}_{P}(\mathcal{A}_n^c\mid D_1) \le \alpha_1$ by (ref) and $\mathbb{P}_{P}(\mathcal{B}_n^c\mid D_1) \le \alpha_2$ by (ref) uniformly for all $P \in \mathcal{P}$.

Proof of Theorem (ref)

Without loss of generality, we set $U_{n,\alpha_2}(\theta, \widehat \theta_1; D_2) = 0$, which only enlarges the confidence set and hence the following result remains to hold. Any element $\theta \in \Theta$ in the confidence set, defined as (ref), satisfies the following:

Now the original confidence set is contained $P$-almost surely in the following supersets:

where \[\Gamma_n(\widehat\theta_1, \theta(P)) := |\mathbb{P}_n(m_{\widehat{\theta}_1}-m_{\theta(P)}) |+\sqrt{\frac{2\widehat \sigma^2_{\widehat\theta_1, \theta(P)} \log(2/\alpha)}{n}}\] and the last step uses (ref). Furthermore, we have

and hence

Using this result, the confidence set can be further contained in

We analyze the superset $\overline{\mathrm{CI}}_{n, \alpha}$. Given $c_0$ and $\beta$ in (ref) and the function $\phi_n$ in (ref), we define $r_n$ as any value that satisfies

We define

where

The constant $M > 0$ will be specified later. We denote by $B_{\|\cdot\|}(\theta; r)$ a $\|\cdot\|$-ball centered at $\theta$ with radius $r \ge 0$. We consider the partition of the parameter space $\Theta$ into the intersection with the ball

where

Thus far, we have shown that $\widehat{\mathrm{CI}}^{\mathrm{E.B.}}_{n,\alpha} \subseteq \overline{\mathrm{CI}}_{n,\alpha}$. We now consider the following elementary result:

Therefore to claim that, with high probability, the set $\widehat{\mathrm{CI}}^{\mathrm{E.B.}}_{n,\alpha}$ is contained in the ball $B_{\|\cdot\|}(\theta(P); \mathrm{R}_M)$ (and hence the diameter is less than $2\mathrm{R}_M$), we need to establish that $\overline{\mathrm{CI}}_{n,\alpha}$ intersects with $B^c_{\|\cdot\|}(\theta(P); \mathrm{R}_M)$ with an arbitrarily small probability.

Below, we adopt the notation $\mathbb{P}^{1}_P \equiv \mathbb{P}_P(\cdot \mid D_1)$, meaning that probability should be regarded as conditioning on $D_1$ under the distribution $P$. We now establish the existence of $M$ large enough such that for $\|\theta-\theta(P)\| > \mathrm{R}_M$,

It follows that

The last term is trivially controlled since

by Markov inequality and the fact that $\Gamma_n'(\widehat\theta_1, \theta(P))$ is deterministic under $\mathbb{P}^{1}_P(\cdot)$. The last display becomes less than $\varepsilon/8$ for $M$ large enough.

Moving onto the term $\mathbf{I}$, we first observe that

We define the “shell": \[S_j = \{\theta \in \Theta : 2^{j}c_0^{-1/(1+\beta)}r_n^{2/(1+\beta)} \le \|\theta-\theta(P)\| < 2^{j+1}c_0^{-1/(1+\beta)}r_n^{2/(1+\beta)}\}\] for each $j \in \{0\} \cup \mathbb{N}$. It then follows that

By assumption (ref) that $q < 1+\beta$, the last display becomes less than $\varepsilon/8$ for $M$ large enough, depending on $\beta$ and $q$.

The term $\mathbf{II}$ can similarly be controlled as:

We denote by $\bar{r}_n := (r_n \vee n^{-1/2})$ where $r_n$ is the solution of the equation given by (ref). We now define the “shell":

for each $j \in \{0\} \cup \mathbb{N}$. It follows that

Now, we observe that

and the mapping $t\mapsto t^2$ is $2$-Lipschitz on $t \in [-1,1]$. Hence, by the contraction inequality, for instance, Theorem 4.12 of ledoux2013probability or Corollary 3.2.2 of gine2021mathematical, we obtain

To complete the argument, we have

We now have that

When $r_n \le n^{-1/2}$, we have $\bar{r}_n = n^{-1/2}$ and thus

where the last inequality follows since $\phi_n(t^{2/(1+\beta)})/t^2$ is strictly decreasing and thus

Hence $ n\phi_n(c_0^{-1/(1+\beta)}n^{-1/(1+\beta)}) \le n^{1/2}$. On the other hand, when $r_n \ge n^{-1/2}$, we have $\bar{r}_n = r_n$. It further follows that $\bar{r}_n \ge n^{-1/2} \Leftrightarrow n^{1/2}\bar{r}_n \ge 1$, and we can bound $n^{-q/(2+2\beta)} r_n^{-q/(1+\beta)} = (n^{1/2}r_n)^{-q/(1+\beta)}$ by one. The rest of the argument is identical to the earlier derivation and the last summation in (ref) can be bounded as

which can be made smaller than $\varepsilon/8$ for $M$ large enough, depending on $\alpha$, $\beta$ and $B_0$.

Finally, the third term can be bounded as

By repeating the analogous peeling argument over the shell \[S_j = \{\theta \in \Theta : 2^{j}c_0^{-1/(1+\beta)}r_n^{2/(1+\beta)} \le \|\theta-\theta(P)\| < 2^{j+1}c_0^{-1/(1+\beta)}r_n^{2/(1+\beta)}\}\] for each $j \in \{0\} \cup \mathbb{N}$, it follows that

Since $q < 1+\beta$, the last expression can be smaller than $\varepsilon/8$ for large $M$ enough, depending on $\alpha$ and $\beta$.

Finally, let $M$ be a large constant only depending on $\varepsilon$, $\alpha$, $\beta$ and $B_0$ such that (ref),(ref),(ref) and (ref) become smaller than $\varepsilon/8$ respectively. Then with probability at least $1-\varepsilon/2$, it holds that

where the constant $\mathfrak{C}$ depends on $\varepsilon$, $\alpha$, $\beta$ and $B_0$. Since all terms in the last display are non-negative, we have

Furthermore, it follows

since the middle term is always smaller than one of the other two. Putting all results together, we conclude the claim such that \[\widehat{\mathrm{CI}}^{\mathrm{E.B.}}_{n,\alpha} \subseteq B_{\|\cdot\|}(\theta(P); \mathrm{R}_n)\] with probability greater than $1-\varepsilon/2$ where

This result is stated under the conditional probability on $D_1$. The only term that remains random is $\Gamma^{1/(1+\beta)}_n(\widehat\theta, \theta(P))$. We establish that there exists $S_\varepsilon$ such that

We observe that

The first term can be bounded by the Markov's inequality as

Similarly, we have

Hence by defining $S_\varepsilon = C_\varepsilon s_n$ where $s_n$ is defined as (ref) and $C_\varepsilon$ is a constant, only depending on the $\varepsilon$, it follows that

Choosing $C_\varepsilon$ large enough, we can obtain

Hence, we conclude the claim such that \[\widehat{\mathrm{CI}}^{\mathrm{E.B.}}_{n,\alpha} \subseteq B_{\|\cdot\|}(\theta(P); \mathrm{R}_n)\] with probability greater than $1-\varepsilon$ where

Proof of Theorem (ref)

We verify the condition (ref), which follows as

The result follows from Theorem (ref).

Proof of Theorem (ref)

The general structure of the proof is identical to the proof of Theorem (ref). By an analogous argument, the CLT-based confidence is contained almost surely by the superset as follows:

where \[\Gamma_n(\widehat\theta_1, \theta(P)) := |\mathbb{P}_n(m_{\widehat{\theta}_1}-m_{\theta(P)}) |+\sqrt{\frac{z_{\alpha}\widehat \sigma^2_{\widehat\theta_1, \theta(P)} }{n}}.\] The main difference from the proof of Theorem (ref) is that we can no longer use the contraction inequality to control the squared process. We now define the “shell": \[S'''_j = \{\theta \in \Theta : 2^{j}c_0^{-1/(1+\beta)}u_n^{2/(1+\beta)} \le \|\theta-\theta(P)\| < 2^{j+1}c_0^{-1/(1+\beta)}u_n^{2/(1+\beta)}\}\] for each $j \in \{0\} \cup \mathbb{N}$. Then, it follows that

By the assumption $q < 1-\beta$, the last series is summable and thus can be made smaller than $\varepsilon$ for $M$ large enough. Then with probability at least $1-\varepsilon/2$, it holds that

where the constant $\mathfrak{C}$ depends on $\varepsilon$, $\alpha$ and $\beta$. We note that the dependence of $\mathfrak{C}$ on $B_0$ is dropped as this was introduced in the proof of Theorem (ref) as a consequence of the contraction inequality. The rest of the proof is identical to that of Theorem (ref).

Proof of Proposition (ref)

Fix $P \in \mathcal{P}$. Beginning with the statement of Theorem (ref), it is immediate that

where $C$ is a universal constant and $B^2 = \operatorname{\mathbb{E}}_P^1[W_1^2]$ and the second inequality follows from Proposition (ref). We now provide the upper bounds on two terms in the parenthesis.

First, by adding and subtracting terms, we obtain

We invoke technical Lemma (ref) provided below to control the approximation term. The equation (ref) implies that there exists $\varphi$ such that

holds for all $\widehat{\theta}_1$ such that $\|\widehat{\theta}_1-\theta(P)\| < \delta_0$. Hence, by the second statement of Lemma (ref),

assuming $\|\widehat{\theta}_1-\theta(P)\| < \delta$ for any $0 < \delta < \delta_0$. Similarly, by the third statement of Lemma (ref),

We thus obtain for any $0 < \delta < \delta_0$,

where we use the trivial bound of $\Delta_{n,P} \le 1$ in the case when $\|\widehat{\theta}_1-\theta(P)\| \ge \delta$. By taking the supremum over $\|t\|=1$, we conclude

for any $0 \le \delta < \delta_0$.

Proof of Proposition (ref)

We fix $P \in \mathcal{P}$ and $t \in \mathbb{R}^d$. We denote by $Z_t:=\langle t, Z\rangle$, which is a real-valued mean-zero random variable and $B_t = (\operatorname{\mathbb{E}}_P[Z_t^2])^{1/2}$. First, we prove $\eqref{eq:unif-integrable-def}\Longrightarrow$ uniform Lindeberg condition. We observe that

for any $\varepsilon > 0$. Hence we have

Assuming uniform integrability under standardization, the last display tends to zero as $\kappa \to \infty$ for fixed $\varepsilon > 0$, and then we take $\varepsilon \to 0$.

Next, we prove $\eqref{eq:norm-equivalence-def} \Longrightarrow \eqref{eq:unif-integrable-def}$. This follows since

as $\kappa \to \infty$. Hence the uniform integrability is implied. These two results establish

In fact, (ref) implies a stronger result than the uniform Lindeberg condition. To see this, we begin from (ref) above and obtain

Hence we have

as $\kappa \to \infty$ under the $L_{2+\delta}$-$L_2$ norm equivalence. Hence not only does the last expression tend to zero, but the rate of convergence is given by $O(\kappa^{-\delta})$.

Statistical Applications

This section contains all proofs associated with the statistical applications. We first provide notations to which we frequently refer. For any set $\Theta$ equipped with a metric $\|\cdot\|$, and any $\varepsilon > 0$, an $\varepsilon$-covering number $\mathcal{N}(\varepsilon,\Theta, \|\cdot\|)$ of $\Theta$ relative to the metric $\|\cdot\|$ is defined as the minimal number of $\|\cdot\|$-balls of radius less than or equal to $\varepsilon$ required for covering $\Theta$. On the other hands, the $\varepsilon$-bracketing number $\mathcal{N}_{[\,]}(\varepsilon,\Theta, \|\cdot\|)$ is the minimal number of “brackets" such that $[L, U] := \{f : L \le f \le U\}$ of size $\|U-L\|\le \varepsilon$ required for covering $\Theta$. In particular, we consider when $\Theta$ contains measurable functions of observations $Z_1\, \ldots, Z_n \in \mathcal{Z}$ and let $Q$ be any discrete probability measure on $Z_1\, \ldots, Z_n$. We define an envelop function $F$ of the class $\Theta$ as $F := z\mapsto \sup_{f\in\Theta}|f(z)|$. The uniform entropy numbers of $\Theta$ relative to $L_r$ is defined as

where $\|f\|_{Q,r} := \left(\sum_{i=1}^n f^r(z_i)Q(z_i)\right)^{1/r}$. Similarly, the bracketing entropy integral is defined as

crucially without taking the supremum over $Q$ and $\varepsilon$ is not normalized by the norm of the envelop function. We use the following result from van2011local:

An analogous result under the bracketing entropy integral is also available:

High-dimensional mean estimation

Misspecified linear regression

Manski's discrete choice model

In this example, we take \[m_{\theta} := (y,x) \mapsto -\frac{1}{2}\, y \cdot \mathrm{sgn}(\theta^\top x).\] whose envelop function for $m_{\theta}-m_{\theta_P}$ is trivially given by $M=1$. The leading constant $1/2$ is introduced without loss of generality.

Quantile estimation without positive densities

For given $\gamma \in (0,1)$, we consider the quantile loss defined as

Technical Lemma

We denote the localized collection of functions by

and let the envelope be denoted by $M_\delta := z \mapsto \sup_{m \in \mathcal{M}_{\delta}}|m(z)|$. The following result provides the upper bound on the expectation of the squared empirical process without requiring the boundedness assumption on the $\mathcal{M}_\delta$.

Additional Details on Numerical Results

This section presents supplementary results complementing those in Section (ref). We begin by stating and proving a lemma related to the confidence set $\widehat{\mathrm{CI}}^{\mathrm{SS+U}}_{N,\alpha}$. To recall, the set $\widehat{\mathrm{CI}}^{\mathrm{SS+U}}_{N,\alpha}$ is given by

We provide a short result to derive the semi-axes of an ellipsoid given by the Wald interval based on the asymptotic distribution. To recall, the confidence set is defined as

Finally, we provide a qualitative illustration of different confidence sets by visualizing the confidence regions in a bivariate setting. We generate $X_1, \ldots, X_{100}$ from a bivariate normal distribution $N(0, \Sigma)$ where

Figure (ref) displays the confidence regions three methods defined in Section (ref) for confidence levels of $95\%$, $85\%$, and $75\%$. This visualization highlights key qualitative differences between the methods. As shown, the proposed confidence sets (middle and right panels) are non-convex, whereas the Wald interval (left panel) forms an ellipse. Additionally, the proposed methods yield slighly enlarged confidence regions. Figure (ref) estimates that the confidence set in the right panel does not enlarge the Wald interval in the left panel by more than a factor of 2. We observe that this bound is indeed a moderate estimate, as the actual confidence sets may be much closer in size. A close inspection of the confidence set presented in the right panel, given by expression (ref), reveals that it coincides with the adaptive confidence sets by Robins2006 and dimension-agnostic confidence sets based on cross U-statistics proposed by kim2020dimension in their Appendix D (See the left panel of their Figure 3), though they did not provide a rigorous analysis. For mean estimation, these methods become identical.