H hierarchical comparability is identified as a sufficient structural condition on $\mathscr S$ under which the optimal complexity is nearly linear, $\widetilde \Theta(n/\epsilon^2)$, with pairwise query families as a canonical example.
Abstract
Motivated by learning from heterogeneous and overlapping data providers, we study a stylized model of distribution learning from restricted conditional samples. The goal is to learn an unknown distribution $p$ on a finite domain $[n]$. The learner is given a fixed family of queryable sets $\mathscr{S} \subseteq 2^{[n]}$, and each query to $S \in \mathscr{S}$ returns an independent sample from the conditional distribution $p(\cdot \mid S)$. Learnability is governed by the co-occurrence graph associated with $\mathscr{S}$: two domain elements are adjacent if they appear together in some queryable set. Pointwise consistency is achievable when this graph is connected on the target support. PAC learning requires more: it is possible when the co-occurrence graph is complete. The optimal sample complexity of PAC learning ranges from nearly linear to quadratic. Every query family with complete co-occurrence graph admits sample complexity $\widetilde O(n^2/\epsilon^2)$, and this bound is tight in the worst case. On the other hand, if $[n]$ is queryable then ordinary sampling improves the bound to $\Theta(n/\epsilon^2)$, and this cannot be improved further even if every set is queryable. More generally, we identify hierarchical comparabilityas a sufficient structural condition on $\mathscr S$ under which the optimal complexity is nearly linear, $\widetilde \Theta(n/\epsilon^2)$, with pairwise query families as a canonical example. Finally, the full range of polynomial rates between linear and quadratic is attainable: for every $\alpha \in (1,2)$, there exists a query family with optimal PAC rate $\widetilde \Theta(n^\alpha/\epsilon^2)$.
We study nearest neighbor search from the perspective of data-driven algorithm design: given a dataset $P \subset \mathbb{R}^d$ of size $n$ and sample access to a query distribution over $\mathbb{R}^d$, the goal is to learn a data structure optimized for queries drawn from that specific distribution. We focus on the class of balanced halfspace trees, which naturally abstracts space-partitioning frameworks like locality-sensitive hashing. Assuming Gaussian-like marginal conditions on the dataset and query distribution, we give an efficient algorithm that learns a tree achieving $o(nd)$ query time, provided that a perfect tree exists. At the core of our algorithmic approach is the balanced halfspace cut problem, where we are given a distribution over $\mathbb{R}^d \times \mathbb{R}^d$ and must find a balanced halfspace that minimizes the fraction of cut pairs. We prove that without distributional assumptions, finding the optimal balanced halfspace is NP-hard. To circumvent this computational barrier, we design an efficient improper learning algorithm: if the optimal halfspace cuts an $\alpha$ fraction of pairs, our algorithm outputs a balanced polynomial threshold function of degree $\tilde{O}(1/\varepsilon^2)$ that cuts at most an $O(\sqrt{\alpha+\varepsilon})$ fraction.
Sanjeev Khanna, Ashwin Padaki, Erik Waingarten· 0 citations
It is shown 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.
Edith Cohen, Haim Kaplan, Yishay Mansour et al.· 0 citations
This work refine the existing parameter estimation guarantees under the fatness assumption, improving the prior sample complexity to $O( \log n / \epsilon^2)$ for $\ell_\infty$-recovery, matching the untruncated minimax rate.
Interaction can reduce the required number of tests by a quadratic factor, but the apparent exponential branching of an interactive evaluation does not yield an exponential query advantage.
We study the problem of learning nearest-neighbor maps from adaptive queries, which is equivalent to the following problem of reconstructing a hidden set $H$ via a nearest-neighbor query oracle. Let $K \subset \mathbb{R}^d$ be a compact domain in a normed space $(\mathbb{R}^d,\| \cdot\|)$ and let $H \subset K$ be a hidden set of $n$ points. Upon querying $q \in K$, the oracle returns some $h \in H$ with minimum distance from $q$. How many queries are required to exactly recover $H$? Previous work has studied this question in specific domains, namely the Boolean hypercube and the $\ell_2$-unit sphere. We generalize previous work and prove the tight worst-case query complexity bound of $\Theta(n\kappa)$, where $\kappa$ is the kissing number of the underlying norm. In the Euclidean norm, obtaining tight asymptotic bounds on $\kappa$ is a significant open question, although it is known that $\kappa = \exp(\Theta(d))$. Our second set of results shows that an exponential dependence on $d$ is required even in natural Euclidean domains: $\exp(\Omega(d))$ queries are needed in the ball, even when $n=2$, and $n\exp(\Omega(d))$ queries are needed in the cone. Lastly, we prove a sharper upper bound in the Euclidean sphere. Here, $d$ can be replaced by $\min(n,d)$ via a dimension reduction preprocessing step. This is a randomized version of a procedure due to Prabhu-Woodruff (ICML 2024) where we improve the query complexity from $O(nd)$ to $O(\min(n,d))$. This reveals a striking contrast between the sphere and the ball: when $n = O(1)$, the sphere admits an $O(1)$ query algorithm, whereas the ball requires $\exp(\Omega(d))$.
We study the problem of estimating the number of edges in an undirected, unweighted graph using sublinear query access. We consider a query model that preserves the structure of Independent Set (IS) queries, but augments their output with a random certificate: given a vertex subset, the oracle returns a uniformly random edge from the induced subgraph if one exists, and returns null otherwise. Using this access, we give a randomized algorithm that outputs a $(1 \pm \varepsilon)$-approximation to the number of edges with constant success probability using $\widetilde{O}(\log^{2} m)$ queries. This implies an exponential separation from both standard IS queries and global random edge-sampling models: estimating the number of edges using standard IS queries require $\widetilde{\Theta}\!\left(\min\left\{\sqrt{m},\, \frac{n}{\sqrt{m}}\right\}\right)$ queries, while direct random edge-sample access requires $\widetilde{\Theta}(\sqrt{m})$ samples. Beyond separation in query complexity, our algorithm is output-sensitive: its query complexity is polylogarithmic in the number of edges in the graph. This aligns with the classical objective in group testing, where one seeks algorithms that are both worst-case optimal and instance-adaptive. Conceptually, our model connects group testing, the decision-versus-counting dichotomy, graph property testing, and the"power of a random certificate", and can be viewed as a structured form of conditional sampling of edges in graphs.
Debarshi Chanda, Buddha Dev Das, Arijit Ghosh et al.· 0 citations