11 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…
Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees
Gautam Chandrasekaran, Adam R. Klivans, Lin Lin Lee +1
We give the first provably efficient algorithms for learning neural networks with distribution shift. We work in the Testable Learning with Distribution Shift framework (TDS learni…
Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
Gautam Chandrasekaran, Vasilis Kontonis, Konstantinos Stavropoulos +1
We study the problem of PAC learning -margin halfspaces with Massart noise. We propose a simple proper learning algorithm, the Perspectron, that has sample complexity $\widetild…
Learning the Sherrington-Kirkpatrick Model Even at Low Temperature
Gautam Chandrasekaran, Adam Klivans
We consider the fundamental problem of learning the parameters of an undirected graphical model or Markov Random Field (MRF) in the setting where the edge weights are chosen at ran…
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 hypoth…
Efficient Discrepancy Testing for Learning with Distribution Shift
Gautam Chandrasekaran, Adam R. Klivans, Vasilis Kontonis +2
A fundamental notion of distance between train and test distributions from the field of domain adaptation is discrepancy distance. While in general hard to compute, here we provide…
Learning in Online MDPs: Is there a Price for Handling the Communicating Case?
Gautam Chandrasekaran, Ambuj Tewari
It is a remarkable fact that the same regret rate can be achieved in both the Experts Problem and the Adversarial Multi-Armed Bandit problem albeit with a worse depen…