用积分二次约束自动分析在线优化算法的动态遗憾，无需梯度有界或可行集有界假设。
Online Convex Optimization and Integral Quadratic Constraints: An automated approach to regret analysis
- 将一阶算法建模为线性系统与梯度算子的反馈连接，引入变分积分二次约束扩展分析框架。
- 通过可解的半定规划给出后悔值上界，依赖于目标函数变化路径长度和条件数。
- 适用于多种强凸光滑问题，尤其适合研究非静态环境下的算法性能。
我们提出一种新方法，用于分析一阶约束在线凸优化算法在强凸和利普希茨光滑目标下的动态遗憾。关键在于，该分析适用于可表示为线性动态系统与一阶预言机反馈连接的一类广泛算法。通过引入变分积分二次约束（variational IQCs），我们将问题转化为一个半定规划，当其可行时，可提供算法的后悔上界。该上界以时间变化的最小值路径长度和目标函数变化量的形式捕捉问题的时间演化特性。与传统在线凸优化结果不同，本方法无需假设梯度有界或可行集有界。数值分析展示了该方法对函数类条件数导致的后悔依赖关系的捕捉能力。
原文摘要 · Abstract (English)
We propose a novel approach for analyzing dynamic regret of first-order constrained online convex optimization algorithms for strongly convex and Lipschitz-smooth objectives. Crucially, we provide a general analysis that is applicable to a wide range of first-order algorithms that can be expressed as an interconnection of a linear dynamical system in feedback with a first-order oracle. By leveraging Integral Quadratic Constraints (IQCs), we derive a semi-definite program which, when feasible, provides a regret guarantee for the online algorithm. For this, the concept of variational IQCs is introduced as the generalization of IQCs to time-varying monotone operators. Our bounds capture the temporal rate of change of the problem in the form of the path length of the time-varying minimizer and the objective function variation. In contrast to standard results in OCO, our results do not require nerither the assumption of gradient boundedness, nor that of a bounded feasible set. Numerical analyses showcase the ability of the approach to capture the dependence of the regret on the function class condition number.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。