Theory Seminar
— 4:30pm
Location:
In Person

Traffic21 Classroom, Gates Hillman 6501
Speaker:
ARSEN VASILYAN
Ph.D. Student, Department of Computer Science, Massachusetts Institute of Technology
https://arsenvasilyan.github.io/
Agnostic proper learning of monotone functions: beyond the blackbox correction barrier
We give the first agnostic, efficient, proper learning algorithm for monotone Boolean functions. Given $2^{\tilde{O}(n^0.5/\eps)}$ uniformly random examples of an unknown function $f:{0,1}^n \rightarrow {0,1}$, our algorithm outputs a hypothesis $g:{0,1}^n \rightarrow {0,1}$ that is monotone and $(opt + \eps)$close to $f$, where $opt$ is the distance from $f$ to the closest monotone function. The running time of the algorithm (and consequently the size and evaluation time of the hypothesis) is also $2^{\tilde{O}(n^0.5/\eps)}$, nearly matching the lower bound of Blais et al (RANDOM '15). We also give an algorithm for estimating up to additive error $\eps$ the distance of an unknown function $f$ to monotone using a runtime of $2^{\tilde{O}(n^0.5/\eps)}$.
Previously, for both of these problems, sampleefficient algorithms were known, but these algorithms were not runtime efficient. Our work thus closes this gap in our knowledge between the runtime and sample complexity. This work builds upon the improper learning algorithm of Bshouty and Tamon (JACM '96) and the proper semiagnostic learning algorithm of Lange, Rubinfeld, and Vasilyan (FOCS '22), which obtains a nonmonotone Booleanvalued hypothesis, then "corrects'" it to monotone using queryefficient local computation algorithms on graphs. This blackbox correction approach can achieve no error better than $2*opt + \eps$ informationtheoretically. We bypass this barrier by augmenting the improper learner with a convex optimization step, and learning and correcting a realvalued function before rounding its values to Boolean. Our realvalued correction algorithm solves the "poset sorting'" problem of [LRV22] for functions over general posets with nonBoolean labels.
Event Website:
http://theory.cs.cmu.edu/#talks