Seminars and Colloquia by Series

Stability, Optimality, and Fairness in Federated learning

Series
ACO Student Seminar
Time
Friday, October 21, 2022 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Kate Donahue – Cornell –

Federated learning is a distributed learning paradigm where multiple agents, each only with access to local data, jointly learn a global model. There has recently been an explosion of research aiming not only to improve the accuracy rates of federated learning, but also provide certain guarantees around social good properties such as total error or fairness. In this talk, I describe two papers analyzing federated learning through the lens of cooperative game theory (both joint with Jon Kleinberg).

 

In the first paper, we discuss fairness in federated learning, which relates to how error rates differ between federating agents. In this work, we consider two notions of fairness: egalitarian fairness (which aims to bound how dissimilar error rates can be) and proportional fairness (which aims to reward players for contributing more data). For egalitarian fairness, we obtain a tight multiplicative bound on how widely error rates can diverge between agents federating together. For proportional fairness, we show that sub-proportional error (relative to the number of data points contributed) is guaranteed for any individually rational federating coalition. The second paper explores optimality in federated learning with respect to an objective of minimizing the average error rate among federating agents. In this work, we provide and prove the correctness of an efficient algorithm to calculate an optimal (error minimizing) arrangement of players. Building on this, we give the first constant-factor bound on the performance gap between stability and optimality, proving that the total error of the worst stable solution can be no higher than 9 times the total error of an optimal solution (Price of Anarchy bound of 9). 


Relevant Links: https://arxiv.org/abs/2010.00753, https://arxiv.org/abs/2106.09580, https://arxiv.org/abs/2112.00818

Bio:
Kate Donahue is a fifth year computer science PhD candidate at Cornell advised by Jon Kleinberg. She works on algorithmic problems relating to the societal impact of AI such as fairness, human/AI collaboration and game-theoretic models of federated learning. Her work has been supported by an NSF fellowship and recognized by a FAccT Best Paper award. During her PhD, she has interned at Microsoft Research, Amazon, and Google.

Computational challenges in operational data assimilation: problems and solutions

Series
Time
Friday, October 21, 2022 - 11:00 for 1 hour (actually 50 minutes)
Location
Online
Speaker
Ivo Pasmans – University of Reading, National Center for Earth Observation

https://gatech.zoom.us/j/95197085752?pwd=WmtJUVdvM1l6aUJBbHNJWTVKcVdmdz09

Operational weather and ocean forecasting proceeds as a sequence of time intervals. During each interval numerical models produce a forecast, observations are collected and a comparison between the two is made. This comparison is used, in a process called data assimilation (DA), to construct observation-informed initial conditions for the forecast in the next time interval. Many DA algorithms are in use, but they all share the need to solve a high-dimensional (>1010) system of linear equations. Constructing and solving this system in the limited amount of time available between the reception of the observations and the start of the next time interval is highly non-trivial for three reasons. 1) As the numerical models are computationally demanding, it is generally impossible to construct the full linear system. 2) Its high dimensionality makes it impossible to store the system as a matrix in memory. Consequently, it is not possible to directly invert it. 3) The operational time-constraints strongly limit the number of iterations that can be used by iterative linear solvers. By adapting DA algorithms to use parallelization, it is possible to leverage the computational power of superclusters to construct a high-rank approximation to the linear system and solve it using less then ~20 iterations. In this talk, I will first introduce the two most popular families of DA algorithms: Kalman filters and variational DA. After this, I will discuss some of the adaptations that have been developed to enable parallelization. Among these are ensemble Kalman filters, domain localization, the EVIL (Ensemble Variational Integrated Localized) and saddle point algorithms.

What is a matroid?

Series
Algebra Student Seminar
Time
Friday, October 21, 2022 - 10:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Tong Jin – Georgia Institute of Technology –
This is a pre-talk for the Algebra Seminar on Oct. 24. I will discuss (various) definitions of matroids, matroid minors, Tutte polynomials and characteristic polynomials, matroid basis polytopes, and Grassmannians. If time permits, I'll also discuss permutohedral varieties and the Cremona map and/or my current work. 
 

Complete integrability of the Benjamin–Ono equation on the multi-soliton manifolds

Series
Math Physics Seminar
Time
Thursday, October 20, 2022 - 16:00 for 1 hour (actually 50 minutes)
Location
Skiles Room 005
Speaker
Ruoci Sun – School of Mathematics, Georgia Tech –

This presentation, which is based on the work Sun [2], is dedicated to describing the complete integrability of the Benjamin–Ono (BO) equation on the line when restricted to every N-soliton mani- fold, denoted by UN . We construct (generalized) action–angle coordinates which establish a real analytic symplectomorphism from UN onto some open convex subset of R2N and allow to solve the equation by quadrature for any such initial datum. As a consequence, UN is the universal covering of the manifold of N-gap potentials for the BO equation on the torus as described by G ́erard–Kappeler [1]. The global well-posedness of the BO equation on UN is given by a polynomial characterization and a spectral char- acterization of the manifold UN . Besides the spectral analysis of the Lax operator of the BO equation and the shift semigroup acting on some Hardy spaces, the construction of such coordinates also relies on the use of a generating functional, which encodes the entire BO hierarchy. The inverse spectral formula of an N-soliton provides a spectral connection between the Lax operator and the infinitesimal generator of the very shift semigroup. The construction of action–angle coordinates for each UN constitutes a first step towards the soliton resolution conjecture of the BO equation on the line.

Statistical Tensor Learning in 2020s: Methodology, Theory, and Applications

Series
Stochastics Seminar
Time
Thursday, October 20, 2022 - 15:30 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Anru Zhang – Duke University –

The analysis of tensor data, i.e., arrays with multiple directions, has become an active research topic in the era of big data. Datasets in the form of tensors arise from a wide range of scientific applications. Tensor methods also provide unique perspectives to many high-dimensional problems, where the observations are not necessarily tensors. Problems in high-dimensional tensors generally possess distinct characteristics that pose great challenges to the data science community. 

In this talk, we discuss several recent advances in statistical tensor learning and their applications in computational imaging, social network, and generative model. We also illustrate how we develop statistically optimal methods and computationally efficient algorithms that interact with the modern theories of computation, high-dimensional statistics, and non-convex optimization.

Examples of constructions of higher dimensional hyperbolic tori with controlled splitting

Series
Joint School of Mathematics and CDSNS Colloquium
Time
Friday, October 14, 2022 - 15:30 for 1 hour (actually 50 minutes)
Location
Online via Zoom; "viewing party" in Skiles 006
Speaker
Jean-Pierre Marco – Sorbonne Universite –

Please Note: Zoom link: https://us06web.zoom.us/j/83392531099?pwd=UHh2MDFMcGErbzFtMHBZTmNZQXM0dz09

In this talk I will generalize a simple trick to produce splitting for the separatrices of (the time-one map of) a simple pendulum, to hyperbolic tori of any dimension $m\geq 2$. The examples will be constructed in the Gevrey class, and the splitting is bounded from below by a term of the form $\exp (-c(1/\eps)^a)$, where $a=\frac{1}{2(\alpha-1)(m-2)}$. This will be compared to usual upper bounds in the same setting.

TBA by Ruth Luo

Series
Combinatorics Seminar
Time
Friday, October 14, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Ruth Luo – University of South Carolina

Minimum degree conditions ensuring the existence of long cycles in hypergraphs

Series
Combinatorics Seminar
Time
Friday, October 14, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Ruth Luo – University of South Carolina –

Dirac proved that every $n$-vertex graph with minimum degree at least $n/2$ contains a hamiltonian cycle. Moreover, every graph with minimum degree $k \geq 2$ contains a cycle of length at least $k+1$, and this can be further improved if the graph is 2-connected. In this talk, we prove analogs of these theorems for hypergraphs. That is, we give sharp minimum degree conditions that imply the existence of long Berge cycles in uniform hypergraphs. This is joint work with Alexandr Kostochka and Grace McCourt.

Efficient and Near-Optimal Online Portfolio Selection

Series
Stochastics Seminar
Time
Friday, October 14, 2022 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Dmitrii M. Ostrovskii – University of Southern California

In the problem of online portfolio selection as formulated by Cover (1991), the trader repeatedly distributes her capital over $ d $ assets in each of $ T > 1 $ rounds, with the goal of maximizing the total return. Cover proposed an algorithm called Universal Portfolios, that performs nearly as well as the best (in hindsight) static assignment of a portfolio, with 

an $ O(d\log(T)) $ regret in terms of the logarithmic return. Without imposing any restrictions on the market, this guarantee is known to be worst-case optimal, and no other algorithm attaining it has been discovered so far. Unfortunately, Cover's algorithm crucially relies on computing the expectation over certain log-concave density in R^d, so in a practical implementation this expectation has to be approximated via sampling, which is computationally challenging. In particular, the fastest known implementation, proposed by Kalai and Vempala in 2002, runs in $ O( d^4 (T+d)^{14} ) $ per round, which rules out any practical application scenario. Proposing a practical algorithm with a near-optimal regret is a long-standing open problem. We propose an algorithm for online portfolio selection with a near-optimal regret guarantee of $ O( d \log(T+d) ) $ and the runtime of only $ O( d^2 (T+d) ) $ per round. In a nutshell, our algorithm is a variant of the follow-the-regularized-leader scheme, with a time-dependent regularizer given by the volumetric barrier for the sum of observed losses. Thus, our result gives a fresh perspective on the concept of volumetric barrier, initially proposed in the context of cutting-plane methods and interior-point methods, correspondingly by Vaidya (1989) and Nesterov and Nemirovski (1994). Our side contribution, of independent interest, is deriving the volumetrically regularized portfolio as a variational approximation of the universal portfolio: namely, we show that it minimizes Gibbs's free energy functional, with accuracy of order $ O( d \log(T+d) ) $. This is a joint work with Remi Jezequel and Pierre Gaillard. 

Pages