Convex Optimization: Algorithms and Complexity

本专著介绍了凸优化的主要复杂性定理及其相应的算法。从黑箱优化的基本理论出发,对结构优化和随机优化的最新进展进行了研究。黑盒优化的介绍,受到Nesterov的开创性著作和Nemirovski的课堂讲稿的强烈影响,包括对切割平面方法的分析,以及(加速)梯度下降方案。我们还特别关注非欧几里得设置(相关算法包括Frank-Wolfe、镜像下降和双重平均),并讨论它们在机器学习中的相关性。我们温和地介绍了结构优化与FISTA(优化光滑项和简单非光滑项的求和),鞍点反射法(Nemirovski的替代Nesterov平滑),以及内部点方法的简明描述。在随机优化中,我们讨论了随机梯度下降、小批量、随机坐标下降和次线性算法。我们也简要地接触到组合问题的凸松弛和使用随机的圆解,以及基于随机漫步的方法。

https://www.nowpublishers.com/article/Details/MAL-050

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

相关内容

图论因其在计算机科学、通信网络和组合优化方面的应用而成为一门重要的学科。它与其他数学领域的互动也越来越多。虽然这本书可以很好地作为图表理论中许多最重要的主题的参考,但它甚至正好满足了成为一本有效的教科书的期望。主要关注的是服务于计算机科学、应用数学和运筹学专业的学生,确保满足他们对算法的需求。在材料的选择和介绍方面,已试图在基本的基础上容纳基本概念,以便对那些刚进入这一领域的人提供指导。此外,由于它既强调定理的证明,也强调应用,所以应该先吸收主题,然后对主题的深度和方法有一个印象。本书是一篇关于图论的综合性文章,主题是有组织的、系统的。这本书在理论和应用之间取得了平衡。这本书以这样一种方式组织,主题出现在完美的顺序,以便于学生充分理解主题。这些理论已经用简单明了的数学语言进行了描述。这本书各方面都很完整。它将为主题提供一个完美的开端,对主题的完美理解,以及正确的解决方案的呈现。本书的基本特点是,概念已经用简单的术语提出,并详细解释了解决过程。

这本书有10章。每一章由紧凑但彻底的理论、原则和方法的基本讨论组成,然后通过示例进行应用。本书所介绍的所有理论和算法都通过大量的算例加以说明。这本书在理论和应用之间取得了平衡。第一章介绍图。第一章描述了同构、完全图、二部图和正则图的基本和初等定义。第二章介绍了不同类型的子图和超图。本章包括图形运算。第二章还介绍了步行、小径、路径、循环和连通或不连通图的基本定义。第三章详细讨论了欧拉图和哈密顿图。第四章讨论树、二叉树和生成树。本章深入探讨了基本电路和基本割集的讨论。第五章涉及提出各种重要的算法,在数学和计算机科学中是有用的。第六章的数学前提包括线性代数的第一个基础。矩阵关联、邻接和电路在应用科学和工程中有着广泛的应用。第七章对于讨论割集、割顶点和图的连通性特别重要。第八章介绍了图的着色及其相关定理。第九章着重介绍了平面图的基本思想和有关定理。最后,第十章给出了网络流的基本定义和定理。

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

概率图模型的形式化提供了一个统一的框架,以捕获随机变量之间的复杂依赖关系,并建立大规模的多元统计模型。图模型已经成为许多统计、计算和数学领域的研究重点,包括生物信息学、通信理论、统计物理、组合优化、信号和图像处理、信息检索和统计机器学习。在特定情况下出现的许多问题——包括计算边际和概率分布模式的关键问题——最好在一般情况下进行研究。利用指数族表示,并利用指数族的累积函数和熵之间的共轭对偶性,我们发展了计算似然、边际概率和最可能配置问题的一般变分表示。我们描述了各种各样的算法——其中包括和积、聚类变分方法、期望传播、平均场方法、最大积和线性规划松弛,以及圆锥规划松弛——是如何以这些变分表示的精确或近似形式来理解的。变分方法提供了一个补充替代马尔可夫链蒙特卡罗作为一个一般来源的逼近方法推断在大规模统计模型。

https://www.nowpublishers.com/article/Details/MAL-001

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

我们写这本书是为了分享一个优雅的视角,它为一阶凸优化方法提供了强大的更高层次的洞察力。一阶凸优化方法的研究始于20世纪60年代和70年代,但当时该领域主要集中在二阶方法上,后者更能有效地解决较小的问题。21世纪初,随着计算能力的提高和大数据的可用性,一阶优化方法成为主流。在这个现代时代,作者进入了优化领域,并发现了(但没有发明)上述观点,我们希望通过这本书来分享它。

我们的目标是通过抽象单调算子提出一个统一的分析凸优化算法。

现代对一阶方法的广泛使用使这一观点比以往任何时候都更适用于优化研究人员和用户。

这本书的组织有点非传统: 章节的结构是围绕推导和分析优化方法的技术,而不是围绕优化方法本身。通过这个组织,我们的目的是提供结构的理论和实现知识经济,因为我们分析了许多优化方法与少量的数学概念。我们希望,这本书能简要介绍凸优化算法的理论。

我们也应该解释一下这本书不是什么。这本书不是关于单调算子理论的。我们使用单调算子作为分析优化算法的一种手段,但我们不关注单调算子本身的研究。这本书不是关于最佳凸优化方法或最强收敛分析的全面参考。我们使用一些技术来推导和分析优化方法,并且我们只给出适合这种方法的方法和结果。

https://large-scale-book.mathopt.com/

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

应用离散结构设计用于大学课程离散数学跨越两个学期。它最初的设计是为了给计算机科学专业的学生介绍在计算机科学中有用的数学主题。它也可以为数学专业的学生提供同样的目的,提供了对许多基本主题的第一次接触。

应用离散结构,是一个两个学期的本科文本在离散数学,侧重于结构性质的数学对象。这些包括矩阵、函数、图、树、格和代数结构。所讨论的代数结构是单体、群、环、场和向量空间。网站:http://discretemath.org应用离散结构已经被美国数学研究所批准作为其开放教科书计划的一部分。更多关于开放教科书的信息,请访问http://www.aimath.org/textbooks/。这个版本使用Mathbook XML (https://mathbook.pugetsound.edu/)创建。Al Doerr是马萨诸塞大学洛厄尔分校数学科学荣誉教授。他的兴趣包括抽象代数和离散数学。Ken levasserur是马萨诸塞大学洛厄尔分校数学科学教授。他的兴趣包括离散数学和抽象代数,以及它们在计算机代数系统中的实现。

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

本教程关注信息理论在统计学中的应用。被称为信息散度或Kullback-Leibler距离或相对熵的信息度量起着关键作用。涵盖的主题包括大偏差、假设检验、指数族的最大似然估计、列联表的分析以及具有“信息几何”背景的迭代算法。同时,还介绍了通用编码的理论,以及由通用编码理论驱动的最小描述长度原理的统计推理。

https://www.nowpublishers.com/article/Details/CIT-004

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

本书是信息论领域中一本简明易懂的教材。主要内容包括:熵、信源、信道容量、率失真、数据压缩与编码理论和复杂度理论等方面的介绍。

本书还对网络信息论和假设检验等进行了介绍,并且以赛马模型为出发点,将对证券市场研究纳入了信息论的框架,从新的视角给投资组合的研究带来了全新的投资理念和研究技巧。

本书适合作为电子工程、统计学以及电信方面的高年级本科生和研究生的信息论基础教程教材,也可供研究人员和专业人士参考。

本书是一本简明易懂的信息论教材。正如爱因斯坦所说:“凡事应该尽可能使其简单到不能再简单为止。''虽然我们没有深人考证过该引语的来源(据说最初是在幸运蛋卷中发现的),但我们自始至终都将这种观点贯穿到本书的写作中。信息论中的确有这样一些关键的思想和技巧,一旦掌握了它们、不仅使信息论的主题简明,而且在处理新问題时提供重要的直觉。本书来自使用了十多年的信息论讲义,原讲义是信息论课程的高年级本科生和一年级研究生两学期用的教材。本书打算作为通信理论.计算机科学和统计学专业学生学习信息论的教材。

信息论中有两个简明要点。第一,熵与互信息这样的特殊量是为了解答基本问题而产生的。例如,熵是随机变量的最小描述复杂度,互信息是度量在噪声背景下的通信速率。另外,我们在以后还会提到,互信息相当于已知边信息条件下财富双倍的增长。第二,回答信息理论问邀的答案具有自然的代数结构。例如,熵具有链式法则,因而,谪和互信息也是相关的。因此,数据压缩和通信中的问题得到广泛的解释。我们都有这样的感受,当研究某个问题时,往往历经大量的代数运算推理得到了结果,但此时没有真正了解问题的全莪,最终是通过反复观察结果,才对整个问题有完整、明确的认识。所以,对一个问题的全面理解,不是靠推理,而是靠对结果的观察。要更具体地说明这一点,物理学中的牛顿三大定律和薛定谔波动方程也许是最合适的例子。谁曾预见过薛定谔波动方程后来会有如此令人敬畏的哲学解释呢?

在本书中,我们常会在着眼于问题之前,先了解一下答案的性质。比如第2章中,我们定义熵、相对熵和互信息,研究它们之间的关系,再对这些关系作一点解释·由此揭示如何融会贯通地使用各式各样的方法解决实际问题。同理,我们顺便探讨热力学第二定律的含义。熵总是增加吗?答案既肯定也否定。这种结果会令专家感兴趣,但初学者或i午认为这是必然的而不会深人考虑。

在实际教学中.教师往往会加人一自己的见解。事实上,寻找无人知道的证明或者有所创新的结果是一件很愉快的事情。如果有人将新的思想和已经证明的内容在课堂上讲解给学生,那么不仅学生会积极反馈“对,对,对六而且会大大地提升教授该课程的乐崆我们正是这样从研究本教材的许多新想法中获得乐趣的。

本书加人的新素材实例包括信息论与博弈之间的关系,马尔可夫链背景下热力学第二定律的普遍性问题,信道容量定理的联合典型性证明,赫夫曼码的竞争最优性,以及关于最大熵谱密度估计的伯格(回定理的证明。科尔莫戈罗夫复杂度这一章也是本书的独到之处。面将费希尔信息,互信息、中心极限定理以及布伦一闵可夫斯基不等式与熵幂不等式联系在一起,也是我们引以为豪之处。令我们感到惊讶的是.关于行列式不等式的许多经典结论,当利用信息论不等式后会很容易得到证明。

自从香农的奠基性论文面世以来,尽管信息论已有了相当大的发展,但我们还是要努力强调它的连贯性。虽然香农创立信息论时受到通信理论中的问题启发,然而我们认为信息论是一门独立的学科,可应用于通信理论和统计学中。我们将信息论作为一个学科领域从通信理论、概率论和统计学的背景中独立出来因为明显不可能从这些学科中获得难以理解的信息概念。由于本书中绝大多数结论以定理和证明的形式给出,所以,我们期望通过对这些定理的巧妙证明能说明这些结论的完美性。一般来讲,我们在介绍问题之前先描述回题的解的性质,而这些很有的性质会使接下来的证明顺理成章。

使用不等式串、中间不加任何文字、最后直接加以解释,是我们在表述方式上的一项创新希望读者学习我们所给的证明过程达到一定数量时,在没有任何解释的情况下就能理解其中的大部分步,并自己给出所需的解释这些不等式串好比模拟到试题,读者可以通过它们确认自己是否已掌握证明那些重要定理的必备知识。这些证明过程的自然流程是如此引人注目,以至于导致我们轻视了写作技巧中的某条重要原则。由于没有多余的话,因而突出了思路的逻辑性与主題思想u我们希望当读者阅读完本书后,能够与我们共同分亨我们所推崇的,具有优美、简洁和自然风格的信息论。

本书广泛使用弱的典型序列的方法,此概念可以追溯到香农1948年的创造性工作,而它真正得到发展是在20世纪70年代初期。其中的主要思想就是所谓的渐近均分性(AEP),或许可以粗略地说成“几乎一切事情都是等可能的"

第2章阐述了熵、相对熵和互信息之同的基本代数关系。渐近均分性是第3章重中之重的内容,这也使我们将随机过程和数据压缩的熵率分别放在第4章和第5章中论述。第6章介绍博弈,研究了数据压缩的对偶性和财富的增长率。可作为对信息论进行理性思考基础的科尔莫戈罗夫复杂度,拥有着巨大的成果,放在第14章中论述。我们的目标是寻找一个通用的最矩描述,而不是平均意义下的次佳描述。的确存在这样的普遍性概念用来刻画一个对象的复杂度。该章也论述了神奇数0,揭示数学上的不少奥秘,是图灵机停止运转概率的推广。第7章论述信道容量定理。第8章叙述微分熵的必需知识,它们是将早期容量定理推广到连续噪声信道的基础。基本的高斯信道容量问题在第9章中论述。第il章阐述信息论和统计学之间的关系,20世纪年代初期库尔贝克首次对此进行了研究,此后相对被忽视。由于率失真理论比无噪声数据压缩理论需要更多的背景知识,因而将其放置在正文中比较靠后的第10章。

网络信息理论是个大的主题,安排在第巧章,主要研究的是噪声和干扰存在情形下的同时可达的信息流。有许多新的思想在网络信息理论中开始活跃起来,其主要新要素有干扰和反馈第16章讲述股票市场,这是第6章所讨论的博弈的推广,也再次表明了信息论和博弈之间的紧密联系。第17章讲述信息论中的不等式,我们借此一隅把散布于全书中的有趣不等式重新收拢在一个新的框架中,再加上一些关于随机抽取子集熵率的有趣新不等式。集合和的体积的布伦一闵可夫斯基不等式,独立随机变量之和的有效方差的熵幂不等式以及费希尔信息不等式之间的美妙关系也将在此章中得到详尽的阐述。

本书力求推理严密,因此对数学的要求相当高·要求读者至少学过一学期的概率论课程且有扎实的数学背景,大致为本科高年级或研究生一年级水平。尽管如此,我们还是努力避免使用测度论。因为了解它只对第16章中的遍历过程的AEP的证明过程起到简化作用。这符合我们的观点,那就是信息论基础与技巧不同,后者才需要将所有推广都写进去。

本书的主体是第2,3,4,5,7,8,9,10,11和巧章,它们自成体系,读懂了它们就可以对信息论有很好的理解。但在我们看来,第14章的科尔莫戈罗夫复杂度是深人理解信息论所需的必备知识。余下的几章,从博弈到不等式.目的是使主题更加连贯和完美。

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

这本书的书名听起来有点神秘。如果这本书以一种错误的方式呈现了这个主题,人们为什么要读它呢?书中哪些地方做得特别“不对”?

在回答这些问题之前,让我先描述一下本文的目标受众。这本书是“荣誉线性代数”课程的课堂讲稿。这应该是高等数学学生的第一门线性代数课程。它的目标是一个学生,虽然还不是非常熟悉抽象推理,但愿意学习更严格的数学,在“烹饪书风格”的微积分类型课程。除了作为线性代数的第一门课程,它也应该是第一门向学生介绍严格证明、形式定义——简而言之,现代理论(抽象)数学风格的课程。

目标读者解释了基本概念和具体实例的非常具体的混合,它们通常出现在介绍性的线性代数文本中,具有更抽象的定义和高级书籍的典型构造。

https://www.math.brown.edu/streil/papers/LADW/LADW_2017-09-04.pdf

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

基于最近关于非凸优化算法在训练深度神经网络和数据分析中的其他优化问题中的应用,我们对非凸优化算法全局性能保证的最新理论成果进行了综述。我们从经典的论证开始,证明一般的非凸问题不可能在合理的时间内得到有效的解决。然后,我们给出了一个可以通过尽可能多地利用问题的结构来寻找全局最优解的问题列表。处理非凸性的另一种方法是将寻找全局最小值的目标放宽到寻找一个平稳点或局部最小值。对于这种设置,我们首先给出确定性一阶方法收敛速度的已知结果,然后是最优随机和随机梯度格式的一般理论分析,以及随机一阶方法的概述。然后,我们讨论了相当一般的一类非凸问题,如α-弱拟凸函数的极小化和满足Polyak- Lojasiewicz条件的函数,这些函数仍然可以得到一阶方法的理论收敛保证。然后我们考虑非凸优化问题的高阶、零阶/无导数方法及其收敛速度。

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

这本书系统性讲述了统计学理论,包括概率理论、分布式理论与统计模型,基本统计理论、贝叶斯理论、无偏点估计、最大似然统计推断、统计假设与置信集、非参与鲁棒推断。

第一门课程以对统计中有用的测量论概率论的概念和结果的简要概述开始。随后讨论了统计决策理论和推理中的一些基本概念。探讨了估计的基本方法和原理,包括各种限制条件下的最小风险方法,如无偏性或等方差法,最大似然法,以及矩法和其他插件方法等函数法。然后详细地考虑了贝叶斯决策规则。详细介绍了最小方差无偏估计的方法。主题包括统计量的充分性和完全性、 Fisher信息、估计量的方差的界、渐近性质和统计决策理论,包括极大极小和贝叶斯决策规则。

第二门课程更详细地介绍了假设检验和置信集的原理。我们考虑了决策过程的表征,内曼-皮尔森引理和一致最有力的测试,置信集和推理过程的无偏性。其他主题包括等方差、健壮性和函数估计。

除了数理统计的经典结果外,还讨论了马尔可夫链蒙特卡洛理论、拟似然、经验似然、统计泛函、广义估计方程、折刀法和自举法。

http://mason.gmu.edu/~jgentle/books/MathStat.pdf

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

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

https://arxiv.org/abs/2009.09623

成为VIP会员查看完整内容
0
26
小贴士
相关主题
相关VIP内容
专知会员服务
94+阅读 · 8月2日
专知会员服务
51+阅读 · 5月4日
专知会员服务
40+阅读 · 3月27日
专知会员服务
121+阅读 · 3月22日
专知会员服务
65+阅读 · 2月28日
专知会员服务
53+阅读 · 2020年12月18日
专知会员服务
69+阅读 · 2020年12月6日
专知会员服务
26+阅读 · 2020年9月25日
相关论文
Khue-Dung Dang,Luca Maestrini
0+阅读 · 11月26日
Dang Quang A,Pham Huy Dien,Dang Quang Long
0+阅读 · 11月24日
Matías Vera,Leonardo Rey Vega,Pablo Piantanida
0+阅读 · 11月24日
Time and Memory Efficient Algorithm for Structural Graph Summaries over Evolving Graphs
Till Blume,David Richerby,Ansgar Scherp
0+阅读 · 11月24日
Yufeng Zhang,Jinghao Zhang,Zeyu Cui,Shu Wu,Liang Wang
7+阅读 · 1月28日
Joaquin Vanschoren
116+阅读 · 2018年10月8日
Georgios Damaskinos,El Mahdi El Mhamdi,Rachid Guerraoui,Rhicheek Patra,Mahsa Taziki
3+阅读 · 2018年7月9日
Joel A. Tropp,Alp Yurtsever,Madeleine Udell,Volkan Cevher
4+阅读 · 2018年1月2日
Top