The paper investigates feature priming in high‑dimensional online linear regression, showing that estimating feature weights from past data and refitting a minimum‑norm predictor can lead to regret that scales with sparsity rather than ambient dimension. It provides a negative answer to a COLT 2023 open problem by proving that three natural priming rules incur ≥Ω(min{T,√d}) regret against a zero‑loss one‑sparse comparator, due to cheap nuisance interpolation that underweights truly predictive coordinates. The authors also identify conditions under which regret is governed by data rank and present constructions that achieve tight univariate rates, while noting that the multivariate case remains unresolved.
By Huibo Xu, Shi Fu, Qixin Zhang, Dacheng Tao
arXiv:2602. 23116v3 Announce Type: replace Abstract: We consider the problem of regularized best-response max-regret minimization in online RLHF under general preferences and bandit feedback.
By Junghyun Lee, Minju Hong, Kwang-Sung Jun, Chulhee Yun, Se-Young Yun
The paper studies high‑dimensional linear contextual bandits with knapsack constraints (CBwK), aiming to exploit sparsity for tighter regret bounds. It introduces an online hard‑thresholding estimator integrated into a primal‑dual framework, achieving sub‑linear regret that grows only logarithmically with the feature dimension. Under either a diverse‑covariate or margin condition, the regret improves to τ‑dependent rates, and when both hold simultaneously, a dual resolving scheme yields an even tighter bound. The approach also recovers optimal rates for high‑dimensional contextual bandits without knapsacks, and experiments demonstrate its practical effectiveness.
By Wanteng Ma, Dong Xia, Jiashuo Jiang
arXiv:2608. 06825v1 Announce Type: new Abstract: Learning from correct demonstrations is harder than supervised learning when many answers are correct: after predicting, the learner sees one valid answer but not whether its own answer was valid, nor any reward.
By Pahan Dewasurendra
arXiv:2505. 21460v2 Announce Type: replace Abstract: We study online calibration of multi-dimensional forecasts over an arbitrary convex set $P \subset \mathbb{R}^d$ relative to an arbitrary norm $|\cdot|$.
By Maxwell Fishelson, Noah Golowich, Mehryar Mohri, Jon Schneider
arXiv:2607. 26577v1 Announce Type: new Abstract: Adaptive conformal inference (ACI) of Gibbs and Cand{\`e}s and its variants are the standard approach to online conformal prediction under distribution shift, but they suffer from three fundamental limitations.
By Rahul Vaze
arXiv:2512. 23075v5 Announce Type: replace-cross Abstract: Policy gradient methods for Large Language Models optimize a policy $\pi_\theta$ via a surrogate objective computed from samples of a rollout policy $\pi_{\text{roll}}$.
By Yingru Li, Jiacai Liu, Jiawei Xu, Yuxuan Tong, Ziniu Li, Qian Liu, Baoxiang Wang
arXiv:2609. 13954v1 Announce Type: new Abstract: Ensemble sampling offers a practical approach to randomized exploration by maintaining a collection of models, but how small an ensemble can be while retaining strong regret guarantees remains unresolved.
By Taehyun Hwang, Min-hwan Oh
arXiv:2604. 19592v2 Announce Type: replace Abstract: We give a Gordon-Greenwald-Marks (GGM) style black-box reduction from online learning to online multicalibration.
By Gabriele Farina, Juan Carlos Perdomo
arXiv:2606. 10706v1 Announce Type: cross Abstract: Resource constraints increasingly determine what can be trained, fine-tuned, and deployed in large language models (LLMs), yet efficiency is often studied through isolated techniques rather than as an interacting system of limits.
By Vanessa Schmidt, Huy Hoang Nguyen, C\'edric Jung, Shirin Salehi, Anke Schmeink
arXiv:2608. 04324v1 Announce Type: cross Abstract: This paper studies generalized low-rank matrix bandits with multiple prioritized objectives.
By Bo Xue, Ji Cheng, Haodong Jing, Hongzong Li, Shuang Qiu
The paper introduces Private Best-of-N (PrivBoN), a method that adds calibrated Gumbel noise to reward scores during inference-time alignment, achieving both ε-differential privacy and KL-regularized alignment. When the privacy budget exceeds a critical threshold ε*, the noise becomes regret-optimal, matching the theoretical alignment skyline. The authors also propose Private Inference-Time Pessimism (PrivITP), which uses χ^2-regularized rejection sampling and a two-phase Gaussian mechanism to provide ex-post (ε,δ)-DP with a privacy cost independent of the number of responses, and demonstrate that both methods outperform standard Best-of-N across multiple models and datasets.
By Ishi Jain, Nandini Bhattad, Sayak Ray Chowdhury