改进在线凸优化的后悔值分析，提升安全性与效率。
Data-Dependent Regret and Polyak Corrections for Constrained Online Convex Optimization
- 用观测梯度累积替代最坏情况假设，更贴近实际数据。
- 引入Polyak修正项，使后悔值降低38%至43%。
- 适合需要每轮保证安全约束的实时决策场景。
约束型在线凸优化需在每一轮中最小化对抗性凸代价的后悔值，同时满足凸约束，适用于安全关键应用。一种计算高效的算法结合在线梯度下降与Polyak可行性步骤，每轮仅需一次约束评估和一次次梯度。尽管该方法实现O(√T)的后悔值并保证每轮可行性，本文通过保留标准最坏情况分析中忽略的两个量，获得更紧致的数据依赖性分析。首先，将梯度上界G_f²T替换为实际观测到的梯度累积G_T = ∑_t ||grad f_t(x_t)||²；其次，识别出非负的Polyak修正项P_T，衡量可行性投影带来的累积平方位移，并以负号进入后悔界。由此产生的改进量Δ_T = (η/2)(G_f²T - G_T) + P_T/(2η)恒为非负。进一步提出AdaOGD-PFS自适应步长方法，在保持每轮可行性的同时实现O(√G_T)的后悔值。在球形与半空间约束问题上的实验表明，后悔值改善达38%至43%，数据依赖梯度与Polyak修正均贡献显著。
原文摘要 · Abstract (English)
Constrained online convex optimization requires minimizing regret against adversarial convex costs while satisfying a convex constraint at every round, as needed in safety-critical applications. A computationally efficient method combines online gradient descent with a Polyak feasibility step, using one constraint evaluation and one subgradient per round. Although this method achieves O(sqrt(T)) regret with per-round feasibility, we derive a tighter, data-dependent analysis by retaining two quantities omitted by the standard worst-case argument. First, we replace the gradient envelope G_f^2 T with the observed accumulation G_T = sum_t ||grad f_t(x_t)||^2. Second, we identify a nonnegative Polyak correction P_T that measures the cumulative squared displacement caused by feasibility projections and enters the regret bound with a negative sign. The resulting improvement, Delta_T = (eta/2)(G_f^2 T - G_T) + P_T/(2 eta), is always nonnegative. We further propose AdaOGD-PFS, an adaptive-step-size method that achieves O(sqrt(G_T)) regret while preserving per-round feasibility. Experiments on ball- and halfspace-constrained problems improve the regret bound by 38 to 43 percent, with both data-dependent gradients and Polyak corrections contributing substantially.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。