Seminars and Colloquia by Series

Minimal problems in 3D reconstruction

Series
ACO Student Seminar
Time
Friday, September 25, 2020 - 13:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/264244877/0166
Speaker
Timothy DuffMath, Georgia Tech

I describe my ongoing work using tools from computational and combinatorial algebraic geometry to classify minimal problems and identify which can be solved efficiently. I will not assume any background in algebraic geometry or computer vision.

Structure-from-motion algorithms reconstruct a 3D scene from many images, often by matching features (such as point and lines) between the images. Matchings lead to constraints, resulting in a nonlinear system of polynomial equations that recovers the 3D geometry. Since many matches are outliers, these methods are used in an iterative framework for robust estimation called RANSAC (RAndom SAmpling And Consensus), whose efficiency hinges on using a small number of correspondences in each iteration. As a result, there is a big focus on constructing polynomial solvers for these "minimal problems" that run as fast as possible. Our work classifies these problems in cases of practical interest (calibrated cameras, complete and partial visibility.) Moreover, we identify candidates for practical use, as quantified by "algebraic complexity measures" (degree, Galois group.)

joint w/ Anton Leykin, Kathlen Kohn, Tomas Pajdla arxiv1903.10008 arxiv2003.05015+ Viktor Korotynskiy, TP, and Margaret Regan (ongoing.)

New Algorithms for Generalized Min Sum Set Cover

Series
ACO Student Seminar
Time
Friday, September 18, 2020 - 13:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/264244877/0166
Speaker

We present a new rounding framework and improve the approximation bounds for min sum vertex cover and generalized min sum set cover, also known as multiple intents re-ranking problem. These classical combinatorial optimization problems find applications in scheduling, speeding up semidefinite-program solvers, and query-results diversification, among others.

Our algorithm is based on transforming the LP solution by a suitable kernel and applying a randomized rounding. It also gives a linear-programming based 4-approximation algorithm for min sum set cover, i.e., best possible due to Feige, Lovász, and Tetali. As part of the analysis of our randomized algorithm we derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which may be of independent interest.

Joint work with Nikhil Bansal, Jatin Batra, and Prasad Tetali. [arXiv:2007.09172]

Online Selection with Cardinality Constraints under Bias

Series
ACO Student Seminar
Time
Friday, September 11, 2020 - 13:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/264244877/0166
Speaker

Optimization and machine learning algorithms often use real-world data that has been generated through complex socio-economic and behavioral processes. This data, however, is noisy, and naturally encodes difficult-to-quantify systemic biases. In this work, we model and address bias in the secretary problem, which has applications in hiring. We assume that utilities of candidates are scaled by unknown bias factors, perhaps depending on demographic information, and show that bias-agnostic algorithms are suboptimal in terms of utility and fairness. We propose bias-aware algorithms that achieve certain notions of fairness, while achieving order-optimal competitive ratios in several settings.

CANCELLED: Online Selection with Cardinality Constraints under Bias

Series
ACO Student Seminar
Time
Friday, March 13, 2020 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Optimization and machine learning algorithms often use real-world data that has been generated through complex socio-economic and behavioral processes. This data, however, is noisy, and naturally encodes difficult-to-quantify systemic biases. In this work, we model and address bias in the secretary problem, which has applications in hiring. We assume that utilities of candidates are scaled by unknown bias factors, perhaps depending on demographic information, and show that bias-agnostic algorithms are suboptimal in terms of utility and fairness. We propose bias-aware algorithms that achieve certain notions of fairness, while achieving order-optimal competitive ratios in several settings.

Strong self concordance and sampling

Series
ACO Student Seminar
Time
Friday, March 6, 2020 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker

Motivated by the Dikin walk, we develop aspects of an interior-point

theory for sampling in high dimensions. Specifically, we introduce symmetric

and strong self-concordance. These properties imply that the corresponding

Dikin walk mixes in $\tilde{O}(n\bar{\nu})$ steps from a warm start

in a convex body in $\mathbb{R}^{n}$ using a strongly self-concordant barrier

with symmetric self-concordance parameter $\bar{\nu}$. For many natural

barriers, $\bar{\nu}$ is roughly bounded by $\nu$, the standard

self-concordance parameter. We show that this property and strong

self-concordance hold for the Lee-Sidford barrier. As a consequence,

we obtain the first walk to mix in $\tilde{O}(n^{2})$ steps for an

arbitrary polytope in $\mathbb{R}^{n}$. Strong self-concordance for other

barriers leads to an interesting (and unexpected) connection ---

for the universal and entropic barriers, it is implied by the KLS

conjecture.

The Karger-Stein Algorithm is Optimal for k-cut

Series
ACO Student Seminar
Time
Friday, February 21, 2020 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jason LiCS, Carnegie Mellon University

In the $k$-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into $k$ connected components. Algorithms due to Karger-Stein and Thorup showed how to find such a minimum $k$-cut in time approximately $O(n^{2k-2})$. The best lower bounds come from conjectures about the solvability of the $k$-clique problem and a reduction from $k$-clique to $k$-cut, and show that solving $k$-cut is likely to require time $\Omega(n^k)$. Our recent results have given special-purpose algorithms that solve the problem in time $n^{1.98k + O(1)}$, and ones that have better performance for special classes of graphs (e.g., for small integer weights).

In this work, we resolve the problem for general graphs, by showing that for any fixed $k \geq 2$, the Karger-Stein algorithm outputs any fixed minimum $k$-cut with probability at least $\widehat{O}(n^{-k})$, where $\widehat{O}(\cdot)$ hides a $2^{O(\ln \ln n)^2}$ factor. This also gives an extremal bound of $\widehat{O}(n^k)$ on the number of minimum $k$-cuts in an $n$-vertex graph and an algorithm to compute a minimum $k$-cut in similar runtime. Both are tight up to $\widehat{O}(1)$ factors.

The first main ingredient in our result is a fine-grained analysis of how the graph shrinks---and how the average degree evolves---under the Karger-Stein process. The second ingredient is an extremal result bounding the number of cuts of size at most $(2-\delta) OPT/k$, using the Sunflower lemma.

Clustering a Mixture of Gaussians

Series
ACO Student Seminar
Time
Friday, February 14, 2020 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
He JiaCS, Georgia Tech

We give an efficient algorithm for robustly clustering of a mixture of two arbitrary Gaussians, a central open problem in the theory of computationally efficient robust estimation, assuming only that the the means of the component Gaussian are well-separated or their covariances are well-separated. Our algorithm and analysis extend naturally to robustly clustering mixtures of well-separated logconcave distributions. The mean separation required is close to the smallest possible to guarantee that most of the measure of the component Gaussians can be separated by some hyperplane (for covariances, it is the same condition in the second degree polynomial kernel). Our main tools are a new identifiability criterion based on isotropic position, and a corresponding Sum-of-Squares convex programming relaxation.

Learning Optimal Reserve Price against Non-myopic Bidders

Series
ACO Student Seminar
Time
Friday, January 10, 2020 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jinyan LiuUniversity of Hong Kong

We consider the problem of learning optimal reserve price in repeated auctions against non- myopic bidders, who may bid strategically in order to gain in future rounds even if the single- round auctions are truthful. Previous algorithms, e.g., empirical pricing, do not provide non- trivial regret rounds in this setting in general. We introduce algorithms that obtain a small regret against non-myopic bidders either when the market is large, i.e., no single bidder appears in more than a small constant fraction of the rounds, or when the bidders are impatient, i.e., they discount future utility by some factor mildly bounded away from one. Our approach carefully controls what information is revealed to each bidder, and builds on techniques from differentially private online learning as well as the recent line of works on jointly differentially private algorithms.

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.