AF:Small:Mathematical Programming for Average-Case Problems

优化可能是最普遍的计算任务，它包括在满足一组约束的情况下找到最大化或最小化某个函数的解决方案。如果问题的解的空间是有限的和离散的，那么这样的问题被称为“组合优化”问题。不幸的是，大多数组合优化问题在计算上难以精确解决，也就是说，人们普遍认为找到最优解将是非常耗时的。为了应对这种计算上的难处，试图找到优化问题的近似解是很自然的。一个经典的寻找近似解的方法已经被研究了四十多年，那就是使用“凸松弛”。凸松弛的思想是将底层优化任务转换为凸优化任务，因为有效的算法以凸优化而闻名。直观地说，凸优化问题的底层解空间是连续的，并且对于每一对解，它们的平均值也是一个解。将任意组合优化问题转换为凸优化任务本质上是有损耗的，因为在此过程中我们只能恢复原始问题的近似解。接下来的问题是，这个近似有多好？哪一个凸松弛产生最好的近似？在过去的二十年里，这些问题已经被广泛地研究在算法中广泛使用的两类基本的凸松弛——即线性和半定义规划。然而，凸松弛的研究主要集中在“最坏情况”上，其目标是在潜在问题的每个实例上证明凸松弛所获得的近似的保证。尽管最坏情况分析是有用的，因为它对潜在问题的每个实例都产生了保证的近似值，但它有时过于悲观。在许多现实环境中，优化问题的底层输入是从自然概率分布中选择的。例如，可以在社交网络上设置优化问题，其中连接不是完全任意的（最坏情况），而是具有可以使用概率分布建模的独特结构。另一个例子是，在存在噪声的情况下恢复信号，噪声通常不是完全任意的（最坏情况），而是有些随机的（平均情况）。本文旨在研究凸松弛技术即线性和半定规划在平均情况下的性能。该提案将开发使用凸松弛的新算法，并描述在平均情况下通过凸松弛获得的近似。一般情况下的算法在实际应用中可能转化为更好的近似值。此外，所开发的技术和提出的问题将推动许多不同领域的最新技术，包括近似算法、计算复杂性理论、概率和随机矩阵理论以及凸优化。除了举办会议演讲和研讨会外，PI还将通过设计关于凸松弛的研究生课程、指导本科生的研究项目、组织工作坊等方式，向更广泛的受众传播这些深入的见解。技术概述：关于组合优化的数学规划的大部分工作都致力于最坏情况输入的算法。换句话说，这些算法对每个输入都有近似或运行时保证。这个研究项目关注的是理解基于数学规划的算法在平均情况下的能力，在这种情况下，算法的输入被假设从一个自然的底层分布中抽样。一个新的和不断增长的工作体研究了各种各样的问题，如随机约束满足问题，统计块模型，种植团，稀疏PCA，张量补全，张量PCA，压缩感知和矩阵补全，其中底层实例是从概率分布中提取的。本项目旨在发展一种描述数学规划能力的理论，特别是在这种情况下的平方和（SoS） SDP层次结构。我们的方法有可能产生非常简单的必要条件和充分条件，这些条件可以精确地预测LP和SDP层次结构对广泛类别的分布问题的有效性。它从我们分析分布设置中的SoS sdp的方法中一个看似老套但重要的概念转变开始，即将分布问题视为从两个不同分布中区分样本的任务。从这个角度来看这个问题，揭示了这个提议的核心论点，即对于广泛的平均情况问题，LP或SDP层次结构的力量是由简单的区分函数族来表征的。例如，我们认为sosdp弛豫对可分辨性的能力是由所谓的低度谱区分器表征的。这些函数计算一个矩阵它的元素是输入的低次多项式然后输出一个特征值的简单函数，比如说最大的一个。这一特性开辟了几个令人兴奋的研究途径，既可以证明对的下界，也可以为分布问题设计算法。通过将这些问题转化为相对于简单区分族的不可区分性领域，它使它们适用于随机矩阵理论和伪随机的工具。一方面，这个研究项目可能会带动和伴随随机矩阵理论的相应进展。另一方面，它有望揭示高维统计和无监督学习（如稀疏PCA、张量PCA和统计块模型）中几个基本任务的计算复杂性。对于像这样的一般情况问题，在缺乏传统的复杂性理论概念（如np完备性）的情况下，描述LP/SDP松弛的能力可能是人们希望产生的最令人信服的证明其复杂性的证据。

Optimization, perhaps the most ubiquitous computational task of all, consists of finding a solution that either maximizes or minimizes a certain function while satisfying a set of constraints. If the space of solutions to the problem is finite and discrete, then such problems are referred to as "combinatorial optimization" problems. Unfortunately, most combinatorial optimization problems are computationally intractable to solve exactly, i.e., it is widely believed that finding the optimal solution would be prohibitively time-consuming. To cope with this computational intractability, it is natural to try to find an approximate solution to the optimization problem. A classic approach to find approximate solutions that has been studied for more than four decades now, is the use of ``convex relaxations". The idea of convex relaxation is to convert the underlying optimization task into a convex optimization task, since efficient algorithms are known for convex optimization. Intuitively, a convex optimization problem is one whose underlying solution space is continuous, and for every pair of solutions, their average is also a solution. Converting an arbitrary combinatorial optimization problem in to a convex optimization task is inherently lossy, in that we only recover an approximate solution to the original problem in the process. The question then is, how good is the approximation? and which convex relaxation yield the best approximation?Over the last two decades, these questions have been extensively studied for two fundamental classes of convex relaxations widely used in algorithms -- namely linear and semi-defintie programming. However, the study of convex relaxations have been mostly centered around the ``worst-case" where the goal is to demonstrate guarantees on the approximation obtained by the convex relaxation, on every instance of the underlying problem. Although worst case analysis is useful in that it yields a guaranteed approximation on every instance of the underlying problem, it is too pessimistic at times. In many real-life settings, the underlying input to the optimization problem is chosen from a natural probability distribution. For example, the optimization problem could be set on a social network, wherein the connections are not completely arbitrary (worst case), but have distinct structure that can be modeled using a probability distribution. Another example, is that of recovering a signal in presence of noise, the noise is typically not completely arbitrary (worst case), but somewhat random (average case).This proposal aims to study the performance of convex relaxation techniques namely linear and semidefinite programming in the average-case setting. The proposal will develop new algorithms using convex relaxations and characterize the approximation obtained via convex relaxations in the average case setting. Algorithms for the average case might translate to better approximations in practical applications. Furthermore, the techniques developed and the questions raised will advance the state-of the-art in many different areas including, approximation algorithms, computational complexity theory, probability and random matrix theory and convex optimization. The PI will disseminate the deeper insights so gained, to a broader of audience through designing a graduate course on convex relaxations, supervising research projects for undergraduates, and organizing a workshop, apart from delivering conference talks and seminars. Technical Overview:A majority of the work on mathematical programming for combinatorial optimization is devoted to algorithms on worst-case inputs. In other words, these algorithms have approximation or run-time guarantees on every input. This research project is concerned with understanding the power of mathematical-programming based algorithms in the average case, where the inputs to the algorithm are assumed to sampled from a natural underlying distribution. A new and growing body of work studies a diverse set of problems like random constraint satisfaction problems, statistical block models, planted clique, sparse PCA , tensor completion, tensor PCA, compressed sensing and matrix completion, where the underlying instance is drawn from a probability distribution.This project intends to develop a theory characterizing the power of mathematical programming, especially the sum-of-squares (SoS) SDP hierarchy in this context. Our approach has the potential to yield remarkably simple necessary and su cient conditions which precisely predict the efficacy of LP and SDP hierarchies for broad classes of distributional problems. It begins with a seemingly trite, but important conceptual shift in our approach for analyzing SoS SDPs in distributional settings, namely cast the distributional problems as the task of distinguishing samples from two diferent distributions. Viewing the problem from this standpoint, exposes the central thesis underlying this proposal that for broad classes of average-case problems, the power of LP or SDP hierarchies are characterized by simple families of distinguishing functions. For example, we argue that the power of SoS SDP relaxations for distinguishability are characterized by so-called low-degree spectral distinguishers. These are functions that compute a matrix whose entries are low-degree polynomials of the input and then output a simple function of the eigenvalues, say the largest one. This characterization opens up several exciting research avenues, both to prove lower bounds against and to devise algorithms for distributional problems. By translating these problems in to the realm of indistinguishability with respect to simple families of distinguishers, it makes them amenable to tools from random matrix theory and pseudorandomness.On the one hand, this research program is likely spur and be accompanied by, corresponding advances in random matrix theory. On the other, it holds the promise to shed light on the computational complexity of several basic tasks in high-dimensional statistics and unsupervised learning such as sparse PCA, tensor PCA and statistical block models. For average-case problems like these, in the absence of conventional complexity theoretic notions such as NP-completeness, characterizing the power of LP/SDP relaxations is possibly the most compelling evidence of their complexity that one can hope to produce.