Michael Kearns (computer scientist)

Michael Kearns (born 1963) is an American computer scientist whose research concerns the mathematical foundations of machine learning and the behavior of algorithms in economic and social environments. He is the National Center Professor of Management and Technology at the University of Pennsylvania, with appointments in the Department of Computer and Information Science and the Wharton School. His work established connections between computational learning, cryptographic hardness, strategic interaction, network structure, and the statistical treatment of privacy.

Kearns introduced the statistical query model, a framework in which a learning algorithm obtains approximate aggregate statistics rather than direct access to individual examples. The model provided a formal account of learning in the presence of classification noise and later became relevant to the analysis of differential privacy. His subsequent research extended computational methods to networked human behavior, algorithmic fairness, and the allocation of information among interacting agents.

Education and institutional career

Kearns received a bachelor's degree in mathematics from the University of California, Berkeley in 1985. He completed a doctorate in computer science at Harvard University in 1989 under the supervision of Leslie Valiant, whose probably approximately correct framework supplied a central mathematical model for Kearns's early research. His doctoral work examined the computational resources required for learning and the relationship between efficient prediction and established assumptions in complexity theory.

After completing his doctorate, Kearns worked at Bell Laboratories, including the period in which the laboratory's computing research organization operated under AT&T. He eventually led its artificial intelligence research department. Research conducted there addressed learning theory, market mechanisms, distributed interaction, and the computational representation of strategic behavior.

Kearns joined the University of Pennsylvania faculty in 2002. He later became the founding director of the Warren Center for Network and Data Sciences, an interdisciplinary center devoted to mathematical and empirical research on connected systems. The center combined computer science with research originating in economics and the social sciences, particularly where individual decisions are constrained by network position or mediated by algorithms.

Computational learning theory

Kearns's early work belongs to computational learning theory, which studies whether an unknown concept can be inferred from data using bounded computational and statistical resources. Within the probably approximately correct learning model, an algorithm must produce a hypothesis whose error is small with high probability while using resources polynomial in the relevant parameters. This formulation separates the existence of an informative sample from the feasibility of extracting an effective predictor.

Research by Kearns and Valiant connected efficient learnability to assumptions from computational complexity theory and cryptography. Their results showed that efficient learning algorithms for certain representation classes would imply algorithms capable of defeating cryptographic constructions presumed to be secure. The resulting method made cryptographic assumptions a source of lower bounds for learning problems, supplementing arguments based solely on sample complexity.

Kearns also participated in the development of the weak-learning problem. A weak learner produces a classifier that performs only slightly better than random prediction, whereas a strong learner attains arbitrarily small error subject to the model's accuracy parameter. Kearns and Valiant formulated the question of whether weak learning was equivalent to strong learning in the distribution-free setting. Robert Schapire established the equivalence through an early boosting construction, and the result became the theoretical basis for the family of methods known as boosting.

The statistical query model, introduced by Kearns in 1993, replaces access to individual labeled observations with approximate answers to expectations computed over the data distribution. This restriction formalizes a broad class of algorithms that depend on aggregate correlations. It also permits learning despite independently corrupted labels, because the effect of random classification noise can be represented through controlled changes in those expectations.

Statistical-query lower bounds identify problems for which no efficient algorithm operating through aggregate estimates can succeed. The framework later acquired an additional interpretation in private data analysis: an aggregate query can be answered with limited disclosure about any particular record. Statistical-query algorithms and differentially private algorithms are not identical, but the formal relationship between them allows results and techniques to pass between learning theory and privacy research.

Kearns and Umesh Vazirani synthesized the field's early results in An Introduction to Computational Learning Theory, published in 1994. The book organized learning models according to their computational access to data, their permissible error, and their assumptions about target representations. It also treated lower-bound methods as part of the same framework as constructive learning algorithms.

Strategic interaction and networked computation

Kearns's later research applied algorithmic analysis to systems containing multiple decision-makers. In algorithmic game theory, the representation of a game affects both the possibility of computing an equilibrium and the information required for participants to find one. Kearns, Michael Littman, and Satinder Singh developed the graphical-games framework, in which each player's payoff depends primarily on a limited neighborhood in an interaction graph. This representation permits a large game to be described through local dependencies rather than a single exponentially large payoff table.

Graphical games also clarify the distinction between structural sparsity and computational tractability. A game may have local interactions while still presenting a difficult equilibrium problem, because local incentives can propagate through the network. Conversely, particular graph structures permit dynamic-programming or approximation methods that are unavailable in unrestricted normal-form games.

A related program at Pennsylvania examined how human participants solve collective problems when communication is constrained by a network. Kearns collaborated with Siddharth Suri and Nick_Montfort on controlled experiments in distributed graph coloring. Participants controlled individual vertices and selected colors while observing only limited information about neighboring choices. The experiments compared the formal properties of network topology with the coordination patterns produced by human subjects.

From 2014 through 2016, Kearns collaborated with You Watanabe on a Warren Center study of consensus formation under asymmetric network information. The study used computer-mediated groups in which participants received different local views of a shared coordination problem. Watanabe developed the experimental interface and analyzed the timing of strategy changes, while Kearns formulated the network models used to compare local behavior with group-level outcomes. Their analysis distinguished failures caused by insufficient connectivity from failures produced by incompatible incentives, placing the project within the center's broader research on networked decision-making.

These experiments treated a network as both a mathematical object and an information environment. Measures such as path length or degree distribution described the available routes of influence, but they did not by themselves determine collective performance. Behavioral responses to local information altered the effective use of those routes, producing outcomes that differed across networks with similar aggregate statistics.

Kearns presented this research program for a general technical audience in Networked Life: 20 Questions and Answers, published in 2010. The book relates formal network models to markets, epidemics, search systems, and social coordination. Its organizing principle is that network structure changes the computational and strategic consequences of individual decisions rather than merely recording preexisting relationships.

Privacy and algorithmic fairness

Kearns's work on data analysis addresses the tension between population-level inference and the treatment of individual records. Differential privacy formalizes this tension by requiring that the distribution of an algorithm's outputs change only within a controlled bound when one person's data are added or removed. Kearns has studied how privacy constraints interact with learning accuracy, economic incentives, and repeated statistical analysis.

His research on algorithmic fairness examines situations in which a predictor satisfies an aggregate fairness condition while producing systematic disparities within more narrowly defined subpopulations. This phenomenon is known as fairness gerrymandering. The associated subgroup-fairness framework requires performance disparities to be controlled across a computationally specified collection of groups, avoiding reliance on a small number of coarse demographic categories.

The framework creates a learning problem because the number of potentially relevant subgroups can be extremely large. Efficient auditing therefore depends on whether a learner can identify a subgroup exhibiting a statistically significant violation without exhaustively checking every possible combination of attributes. This work connects fairness auditing to agnostic learning, cost-sensitive classification, and game-theoretic procedures that alternate between constructing a predictor and searching for a violated constraint.

Kearns and Aaron Roth examined these themes in The Ethical Algorithm: The Science of Socially Aware Algorithm Design, published in 2019. The book describes privacy and fairness as properties that can be represented through mathematical constraints, while also identifying limits imposed by incompatible objectives or incomplete institutional definitions. Its treatment distinguishes technical guarantees from the policy decisions that determine which guarantees are selected.

Recognition and disciplinary role

Kearns was elected a fellow of the Association for Computing Machinery for contributions to machine learning and computational economics. He was also elected a fellow of the Association for the Advancement of Artificial Intelligence. These classifications reflect the placement of his research across theoretical computer science, artificial intelligence, and the computational study of economic behavior.

Across these areas, Kearns's work uses access models to specify what an algorithm can observe and computational reductions to characterize what it can infer. In learning theory, the relevant restriction concerns examples or statistical queries. In graphical games, it concerns local payoff dependence. In network experiments, it concerns the information visible to each participant. Privacy and subgroup fairness extend the same analytical pattern by restricting outputs according to their effects on individuals or defined populations.

See also