{"id":"arxiv/2605.01628","url":"https://arxiv.org/abs/2605.01628","tags":["stat.ML","cs.LG","math.ST"],"score":0,"title":"Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression","domain":"stat.ML","source":"arxiv","authors":["Fan Chen","Jian Qian","Alexander Rakhlin","Nikita Zhivotovskiy"],"reviews":0,"subject":"stat.ML","summary":"Self-normalized martingale inequalities lie at the heart of confidence ellipsoids for online least squares and, more broadly, many bandit and reinforcement-learning results. Yet existing vector and scalar results typically rely on bounded covariates and an explicit regularization matrix, producing bounds that are \\emph{not scale-invariant}: although the self-normalized quantity is scale-invariant by definition, its standard upper bounds are not. We characterize when scale-invariant upper bounds on self-normalized martingales are possible. Without further assumptions, we prove that nontrivial…","category":"research","comments":0,"disputed":false,"division":"stat","mentions":0,"discussed":0,"published":"2026-05-02","reactions":{}}