论文标题
通过基于梯度的算法利用平滑在线凸优化的预测
Leveraging Predictions in Smoothed Online Convex Optimization via Gradient-based Algorithms
论文作者
论文摘要
我们考虑在线凸出优化，随着时变的阶段成本和额外的切换成本。由于切换成本在各个阶段都引入了耦合，因此进行了多步（长期）预测以改善在线性能。但是，长期的预测往往会质量较低。因此，一个关键的问题是：如何减少长期预测错误对在线绩效的影响？为了解决这个问题，我们介绍了一种基于梯度的在线算法，将视野不精确梯度（RHIG）递减，并根据环境的时间变化和预测错误来分析其性能。 RHIG最多只考虑$ W $步骤，预测，以免长期被糟糕的预测误导。我们的遗憾界限建议的$ W $的最佳选择取决于环境变化与预测准确性之间的权衡。此外，我们将RHIG应用于一个公认的随机预测误差模型，并在相关的预测误差下提供了预期的遗憾和浓度界限。最后，我们通过数值测试RHIG在四型跟踪问题上的性能。
We consider online convex optimization with time-varying stage costs and additional switching costs. Since the switching costs introduce coupling across all stages, multi-step-ahead (long-term) predictions are incorporated to improve the online performance. However, longer-term predictions tend to suffer from lower quality. Thus, a critical question is: how to reduce the impact of long-term prediction errors on the online performance? To address this question, we introduce a gradient-based online algorithm, Receding Horizon Inexact Gradient (RHIG), and analyze its performance by dynamic regrets in terms of the temporal variation of the environment and the prediction errors. RHIG only considers at most $W$-step-ahead predictions to avoid being misled by worse predictions in the longer term. The optimal choice of $W$ suggested by our regret bounds depends on the tradeoff between the variation of the environment and the prediction accuracy. Additionally, we apply RHIG to a well-established stochastic prediction error model and provide expected regret and concentration bounds under correlated prediction errors. Lastly, we numerically test the performance of RHIG on quadrotor tracking problems.
