MADDD: Mathematics of Data and Decisions at Davis
Aims: The MADDD seminar aims to gather researchers on all kinds of cutting-edge algorithmic and mathematical techniques used when analyzing and visualizing data, and then making optimal decisions. Thus talks and discussions on the seminar, most often directly motivated by applications, will include (but will not be limited to): Optimization, Applied Computational Harmonic Analysis, Topological Data Analysis, Game Theory, Information theory, Theory of Machine Learning Algorithms, Computational Geometry, Inverse problems, Shape optimization problems, Scheduling problems, Packing, Risk assessment models, Control theory, Computer vision problems, Statistical signal and image processing, Pattern Recognition problems, Clustering and classification, Data Compression, Discrete Mathematics, Numerical Linear and Tensor Algebra, Random matrix theory, Convex and Functional analysis, etc.
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: TBA.
Feb 19: Dmitriy Drusvyatskiy (U Washington). Title: TBA.
Feb 28 (Thursday MSB 3106): Levent Tunçel (U Waterloo). Title: TBA.
Mar 5: Thomas Rothvoss (U Washington). Title: TBA.
Mar 12: Dorit Hochbaum (UC Berkeley). Title: TBA.
Mar 19: Suvrajeet Sen (USC). Title: TBA.