凸优化研究在凸集上最小化凸函数的问题。凸性,连同它的许多含义,已经被用来为许多类凸程序提出有效的算法。因此,凸优化已经广泛地影响了科学和工程的几个学科。

过去几年,凸优化算法彻底改变了离散和连续优化问题的算法设计。对于图的最大流、二部图的最大匹配和子模函数最小化等问题,已知的最快算法涉及到对凸优化算法的基本和重要使用,如梯度下降、镜像下降、内点方法和切割平面方法。令人惊讶的是,凸优化算法也被用于设计离散对象(如拟阵)的计数问题。同时,凸优化算法已经成为许多现代机器学习应用的中心。由于输入实例越来越大、越来越复杂,对凸优化算法的需求也极大地推动了凸优化技术本身的发展。

这本书的目的是使读者能够获得对凸优化算法的深入理解。重点是从第一性原理推导出凸优化的关键算法,并根据输入长度建立精确的运行时间界限。由于这些方法的广泛适用性,一本书不可能向所有人展示这些方法的应用。这本书展示了各种离散优化和计数问题的快速算法的应用。本书中所选的应用程序的目的是为了说明连续优化和离散优化之间的一个相当令人惊讶的桥梁。

目标受众包括高级本科生、研究生和理论计算机科学、离散优化和机器学习方面的研究人员。

https://convex-optimization.github.io/

第一章-连续优化和离散优化的衔接

我们提出了连续优化和离散优化之间的相互作用。最大流问题是一个激励人心的例子。我们也追溯了线性规划的历史——从椭球法到现代内点法。最后介绍了椭球法在求解最大熵问题等一般凸规划问题上的一些最新成果。

第二章 预备知识

我们复习这本书所需的数学基础知识。这些内容包括多元微积分、线性代数、几何、拓扑、动力系统和图论中的一些标准概念和事实。

第三章-凸性

我们引入凸集,凸性的概念,并展示了伴随凸性而来的能力:凸集具有分离超平面,子梯度存在,凸函数的局部最优解是全局最优解。

第四章-凸优化与效率

我们提出了凸优化的概念,并正式讨论了它意味着什么,有效地解决一个凸程序作为一个函数的表示长度的输入和期望的精度。

第五章-对偶性与最优性

我们引入拉格朗日对偶性的概念,并证明在一个称为Slater条件的温和条件下,强拉格朗日对偶性是成立的。随后,我们介绍了拉格朗日对偶和优化方法中经常出现的Legendre-Fenchel对偶。最后,给出了Kahn-Karush-Tucker(KKT)最优性条件及其与强对偶性的关系。

第六章-梯度下降

我们首先介绍梯度下降法,并说明如何将其视为最陡下降。然后,我们证明了梯度下降法在函数的梯度是连续的情况下具有收敛时间界。最后,我们使用梯度下降法提出了一个快速算法的离散优化问题:计算最大流量无向图。

第七章-镜像下降和乘法权值更新

我们推出我们的凸优化的第二个算法-称为镜面下降法-通过正则化观点。首先,提出了基于概率单纯形的凸函数优化算法。随后,我们展示了如何推广它,重要的是,从它推导出乘法权值更新(MWU)方法。然后利用后一种算法开发了一个快速的近似算法来解决图上的二部图匹配问题。

第八章-加速梯度下降

提出了Nesterov的加速梯度下降算法。该算法可以看作是前面介绍的梯度下降法和镜像下降法的混合。我们还提出了一个应用加速梯度法求解线性方程组。

第九章-牛顿法

IWe开始了设计凸优化算法的旅程,其迭代次数与误差成对数关系。作为第一步,我们推导并分析了经典的牛顿方法,这是一个二阶方法的例子。我们认为牛顿方法可以被看作是黎曼流形上的最速下降,然后对其收敛性进行仿射不变分析。

第十章 线性规划的内点法

利用牛顿法及其收敛性,推导出一个线性规划的多项式时间算法。该算法的关键是利用障碍函数的概念和相应的中心路径,将有约束优化问题简化为无约束优化问题。

第十一章-内点法的变种与自洽

给出了线性规划中路径遵循IPM的各种推广。作为应用,我们推导了求解s-t最小代价流问题的快速算法。随后,我们引入了自一致性的概念,并给出了多边形和更一般凸集的障碍函数的概述。

第十二章 线性规划的椭球法

介绍了凸优化的一类切割平面方法,并分析了一种特殊情况,即椭球体法。然后,我们展示了如何使用这个椭球方法来解决线性程序超过0-1多边形时,我们只能访问一个分离oracle的多边形。

第十三章-凸优化的椭球法

我们展示了如何适应椭球法求解一般凸程序。作为应用,我们提出了子模函数最小化的多项式时间算法和计算组合多边形上的最大熵分布的多项式时间算法。

成为VIP会员查看完整内容
0
131

相关内容

凸优化,是数学最优化的一个子领域,研究定义于凸集中的凸函数最小化的问题。

凸优化应用于很多学科领域,诸如自动控制系统,信号处理,通讯和网络,电子电路设计,数据分析和建模,统计学(最优化设计),以及金融。在近来运算能力提高和最优化理论发展的背景下,一般的凸优化已经接近简单的线性规划一样直捷易行。许多最优化问题都可以转化成凸优化。

尽管它在机器学习中有重要的应用,非凸非凹目标的最小-最大优化仍然是难以实现的。不仅没有已知的一阶方法收敛甚至近似局部最小最大点,而且识别它们的计算复杂度也不为人所知。本文给出了非凸非凹目标和线性约束的约束最小-最优优化问题的计算复杂度,以及一阶方法的局限性。

https://arxiv.org/abs/2009.09623

成为VIP会员查看完整内容
0
26

神经网络在诸多应用领域展现了巨大的潜力,成为当前最热门的研究方向之一。神经网络的训练主要通过求解一个优化问题来完成,但这是一个困难的非线性优化问题,传统的优化理论难以直接应用。在神经网络和优化的交叉领域,长期以来研究人员积累了大量的理论研究知识,不过这些研究或过于理论而不被大部分实践者所了解,或过于偏工程而不被理论学者所理解和欣赏。本文的目的是总结目前对于神经网络优化基本理论和算法的现状,架起理论和实践、优化和机器学习界之间的桥梁。

对苦于调参常感到困惑的工程师而言,本文可以提供一些已有的理论理解以供参考,并提供一些思考的方式。对理论学者而言,本文力图解释其作为数学问题的困难之所在以及目前的理论进展,以期吸引更多研究者投身神经网络优化理论和算法研究。

本文概述了神经网络的算法和优化理论。首先,我们讨论梯度爆炸/消失问题和更一般的谱控制问题,然后讨论实际中常用的解决方案,包括初始化方法和归一化方法。其次,我们回顾用于训练神经网络的一般优化方法,如SGD、自适应梯度方法和大规模分布式训练方法,以及这些算法的现有理论结果。第三,我们回顾了最近关于神经网络训练的全局问题的研究,包括局部极值、模式连接、彩票假设和无限宽度分析等方面的结果。

成为VIP会员查看完整内容
1
60

这本书来自统计学习课程,这是一门统计机器学习的入门课程,面向具有一些微积分、线性代数和统计学背景的学生。这门课程的重点是监督学习:分类和回归。本课程将涵盖机器学习和数据科学中使用的一系列方法,包括:

  • 线性回归(包括岭回归和Lasso)
  • 通过logistic回归和k近邻进行分类
  • 线性和二次判别分析
  • 回归和分类树(包括套袋林和随机林)
  • Boosting
  • 神经网络和深度学习

这些方法将在整个课程中被研究并应用于来自各种应用的真实数据。课程还涵盖了一些重要的实际问题,如交叉验证、模型选择和偏方差权衡。课程包括理论(例如,推导和证明)以及实践(特别是实验室和小型项目)。实际部分将使用Python实现。

成为VIP会员查看完整内容
0
118

机器学习是计算机科学中增长最快的领域之一,具有深远的应用。本书的目的是介绍机器学习,以及它所提供的算法范例。本书对机器学习的基本原理和将这些原理转化为实际算法的数学推导提供了理论解释。在介绍了基础知识之后,这本书涵盖了以前教科书没有涉及到的一系列广泛的中心主题。这些包括讨论学习的计算复杂性和凸性和稳定性的概念;重要的算法范例包括随机梯度下降、神经网络和结构化输出学习;以及新兴的理论概念,如PAC-Bayes方法和基于压缩的界限。本文面向高级本科生或刚毕业的学生,使统计学、计算机科学、数学和工程学领域的学生和非专业读者都能接触到机器学习的基本原理和算法。

https://www.cse.huji.ac.il/~shais/UnderstandingMachineLearning/index.html

概述

机器学习是指自动检测数据中有意义的模式。在过去的几十年里,它已经成为几乎所有需要从大数据集中提取信息的任务的通用工具。我们被一种基于机器学习的技术包围着:搜索引擎学习如何给我们带来最好的结果(同时投放有利可图的广告),反垃圾邮件软件学习如何过滤我们的电子邮件信息,信用卡交易被一种学习如何侦测欺诈的软件保护着。数码相机学会识别人脸,智能手机上的智能个人辅助应用学会识别语音指令。汽车配备了使用机器学习算法构建的事故预防系统。机器学习还广泛应用于生物信息学、医学和天文学等科学领域。

所有这些应用程序的一个共同特征是,与计算机的更传统使用相比,在这些情况下,由于需要检测的模式的复杂性,人类程序员无法提供关于这些任务应该如何执行的明确、详细的规范。以智慧生物为例,我们的许多技能都是通过学习我们的经验(而不是遵循给我们的明确指示)而获得或改进的。机器学习工具关注的是赋予程序“学习”和适应的能力。

这本书的第一个目标是提供一个严格的,但易于遵循,介绍机器学习的主要概念: 什么是机器学习?

本书的第二个目标是介绍几种关键的机器学习算法。我们选择展示的算法一方面在实践中得到了成功应用,另一方面提供了广泛的不同的学习技术。此外,我们特别关注适合大规模学习的算法(又称“大数据”),因为近年来,我们的世界变得越来越“数字化”,可用于学习的数据量也在急剧增加。因此,在许多应用中数据量大,计算时间是主要瓶颈。因此,我们明确地量化了学习给定概念所需的数据量和计算时间。

目录:

  • Introduction

Part I: Foundations

  • A gentle start
  • A formal learning model
  • Learning via uniform convergence
  • The bias-complexity trade-off
  • The VC-dimension
  • Non-uniform learnability
  • The runtime of learning

Part II: From Theory to Algorithms

  • Linear predictors
  • Boosting
  • Model selection and validation
  • Convex learning problems
  • Regularization and stability
  • Stochastic gradient descent
  • Support vector machines
  • Kernel methods
  • Multiclass, ranking, and complex prediction problems
  • Decision trees
  • Nearest neighbor
  • Neural networks

Part III: Additional Learning Models

  • Online learning
  • Clustering
  • Dimensionality reduction
  • Generative models
  • Feature selection and generation

Part IV: Advanced Theory

  • Rademacher complexities
  • Covering numbers
  • Proof of the fundamental theorem of learning theory
  • Multiclass learnability
  • Compression bounds
  • PAC-Bayes

Appendices

  • Technical lemmas
  • Measure concentration
  • Linear algebra
成为VIP会员查看完整内容
0
171

这本专著,我通过在线凸优化的现代视角介绍了在线学习的基本概念。这里,在线学习指的是在最坏情况假设下的后悔最小化框架。我提出了凸损失在线学习的一阶和二阶算法,在欧几里德和非欧几里德设置。所有的算法都清晰地呈现为在线镜像下降或跟随正则化及其变体的实例化。特别关注的是通过自适应和无参数在线学习算法来调整算法的参数和在无界域内学习的问题。非凸损失通过凸替代损失和随机化处理。本文还简要讨论了强盗设置问题,讨论了具有对抗性和随机性的多武装强盗问题。这些笔记不需要凸分析的先验知识,所有必需的数学工具都得到了严格的解释。此外,所有的证明都经过精心挑选,尽可能地简单和简短。

成为VIP会员查看完整内容
0
44

高斯过程(GPs)为核机器的学习提供了一种有原则的、实用的、概率的方法。在过去的十年中,GPs在机器学习社区中得到了越来越多的关注,这本书提供了GPs在机器学习中理论和实践方面长期需要的系统和统一的处理。该书是全面和独立的,针对研究人员和学生在机器学习和应用统计学。

这本书处理监督学习问题的回归和分类,并包括详细的算法。提出了各种协方差(核)函数,并讨论了它们的性质。从贝叶斯和经典的角度讨论了模型选择。讨论了许多与其他著名技术的联系,包括支持向量机、神经网络、正则化网络、相关向量机等。讨论了包括学习曲线和PAC-Bayesian框架在内的理论问题,并讨论了几种用于大数据集学习的近似方法。这本书包含说明性的例子和练习,和代码和数据集在网上是可得到的。附录提供了数学背景和高斯马尔可夫过程的讨论。

成为VIP会员查看完整内容
0
130

如今是人工智能高歌猛进的时代,机器学习的发展也如火如荼。然而,复杂的数学公式和难解的专业术语容易令刚接触这一领域的学习者望而生畏。有没有这样一本机器学习的书,能摒弃复杂的公式推导,带领读者通过实践来掌握机器学习的方法?

《机器学习与优化》正是这样一本书!它的写作脱胎于意大利特伦托大学机器学习与智能优化实验室(LION lab)的研究项目,语言轻松幽默,内容图文并茂,涵盖了机器学习中可能遇到的各方面知识。更重要的是,书中特别介绍了两个机器学习的应用,即信息检索和协同推荐,让读者在了解信息结构的同时,还能利用信息来预测相关的推荐项。

本书作者以及读者群发布的数据、指导说明和教学短片都可以在本书网站上找到:https://intelligent-optimization.org/LIONbook/。

本书内容要点: ● 监督学习——线性模型、决策森林、神经网络、深度和卷积网络、支持向量机等 ● 无监督模型和聚类——K均值、自底而上聚类、自组织映射、谱图绘制、半监督学习等 ● 优化是力量之源——自动改进的局部方法、局部搜索和反馈搜索优化、合作反馈搜索优化、多目标反馈搜索优化等 ● 应用精选——文本和网页挖掘,电影的协同推荐系统

成为VIP会员查看完整内容
1
117

本备忘单是机器学习手册的浓缩版,包含了许多关于机器学习的经典方程和图表,旨在帮助您快速回忆起机器学习中的知识和思想。

这个备忘单有两个显著的优点:

  1. 清晰的符号。数学公式使用了许多令人困惑的符号。例如,X可以是一个集合,一个随机变量,或者一个矩阵。这是非常混乱的,使读者很难理解数学公式的意义。本备忘单试图规范符号的使用,所有符号都有明确的预先定义,请参见小节。

  2. 更少的思维跳跃。在许多机器学习的书籍中,作者省略了数学证明过程中的一些中间步骤,这可能会节省一些空间,但是会给读者理解这个公式带来困难,读者会在中间迷失。

成为VIP会员查看完整内容
0
209
小贴士
相关VIP内容
专知会员服务
26+阅读 · 2020年9月25日
专知会员服务
118+阅读 · 2020年6月27日
专知会员服务
130+阅读 · 2020年5月2日
机器学习速查手册,135页pdf
专知会员服务
209+阅读 · 2020年3月15日
【新书】Python编程基础,669页pdf
专知会员服务
109+阅读 · 2019年10月10日
相关资讯
2018年深度学习优化算法最新综述
计算机视觉战队
9+阅读 · 2018年12月11日
【资源】这本开放书籍帮你扫清通往ML的数学绊脚石
机器学习算法与Python学习
45+阅读 · 2018年10月28日
从零开始学习「张氏相机标定法」(四)优化算法前传
计算机视觉life
3+阅读 · 2018年3月14日
贝叶斯机器学习前沿进展
架构文摘
9+阅读 · 2018年2月11日
2017年深度学习优化算法最新综述
计算机视觉战队
5+阅读 · 2017年12月18日
干货|掌握机器学习数学基础之优化[1](重点知识)
机器学习研究会
6+阅读 · 2017年11月19日
相关论文
A Theory of Hyperbolic Prototype Learning
Martin Keller-Ressel
0+阅读 · 2020年10月15日
Shih-Kang Chao,Zhanyu Wang,Yue Xing,Guang Cheng
0+阅读 · 2020年10月13日
Eugene Goldberg
0+阅读 · 2020年10月12日
Kai Yang,Masoud Asgharian,Sahir Bhatnagar
0+阅读 · 2020年10月12日
Meiyan Song,Hangguan Shan,Howard H. Yang,Tony Q. S. Quek
0+阅读 · 2020年10月12日
Jared Millson
0+阅读 · 2020年10月11日
Zhiqiang Wei,Yuanxin Cai,Zhuo Sun,Derrick Wing Kwan Ng,Jinhong Yuan,Mingyu Zhou,Lixin Sun
0+阅读 · 2020年10月11日
Martin Bromberger,Alberto Fiori,Christoph Weidenbach
0+阅读 · 2020年10月9日
Xipeng Qiu,Tianxiang Sun,Yige Xu,Yunfan Shao,Ning Dai,Xuanjing Huang
91+阅读 · 2020年3月18日
Optimization for deep learning: theory and algorithms
Ruoyu Sun
81+阅读 · 2019年12月19日
Top