4 papers
Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals
Jizhou Huang, Brendan Juba
We study three problems that involve identifying homogeneous halfspaces under Gaussian distributions: agnostic learning, one-sided reliable learning, and fairness auditing. In each…
The Limitations and Power of NP-Oracle-Based Functional Synthesis Techniques
Brendan Juba, Kuldeep S. Meel
Given a Boolean relational specification between inputs and outputs, the problem of functional synthesis is to construct a function that maps each assignment of the input to an ass…
Personalized Prediction By Learning Halfspace Reference Classes Under Well-Behaved Distribution
Jizhou Huang, Brendan Juba
In machine learning applications, predictive models are trained to serve future queries across the entire data distribution. Real-world data often demands excessively complex model…
Distribution-Specific Agnostic Conditional Classification With Halfspaces
Jizhou Huang, Brendan Juba
We study ``selective'' or ``conditional'' classification problems under an agnostic setting. Classification tasks commonly focus on modeling the relationship between features and c…