自适应正则化对在线学习最优性至关重要，固定正则化在高维下必有缺陷。
On the necessity of adaptive regularisation:Optimal anytime online learning on $\boldsymbol{\ell_p}$-balls
- 使用随时间变化的自适应正则化，FTRL可实现任意维度下的最优性能。
- 在高维（d > T）和低维（d ≤ T）场景中，固定正则化均无法同时达到最优。
- 证明了高维线性强化学习中所有ℓ_p球均无法获得次线性后悔，适用于理论研究者。
我们研究在ℝ^d空间中ℓ_p-球上（p > 2）的在线凸优化问题。尽管最优后悔界始终为次线性，但其表现会因维度与时间跨度的关系而发生转变：当维度d > 时间范围T时为高维情形，d ≤ T时为低维情形。本文证明，采用随时间变化且自适应于维度状态的正则化项的FTRL算法，在所有维度情形下均可实现任意时间最优。基于此，我们进一步探究：能否通过固定非自适应正则化实现任意时间最优？主要结论表明，对于可分离正则化项，正则化必须具备自适应性；任何固定正则化将在两个维度情形之一中表现次优。此外，我们给出了下界，排除了在足够高维下所有ℓ_p-球（p ≥ 1）的线性带宽问题存在次线性后悔界的可能性。
原文摘要 · Abstract (English)
We study online convex optimization on $\ell_p$-balls in $\mathbb{R}^d$ for $p > 2$. While always sub-linear, the optimal regret exhibits a shift between the high-dimensional setting ($d > T$), when the dimension $d$ is greater than the time horizon $T$ and the low-dimensional setting ($d \leq T$). We show that Follow-the-Regularised-Leader (FTRL) with time-varying regularisation which is adaptive to the dimension regime is anytime optimal for all dimension regimes. Motivated by this, we ask whether it is possible to obtain anytime optimality of FTRL with fixed non-adaptive regularisation. Our main result establishes that for separable regularisers, adaptivity in the regulariser is necessary, and that any fixed regulariser will be sub-optimal in one of the two dimension regimes. Finally, we provide lower bounds which rule out sub-linear regret bounds for the linear bandit problem in sufficiently high-dimension for all $\ell_p$-balls with $p \geq 1$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。