{"id":7334,"date":"2025-10-03T07:03:07","date_gmt":"2025-10-03T07:03:07","guid":{"rendered":"https:\/\/mailitics.com\/index.php\/2025\/10\/03\/2510-01291\/"},"modified":"2025-10-03T07:03:07","modified_gmt":"2025-10-03T07:03:07","slug":"2510-01291","status":"publish","type":"post","link":"https:\/\/mailitics.com\/index.php\/2025\/10\/03\/2510-01291\/","title":{"rendered":"Private Realizable-to-Agnostic Transformation with Near-Optimal Sample Complexity"},"content":{"rendered":"

Private Realizable-to-Agnostic Transformation with Near-Optimal Sample Complexity
\n \t

\n
<\/BR>
\n
\n \t

\n
<\/BR><\/p>\n

arXiv:2510.01291v1 Announce Type: new
\nAbstract: 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 $alpha$, 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})\/alpha^2)$, which is essentially tight assuming a constant privacy parameter $varepsilon = Theta(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})\/alpha^2varepsilon)$ that involves a $1\/varepsilon$ factor.
\n 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})\/alpha^2)$ for any $varepsilonle 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).<\/div>\n

\t

\n
<\/BR>
\n Bo Li, Wei Wang, Peng Ye
\n \t

\n
<\/BR>
\nGo to original source<\/a>
\n \t

\n
<\/BR><\/p>\n","protected":false},"excerpt":{"rendered":"

Private Realizable-to-Agnostic Transformation with Near-Optimal Sample Complexity arXiv:2510.01291v1 Announce Type: new 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 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[62,113,112],"tags":[3559,2449,3948],"class_list":["post-7334","post","type-post","status-publish","format-standard","hentry","category-aimldsaimlds","category-cs-lg","category-stat-ml","tag-agnostic","tag-private","tag-realizable"],"_links":{"self":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/7334"}],"collection":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/comments?post=7334"}],"version-history":[{"count":0,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/7334\/revisions"}],"wp:attachment":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/media?parent=7334"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/categories?post=7334"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/tags?post=7334"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}