Majorizing Measures for the Optimizer
Majorizing Measures for the Optimizer
复制标题
优化器的主要措施
DOI：
10.4230/lipics.itcs.2021.73
复制
发表时间：
2020
影响因子：
5.6
通讯作者：
Makrand Sinha
中科院分区：
文献类型：
--
作者：
Sander Borst;D. Dadush;Neil Olver;Makrand Sinha
由Fernique、Talagrand和许多其他人广泛发展的优化测度理论，为控制随机过程的行为提供了最一般的框架之一。特别是，它可以被应用到推导出的期望上确界和样本路径的连续度的定量界为许多过程。该理论的最高成就之一是Talagrand的严格的替代表征的上确界的高斯过程中的majorizing措施。这个定理的证明是困难的，因此相当大的努力投入到开发更短，更容易理解的证明任务。造成这一困难的一个主要原因被认为是优化措施理论本身，它以不透明和神秘而闻名。因此，最近对该理论的处理（包括Talagrand本人）避免了使用优化措施，而倾向于使用纯组合方法（通用链），其中基于分区序列的对象提供了期望上确界的大致匹配的上界和下界。在本文中，我们回到优化措施作为一个主要的研究对象，并给出了一个观点，我们认为是自然的，从优化的角度来澄清。作为我们的主要贡献，我们基于两个部分给出了优化测度定理的算法证明：（1）我们做出了简单的（但显然是新的）观察，即找到最佳优化测度可以转换为凸规划。这也允许使用来自凸优化的现成方法来有效地计算测量。(2)我们获得基于树的上限和下限证书四舍五入，在一系列的步骤，原始和对偶解决方案，这个凸计划。[...]
The theory of majorizing measures, extensively developed by Fernique, Talagrand and many others, provides one of the most general frameworks for controlling the behavior of stochastic processes. In particular, it can be applied to derive quantitative bounds on the expected suprema and the degree of continuity of sample paths for many processes. One of the crowning achievements of the theory is Talagrand's tight alternative characterization of the suprema of Gaussian processes in terms of majorizing measures. The proof of this theorem was difficult, and thus considerable effort was put into the task of developing both shorter and easier to understand proofs. A major reason for this difficulty was considered to be theory of majorizing measures itself, which had the reputation of being opaque and mysterious. As a consequence, most recent treatments of the theory (including by Talagrand himself) have eschewed the use of majorizing measures in favor of a purely combinatorial approach (the generic chaining) where objects based on sequences of partitions provide roughly matching upper and lower bounds on the desired expected supremum. In this paper, we return to majorizing measures as a primary object of study, and give a viewpoint that we think is natural and clarifying from an optimization perspective. As our main contribution, we give an algorithmic proof of the majorizing measures theorem based on two parts: (1) We make the simple (but apparently new) observation that finding the best majorizing measure can be cast as a convex program. This also allows for efficiently computing the measure using off-the-shelf methods from convex optimization. (2) We obtain tree-based upper and lower bound certificates by rounding, in a series of steps, the primal and dual solutions to this convex program. [...]