CS Paper Radar

Sharp Minimax Regret for Infinite-Memory Logistic Prediction

Vaneet Aggarwal

cs.IT cs.LG ·submitted 2026-08-27 01:31 UTC · v3
theory

Abstract

We study sequential prediction of binary marks whose log-odds are a linear function of all past inputs. The inputs are independent uniform signs. The coefficient of the input observed $j$ steps earlier is unknown, but its absolute value is at most a known number $r_j$, and $\sum_j r_j\le B$. A learner is judged by its expected cumulative log loss in excess of the loss of the true conditional probabilities. We show that for every such sequence $r$ and every horizon $T$, the minimax value of this regret lies between $c\,Γ_T(r)/\max\{1,B^2\}$ and $\frac12Γ_T(r)$, where $Γ_T(r)=\sum_{j\le T}\log(1+(T-j+1)r_j^2)$ and $c$ is an absolute constant. The term for lag $j$ combines the size bound $r_j$ with the number $T-j+1$ of rounds in which that lag influences a prediction, and no monotonicity or other regularity of $r$ is needed. The upper bound is attained by a Bayesian mixture with independent Gaussian priors. For the lower bound, we apply the van Trees inequality at each prediction step and then bound the expected log-determinant of the random matrix whose rows are the lagged input vectors. We also characterize when $\frac12$ is the exact leading constant: for envelopes with a common bound $B$, possibly changing with $T$, the regret is asymptotic to $\frac12Γ_T(r)$ if and only if $\sum_{j\le T}\min\{1,(T-j+1)r_j^2\}=o(Γ_T(r))$. This gives, for example, $\log^2(A^2T)/(8α)$ for $r_j=Ae^{-αj}$, whereas for $r_j=Aj^{-s}$ with $s>1$ the regret is of order $T^{1/(2s)}$ and its ratio to $Γ_T(r)$ stays below $\frac12$. Finally, for a known horizon, an online Newton predictor with features scaled by $r_j$ attains regret of order $Γ_T(r)$ with polynomial computation per round.

Closest papers

Nearest neighbours by meaning across the whole index.

Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant

cs.LG stat.ML ·2026-09-23 ·Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta +2 more
similarity 0.70
Abstract

Prediction with expert advice is a fundamental problem in online learning. When the time horizon $T$ is known in advance, the minimax cumulative regret over $n$ experts is asymptotically $\sqrt{\frac{T \ln n}{2}}$. This is achieved by the Multiplicative Weights Update algorithm with a learning rate tuned to $T$, and is known to be tight. If instead the regret bound is required to hold simultaneously at every time $t$, the best known guarantee has been $\sqrt{t \ln n}$---a factor of $\sqrt{2}$ worse---and it has remained unknown whether this factor of $\sqrt{2}$ is necessary. We show that it is not. We give an algorithm, requiring no knowledge of the horizon, whose cumulative regret satisfies $R_t \le \bigl(1 + O(\sqrt{\ln \ln n / \ln n})\bigr)\sqrt{t \ln n / 2}$ simultaneously for every $t \ge 1$.

0.32

Lower Bounds for Linear-Oracle Online Learning

cs.LG stat.MLmath.OC ·2026-09-29 ·Mohit Sinha
theory similarity 0.68
Abstract

Can a constant number of linear minimizations per round improve on the $T^{3/4}$ regret rate of online Frank-Wolfe on general convex sets? Weibel et al. conjectured that fixed-coefficient methods cannot. We prove their conjecture and extend the lower bound to every deterministic learner in an oracle-only model. The learner receives an initial feasible point and a diameter bound, and must remain feasible on every domain consistent with its oracle replies. For $T$ rounds, at most $b$ calls between decisions, diameter bound $D$, and gradient norm bound $L$, we construct an instance in dimension $d=2b(T-1)+1$ with regret at least $2^{-1/4}LDb^{-1/4}T^{3/4}$. The adversary fixes the domain, initial point, deterministic tie rule and linear losses before play. The vertices form a path on which every point available before a decision has zero current loss, while the final vertex has negative loss on every round. For constant $b$, the result matches the known upper rate for dimension-independent guarantees. For one-call fixed schedules with a nonzero coefficient on the newest gradient, a second construction gives regret at least $3LDT^{3/4}/4$ with unique minimizers at every issued query. Exact-arithmetic certificates for the tuned schedule of Weibel et al. closely match their finite-horizon numerical worst cases, with unique oracle replies.

0.08

Minimax Alternating Regret for the Experts Problem and Online Convex Optimization

cs.LG stat.ML ·2026-08-25 ·Mengxiao Zhang
theory similarity 0.66
Abstract

In this paper, we study alternating regret in online convex optimization (OCO), motivated by the success of alternating learning dynamics in two-player games. Although previous works have shown that $o(\sqrt{T})$ alternating regret is achievable under various assumptions on the loss functions and feasible domains, the minimax regret rate has remained open even for the expert problem. In this paper, we resolve this question by showing matching lower and upper bounds for both the expert problem and general OCO. Somewhat surprisingly, for the $d$-expert problem, we show that the minimax alternating regret is $Θ(\log d)$ by providing both a lower bound and an algorithm achieving a matching upper bound. This significantly improves upon the $O(T^{1/3}\log^{2/3} d)$ established by [HLLZ25]. We further extend our results to general OCO over a $d$-dimensional compact convex set and prove that the worst-case minimax alternating regret is $Θ\left(d\log \left(1+\frac{T}{d}\right)\right)$, also significantly improving upon the $O((d\log T)^{2/3}T^{1/3})$ upper bound and resolving the open problem posed by [CCK+23,HLLZ25]. As a direct implication, our alternating dynamics achieve $O(\frac{\log d}{T})$ convergence to Nash equilibrium in two-player zero-sum games, matching the state of the art, and give the first such convergence rate to coarse correlated equilibrium in two-player general-sum games. Technically, our upper bound for the expert problem is achieved by a corrected variant of Hedge. We extend the same corrected-potential argument to continuous action sets to obtain the optimal alternating-regret rate for OCO. For the lower bounds, the construction for the expert problem repeatedly eliminates half of the candidate experts, while the OCO lower bound instance construction replaces this discrete elimination by a more involved multiscale construction on the unit disk.

0.26

Prediction with Expert Advice under Heavy-Tailed Losses

cs.LG stat.ML ·2026-10-10 ·Yuki Shibukawa, Shinji Ito
hot direction similarity 0.65
Abstract · 49 pages

We study prediction with expert advice over $T$ rounds with $K$ experts under heavy-tailed losses whose $(1+ε)$-moment is bounded by $θ>0$ for some $ε\in(0,1]$. In this setting, existing algorithms designed for the case $ε=1$ can be suboptimal when $ε<1$, suffering an additional polynomial dependence on $K$. We characterize the minimax pseudo-regret rate as $Θ((θT)^{\frac{1}{1+ε}}(\log K)^{\fracε{1+ε}})$ and establish gap-dependent lower bounds in a self-bounded environment. To attain this minimax rate without prior knowledge of either $ε$ or $θ$, we propose Adaptive Heavy-Tailed FTRL, which uses robust data-dependent scale adaptation together with truncation. We further develop Adaptive Heavy-Tailed OMD, which likewise requires neither $ε$ nor $θ$ and achieves near-optimal regret guarantees in both adversarial and self-bounded environments. Finally, when $ε$ and $θ$ are known, an FTRL algorithm with Shannon-entropy regularization achieves optimal regret guarantees in both environments.

0.30

A General $\widetildeΩ(\sqrt{T γ_T})$ Lower Bound for Kernel Bandits

cs.IT stat.MLcs.LG ·2026-10-08 ·Chenkai Ma, Jonathan Scarlett
theory similarity 0.65
Abstract

The kernel bandit problem consists of sequentially optimizing an unknown function with noisy feedback, where the function has bounded norm in a given Reproducing Kernel Hilbert Space (RKHS). A central quantity in the regret analysis of kernel bandits is the maximum information gain $γ_T$. In particular, the best existing upper bounds scale as $\sqrt{Tγ_T}$ up to log factors, and nearly-matching lower bounds have been derived for specific kernels such as squared exponential and Matérn. However, lower bounds for general kernels are lacking, thus making it unclear in what generality the upper bounds are near-optimal. In this paper, we establish a general $Ω(\sqrt{Tγ_T/\log T})$ minimax regret lower bound for non-constant continuous kernels on compact domains, establishing near-optimality (within log factors) in a very general sense. We show that the log factor appearing in this bound is unavoidable in general, but that it can be removed under certain conditions. Among other things, our findings imply that the minimax-optimal scaling is exactly $Θ(\sqrt{Tγ_T})$ (i.e., within constant factors) for the Matérn-$ν$ kernel with $ν\in (0,2)$, $γ$-exponential kernel with $γ\in (0,2)$, and certain piecewise-polynomial kernels.

0.21

Achieving Minimax-Optimal First-Order and Best-of-Both-Worlds Regret Simultaneously in Multi-Armed Bandits

cs.LG ·2026-10-29 ·Mengxiao Zhang
similarity 0.64
Abstract

We study first-order and best-of-both-worlds regret guarantees in multi-armed bandits. Pogodin and Lattimore (2019) proposed an algorithm that combines minimax-optimal worst-case regret with a first-order guarantee whose loss-dependent term is $\mathcal{O}(\sqrt{K L^\star}\log T)$, where $T$ denotes the horizon, $L^\star$ denotes the smallest expected cumulative loss among fixed arms, and $K$ denotes the number of arms. However, a logarithmic gap remains between this loss-dependent term and the optimal first-order scale. In this paper, we remove this logarithmic factor by proposing an efficient and parameter-free algorithm that achieves the minimax optimal first-order regret guarantee $\mathcal{O}(\sqrt{K L^\star})$. Technically, our algorithm is built upon FTRL with a Tsallis entropy regularizer (Zimmert and Seldin,2021), with a learning rate adapted to the learner's cumulative loss and a sampling distribution determined by a scalar fixed point. This construction controls the combined estimation and stability cost in terms of the learner's loss. Moreover, we show that the same algorithm achieves a best-of-both-worlds guarantee, with $\mathcal{O}(\sum_{i\ne i^\star}\frac{\log T}{Δ_i})$ regret for i.i.d. losses with a unique best arm $i^\star$, where $Δ_i$ denotes the suboptimality gap of arm $i$.

0.10

Optimal Alternating Regret for Online Learning and Games

cs.LG cs.GTstat.ML ·2026-08-25 ·Yixin Tao, Weiqiang Zheng
theoryhighly cited similarity 0.64
Abstract · 21 pages

We settle the minimax-optimal alternating regret, a regret notion motivated by alternating learning dynamics in games, for both online linear optimization (OLO) and online convex optimization (OCO). For OLO over the probability simplex $Δ_d$, we give an algorithm with $O(\log d)$ alternating regret that remains a constant for any time horizon $T$, and a matching lower bound. Our constant regret bound significantly improves previous results with $O(\log ^{2/3}d \cdot T^{1/3})$ regret [Cevher, Cutkosky, Kavis, Piliouras, Skoulakis, Viano, NeurIPS 2023, Hait, Li, Luo, Zhang, COLT 2025]. As a result, we obtain alternating learning dynamics with $O(\log d /T)$ convergence to Nash equilibria in two-player zero-sum games and $O(\log d /T)$ convergence to coarse correlated equilibria in two-player general-sum games. This is the first uncoupled learning dynamics with $O(1/T)$ convergence to CCE in two-player general-sum games, while all prior works suffer additional $\log T$ factors. For general OCO over a $d$-dimensional compact convex set, we give an algorithm with $O(d\log (1+T/d))$ alternating regret, improving the previous best of $\widetilde{O}(d^{2/3}T^{1/3})$. We also prove a matching lower bound of $Ω(d\log (1+T/d))$, showing that the $Ω(\log T)$ factor is unavoidable.

0.32

From Approachability Residuals to Anytime-Valid Evidence: The Online Convex Geometry of Testing by Betting

cs.LG ·2026-08-10 ·Jinze Zhao
theory similarity 0.64
Abstract

Betting-based sequential tests and Blackwell approachability are linked by a rate-explicit reduction through support-function residuals. For a compact convex target $S$ and vector observations $r_t$, an OCO learner selects a predictable normal $w_t$ and produces $q_t=\langle w_t,r_t\rangle-h_S(w_t)$. We prove the exact pathwise identity $$ \dist(\bar r_T,S) =\frac1T\sum_{t=1}^Tq_t+\frac{\Reg_T}{T}. $$ When $|q_t|\leq B$, composing this identity with one-sided betting yields a finite-time transfer: if the OCO and log-wealth regrets are at most $a_T$ and $\ell_T$, respectively, then a target gap exceeding \[ \frac{a_T}{T} +2B\sqrt{\frac{\log(1/α)+\ell_T}{T}} \] forces rejection by time $T$, while non-rejection certifies the converse radius. We then formulate a controlled stochastic experiment in which an action selected after $w_t$ satisfies Blackwell's supporting-halfspace condition for every null mean payoff. The resulting wealth is an e-process under adaptive nulls; sublinear OCO regret gives stochastic approachability, whereas persistent mean separation under an alternative gives exponential wealth at rate at least $δ^2/(4B^2)$. Deterministic Blackwell games and passive tests are, respectively, the noise-free and singleton-action cases of this protocol. Bounded two-sample means, kernel MMD, and active heterogeneous data sources instantiate the reduction. The resulting connection is exact algebraically, quantitative at finite time, and operational when experiments are controlled.

0.04