PaperlayerView exact revision on arXiv

Source-linked AI summary

Private Component-by-Component Learning

Dvir Karni, Eliad Tsfadia

arXiv:2610.05102v1cs.LGcs.CR

TL;DR

Sequential private component choices can destroy exact realizability, leaving later learners outside their promised domain. The paper restores realizability with LabelBoost and reuses data across rounds; for halfspaces, it uses a quasi-concave component-depth objective and gives private proper learner guarantees.

  • Problem

    An approximately accurate private component choice can leave no consistent completion of the selected prefix, so the next oracle receives data outside its promised domain.

    Source: §2.1 · p. 10

  • Method

    The framework uses LabelBoost to restore exact realizability after component choices and reuses data across rounds.

    Source: §1.3 · p. 6, §2.2 · p. 10

  • Results

    For halfspaces, exact realizability makes the direct coordinate-depth objective quasi-concave, and the paper gives private proper learner guarantees using quasi-concave optimization and IPConcave.

    Source: §1.3.1 · p. 7, §8.2 · p. 33, §8.3 · p. 35

  • Takeaways & Limitations

    The framework replaces uniform additive VC bounds with realizable bounds, reducing the corresponding dependence on inverse accuracy from quadratic to linear.

    Source: §1.3 · p. 6

    The construction is primarily information-theoretic, and selecting representatives, searching finite domains, and finding good completions may require superpolynomial time.

    Source: §1.5 · p. 9

Abstract

from arXiv · show

We study differentially private learning problems in the realizable setting, where a hypothesis is specified by $k$ 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 $\varepsilon$, pays only $\widetilde O(\sqrt{k}/\varepsilon)$ overhead relative to the active sample requirement of a single component learning step at target accuracy $\Theta(\alpha/k)$. For learning $d$-dimensional halfspaces over a finite coordinate grid of size $L$, 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 $\widetilde{O}\left(\frac{1}{\varepsilon \alpha}\cdot \min\{d^{2.5} \log^*L, \:\: d^{2.5} + d^{1.5} 2^{\log^*L}\}\right),$ which improves on the previously known bound of $\widetilde{O}\left(\frac{1}{\varepsilon \alpha}\cdot\min\{\frac{1}{\alpha}\cdot d^{5.5}\log^*L,\:\: d^{2.5}2^{\log^*L}\}\right).$ We also apply the framework to Boolean compositions: given proper private learners for classes $H_1,\ldots,H_k$, we obtain a proper private learner for $G(H_1,\ldots,H_k)$ for any fixed Boolean function $G:\{0,1\}^k\to\{0,1\}$. Compared with the closure theorem of Alon, Beimel, Moran, and Stemmer [COLT '20], this reduces the overhead on a common component sample bound from $\widetilde O(k/\varepsilon)$ to $\widetilde O(\sqrt{k}/\varepsilon)$.

1 Introduction

The introduction presents a framework for reducing sample costs in private realizable learning with multi-component hypotheses, along with its technical development and applications. It also notes the framework’s primarily information-theoretic nature and leaves efficient halfspace learning with log∗L dependence open.

1.1 Private Learning

  • Private sample complexity remains quantitatively unresolved; for grid halfspaces, necessary bounds are Omega(d + log*L) for improper learners and Omega(d log*L) for proper learners.Finite classes are privately learnable, but generic bounds may exceed their VC dimension substantially.Source: §1.1 · p. 3

1.2 Private Component-by-Component Learning

  • Approximate component choices can break realizability and quasi-concavity; preserving realizability lets halfspace learning optimize depth directly and saves a factor d^3 at constant accuracy.This replaces uniform additive VC approximation with realizable bounds and avoids the convexified-depth conversion loss.Source: §1.2 · pp. 4–5

1.3 Our Results

  • The framework relabels each next active sample with LabelBoost [5] and alternates two reservoirs, obtaining a proper realizable (ε, δ)-PAC learner private on arbitrary datasets with O~(sqrt(k)/epsilon) overhead.The overhead multiplies the active sample requirement for one component step at accuracy Θ(α/k); relabeling keeps each subsequent component problem realizable.Source: §1.3 · p. 6

1.3.1 Applications

  • d^2.5 log*L for IPConcave and d^2.5 + d^1.5 2^log*L for general quasi-concave optimization improve the dimension dependence of private halfspace learning.The direct coordinate-depth objective is quasi-concave when the current prefix has a fully feasible completion.Source: §1.3.1 · p. 7

1.4 Related Work

  • The work builds on LabelBoost [5] and private geometric methods [6] [17] [22], while focusing on sample complexity without a margin assumption rather than computational efficiency.Prior work includes efficient private learners for large-margin halfspaces and linear-algebraic tasks [18].Source: §1.4 · p. 8

1.5 Open Questions

  • The improved halfspace upper bounds still exceed known lower bounds: Omega(d log*L) for proper learners [10] and Omega(d + log*L) for improper learners [1].Closing these gaps, particularly the polynomial gap in d, remains an open question.Source: §1.5 · p. 9
  • The construction may require superpolynomial time, leaving open whether efficient halfspace learners can attain log∗L dependence with small dependence on d.Kaplan et al. [18] give efficient private halfspace algorithms with sample complexity polynomial in d and polylogarithmic in L; the paper also calls for efficient component representations and relabeling procedures.Source: §1.5 · p. 9

1.6 Paper Organization

  • The paper proceeds from techniques and preliminaries to component-by-component learning, CarryForwardLearner and its analyses, then halfspace and Boolean-composition applications.Appendices A–C provide proofs on depth-function quasi-concavity, component oracles from local proper learners, and the halfspace–linear-feasibility reduction.Source: §1.6 · p. 9

2 Our Technique

The technique combines private component oracles while keeping every oracle input exactly realizable, then reuses two reservoirs to control data and privacy costs. LabelBoost restores realizability between component choices, and the analysis bounds the resulting learner’s utility and privacy.

2.1 The Setting

  • Approximate component choices can destroy exact realizability, leaving the next oracle outside the domain where its privacy and utility guarantees apply.The learner must restore realizability after each choice while controlling the added error.Source: §2.1 · p. 10

2.2 Restoring Realizability via LabelBoost

  • LabelBoost [5] relabels the labeled and unlabeled samples using a representative hypothesis, producing a sample exactly realizable by the extended class.When the original class contains a hypothesis with small empirical error, this procedure adds only a small amount of error.Source: §2.2 · p. 10

2.3 Our CarryForwardLearner Algorithm

  • CarryForwardLearner initializes with a relabeled sample, then alternates between two reservoirs to supply fresh active samples as it builds the component prefix.Each next sample is relabeled by LabelBoost for the extended prefix class, and the reservoirs remain unchanged, so subsets may overlap.Source: §2.3 · p. 11
  • Two-round macro-blocks and subsampling control privacy across reused reservoirs, while the unconditional realizability invariant lets realizable-input oracle guarantees yield privacy on arbitrary datasets.Adaptive composition over the reservoir activations gives the learner’s overall privacy guarantee.Source: §2.3 · pp. 11–12
  • Restoring realizability costs O(τ) empirical disagreement per round, and the final error is at most α with probability at least 1 − β when τ = α/(40k).Each active sample must also meet the oracle’s sample requirement MA(τ); the VC and LabelBoost requirements are eO(kv/α).Source: §2.3 · p. 12

3 Preliminaries

The preliminaries establish the learning and privacy notation, then present LabelBoost as a way to make a relabeled sample exactly realizable. The extended analysis bounds its privacy cost, including when only the relabeled carrier is released.

3.1 Notation and PAC learning

  • The section defines realizable PAC utility, private PAC learning, and differential privacy through indistinguishability on neighboring datasets.It also distinguishes realizable private PAC learning, whose utility guarantee is required only on realizable distributions.Source: §3.1 · p. 13, §3.2 · pp. 13–14

3.3 Learning-Theoretic Tools

  • The learning-theoretic tools include VC dimension and a realizable generalization guarantee: agreement with a witness on a random subset implies bounded disagreement on the full sample.The guarantee applies simultaneously to every class hypothesis.Source: §3.3 · pp. 14–15

3.4 LabelBoost

  • LabelBoost selects a hypothesis using the exponential mechanism and relabels both samples, producing a sample exactly realizable by the concept class.It considers representatives of labelings induced on the unlabeled sample together with the auxiliary sample.Source: §3.4 · p. 15

3.5 Extended Privacy Analysis

  • When the continuation is private on realizable inputs, the extended analysis applies LabelBoost while passing it a realizable relabeled sample.The carrier-only release is also stated to be (cLB, 0)-differentially private for a fixed unlabeled carrier.Source: §3.5 · pp. 16–17
  • The LabelBoost weight comparison bounds the ratio of probabilities assigned to any common labeling by 4e in either direction.The analysis defines cLB as ln(4e).Source: §3.5 · p. 17

4 Component-by-Component Learning Framework

The framework represents hypotheses as valid component prefixes and defines private component oracles that extend a prefix while retaining a good completion. Their guarantees are required on realizable prefix states.

4 Component-by-Component Learning Framework

  • The framework builds hypotheses one component at a time, with each oracle receiving the chosen prefix and current labeled sample.The oracle sequence must satisfy totality and prefix validity, realizable-state privacy, and the stated utility guarantee.Source: §4 · p. 18, §4.2 · pp. 19–20

4.1 Component Representations

  • A valid prefix is one extendable to a complete representation, and its completion class contains concepts whose representations extend that prefix.A realizable prefix state pairs such a prefix with a sample witnessed by a concept in its completion class.Source: §4.1 · pp. 18–19

4.2 Private Component Oracles

  • A component oracle chooses the next component so that, with high probability, the extended prefix has a completion close to a witness on the current sample.Its privacy guarantee is also restricted to inputs realizable by the current prefix class.Source: §4.2 · pp. 19–20

5 Generic Learner

CarryForwardLearner applies component oracles sequentially and uses LabelBoost to keep each next active sample realizable. Its stated guarantee is a proper private PAC learner, with realizability maintained at every oracle call.

5 Generic Learner

  • CarryForwardLearner sequentially builds the component vector and uses LabelBoost to carry a labeled sample forward while preserving realizability.The learner begins with an initialization sample and alternates carriers as it proceeds.Source: §5 · pp. 20–21
  • Theorem 5.1 states that CarryForwardLearner is a proper (ε, δ)-differentially private PAC learner for a k-component class.Its sample complexity is specified by the theorem, but the supplied passage does not include the bound.Source: §5 · p. 20
  • Every component oracle is invoked on a realizable input, an invariant that holds for every execution rather than only when oracle utility succeeds.Relabeling after a valid component choice establishes the next realizable state.Source: §5 · p. 21

6 Privacy Analysis

The privacy analysis alternates two reservoirs because a single-reservoir iteration does not directly support composition when carried samples determine later states. It analyzes two-round macro-blocks, amplifies privacy through subsampling, and calibrates the parameters for the full learner.

6 Privacy Analysis

  • A single reservoir does not directly support privacy composition because carried samples and newly sampled carriers both affect later iterations, while including the carried sample can expose differing records.Alternating reservoirs groups two rounds so a record from one reservoir affects the selected components and the relabeled carrier from the other.Source: §6 · pp. 21–22

6.1 The Two-Round Macro-Block

  • The two-round macro-block is shown private on its carrier input by analyzing the second-round continuation on realizable inputs and applying the extended LabelBoost analysis.The block's stated privacy parameters are (C, Δ).Source: §6.1 · pp. 23–24

6.2 Reservoir privacy

  • Uniformly subsampling a reservoir to form a carrier amplifies the privacy guarantee of the carrier-level mechanism.The analysis applies this amplification to initialization and macro-block mechanisms.Source: §6.2 · p. 25

6.3 Privacy Calibration

  • After composing the reservoir guarantees and conditioning on the value-independent partition, the calibrated CarryForwardLearner is (ε, δ)-differentially private on arbitrary input samples.The analysis establishes privacy with respect to each reservoir before combining those guarantees.Source: §6.3 · pp. 26–27

7 Utility Analysis

CarryForwardLearner bounds the error accumulated across its component iterations by controlling each round’s change in the carried hypothesis. Its utility proof applies the one-round guarantee throughout by keeping each active sample i.i.d. from the data distribution.

7 Utility Analysis

  • Setting τ = Θ(α/k) bounds the accumulated error across k iterations by α.The utility theorem concludes that the learner outputs a hypothesis with error at most α, with probability at least 1 − β.Source: §7 · pp. 27–28, It suffices to take · p. 29
  • Each round obtains a completion with empirical error at most τ, then bounds population disagreement by <20τ with total failure probability at most βA + βLB + βVC.The completion comes from the component-oracle guarantee; LabelBoost and all-pairs generalization support the population bound.Source: §7 · pp. 27–28

It suffices to take

  • Alternating reservoirs ensure each round’s active sample consists of i.i.d. draws from D_X, allowing the one-round utility guarantee to apply in every round.The proof uses U(S0) = U(R0) and U(Si−1) = U(Ti−1) for i ≥ 2.Source: §7 · p. 27, It suffices to take · p. 28
  • The proof separately controls initialization and the last transition, then combines the events to conclude the final error guarantee.The initialization bound uses LabelBoost and generalization; the last-round bound uses oracle utility and generalization.Source: It suffices to take · pp. 28–29

8 Applications

This section applies CarryForwardLearner to private halfspace-learning instantiations and to Boolean composition, introducing the obstacle to using local private learners and showing how proper private component learners yield a private realizable learner for their composition. It also describes AI’s role in developing CarryForwardLearner and the authors’ responsibility for the work.

8.1 Common Halfspace Coordinate Framework

  • Realizable prefixes make finite-domain coordinate depth sensitivity-one and quasi-concave, with a completion satisfying all constraints; Theorem 8.5 transfers component-oracle guarantees to proper realizable halfspace learning.Under general position, the reduction from constraint violations to classification errors incurs at most d additional errors.Source: §8.1 · pp. 30–31

8.2 A Coordinate Oracle via Private Quasi-Concave Optimization

  • Cohen et al. [12]'s quasi-concave optimizer yields a realizable coordinate oracle and, through Theorem 8.5, a proper private realizable PAC learner for finite-grid halfspaces.The oracle applies QCOpt to the coordinate-depth objective on finite domains.Source: §8.2 · pp. 31–33

8.3 A Coordinate Oracle via IPConcave

  • IPConcave [22] replaces its generic 1/τ^2 approximation bound with a realizable VC transfer bound of 1/τ, yielding a proper private realizable halfspace learner.The coordinate oracle's utility analysis uses general position and the finite-domain prefix construction.Source: §8.3 · pp. 34–35

8.4 Closure under Boolean Composition

  • A local private learner's realizable utility guarantee may not apply because a sample realizable by the restricted global class need not be realizable by the local class.This motivates the Boolean-composition setting where the available primitives are private learners for local classes.Source: §8.4 · p. 35
  • Relabeling selects a locally learnable component with a good global completion, then lifts its utility guarantee; Boolean composition satisfies the required structural conditions by changing only that component.The relabeling construction is attributed to Alon et al. [2, Algorithm 2]. For Boolean compositions, keeping the suffix fixed ensures global hypotheses agree wherever the replaced local components agree.Source: §8.4 · pp. 35–36
  • Proper private realizable learners for each component class yield a private realizable PAC learner for their Boolean composition.Theorem 8.19 states this for any fixed G and nonempty component classes, with the theorem’s sample-complexity bound stated in the following passage.Source: §8.4 · p. 37

AI use statement

  • AI helped develop CarryForwardLearner and prove its privacy guarantee, while the authors developed the work’s overall roadmap and remain responsible for its final content.The AI assistance followed extensive interaction beginning with an incomplete algorithm version supplied by the authors; other assistance was limited to lower-level tasks.Source: AI use statement · p. 37

A Quasi-Concavity of the Depth Function

For a realizable prefix, the one-coordinate depth objective is quasi-concave on the finite ordered domain. The proof establishes this by showing that its superlevel sets are convex.

A Quasi-Concavity of the Depth Function

  • For a fixed prefix and constraint subset, the feasible completions form a convex set whose projection onto the coordinate is an interval, possibly empty or unbounded.Each affine constraint defines a halfspace, so their intersection is convex and its projection remains convex.Source: A Quasi-Concavity of the Depth Function · p. 39
  • When the prefix and sample are realizable, quasi-concavity on the real line carries over to the finite ordered coordinate domain.The finite domain inherits the order from R, so every ordered triple in that domain is also ordered in R.Source: A Quasi-Concavity of the Depth Function · pp. 39–40
  • For each integer threshold, the depth objective’s superlevel set is a union of intervals and therefore convex.Because the depth objective is integer-valued, it suffices to consider integer superlevel thresholds.Source: A Quasi-Concavity of the Depth Function · p. 40

B Proof of the Local Proper Learner Corollary

The local proper learner corollary establishes validity, privacy, and utility for a component oracle on realizable prefix states. Its utility guarantee provides a completion meeting the required disagreement bound.

B Proof of the Local Proper Learner Corollary

  • The learner’s output is proper, and the structural condition ensures the selected component is valid.The algorithms are defined on every labeled input, and the proper empirical learner outputs an element of H_i.Source: B Proof of the Local Proper Learner… · p. 41
  • Matched sensitivity of the completion score limits its change to at most one across neighboring inputs, supporting the privacy guarantee for the private continuation.The proof applies the privacy-preservation result for the relabeling step followed by the private continuation.Source: B Proof of the Local Proper Learner… · p. 41
  • On a realizable prefix state, the utility argument finds a component hypothesis with a completion whose disagreement is at most τ.The exponential mechanism selects a component hypothesis, and the structural condition supplies a suitable completion.Source: B Proof of the Local Proper Learner… · p. 41

C Halfspaces and Linear Feasibility Reduction

The appendix reduces realizable halfspace learning to coordinate-wise linear-feasibility depth maximization, then uses finite coordinate domains and perturbation to preserve realizability through sequential states. It establishes utility and privacy for the resulting proper learner.

C Halfspaces and Linear Feasibility Reduction

  • Halfspace learning is represented as linear-feasibility constraints, and depth counts the satisfied constraints, including repeated occurrences.The induced range family has VC dimension at most d + 1.Source: C Halfspaces and Linear Feasibility… · p. 42
  • A uniformly random submultiset of size m preserves near-full depth: with probability at least 1−β, every point of full depth on the submultiset has depth at least (1−ρ)n on the original sample.The stated sample-size requirement is m ≥ cρ((d + 1)log(2/ρ) + log(1/β)) for a sufficiently large universal constant c.Source: C Halfspaces and Linear Feasibility… · p. 42
  • Perturbation and rescaling preserve realizability, while the perturbed sample and every active sample are in general position with probability at least 1−β_GP.The general-position event covers all rounds of the carry-forward learner.Source: C Halfspaces and Linear Feasibility… · p. 44
  • After perturbation and rescaling, the maximum finite coordinate-domain size N satisfies log* N ≤ max{log* L, log* d, log* n, log*(1/β_GP)} + O(1).Replacing dependence on N with dependence on L affects only factors suppressed by eO in the final learning bounds.Source: C Halfspaces and Linear Feasibility… · p. 44
  • For a realizable prefix, the coordinate depth objective is sensitivity-one and quasi-concave, and the finite domain contains a coordinate preserving a completion satisfying all sample constraints.This ensures exact realizability can persist at each coordinate step.Source: C Halfspaces and Linear Feasibility… · pp. 43–44
  • With probability at least 1−β, the learner is proper, (ε, δ)-differentially private, and returns a halfspace with error at most α on the original distribution.Properness follows from the coordinate representation, and utility is transferred from the perturbed setting to the original distribution.Source: C Halfspaces and Linear Feasibility… · pp. 45–46
Loading 2610.05102v1…