AI 与机器学习2018arxiv.org
机器学习中的非凸优化
Non-Convex Optimization for Machine Learning
专业 · 约 180 分钟读完前置知识：优化基础、机器学习基础、线性代数与概率
导读
这篇专著综述机器学习中的非凸优化：它关注一类虽然一般情形下是 NP-hard、但因数据或任务具有结构而可高效求解的非凸问题。核心做法是避免把问题松弛成凸问题，转而直接利用任务结构设计可扩展算法；评论中提到，这类方法可在某些情形下以近线性时间求得全局最优。作者也强调，机器学习中的非凸性往往高度结构化，因此值得系统整理相应算法。
HN 关注点：关于“结构化非凸问题可近线性求解、打破 NP-hard 直觉”的论述，以及作者现身回应和关于遗漏文献、流形优化的专业讨论。
HN 评论精选
这几条评论里：质疑 2 亲历 2
亲历强调利用数据/任务结构可把 NP-hard 非凸问题变成近线性可解，并提出区分 tractable 与 intractable 的研究方向。
前言写道：“更戏剧化地说，这本专著将试图展示：那些曾因被证明是 NP-hard 而被回避的问题，如今通过仔细分析和利用额外的任务结构，已有能在近线性时间内运行的求解器！”我在自己关于逆问题（紧群作用下的信号恢复）的研究中也注意到这一点，真的很震撼。这意味着随机生成的问题会是 NP-hard；但只要问题不是随机生成的（即生成过程有规律），往往存在可利用的内在结构，能快速求得全局最优。我觉得未来研究会聚焦于找出“可处理”与“不可处理”问题之间的分界线。
Xcelerate查看英文原文
From the preface: > Put a bit more dramatically, [this monograph] will seek to show how problems that were once avoided, having been shown to be NP-hard to solve, now have solvers that operate in near-linear time, by carefully analyzing and exploiting additional task structure! This is something I've noticed in my own research on inverse problems (signal recovery over the action of compact groups). And it's really quite mind-blowing. What this means is that you can randomly generate problems, and these will be NP-hard to solve. However, assuming the problem is not randomly generated (i.e., there is some regularity in the generative process that produced the data), there often appears to be some inherent structure that can be exploited to solve the problem quickly to its global optimum. I feel like future research will focus on finding the line that divides the "tractable" problems from the "intractable" ones.
亲历作者澄清专著聚焦机器学习中结构化的非凸问题，强调避免松弛、开发可扩展求解器。
（免责声明：我是这本专著的作者之一。）作者们很高兴这本专著引发讨论，也希望它推动非凸优化基础与应用的研究。机器学习、信号处理中的求解器近年进步很大，包括用于调度等的 MILP 求解器和 LASSO 类求解器。这本专著试图简洁清晰地介绍另一组非常有用且成功的机器学习算法技术。正如有人提到的，非凸问题范围极广，几乎包括所有“非凸”的问题；但机器学习中的非凸性往往很有结构，这本专著试图汇集如何针对这些特定非凸实例、开发高度可扩展求解器的知识。一个关键点是普遍避免“松弛”——那种把非凸问题转成凸问题以便套用成熟技术的常见技巧；基于松弛的方法常常难以扩展。
purushot查看英文原文
(Disclaimer: I am an author of the monograph being discussed) The authors are very glad at the discussion this monograph has generated and would be very happy if this leads to more research and advances in the foundations and applications of non-convex optimization. Solvers for various problems that arise in machine learning and signal processing applications, have seen great improvement in recent years. This includes MILP solvers that are very useful for scheduling and other problems and LASSO-style solvers. This monograph was an attempt to present a concise and lucid introduction to another set of very useful and highly successful algorithmic techniques for machine learning problems. As one comment below mentioned, the scope of non-convex problems is quite vast as it pretty much includes any problem that is "not convex". However, the non-convexity that arises in machine learning and related areas is often very structured and this monograph was an attempt at collecting our collective knowledge on how to address these specific instances of non-convexity and develop extremely scalable solvers for them. A key component of this effort turns out to be a general avoidance of "relaxations", a common trick used to convert non-convex problems into convex ones so that well-understood techniques can be applied (LASSO techniques fall into this category). Frequently, these relaxation-based approaches struggle to scale very well. In this monograph we present several algorithmic techniques that avoid relaxations for this reason. These techniques are very intuitive and offer not just excellent performance in practice (much faster than relaxation based techniques), but provably so (the monograph does indulge in formal analyses of the algorithms). This theoretical aspect of the monograph dates back at least a decade, to the initial advances in compressive sensing due to the seminal works of Candes, Tao and Romberg. These initial results were later shown to be a part of a much more general framework, which this monograph also seeks to present, by presenting applications of non-convex optimization techniques to sparse recovery, matrix completion, latent variable models, and robust learning. We welcome comments and suggestions form all. This monograph is very much a work in progress, especially given the fast pace at which machine learning is moving forward and we wish to keep this text relevant to the community in the future as well, by making relevant updates and additions.
质疑批评综述遗漏重要文献，尤其没有提及广泛适用的非凸 Burer-Monteiro 方法。
也许不可避免，但这篇综述漏掉了大量相关文献。尤其是完全没有提到用于求解半定规划的非凸 Burer-Monteiro 方法，而这是相当广泛适用的技术。
vladislav查看英文原文
Perhaps it's unavoidable, but there are large swaths of relevant literature missing from this survey. In particular there is not a single mention of the non-convex Burer-Monteiro method for solving semidefinite programs, a pretty widely applicable technique.
质疑询问与流形优化相比如何，并认为投影梯度下降只是近似，共轭梯度/牛顿法可能更优。
我想知道这本专著中的技术与流形优化相比如何。投影梯度下降看起来像合适流形上最速下降的近似，所以我预期共轭梯度法或牛顿法在实践中会表现更好。
fmap查看英文原文
I wonder how the techniques in this monograph stack up against optimization techniques on manifolds (https://press.princeton.edu/absil). Projected gradient descent seems like an approximation to steepest descent on a suitable manifold, so I would expect conjugate gradient or Newton methods to perform better in practice.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
- 自称作者的回复
- 视频与演讲
- 评论区提到的论文
历次讨论
- 2018Hacker News 讨论帖154 分 · 32 评
同领域还值得读
DeepSeek-R1：通过强化学习激励 LLM 的推理能力
DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via RL
研究如何用强化学习激励大语言模型的推理能力，提出 DeepSeek-R1，并探讨 RL 训练对模型推理表现的影响。
AI 与机器学习2025 · 1,351 分 · 1,056 评 · 引用 30进阶 · 约 80 分钟编辑精选1-bit LLM 时代：面向低成本计算的三值参数
The Era of 1-bit LLMs: ternary parameters for cost-effective computing
提出用三值参数 {-1, 0, 1} 替代 LLM 中的浮点权重，即所谓“1-bit LLM”。
AI 与机器学习2024 · 1,040 分 · 447 评 · 引用 19进阶 · 约 45 分钟编辑精选DeepSeek-V3.2：推进开放大语言模型的前沿
DeepSeek-v3.2: Pushing the frontier of open large language models
这是 DeepSeek-V3.2 的技术报告，延续了 DeepSeek 开源权重模型的路线，目标是让开放模型继续逼近甚至追平前沿闭源模型。
AI 与机器学习2025 · 982 分 · 465 评进阶 · 约 90 分钟编辑精选通过自我对弈与通用强化学习掌握国际象棋和将棋（AlphaZero）
Mastering Chess and Shogi by Self-Play with General Reinforcement Learning
DeepMind 的 AlphaZero 论文：用通用强化学习算法（自我博弈 + MCTS + 神经网络），从零开始仅数小时训练便在国际象棋和将棋上击败了世界顶级引擎 Stock…
AI 与机器学习2017 · 539 分 · 270 评 · 引用 13进阶 · 约 90 分钟编辑精选用强化学习发现更快的矩阵乘法算法
Discovering faster matrix multiplication algorithms with reinforcement learning
论文提出 AlphaTensor，用强化学习搜索矩阵乘法算法。
AI 与机器学习2022 · 518 分 · 111 评专业 · 约 90 分钟编辑精选