Quarterly Theory Workshop: 2022 Junior Theorists Workshop

Synopsis:

Logistics

• Date: Thursday, Jan 5 & Friday, Jan 6, 2023
• Organizers: Ali Vakilian and Suprovat Ghoshal
• Location:  Mudd 3514  Northwestern University (Thursday) ; Toyota Technological Institute at Chicago (Friday)
• Registration: click here to register

Tentative Schedule (Central Time)

Thursday at NU:

• 9:00-9:25 – Breakfast
• 9:25-9:35 – Welcome Remarks
• 9:35-10:05 – Maryam Aliakbarpour Entropy estimation in constant space: an example of statistical inference in limited memory (Video)
  
• 10:05-10:35 – Clayton Thomas Strategyproofness-Exposing Mechanism Descriptions
• 10:35-11:00 – Coffee Break
• 11:00-11:30 – Ewin Tang Query-optimal estimation of unitary channels in diamond distance (Video)
• 11:30-12:00 – Yang Liu Discrepancy Minimization via a Self-Balancing Walk
• 12:00–1:00 – Lunch
• 1:00-1:30 – Zongchen Chen Revisiting Jerrum’s Metropolis Process for the Planted Clique Problem (Video)
• 1:30-2:00 – Robert Andrews  On Matrix Multiplication and Polynomial Identity Testing (Video)
• 2:00-2:30 – Coffee Break
• 2:30-3:00 – Lydia Zakynthinou Differentially Private Gaussian Mean Estimation with Connections to Robustness
• 3:00-3:30 – Min Jae Song Continuous LWE (Video)
• 3:30-4:00 – Coffee Break
•  Local Talks :
• 4:00 — 4:20 – Sami Davies  Faster Ford-Fulkerson via Predictive Flows (Video)
• 4:20 — 4:40 – Quanquan LiuDifferential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs (Video)
• 4:40 — 5:00 – Liren Shan Higher-Order Cheeger Inequality for Partitioning with Buffers (Video)

Friday at TTIC:

• 9:00-9:25 – Breakfast
• 9:25-9:35 – Welcome Remarks
• 9:35-10:05 – Roei Tell Non-black-box Derandomization: Avoiding Classical PRGs, Opening New Directions of Study
• 10:05-10:35 – Li Chen Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
• 10:35-11:00 – Coffee Break
• 11:00-11:30 – Jessica Sorrell Replicability in Learning
• 11:30-12 – Bhaskar Ray Chaudhury On the Computation of Competitive Equilibrium with Chores
• 12:00-2:00 – Lunch
• 2:00-2:30 – Tamalika Mukherjee How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity
• 2:30-3:00 – Mingda Qiao Stronger Calibration Lower Bounds via Sidestepping
• 3:00-3:30 – Coffee Break
•  Local talks 
• 3:30 — 3:50 – Omar Montasser  Boosting Barely Robust Learners
• 3:50 — 4:10 – Yiding Feng Batching and Optimal Multi-stage Bipartite Allocations

Titles and Abstracts

Speaker: Maryam Aliakbarpour
Title: Entropy estimation in constant space: an example of statistical inference in limited memory

Abstract: In this talk, we discuss how memory restrictions affect statistical inference. In particular, we focus on the problem of entropy estimation using only O(1) words of memory. Recent work of Acharya et al. (NeurIPS 2019) showed how to estimate the entropy of a distribution D over an alphabet of size k up to \epsilon additive error by streaming over (k/\epsilon^3)⋅polylog(1/\epsilon) i.i.d. samples and using O(1) words of memory. In our recent work, we give a new constant memory scheme that reduces the sample complexity to (k/\epsilon^2)⋅polylog(1/\epsilon). We conjecture that this is optimal up to polylog(1/\epsilon) factors.

Speaker: Clayton Thomas
Title: Strategyproofness-Exposing Mechanism Descriptions

Abstract: School districts in many cities employ school choice mechanisms, i.e., algorithms that produce a matching of students to schools on the basis of students’ reported preferences over the schools. A hallmark of these algorithms is that they are strategyproof: participants can never gain by misreporting their preferences. Alas, for the most popular and celebrated real-world matching mechanism Deferred Acceptance, strategyproofness is far from apparent from the traditional description of the algorithm, and instead requires an involved mathematical proof. Perhaps unsurprisingly, there is a growing body of evidence that participants in Deferred Acceptance attempt unsuccessfully to “game the system,” resulting in suboptimal matches.

In this talk, first I’ll present a hardness result: a formal sense in which, in contrast to other popular matching mechanisms, strategyproofness is hard to recognize from the traditional description of Deferred Acceptance, or anything remotely resembling this traditional description. Second, I’ll present a new, simple, strategyproofness-exposing description of Deferred Acceptance, which overcomes this hardness result by (among other things) describing only one student’s matched school at a time. Our new description emphasizes strategyproofness, the primary concern of the students reading the description, but this comes at a price: since our new description does not convey the full matching of all students, it does not convey the fact that no school is matched to more students than its capacity. In the full paper, we expand our hardness result to prove that this tradeoff is unavoidable for a broad class of possible mechanism descriptions, and we experimentally investigate in two simple settings how real participants respond to seeing descriptions analogous to our new description of Deferred Acceptance.

Based on joint work with Yannai A. Gonczarowski and Ori Heffetz.

Speaker: Ewin Tang
Title: Query-optimal estimation of unitary channels in diamond distance

Abstract: We will present a quantum algorithm to learn an unknown unitary channel acting on a d-dimensional qudit to diamond-norm error ε, using O(d²/ε) applications of the unknown channel and only one qudit. This improves over prior work by polynomial factors. We also show that Ω(d²/ε) applications are necessary, even if one has access to the inverse or controlled versions of the unknown unitary. Thus, our algorithm uses both the optimal number of qudits and the optimal number of applications. Based on joint work with Jeongwan Haah, Robin Kothari, and Ryan O’Donnell.

Speaker: Yang Liu
Title: Discrepancy Minimization via a Self-Balancing Walk

Abstract: We study discrepancy minimization for vectors in R^n under various settings. The main result is the analysis of a new simple random process in multiple dimensions through a comparison argument. As corollaries, we obtain bounds which are tight up to logarithmic factors for online vector balancing against oblivious adversaries, resolving several questions posed by Bansal, Jiang, Singla, and Sinha (STOC 2020), as well as a linear time algorithm for logarithmic bounds for the Komlós conjecture.

Speaker: Zongchen Chen
Title: Revisiting Jerrum’s Metropolis Process for the Planted Clique Problem

Abstract: Jerrum in 1992 (co-)introduced the planted clique model by proving the failure of the Metropolis process under worst-case initialization to recover any o(sqrt(n))-sized clique planted in the Erdos-Renyi graph G(n,1/2). This result is classically cited in the literature as the “first evidence” of the conjecture that the o(sqrt(n))-sized planted clique recovery is “algorithmically hard”. In this work, we show that the Metropolis process actually fails to work under worst-case initialization for any o(n)-sized planted clique; that is, the failure applies well beyond the sqrt(n) “conjectured algorithmic threshold”. Moreover we also prove, for a large number of temperature values, that the Metropolis process fails under “natural initializations” including the empty clique, resolving an open question posed by Jerrum in 1992. This is joint work with Elchanan Mossel and Ilias Zadik.

Speaker: Robert Andrews
Title:  On Matrix Multiplication and Polynomial Identity Testing

Abstract: Determining the complexity of matrix multiplication is a fundamental problem of theoretical computer science. It is popularly conjectured that ω, the matrix multiplication exponent, equals 2. If true, this conjecture would yield fast algorithms for a wide array of problems in linear algebra and beyond. If instead ω > 2, can the hardness of matrix multiplication be leveraged to design algorithms for other problems? In this talk, I will describe how lower bounds on ω can be used to make progress on derandomizing polynomial identity testing.

Speaker: Lydia Zakynthinou
Title: Differentially Private Gaussian Mean Estimation with Connections to Robustness

Abstract: Gaussian mean estimation is a fundamental problem in statistics, where, given i.i.d. samples from a high-dimensional Gaussian with unknown and unrestricted parameters, we aim to find an accurate estimator of the mean of the distribution in Mahalanobis distance. To protect the privacy of the individuals who participate in the dataset, we seek statistical estimators which satisfy the standard criterion of differential privacy, which makes our problem more challenging in high dimensions. In this talk, I will present a differentially private Gaussian mean estimator which achieves optimal sample complexity, which builds on standard robust statistics. Then we will discuss how robust statistics have driven recent advances in differentially private statistical estimation, including a new black-box reduction which turns robust algorithms into differentially private ones.

Based on joint works with Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman, and Hilal Asi.

Speaker: Min Jae Song
Title: Continuous LWE

Abstract:  Efficiently extracting useful signals from high-dimensional data is a major challenge in machine learning (ML). When a statistical inference task, known to be possible information-theoretically, persistently eludes computationally efficient learning algorithms, the statistician is faced with a perplexing question: is the failure due to lack of algorithmic ingenuity or is the task inherently hard?

My research attempts to answer such questions by establishing connections between lattice-based cryptography and ML. The cross-fertilization of ideas between the two fields has led to advances in understanding the computational complexity of several statistical inference problems, providing answers of both positive and negative nature.

This talk will focus on the negative results, in particular the Continuous Learning with Errors (CLWE) problem which lies at the center of this fruitful connection. CLWE can be seen as a continuous variant of the well-known Learning with Errors (LWE) problem from lattice-based cryptography. As hinted by the close resemblance to LWE, CLWE also enjoys average-case hardness. This has several implications for ML. For example, it shows that estimating the density of Gaussian mixtures is computationally hard. Moreover, it gives rise to “backdoored” Gaussian distributions which have recently been used to plant undetectable backdoors in ML models (Goldwasser et al., 2022).

Speaker: Sami Davies
Title: Faster Ford-Fulkerson via Predictive Flows

Abstract: Recent work has shown that leveraging learned predictions can improve the running time of algorithms for bipartite matching and similar combinatorial problems. In this work we build on this idea to improve the performance of the widely used Ford-Fulkerson algorithm for computing maximum flows by seeding Ford-Fulkerson with predicted flows. Predicted flows may not be feasible, and we provide a fast algorithm to project the prediction to a feasible state for the Ford- Fulkerson algorithm, from which one can ultimately obtain an optimal solution.

Speaker: Roei Tell
Title: Non-black-box Derandomization: Avoiding Classical PRGs, Opening New Directions of Study

Abstract: The textbook paradigm in the area of derandomization uses pseudorandom generators (PRGs) whose output looks random to all efficient observers. But do we really need such strong objects?

In this talk we’ll see how to achieve derandomization without such PRGs, replacing the textbook paradigm with an alternative general approach that carefully tailors pseudorandom choices to each individual observer. The tailoring of pseudorandom choices works in a non-black-box way, extracting information from the code of the particular observer.

This non-black-box derandomization relies on inherently weaker assumptions (compared to the textbook paradigm that relies on circuit lower bounds), and opens the door to a host of applications. Among the applications are the question of fully characterizing derandomization in terms of hardness assumptions; and free lunch theorems in various settings, in which we can eliminate randomness at essentially no observable cost.

The main part of the talk is based on a joint work with Lijie Chen (UC Berkeley).

 

Speaker: Li Chen
Title: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

Abstract: We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities in almost-linear time. Our algorithm builds the flow through a sequence of m^{1+o(1)} approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized almost-constant time using a new dynamic graph data structure.

Our framework extends to algorithms running in almost-linear time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling, p-norm flows, and p-norm isotonic regression on arbitrary directed acyclic graphs.

joint work with Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva.

Speaker: Jessica Sorrell
Title: Replicability in Learning

Abstract: Replicability is vital to ensuring scientific conclusions are reliable, but failures of replicability have been a major issue in nearly all scientific areas of study in recent decades. A key issue underlying the replicability crisis is the explosion of methods for data generation, screening, testing, and analysis, where, crucially, only the combinations producing the most significant results are reported. Such practices (also known as p-hacking, data dredging, and researcher degrees of freedom) can lead to erroneous findings that appear to be significant, but that don’t hold up when other researchers attempt to replicate them.

In this talk, we introduce a new notion of replicability for randomized algorithms. This notion ensures that with high probability, an algorithm returns exactly the same output when run with two samples from the same distribution. Despite the exceedingly strong demand of replicability, there are efficient replicable algorithms for several fundamental problems in statistics and learning, including statistical queries, approximate heavy-hitters, medians, and halfspaces. We also discuss connections to other well-studied notions of algorithmic stability, such as differential privacy.

This talk is based on work with Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Satchit Sivakumar.

Speaker: Bhaskar Ray Chaudhury
Title: On the Computation of Competitive Equilibrium with Chores

Abstract: Competitive Equilibrium with Equal Incomes (CEEI) is a classical notion in microeconomics, where given a set of agents with preferences over items, the goal is to determine prices for the items at which demand equals supply. This concept has found tremendous applications in fair resource allocation, stock-markets, and ridesharing.

We study the computational aspects of determining a CEEI when agents incur disutility/ cost from the set of items (we call the items chores). This setting has recently received attention due to its applications in fair division. However, CE with chores, exhibit far less structure than CE with goods, and is conjectured to be computationally intractable in the seminal work of Bogomolnaia, Moulin, Sandomirskiy, and Yanovskaya.

In contrast to the above conjecture, we present two polynomial time algorithmic solutions to the computation of approximate CEEI. At first, we give a continuous optimization based algorithm that aims to find the approximate KKT points of a non-convex program, which are shown to correspond to an approximate CEEI. Thereafter, we present a combinatorial algorithm, simulating intuitive pricing dynamics (adjustments of prices and allocations, based on demand and supply) that finally converges to an approximate CEEI.

Speaker: Tamalika Mukherjee
Title: How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity

Abstract: We develop a framework for efficiently transforming certain approximation algorithms into differentially-private variants, in a black-box manner. Our results focus on algorithms A that output an approximation to a function f of the form (1−a)f(x)−k<=A(x)<=(1+a)f(x)+k, where 0<=a <1 is a parameter that can be“tuned” to small-enough values while incurring only a poly blowup in the running time/space. We show that such algorithms can be made DP without sacrificing accuracy, as long as the function f has small global sensitivity. We achieve these results by applying the smooth sensitivity framework developed by Nissim, Raskhodnikova, and Smith (STOC 2007).

Our framework naturally applies to transform non-private FPRAS (resp. FPTAS) algorithms into (ϵ,δ)-DP (resp. ϵ-DP) approximation algorithms. We apply our framework in the context of sublinear-time and sublinear-space algorithms, while preserving the nature of the algorithm in meaningful ranges of the parameters. Our results include the first (to the best of our knowledge) (ϵ,δ)-edge DP sublinear-time algorithm for estimating the number of triangles, the number of connected components, and the weight of a MST of a graph, as well as a more efficient algorithm (while sacrificing pure DP in contrast to previous results) for estimating the average degree of a graph. In the area of streaming algorithms, our results include (ϵ,δ)-DP algorithms for estimating L_p-norms, distinct elements, and weighted MST for both insertion-only and turnstile streams. Our transformation also provides a private version of the smooth histogram framework, which is commonly used for converting streaming algorithms into sliding window variants, and achieves a multiplicative approximation to many problems, such as estimating L_p-norms, distinct elements, and the length of the longest increasing subsequence.

Speaker: Mingda Qiao
Title: Stronger Calibration Lower Bounds via Sidestepping

Abstract: We study a model of online binary prediction: A forecaster observes a sequence of T bits one by one and, before each bit is revealed, predicts the “probability” that the bit is 1. The forecaster is called “well-calibrated” if, for each value p, among the timesteps when probability p was predicted, exactly a p-fraction of those bits were 1. The calibration error quantifies the extent to which the forecaster deviates from being well-calibrated.

Despite being a clean and natural problem, the optimal calibration error remained largely open: It was shown by Foster and Vohra (1998) that an O(T^{2/3}) error is achievable, whereas there is a trivial lower bound of Omega(T^{1/2}). In this talk, I will present the first improvement over this T^{1/2} rate on the lower bound side in a joint work with Gregory Valiant (link to paper: https://arxiv.org/abs/2012.03454).

Speaker: Omar Montasser
Title: Boosting Barely Robust Learners

Abstract: Despite extraordinary progress, current machine learning systems have been shown to be brittle against adversarial examples: seemingly innocuous but carefully crafted perturbations of test examples that cause machine learning predictors to miss-classify. In this talk, we will explore when and how we can boost robustness to adversarial examples. We will present an oracle-efficient algorithm for boosting the adversarial robustness of barely-robust learners. Barely-robust learning algorithms learn predictors that are robust only on a small fraction β≪1 of the data distribution. Our proposed notion of barely-robust learning requires robustness with respect to a “larger” perturbation set; which we show is necessary for strongly-robust learning and that weaker relaxations are not sufficient for strongly-robust learning. This reveals a qualitative and quantitative equivalence between two seemingly unrelated problems: strongly-robust learning and barely-robust learning. Our results reveal an interesting landscape for boosting robustness with connections to classical pioneering work on boosting accuracy.