Machine Learning models increasingly affect people's lives, necessitating their audit for fairness and accuracy when applied to diverse populations. However, these models are often difficult to asses, either because they are considered proprietary by their developers in industry or government, or because no individual-level validation data is available to assess them. We consider a classification model applied to a given task, whose properties are impossible to estimate using a validation set, either due to an absence of representative individual-level labeled data or because access to the classifier, even as a black-box model, is impossible. Instead, only aggregate statistics on the rate of positive predictions in each of several sub-populations are available. In addition, we have access to the true rates of positive labels in each of these sub-populations. We show that these aggregate statistics can be used to lower-bound the discrepancy of a classifier, which is a measure that balances inaccuracy and unfairness. To this end, we define a new measure of unfairness, which is equal to the fraction of the population on which the classifier misbehaves, compared to its global, ideally fair behavior, as defined by the measure of equalized odds. We propose an efficient and practical procedure for finding the best possible lower bound on the discrepancy of the classifier, given the aggregate statistics. Experiments demonstrate the empirical tightness of this lower bound, as well as its possible uses on various types of problems, ranging from estimating the quality of voting polls to measuring the effectiveness of patient identification from internet search queries.