Spring 2020

Organizer for Spring 2020: Jesus A. De Loera (Email: [email protected]) . Contact him from an academic email if you wish to receive the ZOOM link and password.

04/07: Stefano Marchesini, (Computational Research Division, Lawrence Berkeley Lab)

Title: High Throughput Phase Retrieval

Abstract: X ray scattering, diffraction, coherent imaging and related phase retrieval inverse problems are the main methods to solve protein structures using x-ray crystallography for drug discovery, to obtain the fastest images ever recorded at suboptical resolution or to achieve unprecedented resolutions with chemical specificity of microchip circuits, biological cells, nanomaterials for energy storage, photovoltaics, geological samples or stardust particles brought back from space. Diffraction based x-ray instruments enable nanometer resolution imaging with chemical and magnetic contrast over large fields of view or volumes. I will present an overview of the experimental schemes, phase retrieval algorithms, computational methods developed for high through-put imaging applications using state of the art x-ray sources, detectors and computing facilities.

04/14: Sam Hopkins (UC Berkeley)

Title: From Proofs to Algorithms for High-Dimensional Statistics

Abstract: I will discuss a novel technique, "Proofs to Algorithms," for designing and analyzing computationally-efficient algorithms for challenging problems in high-dimensional statistics. This technique has recently been used to develop new algorithms with the strongest-known provable guarantees (among polynomial-time algorithms) for a wide array of problems in clustering, regression, heavy-tailed and robust estimation, community detection, and more. Under the hood, Proofs to Algorithms employs the powerful Sum of Squares approach to convex programming, which I will introduce in the talk.

I will illustrate the technique via an application to high-dimensional clustering of samples from Gaussian mixture models, and (time-permitting) discuss some recent developments in heavy-tailed and robust statistics.

Based on joint works with Yeshwanth Cherapanamjeri, Tarun Kathuria, Jerry Li, Prasad Raghavendra, and Nilesh Tripuranenid

04/21: Wotao Yin (UC Los Angeles and Alibaba)

Title: Plug-and-Play Method: a Deep-Learning/Optimization Hybrid Approach for Image Processing

Abstract: Plug-and-play (PnP) is an optimization framework that integrates pre-trained deep networks (or other nonlinear operators) into ADMM and proximal optimization algorithms with provable convergence. It combines the advantages of deep learning and classic optimization.

PnP lets one use excellent pre-trained networks for tasks where there is not sufficient data for end-to-end training. Although previous PnP work has exhibited great empirical results, theoretical analysis addressing even the basic question of convergence has been insufficient. We establish convergence of PnP-FBS and PnP-ADMM with a constant stepsize (rather than using diminishing stepsizes). The nonlinear operator is required to have a certain Lipschitz condition. To meet this condition, we propose real spectral normalization (realSN), a technique for training deep learning-based denoisers to satisfy the proposed Lipschitz condition.

04/28: Yian Ma (UC San Diego)

Title: Briding MCMC and Optimization

Abstract: In this talk, I will discuss three ingredients of optimization theory in the context of MCMC: Non-convexity, Acceleration, and Stochasticity.

I will focus on a class of non-convex objective functions arising from mixture models. For that class of objective functions, I will demonstrate that the computational complexity of a simple MCMC algorithm scales linearly with the model dimension, while optimization problems are NP-hard.

I will then study MCMC algorithms as optimization over the KL-divergence in the space of measures. By incorporating a momentum variable, I will discuss an algorithm which performs "accelerated gradient descent" over the KL-divergence. Using optimization-like ideas, a suitable Lyapunov function is constructed to prove that an accelerated convergence rate is obtained.

Finally, I will present a general recipe for constructing stochastic gradient MCMC algorithms that translates the task of finding a valid sampler into one of choosing two matrices. I will then describe how stochastic gradient MCMC algorithms can be applied to applications involving temporally dependent data, where the challenge arises from the need to break the dependencies when considering minibatches of observations.

05/05: Roummel Marcia (UC Merced)

Title: Optimization Methods for Machine Learning

Abstract: Machine learning (ML) problems are often posed as highly nonlinear and nonconvex unconstrained optimization problems. Methods for solving ML problems based on stochastic gradient descent generally require fine-tuning many hyper-parameters. In this talk we discuss alternative approaches for solving ML problems based on a quasi-Newton trust-region framework that does not require extensive parameter tuning. We will present numerical results that demonstrate the potential of the proposed approaches.

05/12: Venkat Chandrasekaran (Caltech)

Title: Fitting Convex Sets to Data

Abstract: A number of problems in signal processing may be viewed conceptually as fitting a convex set to data. In vision and learning, the task of identifying a collection of features or atoms that provide a concise description of a dataset has been widely studied under the title of dictionary learning or sparse coding. In convex-geometric terms, this problem entails learning a polytope with a desired facial structure from data. In computed tomography, reconstructing a shape from support measurements arises commonly in MRI, robotics, and target reconstruction from radar data. This problem is usually reformulated as one of estimating a polytope from a collection of noisy halfspaces.

In this talk we describe new approaches to these problems that leverage contemporary ideas from the optimization literature on lift-and-project descriptions of convex sets. This perspective leads to natural semidefinite programming generalizations of previous techniques for fitting polyhedral convex sets to data. We provide several stylized illustrations in which these generalizations provide improved reconstructions. On the algorithmic front our methods rely prominently on operator scaling, while on the statistical side our analysis builds on links between learning theory and semialgebraic geometry.

05/19: Paul Atzberger (UC Santa Barbara)

Title: Geometric Approaches for Machine Learning in the Sciences and Engineering

Abstract: There has been a lot of interest recently in leveraging machine learning approaches for modeling and analysis in the sciences and engineering. This poses significant challenges and requirements related to data efficiency, interpretability, and robustness. For scientific problems there is often a lot of prior knowledge about general underlying physical principles, existence of low dimensional latent structures, or groups of invariances or equivariances. We discuss approaches for representing some of this knowledge to enhance learning methods by using results on manifold embeddings, stochastic processes within manifolds, and harmonic analysis. We show how the approaches can be used for high-dimensional stochastic dynamical systems with slow-fast time-scale separations to learn from observations, slow variable representations and reduced models for the dynamics. We also discuss a few other examples where utilizing geometric structure has the potential to improve outcomes in scientific machine learning.

05/26: Prem Devanbu (UC Davis, CS)

Title: "Basic concepts and Live Tutorial on Docker Containers for Novice Users"

Abstract: A "virtual machine" VM is (roughly) a megalomaniacal program that pretends to be an entire computer: when you run one, it's like you have a computer within your computer. Docker Containers are a simple, very bare-bones kind of virtual machine. Docker comes with a rich ecosystem of tools that make it very to build, distribute, download and run VMs. It's so easy, even a hexagenarian full professor can build and distribute containers all day long without begging students for help. Their convenience and resource-thriftiness have made them very popular as a gestalt packaging mechanism for the frenzied rate of what some generously call ``innovation" in on-line services like Uber, Facebook etc. These same features also make them attractive vehicles to capture reproducible data science experiments. In this short 30-40 minute tutorial, I'll give a brief overview of Docker, and show off some of the tools that constitute the eco-system.

06/02: Henry Adams (Colorado State University)

Title: Applied topology: From global to local.

Abstract: Through the use of examples, I will explain one way in which applied topology has evolved since the birth of persistent homology in the early 2000s. The first applications of topology to data emphasized the global shape of a dataset, such as the three-circle model for 3 x 3 pixel patches from natural images, or the configuration space of the cyclo-octane molecule, which is a sphere with a Klein bottle attached via two circles of singularity. More recently, persistent homology is being used to measure the local geometry of data. How do you vectorize geometry for use in machine learning problems? Persistent homology, and its vectorization techniques including persistence landscapes and persistence images, provide popular techniques for incorporating geometry in machine learning. I will survey applications arising from machine learning tasks in agent-based modeling, shape recognition, archaeology, materials science, and biology.

06/09: Bartolomeo Stellato (MIT, ORC)

Title: A Machine Learning Approach to Optimization

Abstract: Most applications in engineering, operations research and finance rely on solving the same optimization problem several times with varying parameters. This method generates a large amount of data that is usually discarded. In this talk, we describe how to use historical data to understand and solve optimization problems. We present a machine learning approach to predict the strategy behind the optimal solution of continuous and mixed-integer convex optimization problems. Using interpretable algorithms such as optimal classification trees we gain insights on the relationship between the problem data and the optimal solution. In this way, optimization is no longer a black-box and practitioners can understand it. Moreover, our method is able to compute the optimal solutions at very high speed. This applies also to non-interpretable machine learning predictors such as neural networks since they can be evaluated very efficiently. We benchmark our approach on several examples obtaining accuracy above 90% and computation times multiple orders of magnitude faster than state-of-the-art solvers. Therefore, our method provides on the one hand a novel insightful understanding of the optimal strategies to solve a broad class of continuous and mixed-integer optimization problems and on the other hand a powerful computational tool to solve online optimization at very high speed.