Seminars and Colloquia by Series

Thresholds versus fractional expectation-thresholds

Series
ACO Student Seminar
Time
Friday, December 6, 2019 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jinyoung ParkRutgers University

Please Note: (This is a joint event of ACO Student Seminar and the Combinatorics Seminar Series)

In this talk we will prove a conjecture of Talagrand, which is a fractional version of the “expectation-threshold” conjecture of Kalai and Kahn. This easily implies various difficult results in probabilistic combinatorics, e.g. thresholds for perfect hypergraph matchings (Johansson-Kahn-Vu) and bounded-degree spanning trees (Montgomery). Our approach builds on recent breakthrough work of Alweiss, Lovett, Wu, and Zhang on the Erdős-Rado “Sunflower Conjecture.” 

This is joint work with Keith Frankston, Jeff Kahn, and Bhargav Narayanan.

Fast convergence of fictitious play

Series
ACO Student Seminar
Time
Friday, November 22, 2019 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Kevin A. LaiCS, Georgia Tech

Fictitious play is one of the simplest and most natural dynamics for two-player zero-sum games. Originally proposed by Brown in 1949, the fictitious play dynamic has each player simultaneously best-respond to the distribution of historical plays of their opponent. In 1951, Robinson showed that fictitious play converges to the Nash Equilibrium, albeit at an exponentially-slow rate, and in 1959, Karlin conjectured that the true convergence rate of fictitious play after k iterations is O(k^{-1/2}), a rate which is achieved by similar algorithms and is consistent with empirical observations. Somewhat surprisingly, Daskalakis and Pan disproved a version of this conjecture in 2014, showing that an exponentially-slow rate can occur, although their result relied on adversarial tie-breaking. In this talk, we show that Karlin’s conjecture holds if ties are broken lexicographically and the game matrix is diagonal. We also show a matching lower bound under this tie-breaking assumption. This is joint work with Jake Abernethy and Andre Wibisono.

Faster Width-dependent Algorithm for Mixed Packing and Covering LPs

Series
ACO Student Seminar
Time
Friday, November 15, 2019 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Digvijay BoobISyE, Georgia Tech

In this talk, we provide the details of our faster width-dependent algorithm for mixed packing-covering LPs. Mixed packing-covering LPs are fundamental to combinatorial optimization in computer science and operations research. Our algorithm finds a $1+\eps$ approximate solution in time $O(Nw/ \varepsilon)$, where $N$ is number of nonzero entries in the constraint matrix, and $w$ is the maximum number of nonzeros in any constraint. This algorithm is faster than Nesterov's smoothing algorithm which requires $O(N\sqrt{n}w/ \eps)$ time, where $n$ is the dimension of the problem. Our work utilizes the framework of area convexity introduced in [Sherman-FOCS’17] to obtain the best dependence on $\varepsilon$ while breaking the infamous $\ell_{\infty}$ barrier to eliminate the factor of $\sqrt{n}$. The current best width-independent algorithm for this problem runs in time $O(N/\eps^2)$ [Young-arXiv-14] and hence has worse running time dependence on $\varepsilon$. Many real life instances of mixed packing-covering problems exhibit small width and for such cases, our algorithm can report higher precision results when compared to width-independent algorithms. As a special case of our result, we report a $1+\varepsilon$ approximation algorithm for the densest subgraph problem which runs in time $O(md/ \varepsilon)$, where $m$ is the number of edges in the graph and $d$ is the maximum graph degree.

Asymptotic normality of the $r\to p$ norm for random matrices with non-negative entries

Series
ACO Student Seminar
Time
Friday, November 1, 2019 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Debankur MukherjeeISyE, Georgia Tech

For an $n\times n$ matrix $A_n$, the $r\to p$ operator norm is defined as $\|A_n\|_{r \to p}= \sup_{\|x\|_r\leq 1 } \|A_n x\|_p$ for $r,p\geq 1$. The $r\to p$ operator norm puts a huge number of important quantities of interest in diverse disciplines under a single unified framework. The application of this norm spans a broad spectrum of areas including data-dimensionality reduction in machine learning, finding oblivious routing schemes in transportation network, and matrix condition number estimation.

 

In this talk, we will consider the $r\to p$ norm of a class of symmetric random matrices with nonnegative entries, which includes the adjacency matrices of the Erd\H{o}s-R\'enyi random graphs and matrices with sub-Gaussian entries. For $1< p\leq r< \infty$, we establish the asymptotic normality of the appropriately centered and scaled $\|A_n\|_{r \to p}$, as $n\to\infty$. The special case $r=p=2$, which corresponds to the largest singular value of matrices, was proved in a seminal paper by F\"uredi and Koml\'os (1981). Of independent interest, we further obtain a sharp $\ell_\infty$-approximation for the maximizer vector. The results also hold for sparse matrices and further the $\ell_\infty$-approximation for the maximizer vector also holds for a broad class of deterministic sequence of matrices with certain asymptotic `expansion' properties.

 

This is based on a joint work with Souvik Dhara (MIT) and Kavita Ramanan (Brown U.).

High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm

Series
ACO Student Seminar
Time
Friday, October 25, 2019 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Wenlong MouEECS, UC Berkeley

We propose a Markov chain Monte Carlo (MCMC) algorithm based on third-order Langevin dynamics for sampling from distributions with log-concave and smooth densities. The higher-order dynamics allow for more flexible discretization schemes, and we develop a specific method that combines splitting with more accurate integration. For a broad class of d-dimensional distributions arising from generalized linear models, we prove that the resulting third-order algorithm produces samples from a distribution that is at most \varepsilon in Wasserstein distance from the target distribution in O(d^{1/3}/ \varepsilon^{2/3}) steps. This result requires only Lipschitz conditions on the gradient. For general strongly convex potentials with α-th order smoothness, we prove that the mixing time scales as O (d^{1/3} / \varepsilon^{2/3} + d^{1/2} / \varepsilon^{1 / (\alpha - 1)} ). Our high-order Langevin diffusion reduces the problem of log-concave sampling to numerical integration along a fixed deterministic path, which makes it possible for further improvements in high-dimensional MCMC problems. Joint work with Yi-An Ma, Martin J, Wainwright, Peter L. Bartlett and Michael I. Jordan.

Expander decomposition: applications to dynamic and distributed algorithms

Series
ACO Student Seminar
Time
Friday, October 4, 2019 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Thatchaphol SaranurakCS, Toyota Technological Institute at Chicago

Expander decomposition has been a central tool in designing graph algorithms in many fields (including fast centralized algorithms, approximation algorithms and property testing) for decades. Recently, we found that it also gives many impressive applications in dynamic graph algorithms and distributed graph algorithms. In this talk, I will survey these recent results based on expander decomposition, explain the key components for using this technique, and give some toy examples on how to apply these components.

Beyond Submodular Maximization

Series
ACO Student Seminar
Time
Friday, September 27, 2019 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Mehrdad GhadiriCS, Georgia Tech

In the past decade, the catalog of algorithms available to combinatorial optimizers has been substantially extended to settings which allow submodular objective functions. One significant recent result was a tight (1-1/e)-approximation for maximizing a non-negative monotone submodular function subject to a matroid constraint. These algorithmic developments were happening concurrently with research that found a wealth of new applications for submodular optimization in machine learning, recommender systems, and algorithmic game theory.

 

The related supermodular maximization models also offer an abundance of applications, but they appeared to be highly intractable even under simple cardinality constraints and even when the function has a nice structure. For example, the densest subgraph problem - suspected to be highly intractable - can be expressed as a monotonic supermodular function which has a particularly nice form. Namely, the objective can be expressed by a quadratic form $x^T A x$ where $A$ is a non-negative, symmetric, 0-diagonal matrix. On the other hand, when the entries $A(u,v)$ form a metric, it has been shown that the associated maximization problems have constant factor approximations. Inspired by this, we introduce a parameterized class of non-negative functions called meta-submodular functions that can be approximately maximized within a constant factor. This class includes metric diversity, monotone submodular and other objectives appearing in the machine learning and optimization literature. A general meta-submodular function is neither submodular nor supermodular and so its multi-linear extension does not have the nice convexity/concavity properties which hold for submodular functions. They do, however, have an intrinsic one-sided smoothness property which is essential for our algorithms. This smoothness property might be of independent interest.

Bounds on Ramsey Games via Alterations

Series
ACO Student Seminar
Time
Friday, September 20, 2019 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
He GuoMath, Georgia Tech

In this talk we introduce a refined alteration approach for constructing $H$-free graphs: we show that removing all edges in $H$-copies of the binomial random graph does not significantly change the independence number (for suitable edge-probabilities); previous alteration approaches of Erdös and Krivelevich remove only a subset of these edges. We present two applications to online graph Ramsey games of recent interest, deriving new bounds for Ramsey, Paper, Scissors games and online Ramsey numbers (each time extending recent results of Fox–He–Wigderson and Conlon–Fox–Grinshpun–He).
Based on joint work with Lutz Warnke.

Graph Algorithms and Offline Data Structures

Series
ACO Student Seminar
Time
Friday, September 13, 2019 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Richard PengCS, Georgia Tech

Graphs, which in their simplest forms are vertices connected by edges,
are widely used in high performance computing, machine learning and
network science. This talk will use recent progresses on two
well-studied algorithmic problems in static and dynamic graph,
max-flows and dynamic matchings, to discuss a methodology for
designing faster algorithm for large graphs. This approach is
motivated by a fundamental phenomenon in data structures: the
advantages of offline data structures over online ones.

I will start by describing how work on max-flows led to a focus on
finding short paths in residual graphs, and how investigating more
global notions of progress in residual graphs led to a more
sophisticated and general understanding of iterative methods and
preconditioning. I will then discuss a similar phenomenon in dynamic
graphs, where maintaining a large matching seems to require the online
detection of short augmenting paths, but can once again be
circumvented through the offline construction of smaller equivalent
graphs.

Differential Privacy: The Census Algorithm

Series
ACO Student Seminar
Time
Friday, September 6, 2019 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Samantha PettiCS, Georgia Tech

For the first time in 2020, the US Census Bureau will apply a differentially private algorithm before publicly releasing decennial census data. Recently, the Bureau publicly released their code and end-to-end tests on the 1940 census data at various privacylevels. We will outline the DP algorithm (which is still being developed) and discuss the accuracy of these end-to-end tests. In particular, we focus on the bias and variance of the reported population counts. Finally, we discuss the choices the Bureau has yet to make that will affect the balance between privacy and accuracy. This talk is based on joint work with Abraham Flaxman.

Pages