随机梯度在匹配问题中取得成功
内容提要
该文综述了随机梯度下降与赌博机算法的结合，提出基于在线SGD的广义线性赌博机算法，利用汤普森抽样平衡探索与利用，复杂度与T、d线性相关，遗憾为O(T)。同时涉及SGD收敛性分析、组合多臂赌博、连续臂全局优化及贝叶斯优化，多数方法在实验中优于现有算法。
延伸解读
在线SGD与汤普森抽样的结合
文章提出一种基于在线随机梯度下降的广义线性赌博机算法，使用单步SGD更新利用历史信息，并借助汤普森抽样实现探索。这种结合在探索与利用之间取得平衡，在合成和实际数据集上优于现有算法。其总时间复杂度与轮次数T和特征数d呈线性关系，遗憾为O(T)，为大规模在线学习场景提供了可扩展的方案。
SGD收敛性分析的进展
文章综述了SGD收敛性分析的多项工作：包括学习率逆时间衰减策略下的自包含证明、随机梯度范数更小的新假设、异步并行环境下降低学习率的收敛证明，以及基于期望平滑性、不依赖梯度方差统一界限的通用定理。这些分析拓展了可达到收敛性的学习率范围，并覆盖了多种SGD变体。
连续臂与组合赌博的算法创新
针对连续臂赌博，文章描述了将问题转化为tree-armed bandits的噪声全局优化算法，无需先验信息即可实现平方根遗憾和优化的反平方根误差，并能自适应组合多个树。对于组合多臂赌博，提出的SGB算法仅对未选择的臂进行优化比例抽样，在单调随机次模奖励下达到(1-1/e)的遗憾边界，复杂度在基数约束k方面优于现有方法。
贝叶斯优化与梯度信息的融合
文章还涉及一种贝叶斯方法，将基于贪心的优化和基于梯度的优化相结合，并使用贝叶斯可信区间权衡探索与利用。实验表明，该方法在广泛问题环境中改善了性能，为元优化和梯度相关信息可获得的应用程序提供了改进。这提示在实际问题中，融合梯度信息与贝叶斯框架可能带来性能提升。
Q&A
基于在线SGD的广义线性赌博机算法是如何平衡探索与利用的？
该算法使用单步SGD更新来利用过去的信息，并使用汤普森抽样实现探索，从而在探索与利用之间取得平衡。
该广义线性赌博机算法的时间复杂度和遗憾界是多少？
总时间复杂度为T和d的线性比例，其中T是总轮次数，d是特征数量；遗憾为O(T)。
SGD在学习率遵循逆时间衰减策略时的收敛速度如何？
文章提供了自包含证明，表明SGD在学习率遵循逆时间衰减策略时具有收敛速度，并将结果应用到带有L2正则化的改进型策略梯度多臂赌博问题的收敛中。
组合多臂赌博问题中SGB算法有什么特点？
SGB是一种新颖的组合性随机贪婪赌博算法，仅观察到每个时间步选择的n个臂的联合奖励，采用优化的随机探索再确认方法，专门设计用于具有大量基本臂的情景。对于单调随机次模性奖励，实现了(1-1/e)的遗憾边界，复杂度为O(n^(1/3) k^(2/3) T^(2/3) log(T)^(2/3))，在基数约束k方面优于最先进的方法。
连续臂赌博中的噪声全局优化算法是如何实现的？
通过将问题转化为tree-armed bandits并提供新结果，描述了一种适用于无穷多个多项式极大值的任何连续奖励函数的噪声全局优化和连续臂赌博算法，在不需要先前信息的情况下实现了臂赌博的平方根遗憾和优化的反平方根误差，并证明了能够自适应地组合多个树以最小化遗憾，在缩放维度方面提供了接近匹配的较低界。
贝叶斯优化方法如何结合贪心和梯度优化？
该方法将基于贪心的优化和基于梯度的优化相结合，并使用贝叶斯可信区间来权衡探索和利用。实验结果表明，在广泛的问题环境中改善了性能，为元优化和梯度相关信息能够获得的应用程序提供了改进的性能。
