Precise Minimax Regret for Logistic Regression with Categorical Feature Values

Philippe Jacquet, Gil Shamir, Wojciech Szpankowski
Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:755-771, 2021.

Abstract

We study logistic regression with binary labels and categorical (discrete) feature values. Our goal is to evaluate precisely the (maximal) minimax regret. We express it as the so called Shtarkov sum known in information theory. To the best of our knowledge such a sum was never computed in the context of logistic regression. To be more precise, the pointwise regret of an online algorithm is defined as the (excess) loss it incurs over some value of a constant comparator (weight vector) that is used for prediction. It depends on the feature values, label sequence, and the learning algorithm. In the maximal minimax scenario we seek the best weights for the worst label sequence over all possible learning algorithms/ distributions, therefore it constitutes a lower bound for the pointwise regret. For finite dimension $d$ and $N$ distinct feature vectors we show that the maximal minimax regret grows as $$ \frac{d}{2} \log (T/2\pi)+C_d + O(N/\sqrt{T}) $$ where $T$ is the number of rounds of running a training algorithm and $C_d$ is explicitly computable constant that depends on the feature values and dimension $d$. We also extend these results to non-binary labels. The {\it precise} maximal minimax regret presented here is the first result of this kind. Our findings are obtained using tools of analytic combinatorics and information theory.

Cite this Paper

BibTeX
@InProceedings{pmlr-v132-jacquet21a, title = {Precise Minimax Regret for Logistic Regression with Categorical Feature Values}, author = {Jacquet, Philippe and Shamir, Gil and Szpankowski, Wojciech}, booktitle = {Proceedings of the 32nd International Conference on Algorithmic Learning Theory}, pages = {755--771}, year = {2021}, editor = {Feldman, Vitaly and Ligett, Katrina and Sabato, Sivan}, volume = {132}, series = {Proceedings of Machine Learning Research}, month = {16--19 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v132/jacquet21a/jacquet21a.pdf}, url = {https://proceedings.mlr.press/v132/jacquet21a.html}, abstract = {We study logistic regression with binary labels and categorical (discrete) feature values. Our goal is to evaluate precisely the (maximal) minimax regret. We express it as the so called Shtarkov sum known in information theory. To the best of our knowledge such a sum was never computed in the context of logistic regression. To be more precise, the pointwise regret of an online algorithm is defined as the (excess) loss it incurs over some value of a constant comparator (weight vector) that is used for prediction. It depends on the feature values, label sequence, and the learning algorithm. In the maximal minimax scenario we seek the best weights for the worst label sequence over all possible learning algorithms/ distributions, therefore it constitutes a lower bound for the pointwise regret. For finite dimension $d$ and $N$ distinct feature vectors we show that the maximal minimax regret grows as $$ \frac{d}{2} \log (T/2\pi)+C_d + O(N/\sqrt{T}) $$ where $T$ is the number of rounds of running a training algorithm and $C_d$ is explicitly computable constant that depends on the feature values and dimension $d$. We also extend these results to non-binary labels. The {\it precise} maximal minimax regret presented here is the first result of this kind. Our findings are obtained using tools of analytic combinatorics and information theory.} }
Endnote
%0 Conference Paper %T Precise Minimax Regret for Logistic Regression with Categorical Feature Values %A Philippe Jacquet %A Gil Shamir %A Wojciech Szpankowski %B Proceedings of the 32nd International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Vitaly Feldman %E Katrina Ligett %E Sivan Sabato %F pmlr-v132-jacquet21a %I PMLR %P 755--771 %U https://proceedings.mlr.press/v132/jacquet21a.html %V 132 %X We study logistic regression with binary labels and categorical (discrete) feature values. Our goal is to evaluate precisely the (maximal) minimax regret. We express it as the so called Shtarkov sum known in information theory. To the best of our knowledge such a sum was never computed in the context of logistic regression. To be more precise, the pointwise regret of an online algorithm is defined as the (excess) loss it incurs over some value of a constant comparator (weight vector) that is used for prediction. It depends on the feature values, label sequence, and the learning algorithm. In the maximal minimax scenario we seek the best weights for the worst label sequence over all possible learning algorithms/ distributions, therefore it constitutes a lower bound for the pointwise regret. For finite dimension $d$ and $N$ distinct feature vectors we show that the maximal minimax regret grows as $$ \frac{d}{2} \log (T/2\pi)+C_d + O(N/\sqrt{T}) $$ where $T$ is the number of rounds of running a training algorithm and $C_d$ is explicitly computable constant that depends on the feature values and dimension $d$. We also extend these results to non-binary labels. The {\it precise} maximal minimax regret presented here is the first result of this kind. Our findings are obtained using tools of analytic combinatorics and information theory.
APA
Jacquet, P., Shamir, G. & Szpankowski, W.. (2021). Precise Minimax Regret for Logistic Regression with Categorical Feature Values. Proceedings of the 32nd International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 132:755-771 Available from https://proceedings.mlr.press/v132/jacquet21a.html.

Related Material