5 papers
Multitask Learning via Shared Features: Algorithms and Hardness
Konstantina Bairaktari, Guy Blanc, Li-Yang Tan +2
We investigate the computational efficiency of multitask learning of Boolean functions over the -dimensional hypercube, that are related by means of a feature representation of…
Differentially Private Decomposable Submodular Maximization
Anamay Chaturvedi, Huy Nguyen, Lydia Zakynthinou
We study the problem of differentially private constrained maximization of decomposable submodular functions. A submodular function is decomposable if it takes the form of a sum of…
Reasoning About Generalization via Conditional Mutual Information
Thomas Steinke, Lydia Zakynthinou
We provide an information-theoretic framework for studying the generalization properties of machine learning algorithms. Our framework ties together existing approaches, including…
Efficient Private Algorithms for Learning Large-Margin Halfspaces
Huy L. Nguyen, Jonathan Ullman, Lydia Zakynthinou
We present new differentially private algorithms for learning a large-margin halfspace. In contrast to previous algorithms, which are based on either differentially private simulat…
Improved Algorithms for Collaborative PAC Learning
Huy L. Nguyen, Lydia Zakynthinou
We study a recent model of collaborative PAC learning where players with different tasks collaborate to learn a single classifier that works for all tasks. Previous work sh…