论文标题
基于PDE的最佳策略，用于不受限制的在线学习
PDE-Based Optimal Strategy for Unconstrained Online Learning
论文作者
论文摘要
不受限制的在线线性优化（OLO）是研究机器学习模型培训的实用问题。现有作品提出了许多基于潜在的算法，但总的来说，这些潜在功能的设计在很大程度上取决于猜测。为了简化此工作流程，我们提出了一个框架，该框架通过求解部分微分方程（PDE）来生成新的潜在功能。 Specifically, when losses are 1-Lipschitz, our framework produces a novel algorithm with anytime regret bound $C\sqrt{T}+||u||\sqrt{2T}[\sqrt{\log(1+||u||/C)}+2]$, where $C$ is a user-specified constant and $u$ is any comparator unknown and unbounded a先验。这样的界限实现了最佳的损失重格折衷，而没有不切实际的thick俩。此外，匹配的下限显示，包括常量乘数$ \ sqrt {2} $在内的领先订单项很紧。据我们所知，提出的算法是第一个实现此类最佳性的算法。
Unconstrained Online Linear Optimization (OLO) is a practical problem setting to study the training of machine learning models. Existing works proposed a number of potential-based algorithms, but in general the design of these potential functions relies heavily on guessing. To streamline this workflow, we present a framework that generates new potential functions by solving a Partial Differential Equation (PDE). Specifically, when losses are 1-Lipschitz, our framework produces a novel algorithm with anytime regret bound $C\sqrt{T}+||u||\sqrt{2T}[\sqrt{\log(1+||u||/C)}+2]$, where $C$ is a user-specified constant and $u$ is any comparator unknown and unbounded a priori. Such a bound attains an optimal loss-regret trade-off without the impractical doubling trick. Moreover, a matching lower bound shows that the leading order term, including the constant multiplier $\sqrt{2}$, is tight. To our knowledge, the proposed algorithm is the first to achieve such optimalities.
