10 papers
Iterative Chow Filtering for Learning with Distribution Shift
Gautam Chandrasekaran, Georgios Gkrinias, Adam R. Klivans +2
Recent work due to Goel et al. gave the first efficient algorithms for learning with distribution shift in the challenging PQ framework. In this setting, a learner receives labeled…
Learning Under Graphical Models
Gautam Chandrasekaran, Jason Gaitonde, Ankur Moitra +1
In a landmark result, Linial, Mansour and Nisan (J. ACM 1993) gave a quasipolynomial-time algorithm for learning constant-depth circuits given labeled i.i.d. samples under the unif…
A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube
Gautam Chandrasekaran, Adam R. Klivans, Konstantinos Stavropoulos +1
We give the first fully polynomial-time algorithm for learning halfspaces with respect to the uniform distribution on the hypercube in the presence of contamination, where an adver…
Sparse Linear Regression is Easy on Random Supports
Gautam Chandrasekaran, Raghu Meka, Konstantinos Stavropoulos
Sparse linear regression is one of the most basic questions in machine learning and statistics. Here, we are given as input a design matrix and meas…
Learning Juntas under Markov Random Fields
Gautam Chandrasekaran, Adam Klivans
We give an algorithm for learning juntas in polynomial-time with respect to Markov Random Fields (MRFs) in a smoothed analysis framework where only the external field h…
Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
Gautam Chandrasekaran, Adam Klivans, Vasilis Kontonis +2
In traditional models of supervised learning, the goal of a learner -- given examples from an arbitrary joint distribution on -- is to output a hypo…