揭示在线镜方法中近似误差的隐藏代价,发现正则化器平滑性决定算法鲁棒性。
The Hidden Cost of Approximation in Online Mirror Descent
- 系统分析近似求解在线镜方法的误差影响,揭示正则化器平滑性与误差鲁棒性的深层关系。
- 负熵正则化需指数级小误差才能避免线性后悔,而对数障碍和塔里斯正则化容忍多项式误差。
- 随机损失下负熵在单纯形上恢复鲁棒性,但在子集上仍需极小误差以避免次优结果。
在线镜下降(OMD)是优化、机器学习与序贯决策中众多算法的基础范式。其迭代依赖于求解优化子问题,但这些子问题通常只能近似求解,导致算法为非精确版本。然而现有分析多假设理想无误差情形,限制了我们对实际性能的把握。本文首次系统研究不精确的OMD,揭示正则化器平滑性与近似误差鲁棒性之间的复杂关系:当正则化器一致光滑时,建立了由误差引起的超额后悔的紧界;对于单纯形及其子集上的屏障正则化器,发现显著差异——负熵需指数级小误差以避免线性后悔,而对数障碍和塔里斯正则化器即使在多项式误差下仍保持鲁棒性;最后,在损失为随机且定义域为单纯形的情况下,负熵重获鲁棒性,但该性质不适用于所有子集,此时仍需指数级小误差以避免次优后悔。
原文摘要 · Abstract (English)
Online mirror descent (OMD) is a fundamental algorithmic paradigm that underlies many algorithms in optimization, machine learning and sequential decision-making. The OMD iterates are defined as solutions to optimization subproblems which, oftentimes, can be solved only approximately, leading to an inexact version of the algorithm. Nonetheless, existing OMD analyses typically assume an idealized error free setting, thereby limiting our understanding of performance guarantees that should be expected in practice. In this work we initiate a systematic study into inexact OMD, and uncover an intricate relation between regularizer smoothness and robustness to approximation errors. When the regularizer is uniformly smooth, we establish a tight bound on the excess regret due to errors. Then, for barrier regularizers over the simplex and its subsets, we identify a sharp separation: negative entropy requires exponentially small errors to avoid linear regret, whereas log-barrier and Tsallis regularizers remain robust even when the errors are only polynomial. Finally, we show that when the losses are stochastic and the domain is the simplex, negative entropy regains robustness-but this property does not extend to all subsets, where exponentially small errors are again necessary to avoid suboptimal regret.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。