3 papers
cs.LG2026
Optimal Dimension-Free Sampling for Regularized Classification
Meysam Alishahi, Alexander Munteanu, Simon Omlor +1
We prove optimal sampling bounds achieving -relative error for a broad class of Lipschitz continuous classification loss functions under various regularization t…
cs.LG2026
Scalable Learning of Multivariate Distributions via Coresets
Zeyu Ding, Katja Ickstadt, Nadja Klein +2
Efficient and scalable non-parametric or semi-parametric regression analysis and density estimation are of crucial importance to the fields of statistics and machine learning. Howe…
cs.CG2026
Hardness of High-Dimensional Linear Classification
Alexander Munteanu, Simon Omlor, Jeff M. Phillips
We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem, which models linear classification. Both are fundamental problems in computati…