{"ID":2861866,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.01291","arxiv_id":"2510.01291","title":"Private Realizable-to-Agnostic Transformation with Near-Optimal Sample Complexity","abstract":"The realizable-to-agnostic transformation (Beimel et al., 2015; Alon et al., 2020) provides a general mechanism to convert a private learner in the realizable setting (where the examples are labeled by some function in the concept class) to a private learner in the agnostic setting (where no assumptions are imposed on the data). Specifically, for any concept class $\\mathcal{C}$ and error parameter $α$, a private realizable learner for $\\mathcal{C}$ can be transformed into a private agnostic learner while only increasing the sample complexity by $\\widetilde{O}(\\mathrm{VC}(\\mathcal{C})/α^2)$, which is essentially tight assuming a constant privacy parameter $\\varepsilon = Θ(1)$. However, when $\\varepsilon$ can be arbitrary, one has to apply the standard privacy-amplification-by-subsampling technique (Kasiviswanathan et al., 2011), resulting in a suboptimal extra sample complexity of $\\widetilde{O}(\\mathrm{VC}(\\mathcal{C})/α^2\\varepsilon)$ that involves a $1/\\varepsilon$ factor. In this work, we give an improved construction that eliminates the dependence on $\\varepsilon$, thereby achieving a near-optimal extra sample complexity of $\\widetilde{O}(\\mathrm{VC}(\\mathcal{C})/α^2)$ for any $\\varepsilon\\le 1$. Moreover, our result reveals that in private agnostic learning, the privacy cost is only significant for the realizable part. We also leverage our technique to obtain a nearly tight sample complexity bound for the private prediction problem, resolving an open question posed by Dwork and Feldman (2018) and Dagan and Feldman (2020).","short_abstract":"The realizable-to-agnostic transformation (Beimel et al., 2015; Alon et al., 2020) provides a general mechanism to convert a private learner in the realizable setting (where the examples are labeled by some function in the concept class) to a private learner in the agnostic setting (where no assumptions are imposed on...","url_abs":"https://arxiv.org/abs/2510.01291","url_pdf":"https://arxiv.org/pdf/2510.01291v1","authors":"[\"Bo Li\",\"Wei Wang\",\"Peng Ye\"]","published":"2025-10-01T04:49:43Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cs.LG\"]","methods":"[\"Generative Adversarial Network\"]","has_code":false}