Search for: All records

As algorithms increasingly inform and influence decisions made about individuals, it becomes increasingly important to address concerns that these algorithms might be discriminatory. The output of an algorithm can be discriminatory for many reasons, most notably: (1) the data used to train the algorithm might be biased (in various ways) to favor certain populations over others; (2) the analysis of this training data might inadvertently or maliciously introduce biases that are not borne out in the data. This work focuses on the latter concern. We develop and study multicalbration -- a new measure of algorithmic fairness that aims to mitigate concerns about discrimination that is introduced in the process of learning a predictor from data. Multicalibration guarantees accurate (calibrated) predictions for every subpopulation that can be identified within a specified class of computations. We think of the class as being quite rich; in particular, it can contain many overlapping subgroups of a protected group. We show that in many settings this strong notion of protection from discrimination is both attainable and aligned with the goal of obtaining accurate predictions. Along the way, we present new algorithms for learning a multicalibrated predictor, study the computational complexity of this task, and draw new connections to computational learning models such as agnostic learning. 

We present an explicit pseudorandom generator with seed length tildeO((log n)w+1) for read-once, oblivious, width w branching programs that can read their input bits in any order. This improves upon the work of Impaggliazzo, Meka and Zuckerman (FOCS'12) where they required seed length n^{1/2+o(1)}. A central ingredient in our work is the following bound that we prove on the Fourier spectrum of branching programs. For any width w read-once, oblivious branching program B : {0, 1}^n -> {0, 1}, any k in {1,2,...,n}, Sum_{S subseteq [n];|S|=k} |\hat{B}(S)| leq O(log n)^{wk}. This settles a conjecture posed by Reingold, Steinke, and Vadhan (RANDOM'13). Our analysis crucially uses a notion of local monotonicity on the edge labeling of the branching program. We carry critical parts of our proof under the assumption of local monotonicity and show how to deduce our results for unrestricted branching programs. 

The direct-sum question is a classical question that asks whether performing a task on m independent inputs is m times harder than performing it on a single input. In order to study this question, Beimel et al [BBKW14] introduced the following related problems: • The choice problem: Given m distinct instances, choose one of them and solve it. • The agreement problem: Given m distinct instances, output a solution that is correct for at least one of them. It is easy to see that these problems are no harder than performing the original task on a single instance, and it is natural to ask whether it is strictly easier or not. In particular, proving that the choice problem is not easier is necessary for proving a direct-sum theorem, and is also related to the KRW composition conjecture [KRW95]. In this note, we observe that in a variety of computational models, if f is a random function then with high probability its corresponding choice and agreement problem are not much easier than computing f on a single instance (as long as m is noticeably smaller than 2^n)