FOCS'23 Workshop: Exploring the Frontiers of Adaptive Robustness

A streaming algorithm is adversarially robust if it retains its performance guarantees over a sequence of updates that are generated adaptively by an adversary that observes the previous outputs of the algorithm. Although deterministic algorithms are inherently robust, many central streaming problems provably require randomization to achieve sublinear space. Since randomized algorithms are not inherently robust to adaptive updates, this raises the question of whether sublinear space adversarially robust algorithms exist for many streaming tasks. In this talk, we will discuss recent results and central challenges for the adversarially robust streaming model, as well as directions for future work.

The performance of randomized algorithms can be considered in both adaptive and non-adaptive settings. Adaptive settings come into play when the algorithm is part of a system with feedback or when an adversary attempts to construct an input that causes the algorithm to fail. Recent research in the past decade has led to a black-box reduction, allowing k replicas of an algorithm designed for non-adaptive inputs to handle a quadratic number of adaptive inputs. However, it is important to understand how robust common practical sketch structures are to adaptive inputs and whether we can improve upon the black-box method. We investigate these questions for CountSketch, a widely-used sketching method.

(Joint work with Xin Lyu, Jelani Nelson, Tamas Sarlos, Moshe Shechner, and Uri Stemmer)

There has been a flurry of recent literature studying streaming algorithms for which the input stream is chosen adaptively by a black-box adversary who observes the output of the streaming algorithm at each time step. However, these algorithms fail when the adversary has access to the internal state of the algorithm, rather than just the output of the algorithm. We study streaming algorithms in the white-box adversarial model, where the stream is chosen adaptively by an adversary who observes the entire internal state of the algorithm at each time step. We show that nontrivial algorithms are still possible.

In the adversarial streaming model, an adversary gives an algorithm a sequence of adaptively chosen updates u_1,...,u_n as a data stream. The goal of the algorithm is to compute or approximate some predetermined function for every prefix of the adversarial stream, but the adversary may generate future updates based on previous outputs of the algorithm. In particular, the adversary may gradually learn the random bits internally used by an algorithm to manipulate dependencies in the input. We introduce adversarially robust streaming algorithms for central machine learning and algorithmic tasks, such as regression and clustering, as well as their more general counterparts, subspace embedding, low-rank approximation, and coreset construction. Our results are based on a simple, but powerful, observation that sampling based algorithms give rise to adversarial robustness which is in contrast to sketching based algorithms, which are very prevalent in the streaming literature but suffer from adversarial attacks. In addition, we show that the well-known merge and reduce paradigm in streaming is adversarially robust. Since the merge and reduce paradigm defines coreset constructions, we thus obtain robust algorithms for k-means, k-median, k-center, Bregman clustering, projective clustering, principal component analysis (PCA) and non-negative matrix factorization.

Ensuring that analyses performed on a dataset are representative of the entire population is one of the central problems in statistics. Most classical techniques assume that the dataset is independent of the analyst's query and break down in the common setting where a dataset is reused for multiple, adaptively chosen, queries. This problem of adaptive data analysis was formalized in the seminal works of Dwork et al. (STOC, 2015) and Hardt and Ullman (FOCS, 2014).

We identify a remarkably simple set of assumptions under which the queries will continue to be representative even when chosen adaptively: The only requirements are that each query takes as input a random subsample and outputs few bits. This result shows that the noise inherent in subsampling is sufficient to guarantee that query responses generalize. The simplicity of this subsampling-based framework allows it to model a variety of real-world scenarios not covered by prior work. We furthermore demonstrate the utility of this framework by designing a state of the art and extremely simple mechanism for answering statistical queries.

We introduce difference estimators for data stream computation, which provide approximations to F(v)-F(u) for frequency vectors v,u and a given function F. We show how to use such estimators to carefully trade error for memory in an iterative manner. We give the first difference estimators for the frequency moments F_p for p between 0 and 2, as well as for integers p>2. Using these, we resolve a number of central open questions in adversarial robust streaming and sliding window models.

For both models, we obtain algorithms for norm estimation whose dependence on epsilon is 1/epsilon^2, which shows, up to logarithmic factors, that there is no overhead over the standard insertion-only data stream model for these problems.

(Joint work with David P. Woodruff)

In recent years, there has been a growing interest in solving various graph coloring problems in the streaming model. The algorithms in this line of work are all crucially randomized, raising the natural question of how important a role randomization plays in streaming graph coloring. In this talk, we review the recent progress on this question, including fully settling the complexity of deterministic algorithms, and a three-way separation between power of randomized algorithms, adversarially robust algorithms, and deterministic algorithms.