Name
Abstract | ||
|---|---|---|
We study online logistic regression with binary labels and general feature values in which a learner tries to predict an outcome/ label based on data/ features received in rounds. Our goal is to evaluate precisely the (maximal) minimax regret which we analyze using a unique and novel combination of information-theoretic and analytic combinatorics tools such as Fourier transform, saddle point method, and Mellin transform in the multi-dimensional settings. To be more precise, the pointwise regret of an online algorithm is defined as the (excess) loss it incurs over a constant comparator which is used for prediction. In the minimax scenario we seek the best learning distribution for the worst label sequence. For dimension d = o(T
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/3</sup>
) we show that the maximal minimax regret grows as $d/2 \cdot \log (2T/\pi ) + {C_d} + O\left({{d^{3/2}}/\sqrt T }\right)$ where T is the number of rounds of running a training algorithm and C
<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</inf>
is explicitly computable constant that depends on dimension d and feature values. We compute explicitly the constant C
<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</inf>
for features uniformly distributed on a d-dimensional sphere or ball. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1109/ISIT50566.2022.9834809 | 2022 IEEE International Symposium on Information Theory (ISIT) |
Keywords | DocType | ISSN |
precise minimax regret,online logistic regression,binary labels,general feature values,unique combination,information-theoretic,analytic combinatorics tools,Fourier transform,saddle point method,multidimensional settings,pointwise regret,online algorithm,constant comparator,minimax scenario,learning distribution,worst label sequence,maximal minimax regret,training algorithm | Conference | 2157-8095 |
ISBN | Citations | PageRank |
978-1-6654-2160-7 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Philippe Jacquet | 1 | 714 | 90.11 |
| Gil I. Shamir | 2 | 0 | 1.01 |
| Wojciech Szpankowski | 3 | 1557 | 192.33 |