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.
翻译:我们考虑以时间变化的阶段成本和额外的转换成本来优化在线连接。由于转换成本在所有阶段都引入了组合,因此将多步头(长期)的预测纳入其中,以改善在线绩效。然而,长期预测往往质量较低。因此,一个关键问题是:如何减少长期预测错误对在线绩效的影响?为了解决这一问题,我们引入了基于梯度的在线算法,即放弃地平轨道不精确错误(RHIG),并通过对环境时间变化和预测错误的动态遗憾来分析其绩效。RHIG只考虑大部分W美元(长期)的跨步头预测避免长期预测误导。我们遗憾界限建议的美元的最佳选择取决于环境变异与预测准确性之间的权衡。此外,我们将RHIG应用于一个成熟的随机预测错误模型,并在相关预测错误下提供预期的遗憾和浓度约束。最后,我们用数字测试RHIG对磁场跟踪问题的业绩。