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

Cornell University, Ithaca NY

Investigators

Abstract

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.