Category Archives: Spring 2014

Michael Joswig; Long and Winding Central Paths

May 23, 2014, 3:30pm
LOW 112
Michael Joswig, Institute of Mathematics, TU Berlin.
Long and Winding Central Paths

Abstract: We disprove a continuous analog of the Hirsch conjecture proposed by Deza, Terlaky and Zinchenko, by constructing a family of linear programs with $3r+4$ inequalities in dimension $2r+2$ where the central path has a total curvature in $\Omega(2^r/r)$. Our method is to tropicalize the central path in linear programming. The tropical central path is the piecewise-linear limit of the central paths of parameterized families of classical linear programs viewed through logarithmic glasses. We show in particular that the tropical analogue of the analytic center is nothing but the tropical barycenter, that is, the maximum of a tropical polyhedron. It follows that unlike in the classical case, the tropical central path may lie on the boundary of the tropicalization of the feasible set, and may even coincide with a path of the tropical simplex method. Finally, our counter-example is obtained as a deformation of a family of tropical linear programs introduced by Bezem, Nieuwenhuis and Rodr\’iguez-Carbonell.

This is joint work with Xavier Allamigeon, Pascal Benchimol and St\’ephane Gaubert.

Noah Simon; Flexible Sparse Modeling

May 13, 2014, 4:00pm
EEB 303
Noah Simon, Department of Biostatistics, University of Washington.
Flexible Sparse Modeling

Abstract: Our ability to collect data has exploded over recent years. Across science and business, we now collect thousands to millions of measurements on each person. It is often of interest to use these measurements to predict some response (eg. likelihood of getting a disease, or probability of clicking a link). Methods for this problem must balance 3 objectives: they must be predictive, they must be computationally tractable, and, in many applications, they must be interpretable. Many machine learning methods are highly successful at the first two, but are black boxes. In contrast, the Lasso (l1 penalized regression) is interpretable and computationally tractable, but assumes linearity which limits its predictive accuracy.

In this talk we will discuss a class of sparse additive models induced by combining sparsity and structural penalties. These are more flexible than the standard linear penalized model, but maintain its interpretability and computational tractability. We will show when these penalties can and cannot be combined to induce the desired structure and sparsity. We will give an efficient algorithm for fitting a wide class of these models. And we will show that some of these models have desirable theoretical properties.

This is joint work with Ashley Petersen and Daniela Witten (UW).

Dan Spielman; Spectral Sparsification of Graphs

May 8th, 2014, 3:30pm
EEB 105
Dan Spielman, Department of Computer Science, Yale.
Spectral Sparsification of Graphs
Math Across Campus Seminar

Abstract: We introduce a notion of what it means for one graph to be a good spectral approximation of another, and prove that every graph can be well-approximated by a graph with few edges.

We ask how well a given graph can be approximated by a sparse graph. Expander graphs can be viewed as sparse approximations of complete graphs, with Ramanujan expanders providing the best possible approximations. We prove that every graph can be approximated by a sparse graph almost as well as the complete graphs are approximated by the Ramanujan expanders: our approximations employ at most twice as many edges to achieve the same approximation factor.

We also present an efficient randomized algorithm for constructing sparse approximations that only uses a logarithmic factor more edges than optimal.

Our algorithms follow from the solution of a problem in linear algebra. Given any expression of a rank-n symmetric matrix A as a sum of rank-1 symmetric matrices, we show that A can be well approximated by a weighted sum of only O(n) of those rank-1 matrices.

This is joint work with Joshua Batson, Nikhil Srivastava and Shang-Hua Teng.

Biosketch: Daniel Alan Spielman received his B.A. in Mathematics and Computer Science from Yale in 1992, and his Ph.D in Applied Mathematics from M.I.T. in 1995. He spent a year as a NSF Mathematical Sciences Postdoc in the Computer Science Department at U.C. Berkeley, and then taught in the Applied Mathematics Department at M.I.T. until 2005. Since 2006, he has been a Professor at Yale University. He is presently the Henry Ford II Professor of Computer Science, Mathematics, and Applied Mathematics.

He has received many awards, including the 1995 ACM Doctoral Dissertation Award, the 2002 IEEE Information Theory Paper Award, the 2008 Godel Prize, the 2009 Fulkerson Prize, the 2010 Nevanlinna Prize, an inaugural Simons Investigator Award, and a MacArthur Fellowship. He is a Fellow of the Association for Computing Machinery and a member of the Connecticut Academy of Science and Engineering. His main research interests include the design and analysis of algorithms, graph theory, machine learning, error-correcting codes and combinatorial scientific computing.

Rina Foygel; Demixing signals: the geometry of corrupted sensing

April 29, 2014, 4:00pm
EEB 303
Rina Foygel, Department of Statistics, University of Chicago.
Demixing signals: the geometry of corrupted sensing

Abstract: In the compressed sensing problem, a high-dimensional signal with underlying structure can often be recovered with a small number of linear measurements. When multiple structured signals are superimposed, similar techniques can be used to try to separate the signals at a low sample size. We extend theoretical work on compressed sensing to the corrupted sensing problem, where our measurements of a structured signal are corrupted in a structured way (such as a sparse set of outliers in the measurements). Convex penalties placed on the signal and the corruption reflect their respective latent structure (e.g. sparsity, block-wise sparsity, low rank, etc). The resulting penalized optimization problem involves a tuning parameter controlling the tradeoff between the two penalties. We find that this tuning parameter can be chosen by comparing geometric properties of the two types of structure, which requires no cross-validation and yields nearly optimal results in theory and in simulations.

Joint work with Lester Mackey.

Sanjeev Arora; Overcoming Intractability in Unsupervised Learning

April 15th, 2014, 4:00pm
CSE 691 (The Gates Commons)
Sanjeev Arora, Department of Computer Science, Princeton.
Overcoming Intractability in Unsupervised Learning

Abstract: Unsupervised learning – i.e., learning with unlabeled data – is increasingly important given today’s data deluge. Most natural problems in this domain – e.g. for models such as mixture models, HMMs, graphical models, topic models and sparse coding/dictionary learning, deep learning – are NP-hard. Therefore researchers in practice use either heuristics or convex relaxations with no concrete approximation bounds. Several nonconvex heuristics work well in practice, which is also a mystery.

The talk will describe a sequence of recent results whereby rigorous approaches leading to polynomial running time are possible for several problems in unsupervised learning. The proof of polynomial running time usually relies upon nondegeneracy assumptions on the data and the model parameters, and often also on stochastic properties of the data (average-case analysis). Some of these new algorithms are very efficient and practical – e.g. for topic modeling.

Biosketch: Sanjeev Arora is the Charles C. Fitzmorris Professor of Computer Science at Princeton University. His research spans Theoretical Computer Science, including foundational work in Algorithms and Computational Complexity. His recent work focuses on provable bounds for Machine Learning. He has received numerous awards and distinction. Most recently, these include the 2012 Fulkerson Prize, the 2011 ACM-Infosys Foundation Award in Computing Sciences, the 2010 Goedel Prize, and the Best Paper Award at the 2010 Annual Symposium on Foundations of Computing. He is an ACM Fellow and recipient of the 1995 ACM Doctoral Dissertation Award.

Hongbo Dong; A New Approach to Relax Nonconvex Quadratics

April 22, 2014, 4:00pm
EEB 303
Hongbo Dong, Depart­ment of Mathematics, Washington State University. 
A New Approach to Relax Nonconvex Quadratics

Abstract: In many areas of engineering and computer sciences, optimization models with nonconvex quadratic functions naturally arise, such as various models related to process networks in Chemical Engineering, computational geometry, as well as cutting and partitioning of graphs. Tractable convex relaxations are often crucial when the global optimal solution or a good approximate solution is of interests. However, most current relaxation methods based on lifting/linearization are bottlenecked by the huge amount of additional variables introduced, especially when there are dense quadratics with a moderate number of variables (n >= 70).

In this talk, we will first describe a few scenarios where nonconvex quadratics naturally arise. Then we will briefly overview some state-of-the-art relaxation methods based on polyhedral as well as semidefinite techniques. Finally I will introduce a novel cutting surface approach to derive convex quadratic relaxations. Our approach uses diagonal perturbations of the quadratics as cutting surfaces that are iteratively added into relaxations. We devise a specialized heuristic algorithm to search for good cutting surfaces, where each iteration needs only O(n^2) flops. Computational results show promises of our new approach, especially when large dense quadratics are present. We show that on a model with one nonconvex quadratic function, only a small number of cutting surfaces are needed to capture the most strength of a semidefinite relaxation, while our approach is much more scalable. We also compare with another approach that generates convex cutting surfaces proposed by (Saxena, Bonami and Lee, 2011). We obtain slightly weaker bounds but in 1-2 orders of magnitude shorter time. Finally, we also discuss how to incorporate our methods into a general branch-and-bound solver for mixed-integer quadratically constrained programs (MIQCP).

This work is based on our recent submission available here.