Technical Summary: Active Subsampling for Measurement-Constrained M-Estimation of Individualized Thresholds with High-Dimensional Data

1. Problem Formulation

The paper addresses the problem of estimating an optimal individualized threshold in high-dimensional settings under measurement constraints. This scenario arises frequently in modern applications, such as electronic health record (EHR) studies, where covariates $(X, Z)$ are available for a large population, but the response variable $Y$ (e.g., a clinical outcome requiring manual chart review) is expensive or time-consuming to obtain. Consequently, only a small subset of size $N$ (the label budget) can be labeled from a large unlabeled dataset of size $n$ ($N \ll n$).

The specific goal is to estimate a high-dimensional parameter $\theta^* \in \mathbb{R}^d$ defining a linear threshold $c(Z) = \theta^{*T}Z$ for a continuous variable $X$. The optimal threshold minimizes the discrepancy between the event $\{X > \theta^T Z\}$ and a binary outcome $Y \in \{-1, +1\}$. Formally, this is framed as an M-estimation problem:
$$\theta^* = \arg\min_{\theta} R(\theta), \quad \text{where} \quad R(\theta) = \mathbb{E}\left[\gamma(Y) L_{01}\{Y(X - \theta^T Z)\}\right]$$
Here, $L_{01}$ is the 0-1 loss, and $\gamma(\cdot)$ is a weight function. The problem is characterized by:

• Non-regularity: The 0-1 loss leads to non-standard limiting distributions and convergence rates (typically slower than the parametric $N^{-1/2}$ rate).
• High-dimensionality: The dimension $d$ may exceed the sample size, requiring sparsity assumptions ($s$-sparse $\theta^*$).
• Measurement Constraints: The estimation process must actively select which data points to label to maximize efficiency, rather than relying on random sampling.

2. Methodology

The authors propose a K-step active subsampling algorithm that iteratively refines the estimator by focusing labeling efforts on the most informative data points.

Core Mechanism

The algorithm operates on the insight that observations where the residual $X - \theta^T Z$ is close to zero (i.e., "near-threshold" points) provide the most information for estimating $\theta^*$. The procedure is as follows:

1. Initialization: Uniformly sample a small subset from the unlabeled data to obtain an initial estimator $\hat{\theta}_1$ using a regularized M-estimator with a smoothed surrogate loss.
2. Active Set Construction: For subsequent iterations $k=2, \dots, K$, define an "active set" $S_k$ containing data points $(X, Z)$ where the estimated residual is small:
   $$S_k = \left\{ (X, Z) : -b_{k-1} \leq \frac{X - \hat{\theta}_{k-1}^T Z}{\sqrt{1 + \|\hat{\theta}_{k-1}\|_2^2}} \leq b_{k-1} \right\}$$
   where $b_{k-1}$ is a tuning parameter controlling the width of the interval.
3. Active Sampling: Sample points from the remaining unlabeled data that fall within $S_k$ with a probability proportional to the budget allocated to that step. Points outside $S_k$ are not labeled.
4. Estimation: Solve a regularized M-estimator on the newly labeled data to update the estimator to $\hat{\theta}_k$.
5. Iteration: Repeat until $K$ steps are completed.

Technical Components

• Smoothed Surrogate Loss: To address the computational intractability of the 0-1 loss and the non-regularity of the problem, the authors use a kernel-smoothed loss function $L_\delta(u) = \int_{u/\delta}^\infty K(t) dt$, where $K$ is a kernel function and $\delta$ is a bandwidth.
• Regularization: An $\ell_1$-penalty is applied to handle high dimensionality ($d \gg N$).
• Path-Following Algorithm: To solve the non-convex optimization problem efficiently, the authors employ a path-following algorithm (Feng et al., 2022) that computes approximate local solutions.

3. Key Theoretical Contributions

The paper establishes a sharp phase transition in the convergence rates of the proposed estimator based on the smoothness parameter $\beta$ of the conditional density of $X$ given $Y$ and $Z$.

Convergence Rates

Let $N$ be the total label budget, $s$ be the sparsity, and $d$ be the dimension. The convergence rate in $\ell_2$ norm depends on $\beta$:

1. Case $\beta > (1+\sqrt{3})/2 \approx 1.37$:

   • A two-step algorithm ($K=2$) suffices to achieve the parametric rate:
     $$\|\hat{\theta}_K - \theta^*\|_2 = O_p\left(\sqrt{\frac{s \log d}{N}}\right)$$
   • This rate is strictly faster than the minimax optimal rate $O_p((s \log d / N)^{\beta/(2\beta+1)})$ achievable with $N$ i.i.d. samples from the population, demonstrating the benefit of active sampling.

2. Case $1 < \beta \leq (1+\sqrt{3})/2$:

   • The two-step algorithm is sub-optimal.
   • To recover the parametric rate, the number of steps $K$ must be increased to a fixed finite value: $K = \lceil \log_{\frac{\beta}{2\beta+1}}(1 - \frac{\beta+1}{2\beta^2}) \rceil + 1$.

3. Case $0 < \beta \leq 1$:

   • The estimator cannot reach the parametric rate with a fixed number of steps.
   • A super-parametric rate is achieved: $O_p((s/N)^{1/(2\beta)})$ (up to logarithmic factors).
   • This requires the number of steps $K$ to grow slowly with $N$: $K = \lceil \log_{2\beta+1}(\log N) \rceil$.

Minimax Optimality

The authors formulate an $N$-budget minimax framework where the sampling distribution $Q$ is chosen to minimize the worst-case risk. They prove that the lower bound for the minimax risk is:
$$\inf_{Q} \inf_{\hat{\theta}} \sup_{P} \mathbb{E}_{P,Q} \|\hat{\theta} - \theta^*(P)\|_2 \gtrsim \left(\frac{s \log(d/s)}{N}\right)^{\frac{1}{2(\beta \wedge 1)}}$$
The proposed active subsampling estimator achieves this rate (up to logarithmic factors), proving it is minimax rate optimal in the measurement-constrained setting.

Adaptation

The paper develops Lepski's methods to adapt to unknown smoothness $\beta$ and sparsity $s$, allowing the algorithm to select tuning parameters without prior knowledge of these quantities.

4. Empirical Results

• Simulations: The method was tested on synthetic data under three models: logistic regression, conditional mean models, and general binary response models. The "two-step active subsampling with path-following" method consistently outperformed passive subsampling (uniform random sampling) and standard $\ell_1$-penalized logistic regression, particularly in terms of $\ell_1$ and $\ell_2$ estimation errors.
• Real Data Application: The method was applied to a diabetes dataset from 130 US hospitals (UCI repository) to predict early readmission based on HbA1c levels. The active subsampling approach identified important covariates (e.g., "time in hospital," "change of medications") and achieved lower estimation errors compared to passive sampling under various label budgets ($N=3000, 4000, 5000$).

5. Significance and Claims

The paper claims to provide a computationally and statistically efficient solution for estimating individualized thresholds when labeling data is costly. Its primary significance lies in:

1. Accelerating Convergence: Demonstrating that active sampling can break the non-regular convergence barrier, achieving parametric rates (or super-parametric rates) that are unattainable with passive sampling under the same budget.
2. Theoretical Precision: Characterizing the exact conditions (via the smoothness parameter $\beta$) under which a simple two-step procedure is sufficient versus when more complex iterative schemes are required.
3. Practical Feasibility: Proposing a gradient-based, path-following algorithm that is computationally tractable for high-dimensional data, unlike many active learning methods that require minimizing the non-convex 0-1 loss directly.
4. Optimality: Establishing that the proposed method is minimax optimal, meaning no other sampling strategy can achieve a faster rate of convergence in the worst-case scenario.

The authors emphasize that their work bridges the gap between non-regular statistical estimation and active learning, offering a rigorous framework for measurement-constrained problems in high dimensions.