Adaptive deep nonparametric regression from dependent data under covariate shift

Technical Summary: Adaptive Deep Nonparametric Regression from Dependent Data under Covariate Shift

Problem Statement
This paper addresses the challenge of nonparametric regression using deep neural networks (DNNs) in settings where the training (source) and testing (target) data follow different distributions, a phenomenon known as covariate shift. Specifically, the marginal distribution of the covariates in the source data ($P_{X_0}$) differs from that in the target data ($Q_{X_0}$), while the conditional distribution of the response given the covariates remains invariant ($P_{Y_0|X_0} = Q_{Y_0|X_0}$).

The study extends existing literature in three critical directions:

1. Dependent Observations: Unlike prior works that primarily assume independent and identically distributed (i.i.d.) data, this paper considers data generated from stationary and ergodic processes, including $\phi$-mixing, strong mixing, and C-mixing processes.
2. Robust Loss Functions: The authors investigate both Huber regression (for robustness against outliers and heavy-tailed errors) and quantile regression, moving beyond the standard least-squares or ReLU-based approaches often found in covariate shift literature.
3. Adaptive Regularization: The paper proposes Sparse-Penalized Deep Neural Network (SPDNN) estimators. Unlike previous methods relying on sparsity-constrained regularization with a fixed, unknown sparsity level $S$, this approach uses a penalty term that allows the estimators to adaptively attain optimal convergence rates without prior knowledge of the target function's smoothness.

Methodology
The authors model the data as a stationary process $Z_t = (X_t, Y_t)$ satisfying $Y_t = h_0(X_t) + \xi_t$, where $h_0$ is the unknown regression function and $\xi_t$ is a centered i.i.d. error process. To handle covariate shift, the methodology relies on the density ratio $r(x) = q_{X_0}(x) / p_{X_0}(x)$.

The core methodology involves:

• Generalized Bernstein-type Inequality: To handle dependent data, the authors utilize a generalized Bernstein-type inequality satisfied by various mixing processes. This inequality introduces an "effective number of observations," denoted as $\phi(n)$, which replaces the sample size $n$ in convergence rate analyses.
• SPDNN Estimators: The estimators are defined by minimizing a loss function (Huber or quantile) plus a sparse penalty term $J_n(h)$. The penalty is based on a function $\pi_{\lambda_n, \tau_n}$ (e.g., clipped $L_1$ or SCAD) applied to the network parameters.
• Two-Step Pre-Training Procedure (Unknown Density Ratio): When $r(x)$ is unknown, a two-step procedure is proposed:
  1. Step 1: Estimate the density ratio $r$ using a least-squares SPDNN estimator ($\hat{r}_S$) trained on unlabeled source and target samples. If $r$ is unbounded, a truncated version ($T_\eta r$) is estimated.
  2. Step 2: Construct a reweighted SPDNN estimator for the regression function $h_0$ using the estimated density ratio from Step 1.
• Truncation for Unbounded Ratios: In cases where the density ratio is unbounded but possesses finite moments, the authors employ a truncated density ratio $T_\eta r(x) = \min(r(x), \eta)$ to ensure stability and derive error bounds.

Key Contributions

1. Unified Theory for Dependent Data: The paper unifies the theoretical analysis for various dependence structures ($\phi$-mixing, strong mixing, C-mixing) under a single framework using the effective sample size $\phi(n)$.
2. Adaptive Minimax Optimality: The proposed SPDNN estimators are shown to adaptively attain the minimax optimal convergence rate (up to a logarithmic factor) for Hölder smooth functions. This holds for both i.i.d. data and classical time series models, even when the density ratio is unknown or unbounded (provided it has sufficient moments).
3. Extension to Huber and Quantile Regression: The authors establish non-asymptotic error bounds for both Huber and quantile regression under covariate shift, addressing the specific calibration issues of the Huber loss parameter in this context.
4. Two-Step Pre-Training Analysis: The paper provides rigorous non-asymptotic $L^2(Q_{X_0})$ error bounds for the pre-training reweighted estimators, demonstrating that the error from estimating the density ratio does not degrade the overall convergence rate of the regression estimator when the sample sizes are appropriately balanced.

Results
The paper establishes non-asymptotic error bounds in the $L^2(Q_{X_0})$ norm for the proposed estimators.

• Unweighted Estimators: Under the assumption that the density ratio is uniformly bounded, the unweighted SPDNN estimator achieves the minimax rate. However, if the ratio is unbounded (but has finite second-order moments), the rate becomes suboptimal.
• Reweighted Estimators: When the density ratio is known and uniformly bounded, the reweighted SPDNN estimator achieves the minimax optimal rate $O((\phi(n))^{-2s/(2s+d)})$, where $s$ is the smoothness parameter.
• Truncated Reweighted Estimators: When the density ratio is unbounded but has finite moments of any order, the reweighted estimator using a truncated density ratio also achieves the minimax optimal rate (up to logarithmic factors).
• Pre-Training Estimators: When the density ratio is unknown and estimated via a two-step procedure, the resulting estimator maintains the minimax optimal rate, provided the sample size used for estimating the density ratio is sufficiently large relative to the regression sample size.

These results are summarized in Table 1 of the paper, which details convergence rates for i.i.d., $\phi$-mixing, exponential $\alpha$-mixing, and geometrically C-mixing processes.

Significance and Claims
The paper claims to extend the theoretical guarantees of deep nonparametric regression to more realistic scenarios involving dependent data and distribution shifts. By introducing sparse-penalized regularization, the authors provide estimators that are adaptive, removing the need for the practitioner to know the smoothness of the target function or the sparsity level in advance.

The authors highlight that their work generalizes previous results (specifically those in [11]) by:

1. Incorporating dependent observations through a generalized Bernstein inequality.
2. Addressing Huber regression, which is crucial for heavy-tailed data where least squares fail to achieve minimax rates.
3. Utilizing sparse-penalized regularization to achieve adaptivity, contrasting with non-adaptive sparsity-constrained methods.

The significance lies in providing a robust theoretical framework for applying deep learning in domains like healthcare and natural language processing, where distribution mismatches and temporal dependencies are common, ensuring that estimators remain optimal even under these complex conditions.