Learning piecewise Lipschitz functions in changing environments
Learning piecewise Lipschitz functions in changing environments
复制标题
DOI：
--
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Dravyansh Sharma;Maria-Florina Balcan;Travis Dick
中科院分区：
文献类型：
--
作者：
Dravyansh Sharma;Maria-Florina Balcan;Travis Dick
存在尖锐（非Lipschitz）、不可预测（w.r.t.\时间和数量）的变化是一个具有挑战性的和基本上未经探索的具有重要意义的问题。我们考虑一类的分段Lipschitz函数，这是最普遍的在线设置在文献中考虑的问题，自然出现在各种组合算法的选择问题，效用函数可以有尖锐的不连续性。通常的“静态”后悔的性能指标最小化之间的差距差距积累的回报和最佳固定点的整个持续时间，因此无法捕捉不断变化的环境。转移遗憾是一个有用的替代方案，它允许最多$s$环境{\it shifts}。在这项工作中，我们提供了一个$O（\sqrt{sdT\log T}+sT^{1-\beta}）$遗憾界的$\beta$分散的功能，其中$\beta$大致量化的不连续性出现在预期中的效用函数（通常是$\beta\ge1/2$在实际问题的兴趣）。我们还提出了一个下界紧到亚对数因子。我们进一步获得改进的界限时，从一个小的专家池中选择。我们经验证明我们的算法在线聚类问题的流行基准的关键应用。
Optimization in the presence of sharp (non-Lipschitz), unpredictable (w.r.t.\ time and amount) changes is a challenging and largely unexplored problem of great significance. We consider the class of piecewise Lipschitz functions, which is the most general online setting considered in the literature for the problem, and arises naturally in various combinatorial algorithm selection problems where utility functions can have sharp discontinuities. The usual performance metric of `static' regret minimizes the gap between the payoff accumulated and that of the best fixed point for the entire duration, and thus fails to capture changing environments. Shifting regret is a useful alternative, which allows for up to $s$ environment {\it shifts}. In this work we provide an $O(\sqrt{sdT\log T}+sT^{1-\beta})$ regret bound for $\beta$-dispersed functions, where $\beta$ roughly quantifies the rate at which discontinuities appear in the utility functions in expectation (typically $\beta\ge1/2$ in problems of practical interest). We also present a lower bound tight up to sub-logarithmic factors. We further obtain improved bounds when selecting from a small pool of experts. We empirically demonstrate a key application of our algorithms to online clustering problems on popular benchmarks.