6 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…
Distribution-Specific Auditing For Subgroup Fairness
Daniel Hsu, Jizhou Huang, Brendan Juba
We study the problem of auditing classifiers with the notion of statistical subgroup fairness. Kearns et al. (2018) has shown that the problem of auditing combinatorial subgroups f…
An Approximate Skolem Function Counter
Arijit Shaw, Brendan Juba, Kuldeep S. Meel
One approach to probabilistic inference involves counting the number of models of a given Boolean formula. Here, we are interested in inferences involving higher-order objects, i.e…