Schedule

Abstract: We propose a new algorithm ProjectiveGeometryResponse (PGR) for locally differentially private (LDP) frequency estimation. For a universe size of k and with n users, our eps-LDP algorithm has communication cost [log k] bits in the private coin setting and eps*log e+O(1) in the public coin setting, and has computation cost O(n+k*exp(eps)* log k) for the server to approximately reconstruct the frequency histogram, while achieving optimal privacy/utility tradeoff, including optimality of the leading constant factor. Our empirical evaluation shows a speedup of over 50x over PI-RAPPOR (Feldman and Talwar; 2021), while using approximately 75x less memory for practically relevant parameter settings. In addition, the running time of our algorithm is within an order of magnitude of HadamardResponse (Acharya, Sun, and Zhang; 2019) and RecursiveHadamardResponse (Chen, Kairouz, and Ozgur; 2020) which have significantly worse reconstruction error. Our new algorithm is based on using Projective Planes over a finite field to define a small collection of sets that are close to being pairwise independent and a dynamic programming algorithm for approximate histogram reconstruction on the server side. We also give an extension of PGR, which we call HybridProjectiveGeometryResponse, that allows trading off computation time with utility smoothly.

Abstract: This talk is about a polynomial time algorithm to recover planted cliques in the semirandom model introduced by Feige and Kilian in 1998. The previous best algorithms for this model succeed if the planted clique is of size at least n^{2/3} in a graph with n vertices. Our algorithms work for planted cliques of a size approaching n^{1/2} -- the information-theoretic threshold in the semirandom model and the conjectured computational threshold even in the easier fully-random model. The result nearly resolves open questions of Feige and Steinhardt.

Our algorithms rely on a new conceptual connection that translates certificates of upper bounds on biclique numbers in \emph{unbalanced} bipartite \Erdos--\Renyi random graphs into algorithms for semi-random planted cliques. The previous best guarantees for semi-random planted cliques (similar to the fully-random version) correspond to basic SDP relaxations of biclique numbers. We construct an SDP lower bound that shows that the \(n^{2/3}\) threshold in prior works is in fact an inherent limitation of these spectral relaxations.

Our key innovation is a new geometric certificate for biclique numbers that can be formalized in a higher constant degree sum-of-squares proof system.

Joint work with Rares Buhai (ETH Zurich) and David Steurer (ETH Zurich).

Abstract: Two complementary facets of the online bipartite matching problem are discussed.

(1) For numerous online bipartite matching problems, such as edge-weighted matching and matching under two-sided vertex arrivals, state-of-the-art fractional algorithms outperform their randomized integral counterparts. Thus, a natural question is whether we can achieve lossless online rounding of fractional solutions in this setting. Even though lossless online rounding is impossible in general, randomized algorithms do induce fractional algorithms of the same competitive ratio, which by definition are losslessly roundable online. This motivates the addition of constraints that decrease the ``online integrality gap'', thus allowing for lossless online rounding. We characterize a set of non-convex constraints which allow for such lossless online rounding and allow for better competitive ratios than yielded by deterministic algorithms.

(2) In a different vein, we study the problem of rounding fractional bipartite matchings in online settings. We assume that a fractional solution is already generated for us online by a black box (via a fractional algorithm, or some machine-learned advice) and provided as part of the input, which we then wish to round. We provide improved bounds on the rounding ratio and discuss several applications.

Based on joint papers with Niv Buchbinder, Aravind Srinivasan, and David Wajc.

Abstract: The paging and the k-server problems are cornerstone problems studied in the online setting, and are reasonably well-understood for almost three decades. The k-server problem concerns moving k identical servers on a metric space to serve requests: in each round a request is presented at a point on a metric space, and it must be served by moving a server to the requested point (unless a server is already present there). The objective is to minimize the total movement of the servers. The paging problem is essentially the k-server problem on a uniform metric space.

A natural variant of the k-server problem is the weighted k-server problem, where the servers are distinct and the contribution of a server to the overall cost is its weight times the distance it travels. Surprisingly, this innocuous-looking introduction of weights makes the problem incredibly challenging. Until recently, even on uniform metric spaces, no non-trivial bounds were known on the randomized competitive ratio, in spite of a triply exponential gap between the obvious upper and lower bounds. In this talk, I will survey the prominent results on the weighted k-server problem, and in particular, discuss a recent doubly exponential improvement in the lower bound on the randomized competitive ratio.

Abstract: List update is one of the most fundamental problems in online algorithms and competitive analysis. The famous algorithm "Move to Front" was analyzed by Sleator and Tarjan who showed that this algorithm is 2-competitive. While this bound is excellent, the total cost of the algorithm might be large. Compared to the optimal solution the algorithm performs extremely well, however the resulting cost of its solution may be large. For example, if we need to access the last half of the elements of the list the cost would be quadratic in the length of the list (rather than linear). This suggests considering the problem wherein each request does not need to be served immediately but rather before some deadline (i.e., each request has a corresponding arbitrary time window) which we will refer to as List Update with Time Windows. Adding this flexibility may significantly improve the cost of the optimal algorithm and thus may require a new online algorithm. In particular, "Move to Front" fails in this case (e.g., many requests arrive on different keys with overlap windows). In this work we design and analyze an $O(1)$ competitive algorithm for the List Update with Time Windows problem. Interestingly, the analysis is significantly more complicated than the analysis of "Move to Front" since, in particular, the set of requests that are served until a certain time may differ between the online algorithm and the optimal one. Hence, a novel potential function is required.

Joint work with Shahar Lewkowicz and Danny Vainstein.

Abstract: We study the problem of designing online algorithms given advice about the input. While prior work had focused on deterministic advice, we only assume distributional access to the instances of interest, and the goal is to learn a competitive algorithm given access to i.i.d. samples. We aim to be competitive against an adversary with prior knowledge of the distribution, while also performing well against worst-case inputs.

We focus on the classical online problems of ski rental and prophet-inequalities, and provide sample complexity bounds for the underlying learning tasks. First, we point out that for general distributions it is information-theoretically impossible to beat the worst-case competitive-ratio with any finite sample size. As our main contribution, we establish strong positive results for well behaved distributions. Specifically, for the broad class of log-concave distributions, we show that poly(1/epsilon) samples suffice to obtain (1 +epsilon)-competitive ratio. Finally, we show that this sample upper bound is close to the best possible, even for very simple classes of distributions.

Abstract: We give a polynomial-time algorithm for online covering IPs with a competitive ratio of O(log mn) when the constraints are revealed in random order, essentially matching the best possible offline bound of O(log n) and circumventing the Ω(log m log n) lower bound known in adversarial order. We then use this result to give an O(log mn) competitive algorithm for the prophet version of this problem, where constraints are sampled from a sequence of known distributions (in fact, our algorithm works even when only a single sample from each of the distributions is given). Since our algorithm is universal, as a byproduct we establish that only O(n) samples are necessary to build a universal map for online covering IPs with competitive ratio O(log mn) on input sequences of length n.

This talk is based on joint work with Anupam Gupta and Gregory Kehne, the first half of which appeared at FOCS 2021.

Abstract: In this talk we will consider the number of predictions used by a learning-augmented algorithm as a resource measure. Focusing on two problems---online learning in the regret setting and online caching in the competitive-ratio setting---we show that a sublinear number of predictions suffices to achieve non-trivial performance gains.

Abstract: Vector norms play a fundamental role in computer science and optimization, so there is an ongoing effort to generalize existing algorithms to settings beyond L_\infty and L_p norms. We show that many online and bandit applications for general norms admit good algorithms as long as the norm can be approximated by a function that is “gradient-stable”, a notion that we introduce. Roughly it says that the gradient of the function should not drastically decrease (multiplicatively) in any component as we increase the input vector. We prove that several families of norms, including all monotone symmetric norms, admit a gradient-stable approximation, giving us good online and bandit algorithms for these norm families. In particular, we give log^2 (dimension)-competitive algorithms for the symmetric norm generalizations of Online Load Balancing and Bandits with Knapsacks.

This is based on a joint work with Thomas Kesselheim and Marco Molinaro that will appear in SODA 2023.

Abstract: Online optimization refers to solving problems where an initially unknown input is revealed incrementally, and irrevocable decisions must be made not knowing future requests. The assumption of not having any prior knowledge about future requests seems overly pessimistic. Given the success of machine-learning methods and data-driven applications, one may expect to have access to predictions about future requests. However, simply trusting them might lead to very poor solutions as these predictions come with no quality guarantee. In this talk we present recent developments in the young line of research that integrates such error-prone predictions into algorithm design to break through worst case barriers. We discuss algorithmic challenges with a focus on online routing and network design. We present algorithms with performance guarantees depending on a novel error metric.

Joint work with Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti-Spaccamela, Leen Stougie, and Michelle Sweering (NeurIPS 2022).

Abstract: Stochastic gradient descent (SGD) is the workhorse of modern machine learning. While SGD has been thoroughly analyzed for independent data and tight finite time guarantees are known, its finite sample performance with dependent data has not been as thoroughly analyzed. In this talk, we will consider SGD-style algorithms for two problems where the data is not independent but rather comes from a Markov chain: learning dynamical systems and Q-learning for reinforcement learning. While vanilla SGD is biased and does not converge to the correct solution for these problems, we show that SGD along with "reverse experience replay" can efficiently find the optimal solutions. Joint work with Naman Agarwal, Syomantak Chaudhuri, Suhas Kowshik, Dheeraj Nagaraj, and Praneeth Netrapalli.

Abstract: We propose a model for online graph problems where algorithms are given access to an oracle that predicts (e.g., based on past data) the degrees of nodes in the graph. Within this model, we study the classic problem of online bipartite matching, and a natural greedy matching algorithm called MinPredictedDegree, which uses predictions of the degrees of offline nodes. For the bipartite version of a stochastic graph model due to Chung, Lu, and Vu where the expected values of the offline degrees are known and used as predictions, we show that MinPredictedDegree stochastically dominates any other online algorithm, i.e., it is optimal for graphs drawn from this model. Since the "symmetric" version of the model, where all online nodes are identical, is a special case of the well-studied "known i.i.d. model", it follows that the competitive ratio of MinPredictedDegree on such inputs is at least 0.7299. For the special case of graphs with power law degree distributions, we show that MinPredictedDegree frequently produces matchings almost as large as the true maximum matching on such graphs. We complement these results with an extensive empirical evaluation showing that MinPredictedDegree compares favorably to state-of-the-art online algorithms for online matching.

Abstract: I will talk about some of my recent work on fast algorithms for linear algebraic primitives tailored for distance matrices, a common family of dense matrices arising in many applications. The main upper bound results are linear time algorithms for computing matrix-vector products for some distance functions, including the L1 metric, which only uses the underlying dataset, rather than constructing the distance matrix. Efficient matrix-vector products automatically have many downstream applications (think power method or iterative methods), and many recent works have nailed down the complexity of various linear algebraic tasks, such as low-rank approximation, in terms of the number of matrix-vector queries required. The upper bound results are complemented by lower bounds, including a conditional nearly quadratic lower bound for any algorithm which computes a matrix-vector product for the L_infinity distance matrix on a set of n points, showing a separation between the L1 and L_infinity cases. Time permitting, I will also talk about constructing approximate L2 distance matrices in time faster than the bound implied by the Johnson-Lindenstrauss lemma. This is joint work with Piotr Indyk.

Abstract: We establish novel techniques to analyze algorithms in the smoothed analysis model for online decision making. In this model, at each step, an adversary chooses the input from distribution with density bounded above by the uniform distribution. Crucially, these techniques hold for adaptive adversaries that can choose distributions based on the decisions of the algorithm and the previous realizations of the inputs. Our technique effectively reduces the setting of adaptive adversaries to the simpler oblivious adversaries. The main application is to show that, in this model, online learning is as easy as offline learning. That is, we show that the regret against smoothed adversaries is captured by the offline complexity measure, VC dimension. Furthermore, we design efficient algorithms for online learning, circumventing impossibility results in the worst case. Based on joint works with Nika Haghtalab, Yanjun Han, Tim Roughgarden and Kunhe Yang.

Abstract: We study the stochastic score classification problem. There are several binary tests, where each test i is associated with a probability p_i of being positive and a cost c_i. The score of an outcome is a weighted sum of all positive tests, and the range of possible scores is partitioned into intervals corresponding to different classes. The goal is to perform tests sequentially (and possibly adaptively) so as to identify the class at the minimum expected cost. We provide the first constant-factor approximation algorithm for this problem, which improves over the previously-known logarithmic approximation ratio. Moreover, our algorithm is non-adaptive: it just involves performing tests in a fixed order until the class is identified. We also perform computational experiments that demonstrate the practical performance of our algorithm for score classification. We observe that, for most instances, the cost of our algorithm is within 50% of an information-theoretic lower bound on the optimal value.

Abstract: We consider the online unrelated-machine load balancing problem with recourse, where the algorithm is allowed to re-assign prior jobs. We give a (2 + 𝜖)-competitive algorithm for the problem with 𝑂𝜖 (log𝑛) amortized recourse per job. This is the first 𝑂(1)-competitive algorithm for the problem with reasonable recourse, and the competitive ratio nearly matches the long-standing best-known offline approximation guarantee. We also show an 𝑂(log log𝑛/log log log𝑛)-competitive algorithm for the problem with 𝑂(1) amortized recourse. The best-known bounds from prior work are 𝑂(log log𝑛)-competitive algorithms with 𝑂(1) amortized recourse, for the special case of the restricted assignment model. Along the way, we design an algorithm for the online generalized network flow problem (also known as network flow problem with gains) with recourse. In the problem, any edge 𝑢𝑣 in the network has a gain parameter 𝛾𝑢𝑣 > 0 and 𝜃-units of flow sent across 𝑢𝑣 from 𝑢’s side becomes 𝛾𝑢𝑣𝜃 units of flow on the 𝑣’th side. In the online problem, there is one sink, and sources come one by one. Upon arrival of a source, we need to send 1 unit flow from the source. A recourse occurs if we change the flow value of an edge. We give an online algorithm for the problem with recourse at most 𝑂(1/𝜖) times the optimum cost for the instance with capacities scaled by 1 1+𝜖 . The (1 + 𝜖)-factor improves upon the corresponding (2 + 𝜖)-factor of prior methods, which only work for the ordinary network flow problem. As an immediate corollary, we also give an improved algorithm for the online 𝑏-matching problem with reassignment costs.

Abstract: We study fully-dynamic multi-dimensional vector scheduling problem with recourse. The adversary presents a stream of $n$ job insertions and deletions, where each job $j$ is a vector in $\mathbb{R}^d_{\geq 0}$. In the vector scheduling problem, the algorithm must maintain an assignment of the active jobs to $m$ identical machines to minimize the makespan (maximum load on any dimension on any machine). The algorithm is allowed to change the assignment from time to time, with the secondary objective of minimizing the amortized recourse, which is the average cardinality of the change of the assignment per update to the instance.

We give a simple randomized algorithm with an $O(1)$ amortized recourse and an $O(\log d/\log \log d)$ competitive ratio against oblivious adversaries.

The main challenge is to determine when and how to migrate jobs to maintain competitive solutions. Our central idea is that for each job, we make these decisions based only on the active set of jobs that are `earlier' than this job in some ordering $\prec$ of the jobs.