- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies private realizable PAC learning under the assumption that each hypothesis can be decomposed into components. The authors propose a framework that solves this problem by learning the components one by one. The major challenge is that after fixing a component, the remaining components may not admit realizability on the sample because the component learner is only approximately accurate. Their algorithm restores realizability through LabelBoost after each approximate component choice and reuses data from two alternating reservoirs.
As applications, they use this framework to improve the sample complexity of private learning halfspaces and boolean composition.
Critical strengths
Improved rates for halfspaces and boolean composition: this work proves sample complexity that improves previous results. The feasible-prefix geometric construction of the coordinate oracle for halfspaces is also interesting.
Critical weaknesses
-
Simpler constructions seem to exist: There have been variants of LabelBoost in the literature that circumvent the realizability issue. For example, Algorithm 4 in this NeurIPS 2025 paper suggests a modified-score LabelBoost. Simply applying it component by component gives the same rate as Theorem 1.1 by advanced composition, without using the proposed two-reservoir idea. This largely weakens the paper's contribution, and the paper lacks a detailed discussion of these variants.
-
Stronger result for boolean composition can be obtained using existing techniques: The paper's Theorem F.19 gives \widetilde O\left(\frac{\sqrt k}{\varepsilon}\max\left\\{\frac{k\max(v,d_{\max})}{\alpha}, M\right\\}\right). But based on the approach I mentioned above, one can run empirical learners in each round, and apply the uniform convergence argument only at the end. This gives a slightly better \widetilde O\left(\frac{v}{\alpha} + \frac{\sqrt k}{\varepsilon}\max\left\\{\frac{k d_{\max}}{\alpha}, M\right\\}\right). This approach is a straightforward combination of techniques developed in the literature.
Questions for authors
Can you clarify my concerns stated in Weaknesses?
3 comments
Thank you for your response. However, my major concern about the significane and technical contribution of the proposed two-reservoir approach remains unresolved.
-
My original review did not claim that the guarantee stated in Li et al., NeurIPS 2025 can be applied directly. Rather, my point concerns their proposed mechanism. The adaptation to recover this paper's result is quite staraightforward: (i) Algorithm. Run their mechanism for rounds. In each round, restrict the hypothesis class to completions of the current prefix and use the component oracle to select the next component. (ii) Utility. Applying their utility bound with a per-round error directly gives the desired overall error. (iii) Privacy. Their privacy analysis can be applied to each round, and advanced composition then yields the overall privacy guarantee.
-
The stronger Boolean composition bound is also imediate from the above procedure: run empirical learners in each round and apply the uniform convergence argument only at the end.
These two observations substantially weakens the claimed two-reservoir approach's significance: both of them are simple consequence of existing techniques, and the latter even yields a stronger sample complexity.
I agree that the suggested approach does not lead to further improvement for halfspaces, but I do not see how this addresses my concern. The central issue is not whether existing techniques can give stronger results, but whether the results established in the paper constite a significant construbiton. If a simple combination of existing techniques already gives Theorem 1.1, this alone substantially undermines the novelty and significance of the proposed approach regardless of whether further improvements are possible.
The author's reply states that "Our approach therefore trades a more involved privacy analysis for a simpler relabeling objective, which simplifies implementation and may reduce running time even when both approaches remain computationally expensive." However, I did not find it sufficient to establish a substantial contribution. The primary focus of this paper is on sample complexity rather than computational efficiency. A potentially simpler implementation or improved running time does not address the concern that the main sample complexity guarantees can already be obtained through straightforward combinations of existing techniques.
We respectfully disagree with the reviewer's assessment that an alternative implementation of Theorem 1.1 substantially undermines the contribution of our work. This contribution includes the formulation of a general component-learning abstraction, with privacy and utility required of the component oracles only on realizable prefix states, and its connection to fundamental learning problems. The proposed adaptation takes this formulation and its component oracles as a starting point.
For halfspaces, obtaining our bounds also requires establishing that exact prefix realizability makes the direct coordinate-depth objective quasi-concave and permits the use of realizable VC bounds. These insights avoid the losses from convexification and reduce the dimension factor multiplying from to . An alternative implementation of the general reduction does not itself supply these geometric observations or their analysis. Although Li et al. 2025 (their arXiv version) has now been publicly available for over a year, to our knowledge no earlier work derived these improved halfspace bounds from its mechanism. Identifying and formalizing this connection is a substantive contribution for such an extensively studied learning problem.
Finally, our comparison of implementation costs was intended to explain a distinction between the reductions. Running time was not our primary objective, but the simpler privacy analysis of the modified-score approach comes with additional optimization over hypotheses inside each relabeling score. Our two-reservoir construction implements the framework using ordinary empirical-error scores, which are evaluated by counting mistakes. For someone using Theorem 1.1 as a black box, this avoids having to implement the additional score optimization alongside the component oracles. This makes the reduction easier to implement and may reduce its running time, even when both generic approaches remain computationally expensive.
In the revision, we will present both our two-reservoir implementation of Theorem 1.1 and the alternative based on the modified-score mechanism of Li et al. (2025), comparing their analyses and computational requirements. We will also include the slightly improved Boolean-composition bound obtainable through a tailored analysis of the modified-score approach.
We thank the reviewer for pointing out this connection. The cited paper uses a modified-score relabeling procedure (Li et al. 2025, Algorithm 4, arXiv:2510.00574) to obtain an agnostic empirical learner from a proper private realizable learner, avoiding the additional quadratic dependence on inverse accuracy from agnostic uniform convergence. Its stated guarantees do not directly cover our component-oracle setting, but with suitable adaptations the approach appears capable of obtaining information-theoretic guarantees comparable to Theorem 1.1. We will discuss this connection in the revision.
We also agree that a construction tailored to Boolean composition can improve on the sample complexity obtained from Theorem 1.1. It uses the composition structure to control completion error on the original sample throughout the rounds and applies population generalization only at the end.
Two distinctions remain relevant. First, for halfspaces, our main application, we do not see a further sample-complexity improvement from the suggested approach; it appears to offer an alternative general learner with comparable guarantees.
Second, our general learner uses ordinary empirical-error scores in its LabelBoost steps. Evaluating a candidate's score requires counting errors, whereas the modified score includes an additional optimization over hypotheses. Our approach therefore trades a more involved privacy analysis for a simpler relabeling objective, which simplifies implementation and may reduce running time even when both approaches remain computationally expensive.