Georgia Institute of Technology School of Mathematics | Georgia Institute of Technology | Atlanta, GA

In 1995, Mitsumatsu constructed a large family of Liouville domains whose topology obstructs the existence of a Weinstein structure.  Stabilizing these domains yields Liouville domains for which the topological obstruction is no longer in effect, and in 2019 Huang asked whether Mitsumatsu's Liouville domains were stably homotopic to Weinstein domains.  We answer this question in the affirmative.  This is joint work-in-progress with J. Breen.

In this talk, I will introduce some recent advances in designing stochastic primal-dual methods for bilinear saddle point problems, in the form of min_x max_y y^TAx under different geometries of x and y. These problems are prominent in economics, linear programming, machine learning and reinforcement learning. Specifically, our methods apply to Markov decision processes (MDPs), linear regression, and computational geometry tasks. 

In our work, we propose a variance-reduced framework for solving convex-concave saddle-point problems, given a gradient estimator satisfying some local properties. Further, we show how to design such gradient estimators for bilinear objectives under different geometry including simplex (l_2), Euclidean ball (l_1) or box (l_inf) domains. For matrix A with larger dimension n, nonzero entries nnz and accuracy epsilon, our proposed variance-reduced primal dual methods obtain a runtime complexity of nnz+\sqrt{nnz*n}/epsilon, improving over the exact gradient methods and fully stochastic methods in the accuracy and/or the sparse regime (when epsilon < n/nnz). For finite-sum saddle-point problems sum_{k=1}^K f_k(x,y) where each f is 1-smooth, we show how to obtain an epsilon-optimal saddle point within gradient query complexity of K+\sqrt{K}/epsilon.

Moreover, we also provide a class of coordinate methods for solving bilinear saddle-point problems. These algorithms use either O(1)-sparse gradient estimators to obtain improved sublinear complexity over fully stochastic methods, or their variance-reduced counterparts for improved nearly-linear complexity, for sparse and numerically sparse instances A. 

This talk is based on several joint works with Yair Carmon, Aaron Sidford and Kevin Tian, with links of papers below:

Variance Reduction for Matrix Games

Coordinate Methods for Matrix Games

Efficiently Solving MDPs using Stochastic Mirror Descent

Bio of the speaker: Yujia Jin is a fourth-year Ph.D. student in Department of Management Science and Engineering, Stanford University, working with Aaron Sidford. She is interested in designing efficient continuous optimization methods, which often run in nearly linear / sublinear time and find vast applications in machine learning, data analysis, reinforcement learning, and graph problems.

Several constructions of the estimators of the mean of a random variable that admit sub-Gaussian deviation guarantees and are robust to adversarial contamination under minimal assumptions have been suggested in the literature. The goal of this talk is to discuss the size of constants appearing in the bounds, both asymptotic and non-asymptotic, satisfied by the median-of-means estimator and its analogues. We will describe a permutation-invariant version of the median-of-means estimator and show that it is asymptotically efficient, unlike its “standard" version. Finally, applications and extensions of these results to robust empirical risk minimization will be discussed.

This talk presents novel approaches to old techniques to forecast COVID-19: (i) a modeling framework that takes into consideration asymptomatic carriers and government interventions, (ii) a method to rectify daily case counts reported in public databases, and (iii) a method to study socioeconomic factors and propagation of disinformation. In the case of (i), results were obtained with a comprehensive data set of hospitalizations and cases in the metropolitan area of San Antonio through collaboration with local and regional government agencies, a level of data seldom studied in a disaggregated manner. In the case of (ii), results were obtained with a simple approach to data rectification that has not been exploited in the literature, resulting in a non-autonomous system that opens avenues of mathematical exploration. In the case of (iii), this talk presents a methodology to study the effect of socioeconomic and demographic factors, including the phenomenon of disinformation and its effect in public health; currently there are few mathematical results in this important area.