arXiv:2605.01628stat.MLcs.LG2026-05

揭示线性回归中尺度不变置信区间的存在条件,解决了一个长期开放问题。

Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression

  • 通过分析自归一化鞅的尺度不变性,发现仅在一维情况下可实现非平凡界
  • 在一维时给出 $O(\log T)$ 的双重均匀后悔上界,高维下不可能实现子线性后悔
  • 在平滑条件下获得无需正则化的自然尺度不变界,适用于非独立自适应过程

自归一化鞅不等式是在线最小二乘法置信椭球的核心,也支撑着许多强化学习与多臂赌博机的结果。然而现有向量和标量结果通常依赖有界协变量和显式正则化矩阵,导致上界不具尺度不变性——尽管自归一化量本身是尺度不变的。本文刻画了尺度不变上界存在的条件:在无额外假设下,非平凡尺度不变界仅在一维 $d=1$ 时成立;此时我们得到 $O(\log T)$ 的尺度不变上界,且对协变量无任何假设。而在 $d>1$ 时,一般情形下不存在非平凡尺度不变界。该二分现象被用于解决一个开放问题(Gaillard 等,ALT 2019):在线线性回归中,是否可在 $\mathbb{R}^d$ 上实现关于协变量尺度和比较器范数均无关的统一后悔上界?答案是一维可行,$d>1$ 时子线性双重均匀后悔不可能实现。进一步,在自然平滑条件下(协变量条件分布相对于固定基测度的 Radon--Nikodym 导数有界),我们无需有界协变量即可恢复子线性后悔,并导出无需常规正则化惩罚的自归一化浓度不等式,从而首次获得适用于自适应、非独立向量鞅的自然尺度不变界。

原文摘要 · Abstract (English)

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 scale-invariant bounds exist only in dimension $d=1$; moreover, in $d=1$ we obtain $O(\log T)$ scale-invariant self-normalized bounds without any assumptions on the covariates. In contrast, for $d>1$ we show that no nontrivial scale-invariant bound can hold in full generality. We then connect this dichotomy to \emph{doubly-uniform} regret in online linear regression (i.e., regret bounds that are simultaneously independent of the covariate scale and the comparator norm) and use it to resolve the open question of Gaillard, Gerchinovitz, Huard, and Stoltz, \emph{``Uniform regret bounds over $\mathbb{R}^d$ for the sequential linear regression problem with the square loss''} (ALT 2019): in $d=1$ we give an explicit algorithm with $O(\log T)$ doubly-uniform regret, whereas for $d>1$ sublinear doubly-uniform regret is impossible. Finally, under a natural \emph{smoothness} condition (bounded Radon--Nikodym derivatives of the conditional covariate laws with respect to a fixed base measure), we recover sublinear regret for $d>1$ without bounded covariates and derive a self-normalized concentration inequality free of the usual regularization penalties, yielding arguably a first natural scale-invariant bound for adaptive, non-i.i.d. vector martingales.

在线学习线性回归鞅理论后悔界

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。