Adaptive Minimax Regret against Smooth Logarithmic Losses over High-Dimensional l1-Balls via Envelope Complexity

Kohei Miyaguchi, Kenji Yamanishi
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:3440-3448, 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 high-dimensional l1-balls within a factor of two. The prior is newly derived for achieving the minimax regret and called the 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-miyaguchi19a, title = {Adaptive Minimax Regret against Smooth Logarithmic Losses over High-Dimensional l1-Balls via Envelope Complexity}, author = {Miyaguchi, Kohei and Yamanishi, Kenji}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {3440--3448}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/miyaguchi19a/miyaguchi19a.pdf}, url = {https://proceedings.mlr.press/v89/miyaguchi19a.html}, 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 high-dimensional l1-balls within a factor of two. The prior is newly derived for achieving the minimax regret and called the 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.} }
Endnote
%0 Conference Paper %T Adaptive Minimax Regret against Smooth Logarithmic Losses over High-Dimensional l1-Balls via Envelope Complexity %A Kohei Miyaguchi %A Kenji Yamanishi %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-miyaguchi19a %I PMLR %P 3440--3448 %U https://proceedings.mlr.press/v89/miyaguchi19a.html %V 89 %X 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 high-dimensional l1-balls within a factor of two. The prior is newly derived for achieving the minimax regret and called the 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.
APA
Miyaguchi, K. & Yamanishi, K.. (2019). Adaptive Minimax Regret against Smooth Logarithmic Losses over High-Dimensional l1-Balls via Envelope Complexity. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:3440-3448 Available from https://proceedings.mlr.press/v89/miyaguchi19a.html.

Related Material