Computer Science Theory Seminar : Past Events
Past Seminars
The following seminars have already happened, you may instead view upcoming seminars in this series.
Aug. 28, 2019
Youming Qiao :
4:15 p.m. in 1325 SEO
Abstract
In the past few years, several research projects of mine (joint with collaborators) suggest that it is fruitful to view linear spaces of matrices as a linear algebraic analogue of graphs. In this talk I will propose such an analogue, and explain why such an analogue may make sense. I will then list several correspondences between structures on graphs and structures on matrix spaces. These include perfect matchings vs full-rank matrices, shrunk subsets vs shrunk spaces, independent sets vs isotropic spaces, random graphs vs random matrix spaces, and isomorphism concepts. These correspondences play an important role in the recent progress on non-commutative rational identity testing, form one bottleneck of putting graph isomorphism in P, and suggest a possible route for post-quantum cryptography.
Sept. 4, 2019
Arturs Backurs :
4:15 p.m. in 1325 SEO
Abstract
Given a kernel function k and a dataset P (of points from $R^d$), the kernel density function of P at a point q from $R^d$ is equal to $KDF_P(q) := 1/|P| \sum_{p \in P} k(p,q)$. Kernel density evaluation has numerous applications, in scientific computing, statistics, computer vision, machine learning and other fields. In all of them it is necessary to evaluate $KDF_P(q)$ quickly, often for many inputs q and large point-sets P.
In this paper we present a collection of algorithms for efficient KDF evaluation under the assumptions that the kernel k is "smooth", i.e., the value changes at most polynomially with the distance. This assumption is satisfied by several well-studied kernels, including the (generalized) t-student kernel and rational quadratic kernel. For smooth kernels, we give a data structure that, after $O(dn log(\Phi n)/\epsilon^2)$ preprocessing, estimates $KDF_P(q)$ up to a factor of $1+\epsilon$ in $O(d log (\Phi n)/\epsilon^2)$ time, where $\Phi$ is the aspect ratio. The $\log(\Phi n)$ term can be further replaced by log n under an additional decay condition on k, which is satisfied by the aforementioned examples.
We further extend the results in two ways. First, we use low-distortion embeddings to extend the results to kernels defined for spaces other than $l_2$. The key feature of this reduction is that the distortion of the embedding affects only the running time of the algorithm, not the accuracy of the estimation. As a result, we obtain $(1+\epsilon)$-approximate estimation algorithms for kernels over other $l_p$ norms, Earth-Mover Distance, and other metric spaces. Second, for smooth kernels that are decreasing with distance, we present a general reduction from density estimation to approximate near neighbor in the underlying space. This allows us to construct algorithms for general doubling metrics, as well as alternative algorithms for $l_p$ norms and other spaces.
Joint work with Moses Charikar, Piotr Indyk and Paris Siminelakis.
Sept. 11, 2019
Anastasios Sidiropoulos :
4:15 p.m. in 1325 SEO
Abstract
We study the problem of supervised learning a metric space under discriminative constraints. Given a universe X and sets S, D of similar and dissimilar pairs in X, we seek to find a mapping f : X → Y , into some target metric space M = (Y, ρ), such that similar objects are mapped close together, and dissimilar objects are mapped to points are mapped far apart from each other. More generally, the goal is to find a mapping of maximum accuracy (that is, fraction of correctly classified pairs). We propose approximation algorithms for various versions of this problem, for the cases of Euclidean and tree metric spaces. For both of these target spaces, we obtain fully polynomial-time approximation schemes (FPTAS) for the case of perfect information. In the presence of imperfect information we present approximation algorithms that run in quasi-polynomial time (QPTAS). We also present an exact algorithm for learning line metric spaces with perfect information in polynomial time. Our algorithms use a combination of tools from metric embeddings and graph partitioning, that could be of independent interest.
Based on joint work with Diego Ihara Centurion and Neshat Mohammadi.
Sept. 25, 2019
Akash Kumar :
4:15 p.m. in 1325 SEO
Abstract
Let G be an undirected, bounded degree graph with n vertices. Fix a finite graph H, and suppose one must remove $\varepsilon n$ edges from G to make it H-minor free (for some small constant $\varepsilon > 0$). We give an $n^{1/2+o(1)}$-time randomized procedure that, with high probability, finds an H-minor in such a graph. For an example application, suppose one must remove $\varepsilon n$ edges from a bounded degree graph G to make it planar. This result implies an algorithm, with the same running time, that produces a $K_{3,3}$ or $K_5$ minor in G. No sublinear time bound was known for this problem, prior to this result.
By the graph minor theorem, we get an analogous result for any minor-closed property. Up to $n^{o(1)}$ factors, this resolves a conjecture of Benjamini-Schramm-Shapira (STOC 2008) on the existence of one-sided property testers for minor-closed properties. Furthermore, our algorithm is nearly optimal, by an $\Omega(\sqrt{n})$ lower bound of Czumaj et al (RSA 2014).
Prior to this work, the only graphs H for which non-trivial property testers were known for H-minor freeness are the following: H being a forest or a cycle (Czumaj et al, RSA 2014), $K_{2,k}$, $(k\times 2)$-grid, and the k-circus (Fichtenberger et al, Arxiv 2017).
(Joint work with C. Seshadhri and Andrew Stolman)
Oct. 9, 2019
Vishesh Jain :
4:15 p.m. in 612 SEO
Abstract
Let $s_n(M_n)$ denote the smallest singular value of an $n\times n$ random (possibly complex) matrix $M_n$. We will discuss a novel combinatorial approach (in particular, not using either inverse Littlewood--Offord theory or net arguments) for obtaining upper bounds on the probability that $s_n(M_n)$ is smaller than $\eta \geq 0$ for quite general random matrix models. Such estimates are a fundamental part of the non-asymptotic theory of random matrices and have applications to the strong circular law, numerical linear algebra etc. In several cases of interest, our approach provides stronger bounds than those obtained by Tao and Vu using inverse Littlewood--Offord theory.
Oct. 16, 2019
Bhaskar DasGupta :
4:15 p.m. in 1325 SEO
Abstract
Anomaly detection problems (also called change-point detection problems) have been studied in data mining, statistics and computer science over the last several decades (mostly in non-network context) in applications such as medical condition monitoring, weather change detection and speech recognition. In recent days, however, anomaly detection problems have become increasing more relevant in the context of network science since useful insights for many complex systems in biology, finance and social science are often obtained by representing them via networks. Notions of local and non-local curvatures of higher-dimensional geometric shapes and topological spaces play a fundamental role in physics and mathematics in characterizing anomalous behaviours of these higher dimensional entities. However, using curvature measures to detect anomalies in networks is not yet very common. To this end, a main goal of this talk is to formulate and analyze curvature analysis methods to provide the foundations of systematic approaches to find critical components and detect anomalies in networks. For this purpose, we use two measures of network curvatures which depend on non-trivial global properties, such as distributions of geodesics and higher-order correlations among nodes, of the given network. Based on these measures, we precisely formulate several computational problems related to anomaly detection in static or dynamic networks, and provide non-trivial computational complexity results for these problems. It is our hope that this paper will stimulate and motivate further theoretical or empirical research concerning the exciting interplay between notions of curvatures from network and non-network domains, a much desired goal in our opinion.
(Joint result with M. V. Janardhanan and F. Yahyanejad)
Oct. 22, 2019
Karthik Chandrasekaran :
4 p.m. in 1325 SEO
Abstract
Finding locally optimal solutions for max-cut and max-k-cut are well-known PLS-complete problems. An instinctive approach to finding such a locally optimum solution is the FLIP method. Even though FLIP requires exponential time in worst-case instances, it tends to terminate quickly in practical instances. To explain this discrepancy, the run-time of FLIP for max-cut has been studied in the smoothed complexity model. Etscheid and Roglin (2014) showed that the smoothed complexity of FLIP for max-cut in arbitrary graphs is quasi-polynomial. Angel, Bubeck, Peres, and Wei (2017) showed that the smoothed complexity of FLIP for max-cut in complete graphs is O(φ^5n^15.1), where φ is an upper bound on the random edge-weight density and n is the number of vertices in the input graph. In this talk, I will present an analysis technique that substantially improves the smoothed run-time bound. Our techniques provide a general framework for analyzing FLIP in the smoothed model. We illustrate this general framework by showing that the smoothed complexity of FLIP for max-3-cut in complete graphs is polynomial and for max-k-cut in arbitrary graphs is quasi-polynomial for constant k.
Based on joint work with Ali Bibak and Charles Carlson.
Oct. 30, 2019
Gyorgy Turan :
4:15 p.m. in 1325 SEO
Abstract
Interpretability is the requirement that a model obtained by machine learning, beyond having predictive power, should be comprehensible for the user, or it should be possible to reason about its properties. For example, decision trees appear to be more interpretable than neural networks. We give a brief introduction to this topic, and discuss experimental results on interpretability aspects of word embeddings in natural language processing, and a theoretical approach to interpretability for Bayesian network classifiers using ordered binary decision diagrams.
Joint work with Vanda Balogh, Gabor Berend, Karine Chubarian and Dimitris Diochnos.
Nov. 5, 2019
Simina Brânzei :
4 p.m. in 1325 SEO
Abstract
We consider a simple variant of the von Neumann model of an expanding economy, in which multiple producers make goods according to their production function. The players trade their goods at the market and then use the bundles acquired for the production in the next round. We study a simple decentralized dynamic---known as proportional response---in which players update their bids proportionally to how useful the investments were in the past round. We show this dynamic leads to growth of the economy in the long term (whenever growth is possible) but also creates unbounded inequality, i.e. very rich and very poor players emerge. We analyze several other phenomena, such as how the relation of a player with others influences its development and the Gini index of the system.
I will also discuss this dynamical system when the amounts of the players are fixed over time and show that it converges to market equilibria from any starting configuration.
This is based on joint work with Mehta and Nisan (https://arxiv.org/pdf/1802.07385.pdf), and with Devanur and Rabani (https://arxiv.org/pdf/1907.05037.pdf)
Nov. 13, 2019
Xue Chen :
4:15 p.m. in 1325 SEO
Abstract
The Fourier transform is a ubiquitous computational tool in processing a variety of signals, including audio, image, and video. In many practical applications, the main reason for using the Fourier transform is that the transformed signal is approximately sparse, which exhibits structures that could be exploited to speed up the computation. While this has been well studied in the discrete setting (e.g., the Goldreich and Levin algorithm and Hassanieh et al.), it is still poorly understood in the more realistic continuous setting.
We consider the problem of reconstructing a continuous Fourier-sparse signal from noisy samples, where the sampling is done over some continuous interval [0,T] and the frequencies can be arbitrary and ``off-grid''. Previous methods for this problem required the gap between the frequencies to be at least 1/T, the threshold required to robustly identify individual frequencies. In this talk, we show an efficient framework that avoids the need for a frequency gap to interpolate the signal. Moreover, we discuss its implications on the more general problem --- reconstructing continuous signals with arbitrary Fourier structures such as narrow-band and multi-band.
Based on recent papers with Daniel Kane, Eric Price, and Zhao Song.
Nov. 20, 2019
Alex Wein :
4:15 p.m. in 1325 SEO
Abstract
High-dimensional inference problems such as sparse PCA and planted clique often exhibit statistical-vs-computational tradeoffs whereby there is no known polynomial-time algorithm matching the performance of the optimal estimator. I will discuss an emerging framework -- based on the so-called low-degree likelihood ratio -- for precisely predicting these tradeoffs and giving rigorous evidence for computational hardness in the conjectured hard regime. This method was originally proposed in a sequence of works on the sum-of-squares hierarchy, and the key idea is to study whether or not there exists a low-degree polynomial that succeeds at a given statistical task.
In the second part of the talk, I will show how to use the above framework to give new results for the sparse PCA problem. Here the goal is to recover a rank-1 signal $xx^\top$ planted in a random matrix (either Wigner or Wishart), where x is rho-sparse (rho fraction of entries nonzero). Polynomial-time algorithms are known when rho << 1/sqrt(n) and naive exhaustive search succeeds when rho << 1; however, no efficient algorithm is known when rho >> 1/sqrt(n). We explore precisely how hard the "hard" regime is by showing that for any rho >> 1/sqrt(n) there is a subexponential-time algorithm of runtime exp(rho^2 n), and the low-degree likelihood ratio suggests that this is optimal. In contrast, naive exhaustive search has runtime exp(rho n).
Based on joint work with Afonso Bandeira, Yunzi Ding, and Tim Kunisky (https://arxiv.org/abs/1907.11635 and https://arxiv.org/abs/1907.11636).
Dec. 4, 2019
Yury Makarychev :
4:15 p.m. in 1325 SEO
Abstract
Consider an instance of Euclidean k-means or k-medians clustering. We show that the cost of the optimal solution is preserved up to a factor of (1+ε) under a projection onto a random O(log(k/ε)/ε^2)-dimensional subspace. Further, the cost of every clustering is preserved within (1+ε). More generally, our result applies to any dimensionality reduction satisfying a mild sub-Gaussian-tail condition. Our bound on the dimension is nearly optimal. Additionally, our result applies to Euclidean k-clustering with the distances raised to the p-th power for any constant p.
Based on a joint work with Konstantin Makarychev and Ilya Razenshteyn.
Feb. 18, 2020
Gabor Berend :
3 p.m. in 1325 SEO
Abstract
Symbolic representations have been superseded by continuous representations in
practically all natural language processing (NLP) applications. Despite the
fact that the popular continuous representations are capable of
solving various NLP tasks close to human performance, the kind of
representations employed in most recent NLP frameworks do not really
resemble human cognition. In this talk, we will review algorithms for
obtaining continuous meaning representations of natural language, then
propose an approach to distill symbolic features from them in a way that convey human interpretable, commonsense knowledge as well. We additionally present our experimental results suggesting that the symbolic features distilled from continuous representations via sparse coding can be used for training standard statistical models that perform comparably to more expensive and less interpretable neural models. Finally, we also introduce an efficient algorithm for constructing multilingual sparse word representations, opening up the possibility for performing zero-shot learning across languages.
Feb. 25, 2020
Lisa Hellerstein :
3 p.m. in 1325 SEO
Abstract
A Boolean function f(x1, ..., xn) is symmetric if its value is determined by the number of its input variables that are set to 1. Given a symmetric Boolean function f(x1,...,xn), suppose we want to determine the value of f on an initially unknown assignment to its inputs xi. For each xi, we are given pi, the probability that xi=1. The xi's are independent. The only way to find the value of xi in the assignment is to "test" xi. The problem is to determine the order in which to perform the tests, so as to minimize the expected number of tests. We present approximation algorithms for versions of this problem and discuss open questions.
Oct. 13, 2021
Jake Maranzatto :
3 p.m. in 636 SEO
Abstract
The goal of statistical reconstruction problems is to quantify how many noisy samples are required to recover a target object with high probability. The canonical example is string trace reconstruction, where bits in a binary string are removed i.i.d to produce samples, and our goal is to design an algorithm to recover the original string with high probability. I'll discuss the history of string reconstruction, as well as some of my work on reconstructing trees.
Oct. 20, 2021
Sami Davies :
3 p.m. in 636 SEO
Abstract
Ever have a linear program with an integrality gap that you'd like to beat and think "darn, I can't come up with a constraint that gets rid of this integrality gap instance!"? Well, LP hierarchies may be the tool for you! They provide a systematic way to add constraints and variables to an LP, thus strengthening it. In this talk, I will
(1) give intuition behind the Sherali-Adams hierarchy and
(2) exemplify the usefulness of the Sherali-Adams hierarchy by applying it to (what was) one of the biggest open questions in scheduling theory.
Oct. 27, 2021
Neshat Mohammadi :
3 p.m. in 636 SEO
Abstract
Learning metric space is a fundamental computational problem, that has found numerous applications and has received significant attention lately. This talk will provide a brief overview of some of my previous and current works in this area.
Nov. 3, 2021
Abhijeet Mulgund :
3 p.m. in 636 SEO
Abstract
Deep learning (DL) is the workhorse of modern machine learning. In practice, DL is a technological marvel. In theory, it poses a problem. Our current understanding of generalization—performance outside a model’s training data—does not adequately explain the success of DL. In this talk we'll go over what deep learning is, what theoretical results we know about its convergence and generalization, and how these results match up with what we see in practice.
Nov. 10, 2021
Chris Jones :
3 p.m. in 636 SEO
Abstract
The sum-of-squares algorithm is a powerful combinatorial optimization algorithm that can be run as a black box on a given problem. However, it is currently quite difficult to determine whether or not sum-of-squares solves the problem, since sum-of-squares is too slow to run in practice, and theoretical analysis is difficult. I will discuss two recent works on lower bounds against sum-of-squares on specific problems: first, for the problem of minimizing the Sherrington-Kirkpatrick Hamiltonian, and second, for the Independent Set problem on sparse graphs. The lower bounds utilize matrix-valued Fourier analysis, combining both combinatorial and spectral techniques.
Nov. 17, 2021
Patrick Bennett :
3 p.m. in 636 SEO
Abstract
We analyze two random greedy processes on sparse random graphs and hypergraphs with fixed degree sequence. We analyze the matching process, which builds a set of disjoint edges one edge at a time, and then we analyze the independent process which builds an independent set of vertices one vertex at a time. Our results for these processes generalize and extend some results of Frieze, Wormald, Brightwell, Janson and Luczak. Using a recent result of Krivelevich, Mészáros, Michaeli, and Shikhelman, we extend our result on the matching process to any (deterministic) regular hypergraph of high girth. This talk is about joint work with Deepak Bal.
Dec. 1, 2021
Kevin Zhou :
4 p.m. in 636 SEO
Abstract
Query learning of automata is a well-studied area of problems, beginning with work of Angluin in 1987 introducing the L* algorithm for DFAs, with a large body of ensuing work applying Angluin's approach to variants and generalizations of DFAs. Most results in the area utilize Angluin's basic method, tailoring the details of the algorithms on a case-by-case basis. Recent work by Chase and Freitag took an alternative approach inspired by model theory, proving general bounds for query learning in terms of various combinatorial measures of complexity. Applying this approach to the setting of DFAs, they obtain new learnability results of a qualitatively different flavor than those of Angluin. We extend these results, proving new bounds in the query complexity of two generalizations of finite automata - automata with advice and nominal automata.
Jan. 26, 2022
Truong Son Hy :
4 p.m. in Zoom
Abstract
Graph neural networks (GNNs) utilizing various ways of generalizing the concept of convolution to graphs have been widely applied to many learning tasks, including modeling physical systems, finding molecular representations to estimate quantum chemical computation, etc. Most existing GNNs address permutation invariance by conceiving of the network as a message passing scheme, where each node sums the feature vectors coming from its neighbors. We argue that this scheme imposes a limitation on the representation power of GNNs such that each node loses their identity after being aggregated by summing. Thus, we propose a new general architecture called Covariant Compositional Networks (CCNs) in which the node features are represented by higher order tensors and transform covariantly/equivariantly according to a specific representation of the symmetry group of its receptive field. Experiments show that CCNs can outperform competing methods on standard graph learning benchmarks and on estimating the molecular properties calculated by computationally expensive Density Functional Theory (DFT). This novel machine learning approach allows scientists to efficiently extract chemical knowledge and explore the increasingly growing chemical data.
Feb. 2, 2022
Saeid Hajizadeh :
4 p.m. in 636 SEO
Abstract
Recently, minimax optimization received renewed focus due to modern applications in machine learning, robust optimization, and reinforcement learning. The scale of these applications naturally leads to the use of first-order methods. However, the nonconvexities and nonconcavities present in these problems, prevents the application of typical Gradient Descent-Ascent, which is known to diverge even in bilinear problems. In this talk, we aim to review some current methods dealing with these nonconvexities in the presence of sufficient interaction between the two competing agents. Recently, it was shown that the Proximal Point Method (PPM) converges linearly for such family of nonconvex-nonconcave problems. We then study the convergence of a damped version of Extra-Gradient Method (EGM) which avoids potentially costly proximal computations, only relying on gradient evaluation. We show that EGM converges linearly for smooth minimax optimization problem satisfying the same nonconvex-nonconcave condition needed by PPM.
Feb. 9, 2022
Damek Davis :
4 p.m. in Zoom
Abstract
Nonsmooth optimization problems arising in practice, whether in signal processing, statistical estimation, or modern machine learning, tend to exhibit beneficial smooth substructure: their domains stratify into “active manifolds” of smooth variation, which common proximal algorithms “identify” in finite time. Identification then entails a transition to smooth dynamics, and permits the use of second-order information for acceleration. While identification is clearly useful algorithmically, empirical evidence suggests that even those algorithms that do not identify the active manifold in finite time—notably the subgradient method—are nonetheless affected by it. This work seeks to explain this phenomenon, asking: how do active manifolds impact the subgradient method in nonsmooth optimization?
To answer this question, our approach posits two algorithmically useful properties that link the behavior of the function on and off the active manifold. The first, which we call aiming, asserts that subgradients point towards the manifold. This property ensures that, though identification fails, the subgradient iterates steadily approach the manifold. The second property states that subgradients on and off the manifold are close in tangent directions up to a linear error. This property ensures that the nonsmooth dynamics of the subgradient method are well-approximated by their smooth shadow along the manifold, with a controlled error. We show that these properties, while not automatic, hold for a wide class of problems, including cone reducible/decomposable functions and generic semialgebraic problems. Moreover, we develop a thorough calculus, proving such properties are preserved under smooth deformations and spectral lifts.
We then turn to algorithmic consequences. Here, the two pillars—aiming and subgradient approximation—fully expose the smooth substructure of the problem, implying that the shadow of the (stochastic) subgradient method along the active manifold is precisely an inexact Riemannian gradient method with an implicit retraction. This viewpoint leads to several consequences that parallel results in smooth optimization, despite the nonsmoothness of the problem: local rates of convergence, asymptotic normality, and saddle point avoidance. The asymptotic normality results appear to be new even in the most classical setting of stochastic nonlinear programming. The results culminate in the following observation: the perturbed subgradient method on generic, Clarke regular semialgebraic problems, converges only to local minimizers.
Feb. 16, 2022
Omar Montassir :
4 p.m. in 636 SEO
Abstract
In this talk, we will discuss the problem of learning an adversarially robust predictor from i.i.d. training data. That is, learning a predictor that performs well not only on future i.i.d. test instances, but also on adversarial perturbations of these instances. There has been much empirical interest in this question, and in this talk we will take a theoretical perspective and see how it leads to practically relevant insights, including: the need to depart from a (robust) empirical risk minimization approach, and thinking of what kind of accesses and reductions can allow provable learning guarantees.
Based on joint work with Steve Hanneke and Nati Srebro.
March 2, 2022
Stoyan Dimitrov :
4 p.m. in 636 SEO
March 9, 2022
Mingquan Ye :
4 p.m. in 636 SEO
Abstract
We study distributed algorithms built around minor-based vertex sparsifiers, and give the first algorithm in the $\textsf{CONGEST}$ model for solving linear systems in graph Laplacian matrices to high accuracy. Our Laplacian solver has a round complexity of $O(n^{o(1)}(\sqrt{n}+D))$, and thus almost matches the lower bound of $\widetilde{\Omega}(\sqrt{n}+D)$, where $n$ is the number of nodes in the network and $D$ is its diameter.
We show that our distributed solver yields new sublinear round algorithms for several cornerstone problems in combinatorial optimization. This is achieved by leveraging the powerful algorithmic framework of Interior Point Methods (IPMs) and the Laplacian paradigm in the context of distributed graph algorithms, which entails numerically solving optimization problems on graphs via a series of Laplacian systems. Problems that benefit from our distributed algorithmic paradigm include exact mincost flow, negative weight shortest paths, maxflow, and bipartite matching on sparse directed graphs. For the maxflow problem, this is the first exact distributed algorithm that applies to directed graphs, while the previous work by [Ghaffari et al.~SICOMP'18] considered the approximate setting and works only for undirected graphs. For the mincost flow and the negative weight shortest path problems, our results constitute the first exact distributed algorithms running in a sublinear number of rounds. Given that the hybrid between IPMs and the Laplacian paradigm has proven useful for tackling numerous optimization problems in the centralized setting, we believe that our distributed solver will find future applications.
At the heart of our distributed Laplacian solver is the notion of spectral subspace sparsifiers of [Li, Schild FOCS'18]. We present a nontrivial distributed implementation of their construction by (i) giving a parallel variant of their algorithm that avoids the sampling of random spanning trees and uses approximate leverage scores instead, and (ii) showing that the algorithm still produces a high-quality subspace spectral sparsifier by carefully setting up and analyzing matrix martingales. Combining this vertex reduction recursively with both tree and elimination-based preconditioners leads to our algorithm for solving Laplacian systems. The construction of the elimination-based preconditioners is based on computing short random walks, and we introduce a new technique for reducing the congestion incurred by the simulation of these walks on weighted graphs.
March 16, 2022
Kevin Stangl :
3 p.m. in 612 SEO
Abstract
In this talk, I will discuss two theoretical models that capture two essential fairness in machine learning problems: the fairness-accuracy tradeoff with biased data and fairness in pipelines.
March 30, 2022
Jafar Jafarov :
3 p.m. in Zoom
Abstract
In the Correlation Clustering problem, we are given a graph with its edges labeled as "similar" and "dissimilar" by a noisy binary classifier, and the goal is to produce a clustering of the vertex set which matches with the edge labels as much as possible. Correlation Clustering has been mainly studied under two models where the input graph is (i) complete and unweighted, and (ii) arbitrary and weighted.
In this talk, we introduce a new model of Correlation Clustering that better captures real life instances. In this model the input graph is complete with bounded edge weights. We give an approximation algorithm and give a matching integrality gap instance. We examine the model under a $\ell_p$ objective which is a generalization of the standard Correlation Clustering objective, MinDisagree. We give an approximation algorithm and show an almost matching integrality gap for this objective.
April 6, 2022
Aaron Potechin :
4 p.m. in 612 SEO
Abstract
Graph matrices are a type of matrix whose entries are functions of a random input such as a $G(n,1/2)$ graph. Thus, graph matrices have entries which are random but are generally not independent. Mathematically, little is known about graph matrices except for rough norm bounds. While these rough norm bounds are sufficient for many applications, we can hope to analyze graph matrices more precisely.
Wigner’s Semicircle Law is a classic result in random matrix theory which says that if $M$ is an $n \times n$ symmetric matrix with random entries drawn independently from a distribution with mean 0 and variance 1 (and bounded moments) then as $n \to \infty$, the spectrum of the eigenvalues of $\frac{M}{\sqrt{n}}$ approaches $\frac{\sqrt{4-x^2}}{2\pi}$.
In this talk, I will describe an analogue of Wigner’s Semicircle Law for Z-shaped graph matrices. I will begin by introducing graph matrices and why they are useful. I will then give a derivation of Wigner’s Semicircle Law and describe how the analysis can be generalized to find the spectrum of the singular values of Z-shaped graph matrices. Finally, I will discuss our upcoming follow-up work on this topic and some open problems.
April 20, 2022
Aravind Reddy :
3 p.m. in 612 SEO
April 27, 2022
Keziah Naggita :
3 p.m. in Zoom
Abstract
The classical Perceptron algorithm provides a simple and elegant procedure for learning a linear classifier. In each step, the algorithm observes the sample's position and label and updates the current predictor accordingly if it makes a mistake. However, in presence of strategic agents that desire to be classified as positive and that are able to modify their position by a limited amount, the classifier may not be able to observe the true position of agents but rather a position where the agent pretends to be. Unlike the original setting with perfect knowledge of positions, in this situation the Perceptron algorithm fails to achieve its guarantees, and we illustrate examples with the predictor oscillating between two solutions forever, making an unbounded number of mistakes even though a perfect large-margin linear classifier exists. Our main contribution is providing a modified Perceptron-style algorithm which makes a bounded number of mistakes in presence of strategic agents with both $\ell_2$ and weighted $\ell_1$ manipulation costs. In our baseline model, knowledge of the manipulation costs (i.e., the extent to which an agent may manipulate) is assumed. In our most general model, we relax this assumption and provide an algorithm which learns and refines both the classifier and its cost estimates to achieve good mistake bounds even when manipulation costs are unknown.
Oct. 18, 2022
Aadirupa Saha :
1 p.m. in 636 SEO
Abstract
Customer statistics collected in several real-world systems have reflected that users often prefer eliciting their liking for a given pair of items, say (A,B), in terms of relative queries like: "Do you prefer Item A over B?", rather than their absolute counterparts: ``How much do you score items A and B on a scale of [0-10]?".
Drawing inspirations, in the search for a more effective feedback collection mechanism, this led to the famous formulation of Dueling Bandits (DB), which is a widely studied online learning framework for efficient information aggregation from relative / comparative feedback. However despite the novel objective, unfortunately, most of the existing DB techniques were limited only to simpler settings of finite decision spaces, and stochastic environments, which are unrealistic in practice.
In this talk, we will start with the basic problem formulations for DB and familiarize ourselves with some of the breakthrough results. Following this, will dive deep into a more practical framework of contextual dueling bandits (C-DB) where the goal of the learner is to make customized predictions based on the user contexts: We will see a new algorithmic approach that can efficiently achieve the optimal regret performance for this problem, resolving an open problem from Dudík et al. [COLT, 2015]. We will conclude the talk with some interesting open problems.
Oct. 18, 2023
Zihan Tan :
noon in 712 SEO
Abstract
Given a large graph G with a subset |T|=k of its vertices called terminals, a quality-q
flow sparsifier is a small graph H that contains T and preserves all multicommodity flows that
can be routed between terminals in T, to within factor q. The problem of constructing flow
sparsifiers with good (small) quality and (small) size has been a central problem in graph
compression for decades.
A natural approach of constructing O(1)-quality flow sparsifiers, which was adopted in most
previous constructions, is contraction. Andoni, Krauthgamer, and Gupta constructed a sketch
of size f(k,\eps) that stores all feasible multicommodity flows up to factor (1+\eps), raised the
question of constructing quality-(1+\eps) flow sparsifiers whose size only depends on k,\eps
(but not the number of vertices in the input graph G), and proposed a contraction-based
framework towards it using their sketch result. In this paper, we settle their question for
contraction-based flow sparsifiers, by showing that quality-(1+\eps) contraction-based flow
sparsifiers with size f(\eps) exist for all 5-terminal graphs, but not all 6-terminal graphs. Our
hardness result on 6-terminal graphs improves upon a recent hardness result by
Krauthgamer and Mosenzon on exact (quality-1) flow sparsifiers, for contraction-based
constructions. Our construction and proof utilize the notion of tight span in metric geometry.
This talk is based on joint work with Yu Chen.
April 22, 2024
Jake Maranzatto :
4 p.m. in 1227 SEO
Abstract
Recently Yates (2021) introduced the "version age of information" metric for studying communication networks where packets are sent between users via independent Poisson processes. For any network G, this produces a graph invariant vAoI(G) characterizing the worst-case version age of a node in the network. In this talk I'll discuss the combinatorics of the vAoI metric, and in particular how this metric varies as one interpolates between the empty graph and complete graph. I'll give the vAoI for the Erdos-Reyni random graph, random d-regular graph, and the family of complete bipartite graphs $K_{n,n-m}$. This is based on my work accepted to ISIT 2024.
April 24, 2024
Yuzhou Wang :
1 p.m. in 636 SEO
Abstract
We consider the algorithmic problem of finding large balanced independent sets in sparse random bipartite graphs, and more generally the problem of finding independent sets with specified proportions of vertices on each side of the bipartition. In a bipartite graph it is trivial to find an independent set of density at least half (take one of the partition classes). In contrast, in a random bipartite graph of average degree d, the largest balanced independent sets (containing equal number of vertices from each class) are typically of density (2 + o_d(1)) log d/d . Can we find such large balanced independent sets in these graphs efficiently? By utilizing the overlap gap property and the low-degree algorithmic framework, we prove that local and low-degree algorithms (even those that know the bipartition) cannot find balanced independent sets of density greater than (1 + ε) log d/d for any ε > 0 fixed and d large but constant. This factor 2 statistical–computational gap between what exists and what local algorithms can achieve is analogous to the gap for finding large independent sets in (non-bipartite) random graphs. Our results therefore suggest that this gap is pervasive in many models, and that hard computational problems can lurk inside otherwise tractable ones. A particularly striking aspect of the gap in bipartite graphs is that the algorithm achieving the lower bound is extremely simple and can be implemented as a 1-local algorithm and a degree-1 polynomial (a linear function).