On the Generalization Ability of Online Gradient Descent Algorithm Under the Quadratic Growth Condition.
On the Generalization Ability of Online Gradient Descent Algorithm Under the Quadratic Growth Condition.
复制标题
二次增长条件下在线梯度下降算法的泛化能力。
DOI：
10.1109/tnnls.2017.2764960
复制
发表时间：
2018
影响因子：
10.4
通讯作者：
Zhang,Changshui
中科院分区：
文献类型：
--
作者：
Chang,Daqing;Lin,Ming;Zhang,Changshui
在线学习已成功应用于各种机器学习问题。在线学习的传统分析通过强凸假设实现了尖锐的泛化界限。在本文中，我们研究了经典在线梯度下降算法在二次增长条件（QGC）下的泛化能力，这是一个比强凸性严格弱的条件。在一些温和的假设下，我们证明当数据独立同分布（i.i.d.）时，超额风险收敛不比 O(log T/T) 差。当数据是从 φ 混合过程生成时，我们实现了超额风险界限 O(log T/T + φ(τ))，其中 φ(τ) 是捕获非独立同分布的混合系数。属性。我们的关键技术基于 QGC 和鞅浓度的组合。我们的结果表明，在线学习中实现急剧的 O(log T/T) 收敛速度并不需要强凸性。我们在合成数据和真实数据上验证了我们的理论。
Online learning has been successfully applied in various machine learning problems. Conventional analysis of online learning achieves a sharp generalization bound with a strongly convex assumption. In this paper, we study the generalization ability of the classic online gradient descent algorithm under the quadratic growth condition (QGC), a strictly weaker condition than strong convexity. Under some mild assumptions, we prove that the excess risk converges no worse than O(log T/T) when the data are independently and identically distributed (i.i.d.). When the data are generated from a φ-mixing process, we achieve the excess risk bound O(log T/T + φ(τ)), where φ(τ) is the mixing coefficient capturing the non-i.i.d. attribute. Our key technique is based on the combination of the QGC and the martingale concentrations. Our results indicate that the strong convexity is not necessary to achieve the sharp O(log T/T) convergence rate in online learning. We verify our theories on both synthetic and real-world data.