88 citations · 311 across the 59 of their papers we have counts for
9 papers · 1 filter
ReLU Regression with Massart Noise
Ilias Diakonikolas, Jongho Park, Christos Tzamos
We study the fundamental problem of ReLU regression, where the goal is to fit Rectified Linear Units (ReLUs) to data. This supervised learning task is efficiently solvable in the r…
Approximating Pandora's Box with Correlations
Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan +1
We revisit the classic Pandora's Box (PB) problem under correlated distributions on the box values. Recent work of arXiv:1911.01632 obtained constant approximate algorithms for a r…
Efficient Algorithms for Learning from Coarse Labels
Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis +1
For many learning problems one may not have access to fine grained label information; e.g., an image can be labeled as husky, dog, or even animal depending on the expertise of the…
Learning General Halfspaces with General Massart Noise under the Gaussian Distribution
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2
We study the problem of PAC learning halfspaces on with Massart noise under the Gaussian distribution. In the Massart model, an adversary is allowed to flip the labe…
Forster Decomposition and Learning Halfspaces with Noise
Ilias Diakonikolas, Daniel M. Kane, Christos Tzamos
A Forster transform is an operation that turns a distribution into one with good anti-concentration properties. While a Forster transform does not always exist, we show that any di…
A Statistical Taylor Theorem and Extrapolation of Truncated Densities
Constantinos Daskalakis, Vasilis Kontonis, Christos Tzamos +1
We show a statistical version of Taylor's theorem and apply this result to non-parametric density estimation from truncated samples, which is a classical challenge in Statistics \c…
Boosting in the Presence of Massart Noise
Ilias Diakonikolas, Russell Impagliazzo, Daniel Kane +3
We study the problem of boosting the accuracy of a weak learner in the (distribution-independent) PAC model with Massart noise. In the Massart noise model, the label of each exampl…
Pricing Ordered Items
Shuchi Chawla, Rojin Rezvan, Yifeng Teng +1
We study the revenue guarantees and approximability of item pricing. Recent work shows that with heterogeneous items, item-pricing guarantees an approximation to th…
Agnostic Proper Learning of Halfspaces under Gaussian Marginals
Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis +2
We study the problem of agnostically learning halfspaces under the Gaussian distribution. Our main result is the {\em first proper} learning algorithm for this problem whose sample…