Seminars and Colloquia by Series

The clique chromatic number of sparse random graphs

Series
ACO Student Seminar
Time
Friday, April 22, 2022 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 254
Speaker
Manuel FernandezMathematics, Georgia Tech

Please Note: Streaming online at https://gatech.zoom.us/j/91232113113?pwd=MDhteEdtcENuME9kdXJmcUY0eWlSUT09

The clique chromatic number of a graph is the smallest number of colors in a vertex coloring so that no inclusion-maximal clique is monochromatic (ignoring isolated vertices). 

For the binomial random graph G_{n,p} the clique chromatic number has been studied in a number of works since 2016, but for sparse edge-probabilities in the range n^{-2/5} \ll p \ll 1 even the order of magnitude remained a technical challenge.

Resolving open problems of Alon and Krivelevich as well as Lichev, Mitsche and Warnke, we determine the clique chromatic number of the binomial random graph G_{n,p} in most of the missing regime: we show that it is of order (\log n)/p for edge-probabilities n^{-2/5+\eps} \ll p \ll n^{-1/3} and n^{-1/3+\eps} \ll p \ll 1, for any constant \eps > 0.

Perhaps surprisingly for a result about random graphs, a key ingredient in the proof is an application of the probabilistic method (that hinges on careful counting and density arguments).

This talk is based on joint work with Lutz Warnke.

A peek into Stochastic Multi-Armed Bandits with Heavy Tails.

Series
ACO Student Seminar
Time
Friday, April 15, 2022 - 13:00 for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Shubhada AgrawalTata Institute of Fundamental Research, Mumbai

Please Note: Link: https://gatech.zoom.us/j/91232113113?pwd=MDhteEdtcENuME9kdXJmcUY0eWlSUT09

In this talk, we will look into the two most widely studied settings of the stochastic multi-armed bandit problems - regret minimization and pure exploration. The algorithm is presented with a finite set of unknown distributions from which it can generate samples. In the regret-minimization setting, its aim is to sample sequentially so as to maximize the total average reward accumulated. In the pure exploration setting, we are interested in algorithms that identify the arm with the maximum mean in a small number of samples on an average while keeping the probability of false selection to at most a pre-specified and small value. Both of these problems are well studied in literature and tight lower bounds and optimal algorithms exist when the arm distributions are known to belong to simple classes of distributions such as single-parameter exponential family, distributions that have bounded support, etc. However, in practice, the distributions may not satisfy these assumptions and may even be heavy-tailed. In this talk, we will look at techniques and algorithms for optimally solving these two problems with minimal assumptions on the arm distributions. These ideas can be extended to a more general objective of identifying the distribution with the minimum linear combination of risk and reward, which captures the risk-reward trade-off that is popular in many practical settings, including in finance.

Parallel server systems under an extended Heavy traffic condition

Series
ACO Student Seminar
Time
Friday, April 8, 2022 - 13:00 for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Eyal CastielIsrael Institute of Technology

Please Note: Link: https://bluejeans.com/520769740/3630

Parallel server systems have received a lot of attention since their introduction about 20 years ago. They are commonly used to model a situation where different type of jobs can be treated by servers with different specialties like data and call centers. Exact optimal policies are often not tractable for those systems. Instead, part of the literature was focused on finding policies that are asymptotically optimal as the load of the network approaches a value critical for stability (heavy traffic approximations). This is done by obtaining a weak convergence to a brownian control problem that is linked to a non-linear differential equation (Hamilton-Jacobi-Bellman). Asymptotically optimal policies have been analyzed for a long time under a restrictive assumption that is not natural for practical applications. This talk will present recent developments that allow for a more general asymptotic optimality result by focusing on the simplest non-trivial example.

Faster p-Norm Regression Using Sparsity

Series
ACO Student Seminar
Time
Friday, March 11, 2022 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 254
Speaker
Mehrdad GhadiriGeorgia Tech CS

Given an n-by-d matrix A and a vector of size n, the p-norm problem asks for a vector x that minimizes the following

\sum_{i=1}^n (a_i^T x - b_i)^p,

where a_i is the i’th row of A. The study of p=2 and p=1 cases dates back to Legendre, Gauss, and Laplace. Other cases of p have also been used in statistics and machine learning as robust estimators for decades. In this talk, we present the following improvements in the running time of solving p-norm regression problems.

For the case of 1

For 1

The talk is based on a joint work with Richard Peng and Santosh Vempala.

The k-Cap Process on Geometric Random Graphs

Series
ACO Student Seminar
Time
Friday, February 11, 2022 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 254
Speaker
Mirabel ReidGeorgia Tech CS

The k-cap (or k-winners-take-all) process on a graph works as follows: in each
iteration, exactly k vertices of the graph are in the cap (i.e., winners); the next round
winners are the vertices that have the highest total degree to the current winners,
with ties broken randomly. This natural process is a simple model of firing activity
in the brain. We study its convergence on geometric random graphs revealing rather
surprising behavior

Realizable Learning is All You Need

Series
ACO Student Seminar
Time
Friday, January 28, 2022 - 13:00 for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Max HopkinsUCSD

Please Note: Link: https://bluejeans.com/520769740/

The equivalence of realizable and agnostic learnability is a fundamental phenomenon in learning theory. With variants ranging from classical settings like PAC learning and regression to recent trends such as adversarially robust and private learning, it’s surprising we still lack a unifying theory explaining these results. 

In this talk, we'll introduce exactly such a framework: a simple, model-independent blackbox reduction between agnostic and realizable learnability that explains their equivalence across a wide host of classical models. We’ll discuss how this reduction extends our understanding to traditionally difficult settings such as learning with arbitrary distributional assumptions and general loss, and look at some applications beyond agnostic learning as well (e.g. to privacy). Finally, we'll end by surveying a few nice open problems in the area.

Based on joint work with Daniel Kane, Shachar Lovett, and Gaurav Mahajan.

Simplicity and Optimality in Multi-Item Auctions

Series
ACO Student Seminar
Time
Friday, January 14, 2022 - 13:00 for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Divyarthi MohanTel Aviv University

Please Note: Link: https://bluejeans.com/520769740/3630

Designing mechanisms to maximize revenue is a fundamental problem in mathematical economics and has various applications like online ad auctions and spectrum auctions. Unfortunately, optimal auctions for selling multiple items can be unreasonably complex and computationally intractable. In this talk, we consider a revenue-maximizing seller with n items facing a single unit-demand buyer. Our work shows that simple mechanisms can achieve almost optimal revenue. We approached the tradeoffs of simplicity formally through the lens of computation and menu size. Our main result provides a mechanism that gets a (1 − ε)-approximation to the optimal revenue in time quasi-polynomial in n and has quasi polynomial (symmetric) menu complexity. 

 

Joint work with Pravesh Kothari, Ariel Schvartzman, Sahil Singla, and Matt Weinberg.

2-norm Flow Diffusion in Near-Linear Time

Series
ACO Student Seminar
Time
Friday, November 12, 2021 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 314
Speaker
Li ChenGeorgia Tech CS

We design an O~(m)-time randomized algorithm for the l2-norm flow diffusion problem, a recently proposed diffusion model based on network flow with demonstrated graph clustering related applications both in theory and in practice. Examples include finding locally-biased low conductance cuts. Using a known connection between the optimal dual solution of the flow diffusion problem and the local cut structure, our algorithm gives an alternative approach for finding such cuts in nearly linear time.

From a technical point of view, our algorithm contributes a novel way of dealing with inequality constraints in graph optimization problems. It adapts the high-level algorithmic framework of nearly linear time Laplacian system solvers, but requires several new tools: vertex elimination under constraints, a new family of graph ultra-sparsifiers, and accelerated proximal gradient methods with inexact proximal mapping computation.

Joint work with Richard Peng and Di Wang.

Hardness and Approximations of Submodular Minimum Linear Ordering Problems

Series
ACO Student Seminar
Time
Friday, November 5, 2021 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 314
Speaker
Michael WigalGeorgia Tech Math

The minimum linear ordering problem (MLOP) asks to minimize the aggregated cost of a set function f with respect to some ordering \sigma of the base set. That is, MLOP asks to find a permutation \sigma that minimizes the sum \sum_{i = 1}^{|E|}f({e \in E : \sigma(e) \le i}). Many instances of MLOP have been studied in the literature, for example, minimum linear arrangement (MLA) or minimum sum vertex cover (MSVC). We will cover how graphic matroid MLOP, i.e. where f is taken to be the rank function of a graphic matroid, is NP-hard. This is achieved through a series of reductions beginning with MSVC. During these reductions, we will introduce a new problem, minimum latency vertex cover (MLVC) which we will also show has a 4/3 approximation. Finally, using the theory of principal partitions, we will show MLOP with monotone submodular function f : E \to \mathbb{R}^+ has a 2 - (1 + \ell_f)/(1 + |E|) approximation where \ell_f = f(E)/(\max_{x \in E}f({x})). As a corollary, we obtain a 2 - (1 + r(E))/(1 + |E|) approximation for matroid MLOP where r is the rank function of the matroid. We will also end with some interesting open questions.

Joint work with Majid Farhadi, Swati Gupta, Shengding Sun, and Prasad Tetali.

Learning traffic correlations in multi-class queueing systems by sampling workloads

Series
ACO Student Seminar
Time
Friday, October 22, 2021 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 314
Speaker
Martin ZubeldiaGeorgia Tech ISyE

We consider a service system consisting of parallel single server queues of infinite capacity. Work of different classes arrives as correlated Gaussian processes with known drifts but unknown covariances, and it is deterministically routed to the different queues according to some routing matrix. In this setting we show that, under some conditions, the covariance matrix of the arrival processes can be directly recovered from the large deviations behavior of the queue lengths. Also, we show that in some cases this covariance matrix cannot be directly recovered this way, as there is an inherent loss of information produced by the dynamics of the queues. Finally, we show how this can be used to quickly learn an optimal routing matrix with respect to some utility function.

Pages