<div dir="ltr">Dear all,<div><br></div><div><div>We look forward to seeing you <b>this Tuesday (10/10)</b> from <b><font color="#ff0000">1</font></b><font color="#ff0000"><b>2:00-1:00 PM (U.S. Eastern time)</b></font> for the next talk of this semester's <b>CMU AI Seminar</b>, sponsored by <a href="https://sambanova.ai/" target="_blank">SambaNova Systems</a>. The seminar will be held in GHC 6115 <b>with pizza provided </b>and will<b> </b>be streamed on Zoom.</div><div><br></div><div>To learn more about the seminar series or to see the future schedule, please visit the <a href="http://www.cs.cmu.edu/~aiseminar/" target="_blank">seminar website</a>.</div><div><br></div><font color="#0b5394"><span style="background-color:rgb(255,255,0)">On this Tuesday (10/10), <u>Jane Lange</u> </span><span style="background-color:rgb(255,255,0)">(MIT) will be giving a talk titled </span><b style="background-color:rgb(255,255,0)">"</b><b style="background-color:rgb(255,255,0)">Agnostic Proper Learning of Monotone Functions: Beyond the Black-Box Correction Barrier</b></font><b style="color:rgb(11,83,148);background-color:rgb(255,255,0)">" </b><font color="#0b5394" style="background-color:rgb(255,255,0)">to present an <span style="caret-color: rgb(11, 83, 148);">agnostic, efficient, proper learning algorithm for monotone Boolean functions</span>.</font></div><div><font color="#0b5394"><span style="background-color:rgb(255,255,0)"><br></span><b>Title</b>: Agnostic Proper Learning of Monotone Functions: Beyond the Black-Box Correction Barrier <br><br></font><div><font color="#0b5394"><b>Talk Abstract</b>: We give the first agnostic, efficient, proper learning algorithm for monotone Boolean functions. Given 2^Õ(sqrt(n)/ε) uniformly random examples of an unknown function f:{±1}^n→{±1}, our algorithm outputs a hypothesis g:{±1}^n→{±1} that is monotone and (opt+ε)-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^Õ(sqrt(n)/ε), nearly matching the lower bound of Blais et al (RANDOM '15). We also give an algorithm for estimating up to additive error ε the distance of an unknown function f to monotone using a run-time of 2^Õ(sqrt(n)/ε). Previously, for both of these problems, sample-efficient algorithms were known, but these algorithms were not run-time efficient. Our work thus closes this gap in our knowledge between the run-time and sample complexity. </font><span style="color:rgb(11,83,148)">This work builds upon the improper learning algorithm of Bshouty and Tamon (JACM '96) and the proper </span>semiagnostic<span style="color:rgb(11,83,148)"> learning algorithm of Lange, Rubinfeld, and Vasilyan (FOCS '22), which obtains a non-monotone Boolean-valued hypothesis, then "corrects" it to monotone using query-efficient local computation algorithms on graphs. This black-box correction approach can achieve no error better than 2opt+ε information-theoretically; we bypass this barrier by a) augmenting the improper learner with a convex optimization step, and b) learning and correcting a real-valued function before rounding its values to Boolean. Our real-valued correction algorithm solves the "poset sorting'' problem of [LRV22] for functions over general posets with non-Boolean labels.</span></div><div><div><div><font color="#0b5394"> </font><font color="#0b5394"><br></font></div><div><font color="#0b5394"><b>Speaker Bio:</b><span class="gmail-Apple-converted-space"> </span>Jane Lange is a PhD student at MIT CSAIL studying theoretical computer science under Ronitt Rubinfeld. She is broadly interested in algorithms related to machine learning and property testing. More specifically, she is interested in the application of techniques from the fields of sublinear algorithms and analysis of Boolean functions for the purpose of designing efficient algorithms for learning, property testing, and other similar problems.<br></font></div><div><br></div><div><font color="#0b5394"><b>In person: </b>GHC 6115</font></div><div><font color="#0b5394"><b>Zoom Link</b>:  <a href="https://cmu.zoom.us/j/99510233317?pwd=ZGx4aExNZ1FNaGY4SHI3Qlh0YjNWUT09" target="_blank">https://cmu.zoom.us/j/99510233317?pwd=ZGx4aExNZ1FNaGY4SHI3Qlh0YjNWUT09</a></font></div></div></div></div><div><br></div><div>Thanks,</div><div>Asher Trockman</div></div>