[机器学习] 3. 镜像下降 Mirror Descent 与线性耦合 Linear Coupling

这篇具有很好参考价值的文章主要介绍了[机器学习] 3. 镜像下降 Mirror Descent 与线性耦合 Linear Coupling。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

ML Theory 太魔怔了!!!!!

我们来考虑更快的下降算法。

\(L\)-smooth 的 Gradient Descent,我们有两种视角来看它。一种是局部视角,梯度方向相近的点的函数值一定会下降,另一种是全局视角,用一个二次函数为整个 \(f\) 提供了一个 lowerbound。当局部梯度的范数很大时,函数值会下降的很快;当全局梯度的范数很小时,每一个 lowerbound 会更紧。所以我们考虑从两种视角出发分别设计一种策略,之后将两者耦合,以达到更快的速率。

为了半形式化地描述两种视角,我们将 Gradient Descent 一般化,称其为 Mirror descent。名字 Mirror 来源于原空间到对偶空间的映射。如果 \(f\) 定义在一个原空间上,那么 \(\nabla f\) 的值域在其对偶空间上,即在每个位置提供了一个线性函数。此时,梯度下降 \(\bm x_{t+1} = \bm x_t + \eta \nabla f(\bm x_t)\) 便是将一个原空间的元素和一个对偶空间的元素进行了线性组合。在 \(L_2\) 范数下,由于其自对偶,这能够说得通,但是在一般的范数中这会变得奇怪。此时应该按照对偶空间的理念,将 \(\nabla f(\bm x_t)\) 认作一个线性函数,因此

\[f(\bm x_t) + (\nabla f(\bm x_t))(\bm x - \bm x_t) \]

便是对 \(f(\bm x)\) 的线性近似。

第一种视角称为正则化视角。我们希望 \(f(\bm x)\) 小,但是又希望 \(\bm x, \bm x_t\) 不要差太远,否则近似的效果会差,因此考虑加入正则化项 \(\frac 1{2\eta} \|\bm x - \bm x_t\|^2\),则

\[\bm x_{t+1} = \operatorname{argmin}_{\bm x} \left\{f(\bm x_t) + (\nabla f(\bm x_t))(\bm x - \bm x_t) + \frac 1{2\eta} \|\bm x - \bm x_t\|^2\right\} \]

它的解便是 \(\bm x_t - \eta \nabla f(\bm x_t)\)。这个正则化的观点,避免了原空间和对偶空间的直接接触。现在考虑对这个正则化项一般化。

定义 对一个凸函数 \(w\),其 Bregman divergence\(V_{\bm x}(\bm y) = w(\bm y) - \langle \nabla w(\bm x), \bm y - \bm x \rangle - w(\bm x)\)\(w\) 被称作距离生成函数。

\(w\) 的凸性是为了保证转化后的问题仍然是凸优化问题。

命题 (triangle equality) \(\forall \bm x, \bm y, \langle -\nabla V_{\bm x}(\bm y), \bm y - \bm u \rangle = V_{\bm x}(\bm u) - V_{\bm y}(\bm u) - V_{\bm x}(\bm y)\).

注意 \(\nabla V_{\bm x}(\bm y)\) 是认 \(\bm x\) 为参数,对 \(\bm y\) 求的梯度。

证明

\[\begin{aligned} \langle -\nabla V_{\bm x}(\bm y), \bm y - \bm u \rangle &= \langle \nabla w(\bm x) - \nabla w(\bm y), \bm y - \bm u\rangle \\ &= (w(\bm u) - w(\bm x) - \langle \nabla w(\bm x), \bm u - \bm x \rangle) - (w(\bm u) - w(\bm y) - \langle \nabla w(\bm y), \bm u - \bm y \rangle) \\ &\hphantom{{}={}} -(w(\bm y) - w(\bm x) - \langle \nabla w(\bm x), \bm y - \bm x \rangle) \\ &= V_{\bm x}(\bm u) - V_{\bm y}(\bm u) - V_{\bm x}(\bm y) \end{aligned}\]

其一个例子为 GD 一讲中

\[\frac 1{\eta} \langle \bm w_{i+1} - \bm w_i, \bm w_i - \bm w^*\rangle - \frac 1{2\eta} \|\bm w_i - \bm w_{i+1}\|^2_2 = \frac 1{2\eta} (\|\bm w_i - \bm w^*\|^2_2 - \|\bm w_{i+1} - \bm w^*\|^2_2) \]

其中 \(\bm x = \bm w_{i+1}, \bm y = \bm w_i, \bm u = \bm w^*, w(\bm x) = \|\bm x\|^2_2, \nabla w(\bm x) = 2\bm x\)

定义一个步长为 \(\alpha\) 的 Mirror step 为

\[\bm x_{k+1} = \mathrm{Mirr}_{\bm x}(\alpha \nabla f(\bm x_k)) \]
\[\mathrm{Mirr}_{\bm x}(\bm \xi) = \operatorname{argmin}_{\bm y} (\langle \bm \xi, \bm y - \bm x \rangle + V_{\bm x}(\bm y)) \]

其中 \(V\) 当作正则化项。如果 \(\bm x = \bm x_k, V_{\bm x}(\bm y) = \|\bm x - \bm y\|^2\) 那就是常见的 GD。

第二种视角称为镜像空间 (Mirror space) 视角,一个 Mirror step 可被视作对偶空间上的梯度下降,即声明一个新的梯度,去找其对应的极值点。过程形如

  • \(\bm x\) 通过 Mirror map 映射到对偶空间上的 \(\bm \theta_k\)
  • \(\bm \theta_{k+1} = \bm \theta_k - \alpha \nabla f(\bm x_k)\)
  • \(\bm \theta_{k+1}\) 映射回原空间上的 \(\overline{\bm x}_{k+1}\)
  • \(\overline{\bm x}_{k+1}\) 投影到约束集中,投影使用 Bregman divergence 作为其距离,即 \(\bm x_{k+1} = \operatorname{argmin}_{\bm y} V_{\overline{\bm x}_{k+1}}(\bm y)\)

按照 Mirror step 的式子,可以看出 Mirror map 就是 \(\nabla w(\cdot)\)。因此实际过程为

  • \(\bm \theta_k = \nabla w(\bm x)\).
  • \(\bm \theta_{k+1} = \bm \theta_k - \alpha \nabla f(\bm x_k)\).
  • \(\overline{\bm x}_{k+1} = (\nabla w)^{-1}(\bm \theta_{k+1})\).
  • \(\bm x_{k+1} = \operatorname{argmin}_{\bm y} V_{\overline{\bm x}_{k+1}}(\bm y)\).

这个视角提出了一点假设,\((\nabla w)^{-1}(\bm x_{k+1})\) 始终存在,即 \(\{\nabla w(\bm x)\} = \mathbb R^n\)

我们来简单地证明两种视角描述的算法是同一件事。

\[\begin{aligned} \bm x_{k+1} &= \operatorname{argmin}_{\bm y} V_{\overline{\bm x}_{k+1}}(\bm y) \\ &= \operatorname{argmin}_{\bm y} \{w(\bm y) - \langle \nabla w(\overline{\bm x}_{k+1}), \bm y - \overline{\bm x}_{k+1}\rangle - w(\overline{\bm x}_{k+1})\} \\ &= \operatorname{argmin}_{\bm y} \{w(\bm y) - \langle \nabla w(\overline{\bm x}_{k+1}), \bm y\rangle \} \\ &= \operatorname{argmin}_{\bm y} \{w(\bm y) - \langle \bm \theta_k - \alpha \nabla f(\bm x_k), \bm y\rangle \} \\ &= \operatorname{argmin}_{\bm y} \{ \alpha \langle\nabla f(\bm x_k), \bm y\rangle + w(\bm y) - \langle \nabla w(\bm x), \bm y\rangle \} \\ &= \operatorname{argmin}_{\bm y} \{ \alpha \langle\nabla f(\bm x_k), \bm y - \bm x\rangle + V_{\bm x}(\bm y) \} \\ \end{aligned}\]

命题\(f\)\(\rho\)-Lipschitz 的,\(w\)\(1\)-强凸的,则 \(T = O\left(\frac {\rho^2}{\epsilon^2}\right)\) 轮后,\(f(\overline {\bm x}) - f(\bm u) < \varepsilon\)

证明

\(1\)-强凸说明

\[V_{\bm x}(\bm y) \geq \frac 12 \|\bm x - \bm y\|^2_2 \]

先来做一个类似于 GD 中 \(L\)-smooth,不使用 \(f\) convex 的一段证明。

\[\begin{aligned} \langle \alpha \nabla f(\bm x_k), \bm x_k - \bm u \rangle &= \langle \alpha \nabla f(\bm x_k), \bm x_k - \bm x_{k+1} \rangle + \langle \alpha \nabla f(\bm x_k), \bm x_{k+1} - \bm u \rangle \\ &= \langle \alpha \nabla f(\bm x_k), \bm x_k - \bm x_{k+1} \rangle + \langle - \nabla V_{\bm x_k}(\bm x_{k+1}), \bm x_{k+1} - \bm u \rangle && (\nabla (V_{\bm x_k}(\bm y) + \langle \alpha \nabla f(\bm x_k), \bm y - \bm x_k\rangle))(\bm x_{k+1}) = \bm 0 \\ &= \langle \alpha \nabla f(\bm x_k), \bm x_k - \bm x_{k+1} \rangle + V_{\bm x_k}(\bm u) - V_{\bm x_{k+1}}(\bm u) - V_{\bm x_k}(\bm x_{k+1}) && \langle -\nabla V_{\bm x}(\bm y), \bm y - \bm u \rangle = V_{\bm x}(\bm u) - V_{\bm y}(\bm u) - V_{\bm x}(\bm y) \\ &\leq \left(\langle \alpha \nabla f(\bm x_k), \bm x_k - \bm x_{k+1} \rangle - \frac 12 \|\bm x_k - \bm x_{k+1}\|^2_2\right) + V_{\bm x_k}(\bm u) - V_{\bm x_{k+1}}(\bm u) \\ &\leq \frac{\alpha^2}2 \|\nabla f(\bm x_k)\|_2^2 + V_{\bm x_k}(\bm u) - V_{\bm x_{k+1}}(\bm u) \\ &\leq \frac {\alpha^2\rho^2}2 + V_{\bm x_k}(\bm u) - V_{\bm x_{k+1}}(\bm u) \end{aligned}\]

\(\overline{\bm x} = \frac 1k\sum_{t=0}^{k-1} \bm x_t\),根据 \(f\) 的凸性,有

\[f(\overline {\bm x}) \leq \frac 1k \sum_{t=0}^{k-1} f(\bm x_t) \]

\[\alpha T(f(\overline {\bm x}) - f(\bm u)) \leq T\frac{\alpha^2\rho^2}2 + V_{\bm x_0}(\bm u) - V_{\bm x_T}(\bm u) \]

假设 \(V_{\bm x_0}(\bm x^*) \leq \Theta\),其中 \(\Theta\) 为常数,则有

\[f(\overline{\bm x}) - f(\bm x^*) \leq \frac{\alpha \rho^2}2 + \frac{\Theta}{\alpha T} \]

\[\alpha = \frac{\sqrt{2 \Theta}}{\rho \sqrt T} \]

则有

\[f(\overline {\bm x}) - f(\bm x^*) \leq \frac{\rho\sqrt{2 \Theta}}{\sqrt T} \]

\(T = O\left(\frac{\rho^2}{\epsilon^2}\right)\)

考虑到 \(\rho\)-Lipschitz 等价于 \(\|\nabla f(x)\|_2 \leq \rho\)。如果我们能给 \(\|\nabla f(x)\|_2\) 设一个阈值 \(K\),对 GD,每一步减小 \(\frac{\|\nabla f\|_2^2}{2L} \geq \frac {K^2}{2L}\),所以只需要 \(O(\frac{\epsilon L}{K^2})\) 轮;对 MD,只需要 \(O(\frac{K^2}{\epsilon^2})\) 轮,令 \(K = \epsilon\sqrt{L \epsilon}\),就有 \(T = O\left(\frac 1{\sqrt{\epsilon}}\right)\),或称,\(O(\frac 1{T^2})\) 的收敛速率。

但 MD 对梯度的要求是全局的,GD 的速率是单点的,因此我们并不能把一个一般的函数用一个全局的阈值 \(K\) 分分清楚。于是我们引入今天的重点,线性耦合 (linear coupling)。当 GD 得到 \(\bm y_k\),MD 得到 \(\bm z_k\) 作为下一步时,我们让 \(\bm x_{k+1} = \tau \bm z_k + (1 - \tau) \bm y_k\)。具体地,

  • \(\bm x_0 = \bm y_0 = \bm z_0\).
  • \(\bm x_{k+1} = \tau \bm z_k + (1 - \tau)\bm y_k\).
  • \(\bm y_{k+1} = -\nabla f(\bm x_{k+1})\).
  • \(\bm z_{k+1} = \mathrm{Mirr}_{\bm z_k}(\alpha \nabla f(\bm x_{k+1}))\).

命题 存在 \(\tau \in (0, 1)\),使得 \(T = O(\frac 1{\sqrt{\epsilon}})\) 轮后,\(f(\overline {\bm x}) - f(\bm x^*) < \epsilon\)

这里非常取巧地把 \(\mathrm{Mirr}\) 的下标改为了和梯度中不一样的参数,这便是一般化起到的作用。在上述 MD 结论的推导中,我们并没有强依赖于下标和梯度参数的一致,在这里这么做实际上只是为了可以裂项,而只有我们将其一般化之后才意识到可以随意地改变参数,如果只是在 GD 的视角下,这个操作不合理的(即在一个点借用别处的梯度)。

证明

尝试使用和 MD 类似的方法,但是不把 \(\|\nabla f(\bm x)\|^2_2\) 化为 \(\rho^2\),而是用 GD 化为 \(f(\bm y)\),再考虑如何将 \(\bm y\) 也裂项。

\[\begin{aligned} \alpha \langle \nabla f(\bm x_{k+1}), \bm z_k - \bm u \rangle &\leq \frac{\alpha^2}2 \|\nabla f(\bm x_{k+1})\|_2^2 + V_{\bm z_k}(\bm u) - V_{\bm z_{k+1}}(\bm u) \\ &\leq \alpha^2 L(f(\bm x_{k+1}) - f(\bm y_{k+1})) + V_{\bm z_k}(\bm u) - V_{\bm z_{k+1}}(\bm u) \end{aligned}\]
\[\begin{aligned} \alpha \langle \nabla f(\bm x_{k+1}), \bm x_{k+1} - \bm u \rangle - \alpha \langle \nabla f(\bm x_{k+1}), \bm z_k - \bm u \rangle &= \alpha \langle\nabla f(\bm x_{k+1}), \bm x_{k+1} - \bm z_k\rangle \\ &= \frac{(1 - \tau)\alpha}{\tau} \langle \nabla f(\bm x_{k+1}), \bm y_k - \bm x_{k+1} \rangle && \tau(\bm x_{k+1} - \bm z_k) = (1 - \tau)(\bm y_k - \bm x_{k+1}) \\ &\leq \frac{(1 - \tau)\alpha}{\tau} (f(\bm y_k) - f(\bm x_{k+1})) && \text{Convexity} \end{aligned}\]

由此,令 \(\frac{1 - \tau}{\tau} = \alpha L\),则有

\[\alpha \langle \nabla f(\bm x_{k+1}), \bm x_{k+1} - \bm u \rangle \leq \alpha^2 L (f(\bm y_k) - f(\bm y_{k+1})) + V_{\bm z_k}(\bm u) - V_{\bm z_{k+1}}(\bm u) \]
\[\begin{aligned} \alpha T (f(\overline {\bm x}) - f(\bm x^*)) &\leq \sum_{k=0}^{T - 1} \alpha \langle \nabla f(\bm x_k), \bm x_k - \bm x^* \rangle \\ &\leq \alpha^2 L(f(\bm y_0) - f(\bm y_T)) + V_{\bm x_0}(\bm x^*) - V_{\bm x_T}(\bm x^*) \end{aligned}\]

假设 \(f(\bm y_0) - f(\bm x^*) \leq d, V_{\bm x_0}(\bm x^*) \leq \Theta\),则有

\[f(\overline{\bm x}) - f(\bm x^*) \leq \frac 1T \left(\alpha Ld + \frac \Theta \alpha\right) \]

\(\alpha = \sqrt{\frac \Theta{Ld}}\) 即可得到

\[f(\overline{\bm x}) - f(\bm x^*) \leq \frac{2\sqrt{L \Theta d}}T \]

\(T = 4 \sqrt{\frac{L \Theta}d}\),则

\[f(\overline {\bm x}) - f(\bm x^*) \leq \frac d2 \]

此时重新设置 \(\alpha\),再进行 \(T' = 4\sqrt{\frac{2L\Theta}{d}}\) 轮,便可以再缩小一倍,以此类推,最终达到 \(\epsilon\),总轮数为

\[O\left(\sqrt{\frac {L \Theta}\epsilon} + \sqrt{\frac {L \Theta}{2 \epsilon}} + \sqrt{\frac {L \Theta}{4\epsilon}} + \ldots\right) = O\left(\sqrt{\frac{L \Theta}{\epsilon}}\right) \]

似乎 Nesterov 证明了 \(O(\frac 1{T^2})\) 是在同假设下最优的下降速率,并且给出了第一代算法,巨难理解,这个线性拟合是最好理解的之一。文章来源地址https://www.toymoban.com/news/detail-711523.html

到了这里,关于[机器学习] 3. 镜像下降 Mirror Descent 与线性耦合 Linear Coupling的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 机器学习--决策树、线性模型、随机梯度下降

    🤵‍♂️ 个人主页:@Lingxw_w的个人主页 ✍🏻作者简介:计算机科学与技术研究生在读 🐋 希望大家多多支持,我们一起进步!😄 如果文章对你有帮助的话, 欢迎评论 💬点赞👍🏻 收藏 📂加关注+    目录  一、决策树 二、线性模型 三、随机梯度下降 决策树(decision

    2024年02月03日
    浏览(41)
  • 机器学习(二):线性回归之梯度下降法

    ✍ 作者简介: i阿极 ,CSDN Python领域新星创作者, 专注于分享python领域知识。 ✍ 本文录入于《机器学习案例》 ,本专栏精选了经典的机器学习算法进行讲解,针对大学生、初级数据分析工程师精心打造,对机器学习算法知识点逐一击破,不断学习,提升自我。 ✍ 订阅后,

    2023年04月22日
    浏览(45)
  • 飞控学习笔记-梯度下降算法(gradient descent algorithm)

    笔记来源于文章:An_efficient_orientation_filter_for_inertial_and_inertial_magnetic_sensor_arrays 共轭: 四元数叉乘: 式(6)为方向余弦矩阵 欧拉角等式: w:角速度

    2024年02月16日
    浏览(39)
  • 【机器学习】P2 线性回归、损失函数与梯度下降

    线性回归简单的说就是线性函数; 线性回归属于机器学习 回归问题; 在线性回归建立的线性关系的模型中,假设目标变量和自变量之间存在一种线性关系,模型的目标是找到最佳的拟合线,是的模型对于未知的数据能够进行最准确的预测; 线性回归模型的一般形式为: y

    2023年04月08日
    浏览(41)
  • 机器学习:基于梯度下降算法的线性拟合实现和原理解析

    当我们需要寻找数据中的趋势、模式或关系时,线性拟合和梯度下降是两个强大的工具。这两个概念在统计学、机器学习和数据科学领域都起着关键作用。本篇博客将介绍线性拟合和梯度下降的基本原理,以及它们在实际问题中的应用。 线性拟合是一种用于找到数据集中线性

    2024年02月10日
    浏览(35)
  • 机器学习的数学基础:从线性代数到梯度下降

    机器学习是人工智能的一个重要分支,它涉及到计算机程序自动化地学习或者预测事物的行为。机器学习的核心是算法,算法需要数学来支持。在本文中,我们将从线性代数到梯度下降的数学基础来讨论机器学习算法的核心。 机器学习的数学基础包括线性代数、微积分、概率

    2024年02月21日
    浏览(45)
  • 吴恩达机器学习-可选实验:使用ScikitLearn进行线性回归(Linear Regression using Scikit-Learn)

    有一个开源的、商业上可用的机器学习工具包,叫做scikit-learn。这个工具包包含了你将在本课程中使用的许多算法的实现。 在本实验中,你将:利用scikit-learn实现使用梯度下降的线性回归 您将使用scikit-learn中的函数以及matplotlib和NumPy。 np.set_printoptions(precision=2) 的作用是告诉

    2024年03月14日
    浏览(47)
  • python机器学习(五)逻辑回归、决策边界、代价函数、梯度下降法实现线性和非线性逻辑回归

    线性回归所解决的问题是把数据集的特征传入到模型中,预测一个值使得误差最小,预测值无限接近于真实值。比如把房子的其他特征传入到模型中,预测出房价, 房价是一系列连续的数值,线性回归解决的是有监督的学习。有很多场景预测出来的结果不一定是连续的,我们

    2024年02月15日
    浏览(84)
  • 【吴恩达·机器学习】第二章:单变量线性回归模型(代价函数、梯度下降、学习率、batch)

    博主简介: 努力学习的22级计算机科学与技术本科生一枚🌸 博主主页: @Yaoyao2024 每日一言🌼: 勇敢的人,不是不落泪的人,而是愿意含着泪继续奔跑的人。 ——《朗读者》 本系列博客文章是博主本人根据吴恩达老师2022年的机器学习课程所学而写,主要包括老师的核心讲义

    2024年02月19日
    浏览(45)
  • 机器学习与深度学习——使用paddle实现随机梯度下降算法SGD对波士顿房价数据进行线性回归和预测

    随机梯度下降(SGD)也称为增量梯度下降,是一种迭代方法,用于优化可微分目标函数。该方法通过在小批量数据上计算损失函数的梯度而迭代地更新权重与偏置项。SGD在高度非凸的损失表面上远远超越了朴素梯度下降法,这种简单的爬山法技术已经主导了现代的非凸优化。

    2024年02月03日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包