Replicable Learning of Large-Margin Halfspaces
<|reference_start|>Replicable Learning of Large-Margin Halfspaces: 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 $\epsilon$. 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 $\tau$, but running time doubly exponential in $1/\tau^2$ and worse sample complexity dependence on $\epsilon$ 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/\tau^{2}$.<|reference_end|>
@article{kalavasis2024replicable,
    title={Replicable Learning of Large-Margin Halfspaces},
    author={Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas,
  Felix Zhou},
    journal={arXiv preprint arXiv:2402.13857},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.13857},
    primaryClass={cs.LG}
}