More Like this

1. PAC-Wrap: Semi-Supervised PAC Anomaly Detection

   Ji, X.; Li, S.; Dobriban, E.; Sokolsky, O.; Lee I. (June 2022, KDD)
2. Collaborative PAC Learning

   Blum, Avrim; Haghtalab, Nika; Procaccia, Ariel D; Qiao, Mingda (December 2017, NIPS 2017)

   We consider a collaborative PAC learning model, in which k players attempt to learn the same underlying concept. We ask how much more information is required to learn an accurate classifier for all players simultaneously. We refer to the ratio between the sample complexity of collaborative PAC learning and its non-collaborative (single-player) counterpart as the overhead. We design learning algorithms with O(ln(k)) and O(ln2 (k)) overhead in the personalized and centralized variants our model. This gives an exponential improvement upon the naïve algorithm that does not share information among players. We complement our upper bounds with an Ω(ln(k)) overhead lower bound, showing that our results are tight up to a logarithmic factor. 

   more » « less
3. Incentive-Aware PAC Learning

   Zhang, Hanrui; Conitzer, Vincent (January 2021, Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21))
4. PAC Learning with Improvements

   Attias, Idan; Blum, Avrim; Naggita, Keziah; Saless, Donya; Sharma, Dravyansh; Walter, Matthew (July 2025, Proceedings of the 42nd International Conference on Machine Learning (ICML))
5. Actor-Critic PAC Robust Policy Search

   Sheckells, Matthew; Garimella, Gowtham; Michra, Subhransu; Kobilarov, Marin (May 2019, ICRA 2019)

   This work studies an approach for computing provably robust control laws for robotic systems operating in uncertain environments. We develop an actor-critic style policy search algorithm based on the idea of minimizing an upper confidence bound on the negative expected advantage of a control policy at each policy update iteration. This new algorithm is a reformulation of Probably-Approximately-Correct Robust Policy Search (PROPS) and, unlike PROPS, allows for both step-based evaluation and step-based sampling strategies in policy parameter space, enabled by the use of Generalized Advantage Estimation and Generalized Exploration. As a result, the new algorithm is more data efficient and is expected to compute higher quality policies faster. We empirically evaluate the algorithm in simulation on a challenging robot navigation task using a high-fidelity deep stochastic model of an agile ground vehicle and compare its performance to the original trajectory-based PROPS 

   more » « less