Adaptive Minimax Regret against Smooth Logarithmic Losses over High-Dimensional $\ell_1$-Balls via Envelope Complexity
This work addresses the challenge of adaptive prediction in high-dimensional settings for statistical learning, though it appears incremental as it builds on existing regret bounds.
The paper tackles the problem of minimax regret with logarithmic loss functions over high-dimensional ℓ₁-balls by developing a new theoretical framework called envelope complexity, resulting in a Bayesian predictor that adaptively achieves the minimax regret within a factor of two, as confirmed in preliminary experiments where it outperforms conventional methods.
We develop a new theoretical framework, the \emph{envelope complexity}, to analyze the minimax regret with logarithmic loss functions and derive a Bayesian predictor that adaptively achieves the minimax regret over high-dimensional $\ell_1$-balls within a factor of two. The prior is newly derived for achieving the minimax regret and called the \emph{spike-and-tails~(ST) prior} as it looks like. The resulting regret bound is so simple that it is completely determined with the smoothness of the loss function and the radius of the balls except with logarithmic factors, and it has a generalized form of existing regret/risk bounds. In the preliminary experiment, we confirm that the ST prior outperforms the conventional minimax-regret prior under non-high-dimensional asymptotics.