# Replicable Learning of Large-Margin Halfspaces

arXiv: https://arxiv.org/abs/2402.13857 · HTML: https://mlsanity.com/paper/2402.13857/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 51 references that are in the map.
- First posted on arXiv 21 Feb 2024.

## Builds on (most cited first, 27 of 27)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [Statistical-Query Lower Bounds via Functional Gradients](https://mlsanity.com/paper/2006.15812/) (2020)
- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Replicable Bandits](https://mlsanity.com/paper/2210.01898/) (2022)
- [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021)
- [Replicable Reinforcement Learning](https://mlsanity.com/paper/2305.15284/) (2023)
- [Replicability in Reinforcement Learning](https://mlsanity.com/paper/2305.19562/) (2023)
- [Locating a Small Cluster Privately](https://mlsanity.com/paper/1604.05590/) (2016)
- [Near-Tight Margin-Based Generalization Bounds for Support Vector Machines](https://mlsanity.com/paper/2006.02175/) (2020)
- [Replicable Clustering](https://mlsanity.com/paper/2302.10359/) (2023)
- [Statistical Indistinguishability of Learning Algorithms](https://mlsanity.com/paper/2305.14311/) (2023)
- [Efficient, Noise-Tolerant, and Private Learning via Boosting](https://mlsanity.com/paper/2002.01100/) (2020)
- [Private Center Points and Learning of Halfspaces](https://mlsanity.com/paper/1902.10731/) (2019)
- [Local Borsuk-Ulam, Stability, and Replicability](https://mlsanity.com/paper/2311.01599/) (2023)
- [Efficient Private Algorithms for Learning Large-Margin Halfspaces](https://mlsanity.com/paper/1902.09009/) (2019)
- [List and Certificate Complexities in Replicable Learning](https://mlsanity.com/paper/2304.02240/) (2023)
- [The Bayesian Stability Zoo](https://mlsanity.com/paper/2310.18428/) (2023)
- [An Introduction to Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2103.00564/) (2021)
- [Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity](https://mlsanity.com/paper/2004.07839/) (2020)
- [User-Level Private Learning via Correlated Sampling](https://mlsanity.com/paper/2110.11208/) (2021)
- [Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise](https://mlsanity.com/paper/2306.16352/) (2023)
- [Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin](https://mlsanity.com/paper/1908.11335/) (2019)
- [Replicability and stability in learning](https://mlsanity.com/paper/2304.03757/) (2023)
- [Differentially Private Learning with Margin Guarantees](https://mlsanity.com/paper/2204.10376/) (2022)
- [Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy](https://mlsanity.com/paper/1307.3102/) (2013)

## Built on by (most cited first, 12 of 12)

- [Replicability in High Dimensional Statistics](https://mlsanity.com/paper/2406.02628/) (2024)
- [On the Computational Landscape of Replicable Learning](https://mlsanity.com/paper/2405.15599/) (2024)
- [Replicable Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2509.08660/) (2025)
- [Replicable Uniformity Testing](https://mlsanity.com/paper/2410.10892/) (2024)
- [Stability and List-Replicability for Agnostic Learners](https://mlsanity.com/paper/2501.05333/) (2025)
- [Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2503.15294/) (2025)
- [Replicable Distribution Testing](https://mlsanity.com/paper/2507.02814/) (2025)
- [Simplicial covering dimension of extremal concept classes](https://mlsanity.com/paper/2511.11819/) (2025)
- [The Sample Complexity of Replicable Realizable PAC Learning](https://mlsanity.com/paper/2602.19552/) (2026)
- [Model Agreement via Anchoring](https://mlsanity.com/paper/2602.23360/) (2026)
- [Tight list replicability bounds via a novel sphere covering theorem](https://mlsanity.com/paper/2606.06148/) (2026)
- [Sign-Rank, Index, and List Replicability: Connections and Separations](https://mlsanity.com/paper/2606.18236/) (2026)

## Abstract (arXiv)

We provide efficient replicable algorithms for the problem of learning large-margin halfspaces. Our results improve upon the algorithms provided by Impagliazzo, Lei, Pitassi, and Sorrell [STOC, 2022]. We design the first dimension-independent replicable algorithms for this task which runs in polynomial time, is proper, and has strictly improved sample complexity compared to the one achieved by Impagliazzo et al. [2022] with respect to all the relevant parameters. Moreover, our first algorithm has sample complexity that is optimal with respect to the accuracy parameter ε. We also design an SGD-based replicable algorithm that, in some parameters' regimes, achieves better sample and time complexity than our first algorithm. Departing from the requirement of polynomial time algorithms, using the DP-to-Replicability reduction of Bun, Gaboardi, Hopkins, Impagliazzo, Lei, Pitassi, Sorrell, and Sivakumar [STOC, 2023], we show how to obtain a replicable algorithm for large-margin halfspaces with improved sample complexity with respect to the margin parameter τ, but running time doubly exponential in 1/τ2 and worse sample complexity dependence on ε than one of our previous algorithms. We then design an improved algorithm with better sample complexity than all three of our previous algorithms and running time exponential in 1/τ2.