Optimal Dimension-Free Sampling for Regularized Classification. Alishahi, M., Munteanu, A., Omlor, S., & Phillips, J. M. May, 2026. arXiv:2605.23726 [cs.LG]![Optimal Dimension-Free Sampling for Regularized Classification [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi abstract bibtex We prove optimal sampling bounds achieving (1 ± ε)-relative error for a broad class of Lipschitz continuous classification loss functions under various regularization terms. This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples. In particular, we prove k2/ε2 upper and lower bounds for ∥ · ∥2/k regularization, and k/ε2 upper and lower bounds for ∥ · ∥1/k regularization. For ∥ · ∥22/k regularization, the sampling complexity depends mainly on a bounded derivative property: if \textbarg′(x)\textbar ≤ g(x), and g(0) \textgreater 0, and g is monotonic or convex, then it admits linear in k sampling complexity; otherwise the general bound is k2/ε2. However, if g(0) = 0, our results indicate that no dimension-free bounds are possible, and even sublinear bounds are ruled out. All upper bounds are complemented by matching lower bounds up to polylogarithmic terms. Moreover, our work relies conceptually and algorithmically on simple uniform or (squared) norm sampling and hereby improves over recent cubic k3/ε2 sensitivity sampling bounds of (Alishahi and Phillips, ICML’24). This is achieved by refined arguments involving higher moment bounds and empirical process analyses to avoid overcounting that appears in the de-facto standard VC-dimension and sensitivity framework.
@misc{alishahi_optimal_2026,
title = {Optimal {Dimension}-{Free} {Sampling} for {Regularized} {Classification}},
url = {http://arxiv.org/abs/2605.23726},
doi = {10.48550/arXiv.2605.23726},
abstract = {We prove optimal sampling bounds achieving (1 ± ε)-relative error for a broad class of Lipschitz continuous classification loss functions under various regularization terms. This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples. In particular, we prove k2/ε2 upper and lower bounds for ∥ · ∥2/k regularization, and k/ε2 upper and lower bounds for ∥ · ∥1/k regularization. For ∥ · ∥22/k regularization, the sampling complexity depends mainly on a bounded derivative property: if {\textbar}g′(x){\textbar} ≤ g(x), and g(0) {\textgreater} 0, and g is monotonic or convex, then it admits linear in k sampling complexity; otherwise the general bound is k2/ε2. However, if g(0) = 0, our results indicate that no dimension-free bounds are possible, and even sublinear bounds are ruled out. All upper bounds are complemented by matching lower bounds up to polylogarithmic terms. Moreover, our work relies conceptually and algorithmically on simple uniform or (squared) norm sampling and hereby improves over recent cubic k3/ε2 sensitivity sampling bounds of (Alishahi and Phillips, ICML’24). This is achieved by refined arguments involving higher moment bounds and empirical process analyses to avoid overcounting that appears in the de-facto standard VC-dimension and sensitivity framework.},
language = {en},
urldate = {2026-06-15},
publisher = {arXiv},
author = {Alishahi, Meysam and Munteanu, Alexander and Omlor, Simon and Phillips, Jeff M.},
month = may,
year = {2026},
note = {arXiv:2605.23726 [cs.LG]},
keywords = {Computer Science - Data Structures and Algorithms, Computer Science - Machine Learning, Statistics - Machine Learning, WG: Observable},
}
Downloads: 0
{"_id":"eC7vJpxiu3K93m6Xo","bibbaseid":"alishahi-munteanu-omlor-phillips-optimaldimensionfreesamplingforregularizedclassification-2026","author_short":["Alishahi, M.","Munteanu, A.","Omlor, S.","Phillips, J. M."],"bibdata":{"bibtype":"misc","type":"misc","title":"Optimal Dimension-Free Sampling for Regularized Classification","url":"http://arxiv.org/abs/2605.23726","doi":"10.48550/arXiv.2605.23726","abstract":"We prove optimal sampling bounds achieving (1 ± ε)-relative error for a broad class of Lipschitz continuous classification loss functions under various regularization terms. This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples. In particular, we prove k2/ε2 upper and lower bounds for ∥ · ∥2/k regularization, and k/ε2 upper and lower bounds for ∥ · ∥1/k regularization. For ∥ · ∥22/k regularization, the sampling complexity depends mainly on a bounded derivative property: if \\textbarg′(x)\\textbar ≤ g(x), and g(0) \\textgreater 0, and g is monotonic or convex, then it admits linear in k sampling complexity; otherwise the general bound is k2/ε2. However, if g(0) = 0, our results indicate that no dimension-free bounds are possible, and even sublinear bounds are ruled out. All upper bounds are complemented by matching lower bounds up to polylogarithmic terms. Moreover, our work relies conceptually and algorithmically on simple uniform or (squared) norm sampling and hereby improves over recent cubic k3/ε2 sensitivity sampling bounds of (Alishahi and Phillips, ICML’24). This is achieved by refined arguments involving higher moment bounds and empirical process analyses to avoid overcounting that appears in the de-facto standard VC-dimension and sensitivity framework.","language":"en","urldate":"2026-06-15","publisher":"arXiv","author":[{"propositions":[],"lastnames":["Alishahi"],"firstnames":["Meysam"],"suffixes":[]},{"propositions":[],"lastnames":["Munteanu"],"firstnames":["Alexander"],"suffixes":[]},{"propositions":[],"lastnames":["Omlor"],"firstnames":["Simon"],"suffixes":[]},{"propositions":[],"lastnames":["Phillips"],"firstnames":["Jeff","M."],"suffixes":[]}],"month":"May","year":"2026","note":"arXiv:2605.23726 [cs.LG]","keywords":"Computer Science - Data Structures and Algorithms, Computer Science - Machine Learning, Statistics - Machine Learning, WG: Observable","bibtex":"@misc{alishahi_optimal_2026,\n\ttitle = {Optimal {Dimension}-{Free} {Sampling} for {Regularized} {Classification}},\n\turl = {http://arxiv.org/abs/2605.23726},\n\tdoi = {10.48550/arXiv.2605.23726},\n\tabstract = {We prove optimal sampling bounds achieving (1 ± ε)-relative error for a broad class of Lipschitz continuous classification loss functions under various regularization terms. This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples. In particular, we prove k2/ε2 upper and lower bounds for ∥ · ∥2/k regularization, and k/ε2 upper and lower bounds for ∥ · ∥1/k regularization. For ∥ · ∥22/k regularization, the sampling complexity depends mainly on a bounded derivative property: if {\\textbar}g′(x){\\textbar} ≤ g(x), and g(0) {\\textgreater} 0, and g is monotonic or convex, then it admits linear in k sampling complexity; otherwise the general bound is k2/ε2. However, if g(0) = 0, our results indicate that no dimension-free bounds are possible, and even sublinear bounds are ruled out. All upper bounds are complemented by matching lower bounds up to polylogarithmic terms. Moreover, our work relies conceptually and algorithmically on simple uniform or (squared) norm sampling and hereby improves over recent cubic k3/ε2 sensitivity sampling bounds of (Alishahi and Phillips, ICML’24). This is achieved by refined arguments involving higher moment bounds and empirical process analyses to avoid overcounting that appears in the de-facto standard VC-dimension and sensitivity framework.},\n\tlanguage = {en},\n\turldate = {2026-06-15},\n\tpublisher = {arXiv},\n\tauthor = {Alishahi, Meysam and Munteanu, Alexander and Omlor, Simon and Phillips, Jeff M.},\n\tmonth = may,\n\tyear = {2026},\n\tnote = {arXiv:2605.23726 [cs.LG]},\n\tkeywords = {Computer Science - Data Structures and Algorithms, Computer Science - Machine Learning, Statistics - Machine Learning, WG: Observable},\n}\n\n\n\n","author_short":["Alishahi, M.","Munteanu, A.","Omlor, S.","Phillips, J. M."],"key":"alishahi_optimal_2026","id":"alishahi_optimal_2026","bibbaseid":"alishahi-munteanu-omlor-phillips-optimaldimensionfreesamplingforregularizedclassification-2026","role":"author","urls":{"Paper":"http://arxiv.org/abs/2605.23726"},"keyword":["Computer Science - Data Structures and Algorithms","Computer Science - Machine Learning","Statistics - Machine Learning","WG: Observable"],"metadata":{"authorlinks":{}},"downloads":0},"bibtype":"misc","biburl":"https://bibbase.org/zotero-group/pratikmhatre/5933976","dataSources":["yJr5AAtJ5Sz3Q4WT4"],"keywords":["computer science - data structures and algorithms","computer science - machine learning","statistics - machine learning","wg: observable"],"search_terms":["optimal","dimension","free","sampling","regularized","classification","alishahi","munteanu","omlor","phillips"],"title":"Optimal Dimension-Free Sampling for Regularized Classification","year":2026}