Boosting for Vector-Valued Prediction and Conditional Density Estimation

Abstract

Despite the widespread use of boosting in structured prediction, a general theoretical understanding of aggregation beyond scalar losses remains incomplete. We study vector-valued and conditional density prediction under general divergences and identify stability conditions under which aggregation amplifies weak guarantees into strong ones. We formalize this stability property as \emph{$(α,β)$-boostability}. We show that geometric median aggregation achieves $(α,β)$-boostability for a broad class of divergences, with tradeoffs that depend on the underlying geometry. For vector-valued prediction and conditional density estimation, we characterize boostability under common divergences ($\ell_1$, $\ell_2$, $\TV$, and $\Hel$) with geometric median, revealing a sharp distinction between dimension-dependent and dimension-free regimes. We further show that while KL divergence is not directly boostable via geometric median aggregation, it can be handled indirectly through boostability under Hellinger distance. Building on these structural results, we propose a generic boosting framework \textsc{GeoMedBoost} based on exponential reweighting and geometric-median aggregation. Under a weak learner condition and $(α,β)$-boostability, we obtain exponential decay of the empirical divergence exceedance error. Our framework recovers classical algorithms such as \textsc{MedBoost}, \textsc{AdaBoost}, and \textsc{SAMME} as special cases, and provides a unified geometric view of boosting for structured prediction.