Precise Regularized Minimax Regret With Unbounded Weights

In online learning, a learner receives data in rounds and, at each round, predicts a label that is then compared to the true label, incurring a loss. The total loss over <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</i> rounds, when compared to the loss of the best expert from a class of experts or forecasters, is called the regret. In this paper, we focus on logarithmic loss for logistic-like experts with <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">unbounded d</i>-dimensional weights, a scenario that has been largely unexplored. To address the irregularities introduced by the unbounded weight norm, we introduce a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">regularized</i> version of the average (fixed design) minimax regret by imposing a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">soft constraint</i> on the weight norm. We demonstrate that the regularized minimax regret is fully characterized by a complexity measure we term the regularized Shtarkov sum. We also show how the behavior of the standard regret can be inferred from the regularized regret. Our main results provide a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">precise</i> characterization of the regularized Shtarkov sum and, consequently, the regularized regret with unbounded weights up to second-order asymptotics. Notably, unlike the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</i>/2 log <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</i> regret growth known for bounded weights, our results imply that the regularized regret grows as (1/2+α/4)<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</i> log <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</i> when the regularization parameter is of order Θ(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">−α</sup>) for α ≤ 1/2. We achieve this using tools from analytic combinatorics, including multidimensional Fourier analysis, the saddle point method, and the Mellin transform.