论文标题
Sublinear遗憾的是Barzilai-Borwein台阶尺寸
Sublinear Regret with Barzilai-Borwein Step Sizes
论文作者
论文摘要
本文使用Barzilai-Borwein Quasi-Newton方法考虑了在线方案。在在线优化问题中，在线代理使用某种算法在每个时间步骤中决定一个目标，之后遇到可能的损失。即使在线玩家理想地尝试在每个时间步骤中做出最佳决策，但与玩家的决策相关的遗憾也有一个遗憾。这项研究由于其快速收敛性，使用了诸如准牛顿方法之类的优化方法来研究在线玩家的遗憾。本文中选择了Barzilai-Borwein（BB）梯度方法，而不是其他准Newton方法，例如Broyden-Fletcher-Goldfarb-Shanno（BFGS）算法，因为其计算复杂性较小。此外，BB梯度方法适用于大规模优化问题，包括本文介绍的在线优化方案。为了证实BARZILAI-BORWEIN（BB）梯度算法的有效性，根据两个BB步长的大小，在本研究中使用了贪婪的在线梯度算法。通过对BB步骤大小的严格遗憾分析，可以确定从BB算法获得的遗憾是及时的。此外，本文表明，使用在线BB算法的平均后悔将其接近零，而不假设要最小化的成本函数强烈凸出。
This paper considers the online scenario using the Barzilai-Borwein Quasi-Newton Method. In an online optimization problem, an online agent uses a certain algorithm to decide on an objective at each time step after which a possible loss is encountered. Even though the online player will ideally try to make the best decisions possible at each time step, there is a notion of regret associated with the player's decisions. This study examines the regret of an online player using optimization methods like the Quasi-Newton methods, due to their fast convergent properties. The Barzilai-Borwein (BB) gradient method is chosen in this paper over other Quasi-Newton methods such as the Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm because of its less computational complexities. In addition, the BB gradient method is suitable for large-scale optimization problems including the online optimization scenario presented in this paper. To corroborate the effectiveness of the Barzilai-Borwein (BB) gradient algorithm, a greedy online gradient algorithm is used in this study based on the two BB step sizes. Through a rigorous regret analysis on the BB step sizes, it is established that the regret obtained from the BB algorithm is sublinear in time. Moreover, this paper shows that the average regret using the online BB algorithm approaches zero without assuming strong convexity on the cost function to be minimized.
