8 citations · 13 across the 13 of their papers we have counts for
8 papers · 1 filter
Streaming Algorithms for Monotonicity Testing
Amir Azarmehr, Soheil Behnezhad, Lily Chung +3
Consider a poset - or equivalently an -vertex DAG - and a boolean function on its vertex set. We say is monotone if f…
Robust learning of halfspaces under log-concave marginals
Jane Lange, Arsen Vasilyan
We say that a classifier is \emph{adversarially robust} to perturbations of norm if, with high probability over a point drawn from the input distribution, there is no point…
Local Lipschitz Filters for Bounded-Range Functions with Applications to Arbitrary Real-Valued Functions
Jane Lange, Ephraim Linder, Sofya Raskhodnikova +1
We study local filters for the Lipschitz property of real-valued functions , where the Lipschitz property is defined with respect to an arbitrary undirected graph $…
Agnostic proper learning of monotone functions: beyond the black-box correction barrier
Jane Lange, Arsen Vasilyan
We give the first agnostic, efficient, proper learning algorithm for monotone Boolean functions. Given uniformly random examples of an unknown…
Properly learning decision trees in almost polynomial time
Guy Blanc, Jane Lange, Mingda Qiao +1
We give an -time membership query algorithm for properly and agnostically learning decision trees under the uniform distribution over . Even in the…
Query strategies for priced information, revisited
Guy Blanc, Jane Lange, Li-Yang Tan
We consider the problem of designing query strategies for priced information, introduced by Charikar et al. In this problem the algorithm designer is given a function $f : \{0,1\}^…