Arsen Vasilyan

Agnostic proper learning of monotone functions: beyond the black-box correction barrier

2023 · arXiv (Cornell University)

We give the first agnostic, efficient, proper learning algorithm for monotone Boolean functions. Given $2^{\tilde{O}(\sqrt{n}/\varepsilon)}$ uniformly random examples of an unknown function $f:\{\pm 1\}^n \rightarrow \{\pm 1\}$, our algorithm outputs a hypothesis $g:\{\pm 1\}^n \rightarrow …

Tolerant Algorithms for Learning with Arbitrary Covariate Shift

2024 · arXiv (Cornell University)

We study the problem of learning under arbitrary distribution shift, where the learner is trained on a labeled set from one distribution but evaluated on a different, potentially adversarially generated test distribution. We focus on …