Winter 2019

Organizer for Winter 2019: Robert Krone (Email: rckrone@ucdavis.edu)

Jan 8: Gennadiy Averkov (OvGU Magdeburg). Title: Improving cuts by means of lifting.

Abstract: I will report on results obtained in a joint work with Amitabh Basu. We study the uniqueness of minimal liftings of cut-generating functions obtained from maximal lattice-free polyhedra. We prove a basic invariance property of unique minimal liftings for general maximal lattice-free polyhedra. This generalizes a previous result by Basu, Cornuejols and Koeppe for simplicial maximal lattice-free polytopes, thus completely settling this fundamental question about lifting for maximal lattice-free polyhedra. We further give a very general iterative construction to get maximal lattice-free polyhedra with the unique-lifting property in arbitrary dimensions. This single construction not only obtains all previously known polyhedra with the unique-lifting property, but goes further and vastly expands the known list of such polyhedra. Finally, we extend characterizations about lifting with respect to maximal lattice-free simplices to more general polytopes. These nontrivial generalizations rely on a number of results from discrete geometry, including the Venkov-Alexandrov-McMullen theorem on translative tilings and characterizations of zonotopes in terms of central symmetry of their faces.

Jan 22: Krishnakumar Balasubramanian (UC Davis). Title: Applications of Stein's Identity to Non-Convex Optimization and Sampling.

Abstract: Optimization and sampling are arguably the two computational backbones of Frequentist and Bayesian statistics respectively. In this talk the use of Stein's identity for performing stochastic Zeroth-Order (ZO) non-convex optimization and sampling will be discussed. Specifically, we consider the case when the function (or density) under consideration is not available to us analytically, rather we are able to only obtain noisy evaluations. Using Stein's identity, techniques for estimating gradient and Hessian of the function (or the potential functions of a density) will be introduced. Based on this, the following algorithms and the corresponding theoretical results will be discussed: (i) ZO conditional gradient method, (ii) ZO stochastic gradient method in high-dimensions (iii) ZO Newton's method for escaping saddle points (iv) ZO Euler and Ozaki discretized Monte Carlo sampling.

Jan 29: Ilan Adler (UC Berkeley). Title: A simple reduction of wide range of optimization, engineering and economics problems to Bimatrix Games.

Abstract: It is well known that many optimization problems, ranging from linear programming to hard combinatorial problems, as well as many engineering and economics problems, can be formulated as linear complementarity problems (LCP).One particular LCP, finding a Nash equilibrium of a bimatrix game (2-NASH), motivated the development of the elegant Simplex-like Lemke’s algorithm which is guaranteed to terminate in a finite number of iterations but not necessarily with a solution (or a certificate that no solution exists). Over the years, many subclasses of LCP, covering a variety of optimization problems, were proven to be solvable by Lemke’s algorithm.

It turned out that, in general, Lemke solvable LCPs belong to the complexity class PPAD (Polynomial-time Parity Argument Directed) and that, quite surprisingly, 2 NASH is PPAD-complete. Thus, Lemke solvable LCPs can be formulated as 2 NASH. While of great theoretical value, the ingeniously constructed reduction (which is designed for all PPAD problem) is very complicated, difficult to implement, and not readily available for potential insights. In this talk, I’ll present and discuss a simple reduction of Lemke-solvable LCPs to bimatrix games that is easy to implement and have the potential to gain additional insights to problems (including several models of market equilibrium) for which the reduction is applicable.

Feb 5: Jelena Diakonikolas (UC Berkeley). Title: Invariance in First-Order Convex Optimization.

Abstract: First-order methods with optimal worst-case iteration complexities for various classes of convex optimization problems have been known for decades. However, their standard analysis bears little intuition, which makes their generalization to new problems arising in modern data analysis applications challenging. In this talk, I will present a novel general and unifying framework for the analysis of first-order methods. The framework relies on the construction of a primal-dual gap and can be likened to Lagrangian mechanics: continuous-time methods and their convergence analysis follow directly from enforcing a certain invariance. The discrete-time methods can then be obtained by using different methods of discretization. This stands in contrast with standard approaches, which can be thought of as being analogous to Newtonian mechanics, where an action (i.e., a predetermined optimization method) is applied to a system and then its behavior (convergence) analyzed. To illustrate the power and generality of our framework, I will show that it recovers a wide range of known first-order methods in a unifying manner, and that it also yields novel methods that outperform existing ones on problems arising in machine learning applications. Based on joint work with Lorenzo Orecchia.

Feb 12: Sean Kafer (U Waterloo). Title: The circuits of combinatorial polytopes: diameter bounds and hardness of computation.

Abstract: The combinatorial diameter of a polytope P is the maximum value of a shortest path between two vertices of P, where the path moves along edges of P. Its study is motivated largely by its implications on the running time of the Simplex algorithm to solve linear programs (LP’s). In contrast, the circuit diameter of P is defined as the maximum value of a shortest path between two vertices of P, where the path uses potential edge directions of P i.e., all edge directions that can be obtained by translating the facets of P. Such directions are called the circuits of P.

In this talk, I will present a characterization of the circuit diameter of some polytopes corresponding to classical combinatorial optimization problems, such as the Matching polytope and Traveling Salesman polytope. I will further give a complete characterization of the circuits of the Fractional Matching polytope, and use that to derive some hardness of computation results. Specifically, De Loera, Hemmecke, and Lee recently studied the potential use of circuits to develop Simplex-like algorithms to solve LP’s. They propose an augmentation procedure which iteratively finds better feasible solutions by moving along circuits, and they propose three different oracles for choosing a circuit at each step. We prove that two of these oracles are NP-hard to compute. The first part of the talk is based on a joint work with K. Pashkovich and L. Sanità, while the second part is based on a joint work with J. De Loera and L. Sanità.

Feb 19: Dmitriy Drusvyatskiy (U Washington). Title: Stochastic methods for nonsmooth nonconvex optimization.

Abstract: Stochastic iterative methods lie at the core of large-scale optimization and its modern applications to data science. Though such algorithms are routinely and successfully used in practice on highly irregular problems, few performance guarantees are available outside of smooth or convex settings. In this talk, I will describe a framework for designing and analyzing stochastic methods on a large class of nonsmooth and nonconvex problems, with provable efficiency guarantees. The problem class subsumes such important tasks as phase retrieval, robust PCA, and minimization of risk measures, while the methods include stochastic subgradient, Gauss-Newton, and proximal point iterations. The main thread of the proposed framework is appealingly intuitive. I will show that a wide variety of stochastic methods can be interpreted as inexact gradient descent on an implicit smoothing of the problem. Optimal learning rates and novel sample-complexity bounds follow quickly from this viewpoint.

Mar 5: Thomas Rothvoss (U Washington). Title: Algorithms for Discrepancy Minimization.

Abstract: A classical theorem of Spencer shows that any set system with n sets and n elements admits a coloring of discrepancy O(n^1/2). Recent work of Bansal, Lovett and Meka shows that such colorings can be found in polynomial time. We continue this exciting line of research and present two new algorithms: (1) We present a deterministic polynomial time algorithm for finding colorings in the Lovett-Meka setting. The algorithm is based on the Multiplicative Weight Update Method. (2) It was known non-constructively that any symmetric convex set K with measure at least exp(-n/500) must contain a partial coloring, which is a point in [-1,1]^n with Omega(n) coordinates in {-1,+1}. We prove that a surprisingly simple algorithm can find such partial colorings.

This is joint work with Avi Levy and Harish Ramadas.

Mar 12: Dorit Hochbaum (UC Berkeley). Title: Machine Learning and Data Mining with Combinatorial Optimization.

Abstract: The dominant algorithms for machine learning tasks fall most often in the realm of AI or continuous optimization of intractable problems. We present combinatorial algorithms for machine learning, data mining, and image segmentation that, unlike the majority of existing machine learning methods, utilize pairwise similarities. These algorithms are efficient and reduce the classification problem to a network flow problem on a graph. One of these algorithms addresses the problem of finding a cluster that is as dissimilar as possible from the complement, while having as much similarity as possible within the cluster. These two objectives are combined either as a ratio or with linear weights. This problem is polynomial time solvable and is a variant of normalized cut, which is intractable. The problem and the polynomial-time algorithm solving it are called HNC. It is demonstrated, via an extensive empirical study, that incorporating the use of pairwise similarities improves accuracy of classification and clustering. However, the use of similarities implies a quadratic rate of growth in the size of the data. A methodology called "sparse computation" has been devised to address and eliminate this quadratic growth. It is demonstrated that the technique of "sparse computation" enables the scalability of similarity-based algorithms to very large-scale data sets

while maintaining high levels of accuracy. We demonstrate several applications of variants of HNC for data mining, medical imaging, and image segmentation tasks, including a recent one in which HNC is among the top performing methods in a benchmark for cell identification in calcium imaging movies for neuroscience brain research.

Mar 19: Suvrajeet Sen (USC). Title: Stochastic Decomposition: A Revival.

Abstract: Stochastic Decomposition (SD) is a Stochastic Linear Programming algorithm which is experiencing a resurgence after more than 30 years of its invention. This algorithm, which was born around 1987, celebrated its thirtieth anniversary by announcing new results related to variance reduction, and new optimality tests. Subsequently, other new results allowing random costs, as well as convergence rates have been discovered recently. This seminar will discuss both mathematical and computational aspects, and we will also discuss real-scale problems arising in renewable integration for the electricity grid.