如何从零开始学习凸优化？

量子计算9 · 发表于 2022-1-23 20:18

Boyd的书是本好书，但针对题目学习的目的，我强烈建议题主暂时不要学Boyd的Convex Optimization，理由如下：
1. Boyd的书侧重凸分析的基础，花了非常长的篇幅介绍函数的凸性、对偶等，但在机器学习中，至少在刚入门不久的阶段这些东西用的不算多，或者说在大多数情况下只需要对这些有基本概念就行；
2. 这本书虽然很厚，但介绍的算法非常有限，学了很长时间你会觉得对你的研究基本毫无帮助，你要的东西书中没有，学的东西大多也用不上，让你很容易半途而废；
3. 目前机器学习领域优化研究的热点在往非凸优化转，ICML/NIPS上现在有越来越多的paper在研究算法在非凸情况下的收敛性（谁叫目前最热门的DNN是非凸的呢）。
我建议题目先读两个monograph：一个是Bubeck的《Convex Optimization: Algorithms and Complexity》，接下来再读Bottou、Curtis和Nocedal合作写的《Optimization Methods for Large-Scale Machine Learning》。前者从凸性的基本概念开始介绍，把常用的一阶算法都做了系统的介绍，它不需要任何优化基础就可以读懂；后者介绍了机器学习和优化交叉领域目前最新的研究成果，这个survey非常新，去年才写出来，今年也做过更新，而且作者也很牛，Bottou是在机器学习和优化交叉方向最优秀的几位研究者之一，Nocedal是鼎鼎大名的传统优化大牛（目前在世的人中排前5应该不过分）。认真读过这两个过后，我相信题主看目前主流机器学习优化相关的paper、做一些相关研究毫无问题。
当然，如果题目想做好的研究，系统地学习凸优化的东西还是有必要的。这个可以等你入门了再一边做研究一边慢慢细读Convex Optimization、Numerical Optimization、Introductory Lectures on Convex Optimization等书。
本人也是做这方面研究的。我所在的组是做纯优化的，但我的研究方向更多偏向机器学习中的优化，paper也都发在NIPS等机器学习相关的会议上。所以我两边都比较了解，以上是以我自身体会给题主的建议。

kirin77 · 发表于 2022-1-23 20:18

Boyd的书是本好书，但针对题目学习的目的，我强烈建议题主暂时不要学Boyd的Convex Optimization，理由如下：
1. Boyd的书侧重凸分析的基础，花了非常长的篇幅介绍函数的凸性、对偶等，但在机器学习中，至少在刚入门不久的阶段这些东西用的不算多，或者说在大多数情况下只需要对这些有基本概念就行；
2. 这本书虽然很厚，但介绍的算法非常有限，学了很长时间你会觉得对你的研究基本毫无帮助，你要的东西书中没有，学的东西大多也用不上，让你很容易半途而废；
3. 目前机器学习领域优化研究的热点在往非凸优化转，ICML/NIPS上现在有越来越多的paper在研究算法在非凸情况下的收敛性（谁叫目前最热门的DNN是非凸的呢）。
我建议题目先读两个monograph：一个是Bubeck的《Convex Optimization: Algorithms and Complexity》，接下来再读Bottou、Curtis和Nocedal合作写的《Optimization Methods for Large-Scale Machine Learning》。前者从凸性的基本概念开始介绍，把常用的一阶算法都做了系统的介绍，它不需要任何优化基础就可以读懂；后者介绍了机器学习和优化交叉领域目前最新的研究成果，这个survey非常新，去年才写出来，今年也做过更新，而且作者也很牛，Bottou是在机器学习和优化交叉方向最优秀的几位研究者之一，Nocedal是鼎鼎大名的传统优化大牛（目前在世的人中排前5应该不过分）。认真读过这两个过后，我相信题主看目前主流机器学习优化相关的paper、做一些相关研究毫无问题。
当然，如果题目想做好的研究，系统地学习凸优化的东西还是有必要的。这个可以等你入门了再一边做研究一边慢慢细读Convex Optimization、Numerical Optimization、Introductory Lectures on Convex Optimization等书。
本人也是做这方面研究的。我所在的组是做纯优化的，但我的研究方向更多偏向机器学习中的优化，paper也都发在NIPS等机器学习相关的会议上。所以我两边都比较了解，以上是以我自身体会给题主的建议。

stonstad · 发表于 2022-1-23 20:28

看到好像没有人说到我推荐的这个课程，在这个问题下也回答一下。
Boyd 的《Convex Optimization》确实是一本好书，当年在数学系读书的时候，很多老师也都推荐这本书。这本书的优点是大而全，拿在手上就能感受到沉甸甸的重量。。。我自己也曾经想好好读一读这本书，尝试了几次都没有完整地坚持下来。。
究其原因在于，对于初学者来说，如此厚重的书有时却不一定友好，因为不知道哪些东西该跳过（或者可以跳过），只能硬着头皮从头看到尾，生怕错过了什么重要部分。但书本身又太厚重，花费很多时间，结果才发现看了1/10，很容易坚持不下去。于是就出现了题主所说的“看第二章的时候就看晕了，优化的部分都还没看到，一大堆概念感觉很多都不会”。。
其实如果不是专业研究运筹学或者优化理论，不太需要把整本书完整的看下来，也不需要去看太多专业的优化书籍。
这里强烈推荐 CMU 的青年才俊 Ryan Tibshirani 开设的《Convex Optimization》的课程。Ryan 是统计系的老师，开设这门课也主要是面向机器学习研究的同学，所以很适合机器学习领域的同学学习该课程。
看 Boyd 的书以及看 Boyd 的视频都没坚持下来的我，竟然把这门课完整地看下来了。一是这门课比较精简，并不需要花太多时间在上面，学习起来比较有动力；二是因为 Ryan 是个非常好的老师，绝不是照本宣科那种。尽管看上去非常年轻，但是非常循循善诱，讲课的功底非常好。说实话，这么多年，我遇到过的能把数学课讲得深入浅出的，一个手都能数得过来。Ryan 就是其中一个。
这门课从比较基础的地方讲起，并不需要太多预备知识，像题主所说的泛函分析完全不需要。尽管有公式推导，也有收敛性和收敛速度证明这些。本来我之前看书看到这些东西也头大，在 Ryan 的讲解下却听懂了！！
这门课的主页在http://www.stat.cmu.edu/~ryantibs/convexopt/，里面有上课时用的 slides，还有Note，在 YouTube 上还有当年上课时录的视频。
我当年看的应该是2016年的版本，现在好像有更新的。
Ryan 的英语比较纯正，没什么口音，配合 YouTube 的字幕和 slides 看，听懂问题不大。不过课程后半段有个印度裔老师，说的英语我就听得不太懂。。靠着看 slides 也坚持了下来。
课程最后也会请一些嘉宾（Guest Lecture）来讲讲跟课程相关的比较前沿的东西，我当年看的时候，请的一个嘉宾来讲了 SGD 的一些相关算法，像是什么 SVRG，SAGA 这种算法，直接看论文都不太看得明白，也在这门课上听懂了。
这里附上这门课的目录，有兴趣的同学可以看看。这门课基本覆盖了机器学习里面能用到的优化算法，像是 SVM 里面需要用到的 Duality，以及很多基于梯度的优化算法。学完这门课，基本上机器学习相关论文里遇到的优化部分都没太多问题。

国外其实有很多不错的公开课，也有很多非常年轻的老师讲课水平非常好，像是 Stanford 的Richard Socher（当年看他讲的NLP入的门）和 MIT 的Erik Demaine（他讲的算法课非常好）都是非常年轻，但是讲课水平极高。

XGundam05 · 发表于 2022-1-23 20:35

从零开始话，我觉得cuhk苏文藻老师的课绝对是不错的选择。目前在上他的课，讲的非常好，只是我学的不好,,^,,
百度搜索
cuhk engg 5501 foundations of optimization
男神的网站上有详细的讲义，基本就属于“逐字稿”。而且也提供了几本免费的参考书。
然后可以和我一起讨论作业啊_(:з」∠)_

RecursiveFrog · 发表于 2022-1-23 20:42

谢邀，既然题主点名要学 Boyd ，最直接的方法显然是去听 Boyd 和他的 PhD 学生讲的免费公开课，跟着做他的网站上的作业和考试题。
公开课：Convex Optimization
他在 YouTube 上也发布了在斯坦福大学授课时的课程视频，虽然时间久远一些，但感觉要比公开课中的讲的好，Boyd 的美式英语非常标准易懂，听他的课是一种享受：
课程视频：Lecture 1 | Convex Optimization
作业：EE364a: Homework
对机器学习感兴趣的话，顺便推荐 Hastie、 Tibshirani 两位大牛合开的统计学习课，也和凸优化有一部分重叠。
公开课：Statistical Learning
广告时间：
分布式/随机优化领域的研究如何开展？PS：Course staff 之一，萌萌的 Ernest Ryu 正在我之前所在的组做 postdoc ：）

IT圈老男孩1 · 发表于 2022-1-23 20:47

非凸优化问题被认为是非常难求解的，因为可行域集合可能存在无数个局部最优点，通常求解全局最优的算法复杂度是指数级的（NP 困难）。在近日的一篇文章中，斯坦福大学助理教授马腾宇介绍了机器学习中的非凸优化问题，包括广义线性模型、矩阵分解、张量分解等。
非凸优化在现代机器学习中普遍存在。研究人员设计了非凸目标函数，并使用现成的优化器（例如随机梯度下降及其变体）对其进行了优化，它们利用了局部几何并进行迭代更新。即使在最坏的情况下求解非凸函数都是 NP 困难的，但实践中的优化质量通常也不是问题，人们普遍认为优化器会找到近似全局最小值。
最近，在斯坦福大学助理教授马腾宇（Tengyu Ma）的一篇文章中，他为这种有趣的现象假设了一种统一的解释：实际使用目标的大多数局部最小值约为全局最小值，并针对机器学习问题的具体实例进行了严格地形式化。

文章地址：https://www.zhuanzhi.ai/paper/db8182cc06b1305e450a66a7893e9230
优化非凸函数已成为现代机器学习和人工智能的标准算法技术。了解现有的优化非凸函数启发式方法非常重要，我们需要设计更有效的优化器。其中最棘手的问题是寻找非凸优化问题的全局极小值，甚至仅仅是一个 4 阶多项式——NP 困难。因此，具有全局保证的理论分析依赖于优化的目标函数的特殊属性。为了描述真实世界目标函数的属性特征，研究者假设机器学习问题的许多目标函数具有以下属性：全部或者绝大多数局部极小值近似于全局极小值。
基于局部导数的优化器可以在多项式时间内求解这一系列函数（下文讨论中也增加了一些额外的假设）。经验证据也表明机器学习和深度学习的实际目标函数可能具有这样的属性。
文章共分为七个章节，各章节主旨内容如下：

第一章：非凸函数的基本内容；
第二章：分析技术，包括收敛至局部极小值、局部最优 VS 全局最优和流形约束优化；
第三章：广义线性模型，包括种群风险分析和经验风险集中；
第四章：矩阵分解问题，包括主成分分析和矩阵补全；
第五章：张量分解，包括正交张量分解的非凸优化和全局最优；
第六章：神经网络优化的综述与展望。

文章细节
广义线性模型
第三章讲了学习广义线性模型的问题，并证明该模型的损失函数是非凸的，但局部极小值是全局的。在广义线性模型里，假设标签

生成自

，其中σ: R→R 是已知的单调激活函数，ε_i∈R 均为独立同分布（i.i.d.）的均值零噪声 (与 x_i 无关)，

是一个固定的未知真值系数向量。
研究者的目标是从数据中恢复ω*，然后最小化经验平方风险：

。

是相应的种群风险（population risk）。
该研究通过对其 landscape 属性的表征来分析
的优化，分析路径包括两个部分：a) 所有种群风险的局部极小值都是全局极小值；b) 经验风险
具有同样的属性。
不再是凸的。在本节其余部分中，研究者对这个问题进行了规律性假设。为了便于阐述，这些假设比必要的假设更为有力。当σ是恒等函数时，即σ（t）=t 为线性回归问题，损失函数是凸的。在实践中，人们已经把σ作为 sigmoid 函数，然后目标

不再是凸的。在本节其余部分中，研究者对这个问题进行了规律性假设。为了便于阐述，这些假设比必要的假设更为有力。
PCA 与矩阵补全
第四章讨论了基于矩阵分解的两个优化问题：主成分分析（PCA）和矩阵补全。它们与广义线性模型的根本区别在于，目标函数具有非局部极小或全局极小的鞍点。这意味着拟凸条件或 Polyak-Lojasiewicz（PL）条件不适用于这些目标。因此，需要更复杂的技术来区分鞍点和局部极小值。
主成分分析的一种解释是用最佳低秩近似来逼近矩阵。给出一个矩阵

，求其最佳秩 r 逼近（Frobenius 范数或谱范数）。为了便于说明，研究者取

，并假设 M 是维数为 d×d 的对称半正定。在这种情况下，最佳秩 1 近似的形式为

矩阵补全是指从部分观测项中恢复低秩矩阵的问题，在协同过滤和推荐系统、降维、多类学习等方面得到了广泛的应用。研究者讨论了秩为 1 对称矩阵补全。
张量分解
第五章分析了另一个机器学习优化问题——张量分解。张量分解与矩阵分解或广义线性模型的根本区别在于，这里的非凸目标函数具有多个孤立的局部极小值，因此局部极小值集不具有旋转不变性，而在矩阵补全或主成分分析中，局部极小值集具有旋转不变性。这从本质上阻止只使用线性代数技术，因为它们本质上是旋转不变的。
研究者专注于一个最简单的张量分解问题——正交四阶张量分解。假设得到一个对称的 4 阶张量

，它具有低秩结构，即：

其中

。研究者的目的是恢复底层组件 a_1, . . . , a_n。他假设 a_1, . . . , a_n 是单位范数 R^d 中的正交向量，则目标函数为：

原文链接：斯坦福助理教授马腾宇：机器学习非凸优化问题 - 专知VIP

Ylisar · 发表于 2022-1-23 20:56

谢邀，我的观点和前几位答主有点不同，如果真的是学凸优化的话，boyd这本书很值得细啃，倒是那门公开课给我的感觉很一般，如果没啃过书的话能吸收到的东西很有限，啃完书又很有余力的话看看吧。
那么说说这本书，我喜欢它的原因有两个，一是这本书的理论深度刚刚好。我对比另外两本书是rockafellar的凸分析和nocedal的数值最优化，前者是凸理论的巨著经典，后者是计算数学和最优化方向很好的入门书。对于大多数人来说，凸分析太过抽象，缺乏场景来帮助理解，而数值最优化太偏重应用，对于研究的帮助有限，而凸优化这本书相当平衡，对于凸集，对偶这些基础知识讲的足够，同时又有充足的例子给出应用场景。对于这本书，我的建议是先花大力气看前几章，凸集和凸函数，拉格朗日对偶的推导，还有线性规划这些章节的理论基础都吃透。而对于后几章可以选择性的看，毕竟对于机器学习来说这本书里的问题都太老了，全局的算法也几乎都用不到，有了基础后还是要抓紧投入paper，时不时翻一些作为扩充即可。
那么好像还是没讲怎么看，这里就要提我喜欢这本书的另一个原因了，就是它的习题。比起它的内容，这本书的题有点难度，很值得一做，不少证明在当时都挺靠近研究前沿的。一般看书我都是两周后试着不翻书本把定理来检验自己的掌握程度的，而这门课我记得是靠作业顶的，当然你也可以都试试。
最后，来一个从零开始学的诀窍…就是…
先！看！起！来！

Ylisar · 发表于 2022-1-23 21:03

当然是学习这个网站的slides啊：
CONVEX OPTIMIZATION

HuldaGnodim · 发表于 2022-1-23 21:10

请参阅我的博客文章: (我的凸优化学习之路)

ainatipen · 发表于 2022-1-23 21:17

实名推荐科大凌青老师（看主页现在成了中山的老师）的《最优化理论》这门课！
小白表示老师讲得很有趣，深入浅出而且旁征博引。
B站有搬运版而且音质相对很多录播课程非常优秀了。
BTW, 老师的随课教程也是Boyd的这本~
下面是课程链接哈
中科大研究生课程-机器学习之凸优化

		自动登录	找回密码
密码			立即注册

如何从零开始学习凸优化？

本帖子中包含更多资源

本帖子中包含更多资源