Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins
Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins
复制标题
DOI：
--
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Spencer Frei;Yuan Cao;Quanquan Gu
中科院分区：
文献类型：
--
作者：
Spencer Frei;Yuan Cao;Quanquan Gu
我们分析了凸代理上梯度下降的特性，以实现线性半空间的不可知学习的零一损失。如果 $\mathsf{OPT}$ 是半空间实现的最佳分类误差，通过诉诸软边际的概念，我们能够证明梯度下降找到具有分类误差 $\tilde O(\mathsf{OPT}^{1/2}) + \varepsilon$ 的半空间，在 $\mathrm{poly}(d,1/\varepsilon)$ 中，对于包括对数凹的广泛分布类别，时间和样本复杂度各向同性分布作为一个子类。在此过程中，我们回答了 Ji 等人最近提出的一个问题。 （2020）关于损失函数的尾部行为如何影响梯度下降的样本复杂性和运行时保证。
We analyze the properties of gradient descent on convex surrogates for the zero-one loss for the agnostic learning of linear halfspaces. If $\mathsf{OPT}$ is the best classification error achieved by a halfspace, by appealing to the notion of soft margins we are able to show that gradient descent finds halfspaces with classification error $\tilde O(\mathsf{OPT}^{1/2}) + \varepsilon$ in $\mathrm{poly}(d,1/\varepsilon)$ time and sample complexity for a broad class of distributions that includes log-concave isotropic distributions as a subclass. Along the way we answer a question recently posed by Ji et al. (2020) on how the tail behavior of a loss function can affect sample complexity and runtime guarantees for gradient descent.