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

自20世纪40年代末的S以来，优化建模和求解模型的算法一直是美国经济效率提高的关键。随着计算机设计的进步，以及最近互联网应用产生的海量和复杂数据集的可获得性，优化的相关性增加了许多倍。优化已成为机器学习的核心部分。然而，即使是最有效的优化算法也无法成功地处理由几乎没有特殊结构的海量数据集填充的复杂模型，主要问题是计算机(即使是大型计算机)上可用的核心内存有限。虽然摩尔定律准确地预测了计算能力呈指数级增长，但令人惊讶的是，数据集的大小增长得更快。该项目的一个核心重点是设计算法，通过将模型分解为一系列计算问题，从而能够解决充满巨大数据集的复杂优化模型，每个问题只依赖于一部分数据，而不会占用太多的核心内存。研究生参与了这项研究。一般方法使用了最基本的凸优化算法，即次梯度方法，可以追溯到1960年的S。同时，该方法利用并改进了研究者近年来提出的一个框架，将一个一般的凸优化问题转化为一个等价的凸优化问题，该问题的唯一约束是线性方程，其目标函数是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.