First-Order Algorithms for Convex Optimization

3 Oct
Computer Science Colloquium Series
Garud Iyengar, Columbia University
Thursday, October 3, 2013 - 4:00pm
Maxwell Dworkin G125

There is growing interest in developing fast first-order algorithms for solving convex optimization problems.  There are many reasons for this:  first-order algorithms are scalable to very large problem sizes (Big Data!), can be solved in a distributed manner, even work with stochastic estimates of the gradients!  These algorithms have been discovered in many different contexts:  approximation algorithms for packing-covering linear and semidefinite programs, the multiplicative weight algorithm, AdaBoost, Forward stage-wise regression, etc.

Recently, accelerated versions of first-order algorithms have been proposed for convex objectives that have additional "structure."  These accelerated algorithms are significantly faster both in theory and in practice.  However, to be efficient these algorithms require that the feasible set be "simple" in the sense that an appropriately defined convex optimization problem can be solved in closed form.

We will first discuss how "structure" can be used to develop faster algorithms for packing-covering linear and semidefinite programs, and some related large scale portfolio selection problems.  Next, we will show how to extend accelerated first-order algorithms to  feasible sets that are not "simple."  We provide convergence rate guarantees for these algorithms.  We also show how these algorithms can be adapted to solve important problems in signal processing, shape-restricted regression and distributed maximum-likelihood estimation.

Speaker Bio: 

Garud Iyengar is a Professor in the Industrial Engineering and Operations Research Department in the School of Engineering and Applied Science at Columbia University.  He received his B. Tech. in Electrical Engineering from IIT Kanpur, and an MS and PhD in Electrical Engineering from Stanford University.  His research interests are broadly in information theory, control and optimization.

His published works span a diverse range of fields, including information theory, applied mathematics, computer science, operations research, economics and financing engineering.  His current projects focus on the areas of large scale portfolio selection, systemic risk management, quantitative marketing, smart grids, public health and systems biology.

L. Mahadevan and David Parkes
Gioia Sweetland