Research map / Learning theory and algorithms / Sample complexity
Minimax Optimal Two-Stage Algorithm For Moment Estimation Under Covariate Shift
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives a minimax lower bound for estimating the q-th moment of a Sobolev function under covariate shift with known densities, proposes a two-stage control-variate estimator that attains it up to log factors, and adds a truncated, plug-in version with double robustness for unknown likelihood ratios.
Problem
Estimating the q-th moment of an unknown smooth function under the target distribution when only labeled samples from a shifted source distribution are available; prior work does not establish the optimal rate for moments or how to keep a nonparametric estimator optimal under covariate shift.
Approach
A two-stage estimator: fit an optimal nonparametric regressor on half the source sample, then correct its target-moment plug-in using importance-weighted residuals from the other half (control-variate style), with likelihood-ratio truncation and unlabeled target samples for the unknown-density case.
Key results
- Two-stage estimator attains the minimax rate up to a log factor: error bound B·b̄·n^{max{-q(s/d-1/p)-1, -1/2-s/d}}.
- Truncated estimator gives a B-independent bound of b̄·r(n)^{α/(α+1)}, and the plug-in version adds only an m^{-1/2} term.
- Simulations (100 repeats, random forest) show Monte Carlo beats two-stage at B=1, while the two-stage estimator is more accurate and stable as B grows.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a two-stage estimator with likelihood-ratio-weighted residual calibration | Moment estimation under covariate shift with known source and target distributions · Moment estimation under covariate shift | expected absolute error rate: \lesssim B \cdot \bar{b} \cdot n^{\max\{-q(\frac{s}{d}-\frac{1}{p})-1,-\frac{1}{2}-\frac{s}{d}\}} | Helped |
| Add truncation of likelihood ratios at threshold T (ablation) | Two-stage moment estimator · Moment estimation with bounded-tail likelihood ratios | stability: \lesssim \bar{b} \cdot r(n)^{\frac{\alpha}{\alpha+1}} | Helped |
| Estimate the target expectation from m unlabeled target samples and use an estimated, truncated likelihood ratio | Two-stage moment estimator · Moment estimation under covariate shift with unknown distributions | expected absolute error: m^{-\frac{1}{2}} | Mixed |
| Use the two-stage estimator instead of the Monte Carlo estimator | Synthetic covariate-shift experiments · Synthetic data, B = 1 | L1 error | Hurt |
| Use the two-stage estimator instead of the Monte Carlo estimator | Synthetic covariate-shift experiments · Synthetic data, increasing B | L1 error | Helped |
| Add truncation to the two-stage estimator (ablation) | Two-stage estimator · Synthetic covariate-shift experiments, B = 3.98, 12.08, and 23.03 | stability | Helped |
| Rely on consistency of either the likelihood-ratio estimator or the function estimator | Plug-in truncated estimator · Moment estimation under covariate shift | consistency | Helped |
Surprising findings
- Monte Carlo estimator outperforms the two-stage methods when there is no covariate shift (B=1).
Limitations
- Assumes p>=2, q<=p<=2q and a bounded source density, which may be restrictive.
- Truncation threshold T must be chosen by grid search since the constants are unknown.
- Analysis restricted to uniformly B-bounded likelihood ratios and moment functionals.
Experimental setup
Datasets: synthetic data generated from truncated normal and uniform distributions
Benchmarks: synthetic covariate shift experiments
Metrics: L1 error between true and estimated moment required sample size for target error
Baselines: Monte Carlo estimator one-stage estimator
Builds on: importance weighting under covariate shift regression-adjusted control variates method of two fuzzy hypotheses
Closest papers by meaning
- Maximum Likelihood Estimation is All You Need for Well-Specified Covariate Shift (ICLR 2024 · similarity 0.87)
- ReTaSA: A Nonparametric Functional Estimation Approach for Addressing Continuous Target Shift (ICLR 2024 · similarity 0.84)
- Adaptive Estimation and Learning under Temporal Distribution Shift (ICML 2025 · similarity 0.84)
- Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination (ICML 2025 · similarity 0.84)
- The Minimax Rate of Second-Order Calibration (NeurIPS 2026 · similarity 0.83)
- Quantifying Uncertainty in the Presence of Distribution Shifts (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.