Design of Gradient-Based Methods for Solving General and Huge Convex Optimization Problems

自20世纪40年代末以来，优化建模和求解模型的算法一直是美国经济效率提高的关键。随着计算机设计的进步，以及最近互联网应用程序产生的大量复杂数据集的可用性，优化的相关性增加了许多倍。优化已经成为机器学习的核心部分。然而，即使是最有效的优化算法也无法成功地处理由具有很少特殊结构的庞大数据集填充的复杂模型，主要问题是（即使是大型）计算机上可用的核心内存有限。虽然摩尔定律准确地预测了计算能力将呈指数级增长，但令人惊讶的是，数据集的规模增长得更快。该项目的一个核心焦点是设计能够解决由庞大数据集填充的复杂优化模型的算法，通过将模型分解为一系列计算问题，每个问题仅依赖于数据的一部分，而不是太多的核心内存。研究生参与研究。一般的方法是利用凸优化的最基本的算法，即子梯度方法，可以追溯到20世纪60年代。同时，该方法利用并推进了研究者近年来提出的框架，将一般凸优化问题转化为等效凸优化问题，其唯一约束是线性方程，目标函数是Lipschitz连续的（从而允许直接应用子梯度方法）。目前正在对线性规划进行初步探索，其雄心勃勃的目标是解决单纯形法无法解决的问题（在基逆矩阵大于核心存储器允许的情况下）。研究还将重点放在涉及目标函数的问题上，目标函数本身是许多函数的总和，这是机器学习中的一种常见设置。这里的目标是设计能够以原则（和有效）的方式选择求和函数的算法，而不像增量（子）梯度方法，它随机地均匀地选择求和。此外，正在尝试扩展研究者的框架，以便提供一种方法，例如，将可能具有有界域的连续可微目标函数转换为具有lipschitz -连续梯度的整个函数，从而使加速方法易于应用。该项目的一个特别重要的方面是，当所解决的优化问题具有某种特殊的几何结构（例如“锐度”，其中目标函数随着到最优性的距离线性增长）时，设计用于加速一阶方法的实用方案。我们的目标是设计方案，不需要知道控制几何结构的参数，但无论何时结构存在（无论用户是否知道结构存在），都保证实现最佳加速。研究生参与研究。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Optimization modeling, and algorithms for solving the models, have been key to gains in efficiency in the US economy since the late 1940's. The relevance of optimization has increased manyfold alongside advances in computer design, and recently alongside the availability of vast and complex datasets arising from internet applications. Optimization has become a central part of machine learning. However, even the most efficient optimization algorithms are unable to succeed for complicated models populated by huge datasets possessing little special structure, the main problem being the limited core memory available on (even large) computers. While Moore's Law accurately predicted exponentially-increasing computing power, the surprise has been that the sizes of datasets are increasing much faster. A central focus of the project is the design of algorithms capable of solving a complicated optimization model populated with a huge dataset, by breaking apart the model into a sequence of computational problems, each relying on only a portion of the data, not too much for core memory. Graduate students participate in the research.The general approach makes use of the most elemental of algorithms for convex optimization, namely, subgradient methods, dating to the 1960's. In tandem, the approach makes use of -- and advances -- a framework promoted by the investigator in recent years, whereby a general convex optimization problem is transformed into an equivalent convex optimization problem whose only constraints are linear equations and for which the objective function is Lipschitz continuous (thereby allowing direct application of subgradient methods). Exploration is being done initially for linear programming, an ambitious goal being to solve problems even beyond the reach of the simplex method (in cases where the basis-inverse matrix is larger than core memory permits). Focus also is being given to problems involving an objective function that is itself the sum of many functions, a common setting in machine learning. Here the goal is to devise algorithms that are able to choose the summand functions in a principled (and efficient) manner, unlike incremental (sub)gradient methods, which choose a summand uniformly at random. Additionally, attempts are being made to extend the investigator's framework so as to provide, for example, a way to transform a continuously-differentiable objective function, possibly with bounded domain, into an entire function possessing Lipschitz-continuous gradient, thereby allowing accelerated methods to be applied easily. A particularly important aspect of the project is the design of practical schemes for speeding up first order methods when the optimization problem being solved has some particular kind of geometrical structure (such as "sharpness," where the objective function grows linearly with the distance to optimality). The goal is to design schemes that require no knowledge of parameters governing the geometrical structure, and yet that are guaranteed to achieve optimal speedup whenever the structure is present (regardless of whether the user knows the structure is present). Graduate students participate in the research.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.