arXiv:2602.19172cs.LG2026-02被引 1

提出新方法分析ReLU网络在线回归的有限累积损失,揭示其与分类的本质差异。

Online Realizable Regression and Applications for ReLU Networks

  • 用覆盖数构造熵势函数,统一上界在线回归的实可学习性
  • 证明ReLU网络在特定条件下累积损失为有限值,且与有效维度相关
  • 适用于研究在线学习中回归与分类的性能边界差异

实可学习的在线回归与在线分类行为截然不同。即使无边际或随机假设,仅凭实可学习性即可在满足近似三角不等式的损失下实现无时间依赖(有限)累积损失,而对应分类问题可能有无限误判。本文在对抗模型下研究满足近似三角不等式的损失(近似伪度量)下的实可学习在线回归。近期工作表明,最小最大实可学习累积损失由缩放后的Littlestone/在线维数 $\mathbb{D}_{\mathrm{onl}}$ 决定,但该量难分析。本文提出通用势函数方法,将 $\mathbb{D}_{\mathrm{onl}}$ 上界表示为仅依赖于假设类在诱导上确界伪度量下覆盖数的杜德利型熵积分:定义熵势函数 $Φ(\mathcal{H})=\int_{0}^{diam(\mathcal{H})} \log N(\mathcal{H},\varepsilon)\,d\varepsilon$,其中 $N(\mathcal{H},\varepsilon)$ 为 $\varepsilon$-覆盖数。对任意 $c$-近似伪度量损失,有 $\mathbb{D}_{\mathrm{onl}}(\mathcal{H})\le O(c)\,Φ(\mathcal{H})$。特别地,多项式熵意味着 $Φ(\mathcal{H})<\infty$,从而获得透明依赖于有效维度的无时间依赖累计损失。我们在两类函数族上验证方法:证明了 $q$ 与 $d$ 的尖锐二分法——对 $L$-利普希茨回归,当且仅当 $q>d$ 时总损失为有限且可高效实现 $Θ_{d,q}(L^d)$;对有界范数 $k$-ReLU 网络,回归可实现有限损失(甚至 $\widetilde O(k^2)$,单个 ReLU 时为 $O(1)$),而分类在 $k=2,d=1$ 时即已不可能。

原文摘要 · Abstract (English)

Realizable online regression can behave very differently from online classification. Even without any margin or stochastic assumptions, realizability may enforce horizon-free (finite) cumulative loss under metric-like losses, even when the analogous classification problem has an infinite mistake bound. We study realizable online regression in the adversarial model under losses that satisfy an approximate triangle inequality (approximate pseudo-metrics). Recent work of Attias et al. shows that the minimax realizable cumulative loss is characterized by the scaled Littlestone/online dimension $\mathbb{D}_{\mathrm{onl}}$, but this quantity can be difficult to analyze. Our main technical contribution is a generic potential method that upper bounds $\mathbb{D}_{\mathrm{onl}}$ by a concrete Dudley-type entropy integral that depends only on covering numbers of the hypothesis class under the induced sup pseudo-metric. We define an \emph{entropy potential} $Φ(\mathcal{H})=\int_{0}^{diam(\mathcal{H})} \log N(\mathcal{H},\varepsilon)\,d\varepsilon$, where $N(\mathcal{H},\varepsilon)$ is the $\varepsilon$-covering number of $\mathcal{H}$, and show that for every $c$-approximate pseudo-metric loss, $\mathbb{D}_{\mathrm{onl}}(\mathcal{H})\le O(c)\,Φ(\mathcal{H})$. In particular, polynomial metric entropy implies $Φ(\mathcal{H})<\infty$ and hence a horizon-free realizable cumulative-loss bound with transparent dependence on effective dimension. We illustrate the method on two families. We prove a sharp $q$-vs.-$d$ dichotomy for realizable online learning (finite and efficiently achievable $Θ_{d,q}(L^d)$ total loss for $L$-Lipschitz regression iff $q>d$, otherwise infinite), and for bounded-norm $k$-ReLU networks separate regression (finite loss, even $\widetilde O(k^2)$, and $O(1)$ for one ReLU) from classification (impossible already for $k=2,d=1$).

在线学习回归分析ReLU网络熵界

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