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

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

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.