Research map / Learning theory and algorithms / Sample complexity
Replicable Learning of Large-Margin Halfspaces
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.
Gives new efficient, proper, dimension-independent replicable learners for tau-margin halfspaces via batched SVM averaging, Johnson-Lindenstrauss projection, and Alon-Klartag rounding, plus SGD and inefficient variants with improved sample complexity.
Problem
Replicable PAC learning of large-margin halfspaces with sample complexity that is dimension-independent and computationally efficient, improving on Impagliazzo et al. (2022).
Approach
Run SVM on independent batches, average the resulting unit normals, project with a data-oblivious JL matrix to dimension depending only on tau, and round with the Alon-Klartag randomized rounding scheme using shared randomness so that two executions output identical vectors with high probability.
Key results
- Efficient proper replicable algorithm with sample complexity eps^-1 tau^-7 rho^-2 (poly time), improving on ILPS22's (d eps^-3 tau^-8 rho^-2)^1.01 and (d^3 eps^-4 tau^-10 rho^-2)^1.01.
- SGD-based variant achieves eps^-2 tau^-6 rho^-2 sample complexity in poly time.
- Inefficient algorithm achieves eps^-1 tau^-4 rho^-2 samples with running time poly(d)*poly(1/eps,1/tau,1/rho,1/delta)^(1/tau^2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace ILPS22 rounding-and-boosting algorithms with the efficient batch-SVM algorithm | Replicable learning of τ-margin halfspaces · τ-margin halfspaces | sample complexity: (d \epsilon^{-3} \tau^{-8} \rho^{-2} )^{1.01} -> \epsilon^{-1} \tau^{-7} \rho^{-2}; (d^3 \epsilon^{-4} \tau^{-10} \rho^{ | Helped |
| Use the SGD-based algorithm instead of the efficient batch-SVM algorithm | Replicable learning of τ-margin halfspaces · τ-margin halfspaces | sample complexity dependence on τ: \epsilon^{-1} \tau^{-7} \rho^{-2} -> \epsilon^{-2} \tau^{-6} \rho^{-2} | Helped |
| Use the SGD-based algorithm instead of the efficient batch-SVM algorithm | Replicable learning of τ-margin halfspaces · τ-margin halfspaces | sample complexity dependence on ε: \epsilon^{-1} -> \epsilon^{-2} | Hurt |
| Apply the DP-to-replicability reduction | Replicable learning of τ-margin halfspaces · τ-margin halfspaces | sample complexity dependence on τ: \tau^{-8} -> \tau^{-4}; \tau^{-10} -> \tau^{-4} | Helped |
| Replace the DP-to-replicability algorithm with the improved inefficient algorithm | Replicable learning of τ-margin halfspaces · τ-margin halfspaces | sample complexity dependence on ε: \epsilon^{-2} -> \epsilon^{-1} | Helped |
| Replace the DP-to-replicability algorithm with the improved inefficient algorithm | Replicable learning of τ-margin halfspaces · τ-margin halfspaces | sample complexity: \epsilon^{-2} \tau^{-4} \rho^{-2} -> \epsilon^{-1} \tau^{-4} \rho^{-2} | Helped |
Limitations
- Sample complexity still has a tau^-4 or tau^-7 dependence, not matching the tau^-2 non-replicable rate.
- The best-tau algorithm is computationally inefficient, with running time exponential in 1/tau^2.
- Analysis of the aggregation step is pessimistic, using a pigeonhole argument.
Experimental setup
Metrics: sample complexity running time replicability parameter rho population error
Baselines: ILPS22 foams ILPS22 box DP-to-replicability reduction with LNUZ20 learner
Builds on: Impagliazzo et al. 2022 replicable learning DP-to-replicability reduction (Bun et al. 2023) Alon-Klartag rounding Johnson-Lindenstrauss lemma DP large-margin halfspace SGD (Kaplan et al.)
Closest papers by meaning
- A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise (NeurIPS 2024 · similarity 0.91)
- Reliable Learning of Halfspaces under Gaussian Marginals (NeurIPS 2024 · similarity 0.88)
- Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random (NeurIPS 2024 · similarity 0.88)
- An Efficient Tester-Learner for Halfspaces (ICLR 2024 · similarity 0.87)
- Tight Generalization Bounds for Large-Margin Halfspaces (NeurIPS 2025 · similarity 0.87)
- Smoothed Agnostic Learning of Halfspaces over the Hypercube (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.