acceptodds
Under review as a conference paper at ICLR 2027

Private Component-by-Component Learning

Abstract

We study differentially private learning problems in the realizable setting, where a hypothesis is specified by components. A direct iteration of private component learners is obstructed by a simple difficulty: an approximate choice of the next component may destroy exact realizability of the labeled sample, even when the next component is locally accurate. We restore realizability using the LabelBoost procedure of Beimel, Nissim, and Stemmer [SODA '15, Algorithmica '21] and recycle data through two alternating reservoirs. The resulting learner, for a target privacy , pays only a privacy overhead relative to the active sample requirement of a single component learning step at target accuracy . For learning -dimensional halfspaces over a finite grid of size , exact realizability makes the direct component-depth objective quasi-concave. Instantiating the framework with the IPConcave algorithm of Nissim, Tsfadia, and Yan [SODA '26] and with the quasi-concave optimizer of Cohen, Lyu, Nelson, Sarl\'os, and Stemmer [STOC '23] yields a realizable sample complexity of , which improves on the previously known bound of . We also apply the framework to Boolean compositions: given proper private learners for classes , we obtain a proper private learner for for any fixed Boolean function . The resulting sample bound incurs a overhead relative to the maximum of the component learning costs at accuracy and the relevant VC-dimension term. Compared with the closure theorem of Alon et al. [COLT '20], this reduces the overhead on a common component sample bound from to .

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Differential privacy, PAC learning, Halfspace learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_9RoLOpenReview ↗
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 kk 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
  1. 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.

  2. 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

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.

Thank you for your response. However, my major concern about the significane and technical contribution of the proposed two-reservoir approach remains unresolved.

  1. 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 kk 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 O(α/k)O(\alpha / k) 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.

  2. 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 log⁡∗L\log^* L from d5.5d^{5.5} to d2.5d^{2.5}. 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.

Reviewer_sYvkOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies differentially private learning in the realizable setting when hypotheses are constructed sequentially from kk components. The main difficulty is that an approximately accurate component selection may destroy exact realizability, preventing subsequent component learners from satisfying their guarantees. The authors propose CarryForwardLearner, which uses LabelBoost to restore realizability after each component selection and two alternating reservoirs to reuse samples while controlling privacy loss. The framework achieves a O~(k/ε)\widetilde{O}(\sqrt{k}/\varepsilon) sample overhead relative to the active-sample requirement of a component learner at accuracy Θ(α/k)\Theta(\alpha/k). The framework is applied to private halfspace learning and Boolean compositions. For halfspaces, preserving realizability allows direct optimization of the coordinate-depth objective without convexification and enables realizable VC bounds, improving the dimension dependence of the log⁡∗L\log^* L branch from d5.5d^{5.5} to d2.5d^{2.5}. For Boolean compositions, the framework reduces the overhead on a common proper component-learner sample requirement from approximately kk to k\sqrt{k}.

Critical strengths

The main strength is the realizability-preserving component-learning framework. Lemma C.2 establishes that each component oracle receives an exactly realizable sample, regardless of earlier utility successes or failures. The two-reservoir construction and its macro-block privacy analysis provide a technically interesting mechanism for reusing samples, resulting in a O~(k/ε)\widetilde{O}(\sqrt{k}/\varepsilon) overhead rather than allocating separate samples to all kk components. This is a meaningful methodological contribution.

Lemma G.2 establishes quasi-concavity of the direct coordinate-depth objective under exact prefix realizability, avoiding the convexification used in previous constructions. Combined with realizable VC generalization, this yields a significant reduction in the polynomial dependence on dimension. This concrete theoretical improvement is the strongest reason for my positive assessment of the paper.

Critical weaknesses

The technical results are stated in terms of the finite coordinate-domain size NN, while the headline bound depends on the original grid parameter LL. Because the perturbation and rescaling procedure makes NN depend on the sample size nn, the derivation needs to explicitly address this dependence. Without this step, it is difficult to fully verify the advertised domain-size dependence of the main halfspace results.

In Lemma F.7, the quasi-concave optimizer is applied to an objective whose quasi-concavity is established only for realizable prefix states. The applicability of the optimizer's privacy guarantee under this restriction, including the fallback mechanism, needs clarification. The without-replacement VC argument in Theorem A.10 and the empty-carrier LabelBoost initialization also require more explicit justification. These issues appear potentially fixable, but they prevent full confidence in all the stated guarantees at this stage.

Questions for authors
  1. Could the authors explicitly derive the relationship between the coordinate-domain size NN, the original grid parameter LL, the dimension dd, and the sample size nn? Since the perturbation resolution depends on nn, how is this dependence handled without circularity when deriving the final bound? An explicit calculation establishing the stated log⁡∗L\log^* L and 2log⁡∗L2^{\log^* L} dependencies would strengthen the main result.

  2. The coordinate-depth objective is proved quasi-concave on realizable prefix states, but not necessarily on arbitrary labeled samples. Why is this sufficient for the privacy guarantee of the Cohen et al. optimizer? Does its privacy proof invoke quasi-concavity on any intermediate datasets outside the realizable domain? Additionally, how is privacy preserved by the total extension when the optimizer returns a default coordinate?

  3. Could the authors provide a rigorous construction of the coupling used to transfer the realizable VC bound from sampling with replacement to uniform sampling without replacement? Specifically, how are repeated indices handled, and why does the resulting subset have the claimed uniform distribution? This argument supports the realizable transfer bound used in the IPConcave application.

  4. The initialization step uses LabelBoost with T=∅T=\varnothing, while Corollary A.13 assumes ∣S∣=∣T∣=m|S|=|T|=m. Could the authors state and justify the precise utility guarantee used for initialization? A direct argument based on the exponential mechanism and the growth-function bound would resolve this issue.

I think this paper makes a meaningful theoretical contribution to differentially private learning. The main idea of restoring realizability after each component selection is interesting, and I find the two-reservoir approach to sample reuse particularly valuable. The halfspace application is the strongest part of the work, especially the observation that exact realizability makes the direct coordinate-depth objective quasi-concave and leads to improved sample-complexity bounds. However, I still have some concerns about the completeness of the technical arguments. In particular, I would like to see a more explicit derivation of the final dependence on the grid size LL, as well as clarification of the privacy guarantee for the quasi-concave optimizer when its assumptions hold only on realizable inputs. Some supporting proofs and notation in the appendices could also be improved. Overall, I lean toward weak acceptance because the theoretical contributions appear substantial and the concerns seem potentially addressable, although my confidence would increase if the authors clarified these points.

3 comments

We thank the reviewer for the positive review and helpful questions.

1. Coordinate-domain size and the dependence on n.

Let βGP\beta_{\mathrm{GP}} be the failure probability of the general position guarantee, and let NN, LL, dd, and nn denote the maximum coordinate-domain size, grid size, dimension, and total sample size, respectively. Counting possible numerators and denominators after perturbation and rescaling gives

N≤(2d)O(d6)LO(d8)nO(d3)(1/βGP)O(d2),N\le (2d)^{O(d^6)}L^{O(d^8)}n^{O(d^3)} (1/\beta_{\mathrm{GP}})^{O(d^2)},

and consequently

log⁡∗N≤max⁡log⁡∗L,log⁡∗d,log⁡∗n,log⁡∗(1/βGP)+O(1).\log^*N\le\max\\{\log^*L,\log^*d,\log^*n, \log^*(1/\beta_{\mathrm{GP}})\\}+O(1).

To avoid circularity, we choose each sample size from the original parameters. Set βGP=β/2\beta_{\mathrm{GP}}=\beta/2 and let

ℓ=max⁡1,log⁡∗L,log⁡∗d,log⁡∗(1/(αβεδ)).\ell=\max\\{1,\log^* L,\log^* d, \log^*(1/(\alpha\beta\varepsilon\delta))\\}.

Substituting ℓ\ell for log⁡∗N\log^* N gives the candidates

nIP=O~(d2.5ℓεα),nQC=O~(d2.5+d1.52ℓεα).n_{\mathrm{IP}} =\widetilde O\left(\frac{d^{2.5}\ell}{\varepsilon\alpha}\right), \qquad n_{\mathrm{QC}} =\widetilde O\left( \frac{d^{2.5}+d^{1.5}2^\ell}{\varepsilon\alpha}\right).

For each candidate, we set the perturbation resolution using that sample size and substitute it into the bound on NN. Both candidates grow at most polynomially in dd, 1/(αβεδ)1/(\alpha\beta\varepsilon\delta), and 2ℓ2^\ell, so log⁡∗n≤ℓ+O(1)\log^* n\le\ell+O(1) for each. Hence log⁡∗N≤ℓ+O(1)\log^* N\le\ell+O(1) and 2log⁡∗N=O(2ℓ)2^{\log^* N}=O(2^\ell). With sufficiently large constants and the stated logarithmic factors, each candidate meets its own oracle's sample requirement on the domain it induces. We use the instantiation requiring min⁡nIP,nQC\min\\{n_{\mathrm{IP}},n_{\mathrm{QC}}\\} samples.

2. Optimizer privacy on realizable inputs and the fallback.

Cohen et al. (2023, Section 4.1) reduce quasi-concave optimization to the interior-point problem. Given SS and an integer-valued quality function QSQ_S on a finite ordered domain, they construct a fixed-size synthetic dataset TST_S. An interior point of TST_S yields an approximate maximizer of QSQ_S. For neighboring S,S′S,S', sensitivity one and quasi-concavity of both objectives imply that TS,TS′T_S,T_{S'} have cumulative distance at most 22, meaning their counts at or below any threshold differ by at most 22. Their cumulatively private interior-point algorithm (Algorithm 8 and Theorem B.1) gives privacy after rescaling its parameters. It operates on the synthetic datasets without evaluating QQ on other datasets.

For a fixed prefix, QSQ_S is a function of the next coordinate, with depth maximized over the later coordinates. It has sensitivity one and may fail to be quasi-concave on arbitrary inputs. Our oracle's privacy requirement compares neighboring samples S,S′S,S' that each admit a realizing completion of that prefix. Both objectives are quasi-concave on the same fixed domain (Lemma F.3), so the argument above applies.

The total extension (Appendix F.2) ensures a valid coordinate on every input, defaulting to min⁡Y~i(y≤i−1)\min\widetilde Y_i(y_{\le i-1}) if the construction or output is invalid. On realizable inputs the construction is valid and the full output distribution is private, even when utility fails. Mapping a failure symbol or out-of-domain output to the default is post-processing because the domain and default depend only on the fixed prefix and public grid, preserving the privacy required by Assumption B.4.

3. Coupling for sampling without replacement.

The coupling lets us use the realizable VC bound for sampling with replacement. Treat the nn occurrences in SS as separately indexed examples, even when their values coincide. Draw AA by sampling m≤nm\le n indices independently and uniformly with replacement.

Construct BB directly from AA. Keep each distinct index in AA once, then add indices uniformly from those not yet in BB until BB has size mm. Every permutation of the indices preserves the distribution of BB, so all mm-subsets are equally likely.

A classifier with zero error on BB also has zero error on AA, since every index drawn in AA appears in BB at least once. Thus the realizable VC bound for AA guarantees that, with probability at least 1−β1-\beta, every classifier consistent with BB disagrees with the target hh on at most a τ\tau fraction of SS.

4. Empty-carrier initialization.

We agree that Corollary A.13 does not cover this call but it easily fixable using the same stpes. When T=∅T=\emptyset, realizability supplies a zero-error representative. Sauer's lemma bounds the number of representatives by (em/v)v(em/v)^v, where m=∣S∣m=|S| and v=VC(C)v=\mathrm{VC}(\mathcal C). The exponential mechanism then gives

Pr⁡[err⁡S(h0)>τ]≤(em/v)ve−mτ/2≤β\Pr[\operatorname{err}_S(h_0)>\tau]\le (em/v)^v e^{-m\tau/2}\le\beta

for m≥(c/τ)(vlog⁡(2/τ)+log⁡(2/β))m\ge(c/\tau)(v\log(2/\tau)+\log(2/\beta)) and a sufficiently large universal constant cc. Our existing sample bound covers this requirement, and we will state the initialization guarantee separately.

Thank you for the detailed responses and clarifications. The explanations regarding the dependence of the coordinate-domain size on the sample size (Q1), the sampling-without-replacement coupling (Q3), and the initialization step (Q4) address my concerns. I will maintain my positive assessment of the paper.

The clarification regarding the quasi-concave optimizer is also helpful. However, I have a follow-up question: As I understand it, the existing privacy guarantee is established under a general quasi-concavity assumption, whereas the proposed objective is shown to be quasi-concave only on realizable inputs. Although the authors provide an intuitive explanation, could they formally justify why the privacy guarantee continues to hold under this restricted assumption (including the handling of the fallback mechanism)?

We thank you for raising this point. The current statement of Proposition F.6 leaves implicit why the privacy guarantee applies when the score is known to be quasi-concave only on realizable inputs. We will revise the proposition to justify the guarantee formally under this restricted assumption. For each fixed prefix, Definition B.3 requires (εA,δA)(\varepsilon_A,\delta_A)-indistinguishability only for pairs of neighboring samples that are both realizable for that prefix. Lemma F.3 establishes sensitivity 11 of the coordinate-depth score and quasi-concavity on both inputs of every such pair.

Applying the revised Proposition F.6 below to every such pair in Lemma F.7 establishes that the coordinate oracle is (εA,δA)(\varepsilon_A,\delta_A)-differentially private on realizable prefix states, as required by Definition B.3.

Proposition F.6 Let Y\mathcal{Y} be a finite ordered domain of size NN, and let Q(S,y)Q(S,y) be an integer-valued score function on samples SS and candidates y∈Yy \in \mathcal{Y}. For 0<εA≤40 < \varepsilon_A\le4 and 0<δA≤1/20 < \delta_A\le1/2, there exists a quasi-concave optimization algorithm QCOpt\mathsf{QCOpt} such that, whenever Q(S,⋅)Q(S,\cdot) is quasi-concave, QCOpt(S,Q,Y,εA,δA)\mathsf{QCOpt}(S,Q,\mathcal{Y},\varepsilon_A,\delta_A) returns a point y^∈Y\widehat{y}\in\mathcal{Y} that, with probability at least 1−δA1-\delta_A satisfies

\geq \max_{y \in \mathcal{Y}} Q(S,y) - E_{\mathrm{QC}}, \qquad E_{\mathrm{QC}} = \widetilde{O}\\!\left( \frac{2^{\log^* N}\log(1/\delta_A)}{\varepsilon_A} \right),$$ where $\widetilde{O}$ suppresses polynomial factors in $\log^* N$. Moreover, for every pair of neighboring samples $S,S'$ such that $Q(S,\cdot)$ and $Q(S',\cdot)$ are both quasi-concave on $\mathcal{Y}$ and $$\max_{y \in \mathcal{Y}} \bigl|Q(S,y)-Q(S',y)\bigr| \leq 1,$$ the outputs $\mathsf{QCOpt}(S,Q,\mathcal{Y},\varepsilon_A,\delta_A)$ and $\mathsf{QCOpt}(S',Q,\mathcal{Y},\varepsilon_A,\delta_A)$ are $(\varepsilon_A,\delta_A)$-indistinguishable. **Proof.** Write $\mathcal{Y}=\\{z_1 < \cdots < z_N\\}$. Use the cumulatively private interior-point algorithm from the proof of Theorem 4.2 in Appendix B of Cohen et al. (2023), with privacy parameters $$\varepsilon_0=\min\\{\varepsilon_A/2,1/2\\}, \qquad \delta_0=\frac{\delta_A}{1+e^{\varepsilon_0}}.$$ Let $r$ be the input size prescribed by Cohen et al. for the IPP algorithm, and set $E_{\mathrm{QC}}=r$. The parameter choices in their proof give the stated bound on $r$ and a failure probability of at most $\delta_0\le\delta_A$. For a sample $S$ with quasi-concave score $Q(S,\cdot)$, let $M_S=\max_{y\in\mathcal{Y}}Q(S,y)$ and define $$q_S(j)=\max\\{0,Q(S,z_j)-M_S+r\\} \quad j\in[N], \qquad q_S(0)=0.$$ Form $T_S$ by including $\max\\{q_S(j)-q_S(j-1),0\\}$ copies of $z_j$ for each $j\in[N]$. By quasi-concavity, $q_S$ is nondecreasing up to a maximizer and nonincreasing thereafter, so $$\\#\\{x\in T_S:x\le z_j\\}=\sum_{\ell=1}^j \max\\{q_S(\ell)-q_S(\ell-1),0\\}= \max_{1\le\ell\le j}q_S(\ell).$$ In particular, $|T_S|=r$. The algorithm returns the output of the interior-point algorithm on $T_S$. For neighboring $S,S'$ satisfying the hypotheses, $|M_S-M_{S'}|\le 1$, so $|q_S(j)-q_{S'}(j)|\le 2$ for every $j$. The identity above gives cumulative distance at most two between $T_S$ and $T_{S'}$. By group privacy, the two outputs are $(2\varepsilon_0,(1+e^{\varepsilon_0})\delta_0)$-indistinguishable, and hence $(\varepsilon_A,\delta_A)$-indistinguishable. Group privacy uses only synthetic datasets of size $r$, so it requires no further evaluations of $Q$ or quasi-concavity assumptions. With probability at least $1-\delta_A$, the output $\widehat y$ lies between the smallest and largest elements of $T_S$. Both endpoints have positive $q_S$ scores. By quasi-concavity, $q_S$ is positive throughout that interval, so $Q(S,\widehat y) > M_S-r$. To handle the fallback, fix a prefix $p$ and let $Y$ be its coordinate domain. Let $M_p(S)$ denote the output of the interior-point algorithm on $T_S$, and define $$g_p(u)= \begin{cases} u, & u\in Y,\\\\ \min Y, & \text{otherwise}. \end{cases}$$ Whenever the construction is valid, define $A_p(S)=g_p(M_p(S))$. For neighboring samples $S,S'$ that are both realizable for $p$, the construction deterministically produces valid inputs $T_S$ and $T_{S'}$ of size $r$. By the preceding privacy argument, $M_p(S)$ and $M_p(S')$ are $(\varepsilon_A,\delta_A)$-indistinguishable. Since $g_p$ is fixed by the prefix and the public grid, the same holds for $A_p(S)$ and $A_p(S')$ by post-processing. If the construction fails to produce a valid input, the oracle returns $\min Y$, ensuring totality and validity on all inputs.
Reviewer_wCq9OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies differentially private (DP) learning problems in the realizable setting, where a hypothesis is constructed by composing kk components. This paper largely tackles the issue that arises when the learning is happening component-by-component: learning the next component might destroy the realizability thus far. They use LabelBoost (Beimel et al. (2015)) to correct that issue. They provide bounds for learning problems, such as halfspaces and boolean compositions. Using prior methods, such as IPConcave, as oracles, they improve on prior upper bounds for halfspaces.

Critical strengths
  1. The solution of restoring the realizability sequentially was not really obvious, and this paper cleanly uses prior work to fix that. The algorithmic ideas are generally quite interesting in this paper.
  2. The improvements in the sample complexity for learning halfspaces is significant in terms of dd (unless I'm misunderstanding something).
Critical weaknesses
  1. One weakness is the writing of this paper, which assumes some knowledge about the prior techniques in this area. I would describe the high-level algorithm more clearly, and not mix the intuition about the analysis in there. It took some effort to understand even the high-level idea of the framework.
  2. It would be good to see applications for this problem. I can intuitively see in certain cases, but I don't know for which problems a direct solution would be better both sample-wise and computationally. The lack of comparisons for other problems with any existing baseline is a drawback.
  3. Significance-wise, I would like to understand if there are other important problems, which don't have the best solution, except for learning them component-wise, for which this work could be useful. Essentially, I want to understand: how useful was it to solve this problem? The motivation is lacking.
Questions for authors
  1. Could you comment on or add a discussion about the time complexity or computational efficiency here? I don't think I would be offended by the running time not being the best, but it's just good to know where the SOTA lies.
  2. Are there any potential comparisons of bounds in terms of the sample complexity for problems, other than halfspaces?
  3. In line 112, what are "superlevel" sets?
2 comments

We thank the reviewer for the constructive feedback. We will clarify the motivation and prerequisites and separate the algorithm overview from the analysis.

1. Running time.

For kk components and nn examples, we make kk calls each to the oracles and LabelBoost, including initialization. Each oracle receives m≈εn/km \approx \varepsilon n/\sqrt{k} examples, and LabelBoost uses at most 2m2m points per call. The total time is

O(n+km+kTA(m)+kTLB(m)),O\left(n+km+kT_A(m)+kT_{\mathrm{LB}}(m)\right),

where TAT_A and TLBT_{\mathrm{LB}} are the respective call costs and O(n+km)O(n+km) covers sampling and bookkeeping.

For dd-dimensional halfspaces, LabelBoost can enumerate and score the HH labelings induced by the current prefix class. Sauer's lemma gives H≤(2em/v)vH\le(2em/v)^v for 1≤v≤2m1\le v\le 2m, where v≤d+1v\le d+1 is its VC dimension. We enumerate the labelings using linear programming to discard infeasible partial labelings. At each step, at most HH partial labelings survive, since each has a distinct feasible complete extension. This gives O(mH)O(mH) polynomial-time feasibility tests and time mO(d)m^{O(d)}.

For TAT_A, Nissim et al. (2026b, SODA version) give an O(md+2)O(m^{d+2}) optimization cost per coordinate for IPConcave, arising from optimizing cdepth\mathrm{cdepth} on potentially nonrealizable subproblems. In our realizable setting, a feasible completion maximizes depth, so a faster oracle implementation may be possible.

Nguyễn et al. (2020) use O~(1/(αεγ2))\widetilde O(1/(\alpha\varepsilon\gamma^2)) samples and run in time polynomial in 1/γ1/\gamma under a margin assumption γ>0\gamma>0.On integer grids, Kaplan et al. (2025) and Ene et al. (RANDOM 2025, arXiv:2507.10946) yield learners with poly(n,d,log⁡L)\mathrm{poly}(n,d,\log L) arithmetic cost and sample bounds that depend on log⁡L\log L. We improve the dimension factors in existing bounds with log⁡∗L\log^* L or 2log⁡∗L2^{\log^* L} dependence. For the log⁡∗L\log^* L bound, this saves a factor of d3d^3, from d5.5d^{5.5} to d2.5d^{2.5}.

Whether private halfspace learning on a finite grid can achieve O~(log⁡∗L)\widetilde O(\log^* L) dependence on the grid size in polynomial time remains open.

2. Further sample-complexity comparisons.

Yes. Promising candidates include unions of rectangles, convex polygons, balls, and ellipsoids. For fixed accuracy, confidence, and privacy parameters, let t=log⁡∗Lt=\log^* L, where LL is the grid size per coordinate. Using the same proper component learners, Alon et al. (2020, Theorem 29) and our Theorem F.19 give the following sample bounds, up to logarithmic factors.

ClassAlon et al. closureOur framework
Unions of kk axis-aligned rectangles in dd dimensionsO~(dk4+dk2t)\widetilde O(dk^4+dk^2t)O~(dk2.5+dk1.5t)\widetilde O(dk^{2.5}+dk^{1.5}t)
Convex polygons with kk sidesO~(k4+k2t)\widetilde O(k^4+k^2t)O~(k2.5+k1.5t)\widetilde O(k^{2.5}+k^{1.5}t)

For comparison, the exponential mechanism over unions of rectangles gives a O~(dklog⁡L)\widetilde O(dk\log L) sample bound, and Kaplan et al. (ICML 2019, arXiv:1902.05017) give an efficient learner for polygons with O~(klog⁡L)\widetilde O(k\log L) samples. The comparison depends on the parameter regime.

Using feature lifting, we can view balls and ellipsoids as halfspaces in O(d)O(d) and O(d2)O(d^2) dimensions, respectively. Taking the halfspace bound of Nissim et al. (2026b) as the baseline after lifting, the bounds that retain log⁡∗L\log^* L dependence could decrease from O~(d5.5t)\widetilde O(d^{5.5}t) to O~(d2.5t)\widetilde O(d^{2.5}t) for balls and from O~(d11t)\widetilde O(d^{11}t) to O~(d5t)\widetilde O(d^5t) for ellipsoids. These lifted learners would be improper. We will verify the required assumptions before stating these applications as corollaries.

3. Superlevel sets.

A superlevel set contains the points where a function is at least a given threshold. For a quasi-concave function, each superlevel set is convex, so in one dimension it is an interval. Nissim et al. (2026b) and Kaplan et al. (2020b) use the cdepth\mathrm{cdepth} function because the depth objective can fail to be quasi-concave on nonrealizable inputs. A sufficiently high cdepth\mathrm{cdepth} still gives a guarantee on depth.

Write DS(y)=z∈Rd:depthS(z)≥yD_S(y)=\\{z\in\mathbb R^d:\mathrm{depth}_S(z)\ge y\\} for the superlevel set of depth. The convexified depth is

cdepth(x)=max⁡y∈R:x∈ConvexHull⁡(DS(y)).\mathrm{cdepth}(x)=\max\\{y\in\mathbb R:x\in\operatorname{ConvexHull}(D_S(y))\\}.

Hence cdepth(x)≥k\mathrm{cdepth}(x)\ge k exactly when xx is a convex combination of points whose depth is at least kk. The superlevel set at kk is therefore the convex hull of DS(k)D_S(k). This explains why cdepth\mathrm{cdepth} is quasi-concave. We will define superlevel sets at their first occurrence.

Reviewer_wCq9OpenReview ↗

Thanks

Thank you for your response! I will keep this in mind for evaluation later.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.