Adaptive Minimax Regret against Smooth Logarithmic Losses over HighDimensional l1Balls via Envelope Complexity
[edit]
Proceedings of Machine Learning Research, PMLR 89:34403448, 2019.
Abstract
We develop a new theoretical framework, the envelope complexity, to analyze the minimax regret with logarithmic loss functions. Within the framework, we derive a Bayesian predictor that adaptively achieves the minimax regret over highdimensional l1balls within a factor of two. The prior is newly derived for achieving the minimax regret and called the spikeandtails (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.
Related Material


