Shay Sapir

Edith Cohen, Haim Kaplan, Yishay Mansour et al.

The Adaptive Data Analysis (ADA) problem formalizes the challenge of preventing false discovery and overfitting when a dataset is repeatedly reused. Formally, our input is a dataset containing $n$ i.i.d. samples from an unknown distribution $\mathcal{P}$ over a domain $\mathcal{X}$, and our goal is to answer a sequence of $k$ adaptively chosen statistical queries with respect to $\mathcal{P}$. The main question is how many queries we can support (i.e., how large $k$ can be), primarily as a function of the number of samples $n$. This question has been intensively studied and is relatively well-understood for randomized mechanisms: there are computationally efficient mechanisms that support $k \approx n^2$ queries, and no computationally efficient mechanism can answer $k \gg n^2$ queries. In this paper, we address a fundamental question: is randomness necessary for ADA? Despite a decade of work on ADA, this question remains open. A folklore observation dating back to the initial works on ADA is that randomness is not necessary when the analyst is computationally bounded. Yet, the necessity of randomness against computationally unbounded analysts has remained elusive. Our main contribution resolves this gap in the information-theoretic Random Oracle model. Perhaps surprisingly, we show that randomness is strictly necessary to answer a non-trivial number of adaptive queries: when the analyst is unbounded, any deterministic mechanism can be forced to fail after just $k = \tilde{O} (n)$ queries.

Haim Kaplan, Shay Sapir, Uri Stemmer

We analyze a balls-and-bins game against an adaptive adversary that sequentially deletes bins. Starting with $n$ balls distributed across $n$ bins, the adversary deletes a bin in each step, forcing the algorithm to redistribute its balls to surviving bins. We prove that after $n/2$ rounds, uniform random redistribution yields optimal $O(n)$ recourse and $O(\frac{\log n}{\log \log n})$ maximum load. Furthermore, we show that applying the ``power of two choices'' reduces the maximum load to $O(\log \log n)$ while maintaining linear recourse. We also consider a variation of this game where the balls from the deleted bin are partitioned evenly among $d \ll n$ random bins rather than being redistributed independently. We demonstrate that keeping the balls together ($d=1$), which gives small maximum load and recourse against an oblivious adversary, fails against an adaptive adversary. Nevertheless, we show that splitting the balls into just two groups ($d=2$) is sufficient to recover linear recourse and efficient load balancing in the adaptive setting.

Jie Gao, Rajesh Jayaram, Benedikt Kolbe et al.

Randomized dimensionality reduction is a widely-used algorithmic technique for speeding up large-scale Euclidean optimization problems. In this paper, we study dimension reduction for a variety of maximization problems, including max-matching, max-spanning tree, max TSP, as well as various measures for dataset diversity. For these problems, we show that the effect of dimension reduction is intimately tied to the \emph{doubling dimension} $λ_X$ of the underlying dataset $X$ -- a quantity measuring intrinsic dimensionality of point sets. Specifically, we prove that a target dimension of $O(λ_X)$ suffices to approximately preserve the value of any near-optimal solution,which we also show is necessary for some of these problems. This is in contrast to classical dimension reduction results, whose dependence increases with the dataset size $|X|$. We also provide empirical results validating the quality of solutions found in the projected space, as well as speedups due to dimensionality reduction.