← 研踪 PaperTrailarXiv:2611.25936 · v1
Hellinger Decision Trees for Density Ratio Estimation: Finite-Sample Guarantees
首次提交 2026-11-19 19:23
版本更新 2026-11-19 19:23
雷达观测 2026-11-20 19:57
摘要
Density ratios play a central role in two-sample comparison, distribution-shift adaptation, and generative-model evaluation. However, estimating a density ratio through separate estimation of the underlying densities can be unnecessarily challenging. In this paper, we develop a direct approach to the log density ratio estimation by minimizing a balanced Hellinger risk over additive ensembles of axis-aligned decision trees, trained using Newton boosting. We establish finite-sample guarantees for the estimator produced by the algorithm and derive an explicit convergence rate. Under suitable tail and Hölder smoothness conditions, together with an additional assumption on the progress made at each boosting iteration, our rate matches, up to logarithmic factors, the classical minimax-optimal rate for function estimation. A key technical contribution is an optimization analysis that exploits the special exponential structure of the Hellinger risk. In particular, we show that the decrease in the second-order Taylor approximation (which is computable) of the empirical risk controls the actual decrease in that risk, yielding a direct optimization guarantee for the boosting algorithm. This allows us to establish statistical convergence guarantees for the algorithm's output without relying on an idealized empirical-risk minimizer. Experiments on synthetic data corroborate the predicted convergence behavior, while experiments on public datasets demonstrate the practical effectiveness of the proposed estimator.
作者备注:45 pages, 5 figures, 2 tables
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-19 19:23 · 最新观测版本
Hellinger Decision Trees for Density Ratio Estimation: Finite-Sample Guarantees
Density ratios play a central role in two-sample comparison, distribution-shift adaptation, and generative-model evaluation. However, estimating a density ratio through separate estimation of the underlying densities can be unnecessarily challenging. In this paper, we develop a direct approach to the log density ratio estimation by minimizing a balanced Hellinger risk over additive ensembles of axis-aligned decision trees, trained using Newton boosting. We establish finite-sample guarantees for the estimator produced by the algorithm and derive an explicit convergence rate. Under suitable tail and Hölder smoothness conditions, together with an additional assumption on the progress made at each boosting iteration, our rate matches, up to logarithmic factors, the classical minimax-optimal rate for function estimation. A key technical contribution is an optimization analysis that exploits the special exponential structure of the Hellinger risk. In particular, we show that the decrease in the second-order Taylor approximation (which is computable) of the empirical risk controls the actual decrease in that risk, yielding a direct optimization guarantee for the boosting algorithm. This allows us to establish statistical convergence guarantees for the algorithm's output without relying on an idealized empirical-risk minimizer. Experiments on synthetic data corroborate the predicted convergence behavior, while experiments on public datasets demonstrate the practical effectiveness of the proposed estimator.
查看此版本解读 →查看此版本原文 ↗