3 papers
cs.LG2026
Efficient Parameter Estimation of Truncated Boolean Product Distributions
Dimitris Fotakis, Alkis Kalavasis, Christos Tzamos
We study the problem of estimating the parameters of a Boolean product distribution in dimensions, when the samples are truncated by a set accessible thr…
cs.LG2025
Learning Intersections of Two Margin Halfspaces under Factorizable Distributions
Ilias Diakonikolas, Mingchen Ma, Lisheng Ren +1
Learning intersections of halfspaces is a central problem in Computational Learning Theory. Even for just two halfspaces, it remains a major open question whether learning is possi…
cs.LG2025
Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise
Ilias Diakonikolas, Mingchen Ma, Lisheng Ren +1
We study the task of Multiclass Linear Classification (MLC) in the distribution-free PAC model with Random Classification Noise (RCN). Specifically, the learner is given a set of l…