Optimal Hypothesis Selection in (Almost) Linear Time

Thank you for your feedback.

In response to your question, there is no explicit lower bound for the time complexity of this problem. As you mentioned, it is possible that an algorithm could exist with a time complexity of just $\Theta(n + s)$. However, for algorithms that operate by querying the probabilities of various sets according to an unknown distribution $P$—such as querying semi-distances or similar concepts, as many previous algorithms have done—we speculate that $\Theta(n)$ queries to the semi-distances are both necessary and sufficient. This would result in an overall time complexity of $\Omega(n \cdot s)$. We will clarify this in the future versions of our paper.

Evidence suggesting that $O(n)$ queries might be sufficient comes from the upper bound of [MS08]. They demonstrated that there exist $O(n)$ sets to query, whose responses are sufficient to solve the problem. In their work, these sets and the order in which to query them are determined through an exponential time preprocessing step over the class $\mathcal{H}$. It would be valuable to explore whether this problem can be solved with $\Theta(n)$ queries without relying on the preprocessing step.

Thank you for your feedback. We will include the motivations and applications of hypothesis selection, as well as an overview of previous algorithms, in our paper. In this rebuttal, some applications of hypothesis selection are discussed in our response to Reviewer fMmw, for your reference.

Regarding your question about relaxing the model, the short answer is yes; our algorithms remain effective with some minimal adjustments as long as approximations of Scheffe sets are provided.

Currently, in our paper, we compare the PDF of the known distributions, $H_i(x) > H_j(x)$, to determine whether $x$ belongs to $S_{ij}$, the Scheffe set of $H_i$ and $H_j$. However, this assumption can be relaxed if we can identify an alternative set $S'\_{ij}$ that captures most of the discrepancy between $H_i$ and $H_j$. In particular, it is sufficient to have: $\|H\_i - H\_j \|\_{TV} \leq (1+ \Theta( \epsilon)) \cdot |H_i(S'\_{ij}) - H_j(S'\_{ij}) | \,.$ Even with these imperfect sets, $w_{i^*}(H_i)$ is a good proxy for the quality of hypothesis $H_i$ (up to additive error $\epsilon$). See the equations after Line 180 in the paper.

Presentation: Thank you for your feedback regarding the presentation of our paper. Our overview was intended to provide a high-level description of our algorithm to avoid obscuring the main technical ideas with detailed specifics. We will certainly focus on enhancing the clarity and quality of our write-up in future versions.

Dependency on $\epsilon$ and $\delta$: Please see our global rebuttal.

Below is our answer to your questions:

• In Table 1, for [ABS23] the dependence on $\delta$ is $1/\delta$, while for the rest it is $O(\log(1/\delta))$ (or unspecified by the authors).

• Correct. There exists an $i^*$ such that for every $H_i$, $w_{i^*}(H_i)$ determines the quality of $H_i$.

• Correct. To ensure that a random hypothesis in a bucket is not too far, with a probability of $1-\delta$ in a single round, we have to sample $O(\log(n)/\delta)$ hypotheses and check if H_{i^} is prompting them. Or, we can try all hypotheses in the bucket. Hence, relying on this structural property of $H_{i^*}$ makes a polynomial dependency on $\delta$ inevitable. We speculate that improving the dependency on $\delta$ for this algorithm would require new algorithmic ideas. The main difficulty here is that there is no (known) general technique for boosting the confidence parameter while keeping $\alpha$ the same. In many settings, the success probability of a learning algorithm can be amplified from a constant, say 2/3, to at least $1-\delta$ at a cost of at most $\log(1/\delta)$ in running time and sample complexity. However, in hypothesis selection, choosing the best output from several runs of a given algorithm requires executing a second hypothesis selection algorithm, which introduces another factor of $\alpha$ in the approximation—leading to a total factor of at least $9$. As a result, these kinds of two-phase algorithms are not sufficient in the low $\alpha$ regime. Some previous results, such as [ABS23], also suffer from a polynomial dependency on $\delta$. Our second algorithm circumvents this polynomial dependence at the cost of a slightly worse accuracy parameter $(\alpha = 4)$.

Presentation

Thank you for your feedback regarding the presentation of our paper. Our overview was intended to provide a high-level description of our algorithm to avoid obscuring the main technical ideas with detailed specifics. We will certainly focus on enhancing the clarity and quality of our write-up in future versions.

Novelty of our techniques

The essence of our first algorithm indeed stems from the minimum distance estimate [DL01]. However, the primary challenge we faced was implementing this approach in linear time. Specifically, it is not feasible to compute the maximum semi-distances, $W(H_i)$, for all hypotheses in linear time. To address this, we developed an efficient and advanced method to estimate these values by taking the maximum over a small subset of semi-distances, while ensuring the algorithm's correctness. This approach allows us to achieve an algorithm that runs in (almost) linear time in $n$.

Our second algorithm is completely novel to the best of our knowledge. It achieves the desired time complexity (up to logarithmic factors) with $\alpha = 4$, an accuracy parameter that surpasses all previously known results. Our work introduces a novel algorithmic approach to this problem, marking a significant departure from existing techniques. We hope these new ideas will inspire future research.

Dependency on $\epsilon$ and $\delta$

Please see our global rebuttal.

Applications of hypothesis selection

Density estimation is a fundamental problem in statistics, with hypothesis selection being an important special case. It involves choosing the best distribution from a set of known models that represent potential underlying data distributions. For example, this set might include Poisson and gamma distributions with various parameters to model the number of arrivals per time unit. This technique is applicable in areas such as denoising, anomaly detection, selecting interpretable data distributions, strategy selection, and more.

That said, we view our results as a fundamental theoretical tool. Hypothesis selection has been instrumental in learning structured distributions (e.g., learning mixture of Gaussians [DK14, SOAJ14]). For additional references, see Section 1.3. Another significant aspect of hypothesis selection is its agnostic nature, allowing for learning even when the unknown distribution is not within the considered class. Hence, hypothesis selection is applicable even when data is noisy.

Addressing the importance of improving $\alpha$ by a constant factor

In most learning algorithms, the error guarantee decreases polynomially as the number of samples increases, so constant factors may not be as crucial. However, this is not the case in hypothesis selection. The output hypothesis is guaranteed to be $(\alpha \cdot OPT + \epsilon)$-close to $P$ in total variation distance. While increasing the number of samples can reduce $\epsilon$ to negligible levels, it does not improve the term $\alpha \cdot OPT$. $\alpha$ is an inherent property of the algorithm and directly impacts the best achievable error guarantee. Therefore, even a constant improvement in $\alpha$ is significant.

Some may argue that focusing on improving $OPT$ is more beneficial than refining $\alpha$. For instance, in the cover method (as you mentioned), using a finer $\gamma$-net can ensure that $OPT < \gamma$. However, this approach can drastically increase the algorithm's running time, as the size of the net can grow super-polynomially with $\gamma$. For example, in the case of mixtures of $k$ Gaussians, the dependence of the net size on $\gamma$ is roughly $O(\gamma^{-3\cdot k})$ (see [SOAJ14]). Thus, reducing $\gamma$ by a factor of three could increase the size of $\mathcal{H}$ by an exponential factor in $k$, and consequently, the running time, leading to an inefficient algorithm.