Research map / Learning theory and algorithms / Sample complexity

On Rate-Optimal Partitioning Classification from Observable and from Privatised Data

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Minimax estimation rates

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves convergence rates for partitioning classifiers, with and without local differential privacy (Laplace noise), replacing the strong density assumption with a combined margin-and-density condition whose rates depend only on the intrinsic dimension d_a of the absolutely continuous part.

Problem

Existing convergence rates for partitioning classification require the strong density assumption (SDA), which is restrictive, and the privatised (LDP) case was conjectured to possibly converge arbitrarily slowly without it.

Approach

Assumes the input law is a mixture of an absolutely continuous part supported on a d_a-dimensional subspace and a discrete part, and introduces a combined margin and density condition replacing SDA; for LDP, adds Laplace noise to cell-wise discretised labels and derives rates depending on 2d_a.

Key results

• Without SDA, the binary partitioning classifier achieves O(n^{-(1+min{1,gamma,gamma_1})/(2+d_a)}) excess risk, matching the minimax optimal rate under SDA when gamma <= min(1, gamma_1).
• Under epsilon-LDP with Laplace noise, the rate depends on 2d_a and the conjectured arbitrarily slow convergence without SDA is refuted; with h_n=(sigma_Z^2/n)^{1/(2+2d_a)} the rate is O((sigma_Z^2/n)^{(1+min{gamma,gamma_2})/(2+2d_a)}).
• Multi-class extensions hold with a constant growing as M^2 in the number of classes.

Surprising findings

• The convergence rate depends only on the intrinsic dimension d_a of the absolutely continuous component rather than the ambient dimension d.

Limitations

• Requires bounded support of X so that the number of occupied cells is O(h^{-d_a}); unbounded support needs tail control.
• Privatisation bounds are slower, with estimation error depending on h^{-2d_a}, and the CLT approximation prevents super-fast rates when min(gamma,gamma_1) >= 1.
• Purely theoretical; no experiments are reported.

Experimental setup

Metrics: convergence rate of expected excess risk

Baselines: plug-in partitioning classifier with SDA privatised partitioning classifier (Kohler-Krzyzak-type LDP)

Builds on: partitioning classification (Györfi et al.) margin condition (Mammen-Tsybakov) strong density assumption (Kohler-Krzyzak)

Closest papers by meaning

• Non-parametric classification via expand-and-sparsify representation (NeurIPS 2024 · similarity 0.84)
• Distribution-Specific Agnostic Conditional Classification With Halfspaces (ICLR 2025 · similarity 0.84)
• Attribute-Efficient Learning of Sparse Halfspaces with Constant Malicious Noise Rate (NeurIPS 2026 · similarity 0.83)
• Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise (ICML 2025 · similarity 0.83)
• The optimality of kernel classifiers in Sobolev space (ICLR 2024 · similarity 0.83)
• Public-data Assisted Private Stochastic Optimization: Power and Limitations (NeurIPS 2024 · similarity 0.83)