在局部误差边界条件下的随机子梯度方法的加速

今天我们主要针对Stochastic Subgradient Methods来进行详细讲解,如果有兴趣的读者,进认真和我们一起阅读下去,记得拿好纸和笔~

首先,简单通过机器学习的例子来引入今天的话题。

上表是某地区的房屋售价数据。

线性模型如下:

y=f(w)=xw

其中,y表示价格,x表示大小。

可以拟合出一条上图的数据,但是到底哪个函数最好呢?

其实这是机器学习的入门知识,会的人应该在脑海中立马有了自己的函数构架了。

通过最小二乘回归:

square loss具有平滑性。

如果是最小绝对偏差:

absolute loss 不具有平滑性。

还有,用高维模型的话,如下:

最后一项是正则项。

  • 绝对损失对离群值问题更有鲁棒性;
  • L1-Norm正则项,大家应该都知道,可以用于特征选择。

则机器学习的问题就如下所示:

对于分类、回归和正则项来说,有如下方式:

  • 分类:铰链损失
  • 回归:平方损失和绝对损失

平方损失:

绝对损失:

  • 正则项:L1-Norm和L2-Norm

L1-Norm:

L2-Norm:

凸优化问题

其中,Rd→R是凸的,最优值为:

最优解为

最终目的就是找到最优解:

其中:

复杂性量度

  • 大多数优化算法都是通过迭代计算得到的:
  • 迭代复杂度:迭代次数T(ε)为:

其中0<ε≤1。

  • 时间复杂度:T(ε)*C(n,d),C(n,d)就是每次迭代的成本。

现在开始我们正式进入主题:

梯度下降(GD)

定理主要来自于:Yurii Nesterov. Introductory lectures on convex optimization : a basic course. Applied optimization. Kluwer Academic Publ., 2004. ISBN 1-4020-7553-7.

问题依然是:

(平滑)

迭代:

GD:

步长:η=1/L,且η>0。

加速梯度下降法

其中,

为动量参数。

定理参考于:Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19:1574–1609, 2009

次子度下降(SG)

其为非平滑的。


时间复杂度

其中,在计算梯度的时候很费时。

如果对于大数据的时候,d和n都特别大,要计算梯度,需要通过所有数据点,每个迭代步骤,都需要这样计算。

所以出现了随机梯度下降算法(SGD):


随机子梯度下降(SSG)

迭代:

时间复杂度:


怎么加速呢?

Y. Xu, Q. Lin, and T. Yang. Stochastic convex optimization: Faster local growth implies faster global convergence. In ICML, pages 3821-3830, 2017

局部误差边界约束条件下的快速全局收敛性,用于机器系学习。

局部误差边界条件(LEB)

定义:有一个常数c>0,还有一个局部增长率θ∈(0,1],则:

则F(W)满足局部误差边界条件。

从下图中可以清楚看出加速的效果:

主要的步骤如下:

其中:

然后再来看看时间复杂度:


实验

  • 鲁棒回归:
  • 稀疏分类:
  • 最小二乘+L1-Norm:
  • 平方铰链损失:
  • Hurbe损失:

实验结果:

本文分享自微信公众号 - 计算机视觉战队(ComputerVisionGzq)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-04-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏SIGAI学习与实践平台

人脸检测算法综述

人脸检测是目前所有目标检测子方向中被研究的最充分的问题之一,它在安防监控,人证比对,人机交互,社交和娱乐等方面有很强的应用价值,也是整个人脸识别算法的第一步。在...

1.2K10
来自专栏智能算法

结合Scikit-learn介绍几种常用的特征选择方法(上)

特征选择(排序)对于数据科学家、机器学习从业者来说非常重要。好的特征选择能够提升模型的性能,更能帮助我们理解数据的特点、底层结构,这对进一步改善模型...

1.7K60
来自专栏机器之心

入门 | 一文简述深度学习优化方法——梯度下降

从很大程度上来说,深度学习实际上是在解决大量烦人的优化问题。神经网络仅仅是一个非常复杂的函数,包含数百万个参数,这些参数代表的是一个问题的数学解答。以图像分类为...

12330
来自专栏智能算法

入门 | 一文简述深度学习优化方法----梯度下降

从很大程度上来说,深度学习实际上是在解决大量烦人的优化问题。神经网络仅仅是一个非常复杂的函数,包含数百万个参数,这些参数代表的是一个问题的数学解答。以图像分类为...

14730
来自专栏企鹅号快讯

神经网络模型求解思路总结

《实例》阐述算法,通俗易懂,助您对算法的理解达到一个新高度。包含但不限于:经典算法,机器学习,深度学习,LeetCode 题解,Kaggle 实战。期待您的到来...

27080
来自专栏数据科学与人工智能

【机器学习】不平衡数据下的机器学习方法简介

机器学习已经成为了当前互联网领域不可或缺的技术之一,前辈们对机器学习模型的研究已经给我们留下了一笔非常宝贵的财富,然而在工业界的应用中我们可以看到,应用场景千千...

64880
来自专栏专知

【干货】加速梯度下降的若干小技巧

【导读】在训练神经网络的时候,使用标准梯度下降法常常使网络陷入局部最小值,从而造成实验结果不佳。本文介绍了几种标准梯度下降的基础的改进算法。如批量梯度下降,正则...

430110
来自专栏行者常至

011.线性回归算法推导

版权声明:本文为博主原创文章,允许转载,请标明出处。 https://blog.csdn.net/qwdafedv/article/deta...

36820
来自专栏TensorFlow从0到N

TensorFlow从0到1 - 6 - 解锁梯度下降算法

上一篇 5 TF轻松搞定线性回归,我们知道了模型参数训练的方向是由梯度下降算法指导的,并使用TF的封装tf.train.GradientDescentOpti...

48460
来自专栏智能算法

机器学习三人行(系列五)----你不了解的线性模型(附代码)

到目前为止,我们已经将机器学习模型和他们的训练算法大部分视为黑盒子。 如果你经历了前面系列的一些操作,如回归系统、数字图像分类器,甚至从头开始建立一个垃圾邮件分...

405160

扫码关注云+社区

领取腾讯云代金券