Mehryar Mohri
Mehryar Mohri leads the Learning Theory Team in Google Research. The team has extensive expertise in a variety of areas, including learning theory, statistical learning theory, optimization, decision making under uncertainty, reinforcement learning, and theory and algorithms in general.
Authored Publications
Sort By
Linear-Core Surrogates: Smooth Loss Functions with Linear Rates for Classification and Structured Prediction
Proceedings of the 43rd International Conference on Machine Learning (ICML 2026)
Preview abstract
A fundamental dichotomy in the theory of classification sets smoothness against statistical efficiency: smooth surrogate losses such as the logistic loss enable fast $O(1/T)$ optimization but yield slow square-root $H$-consistency bounds, while piecewise-linear losses like the Hinge loss achieve optimal linear $H$-consistency rates but are non-differentiable. We introduce Linear-Core (LC) Surrogates, the first family of explicit convex loss functions that provably resolve this tension. By stitching a linear core to a smooth tail, we construct surrogates that are differentiable everywhere ($C^1$, and even $C^2$ under mild conditions) while retaining strict linear $H$-consistency bounds, the strongest known form of consistency guarantee. We establish these linear bounds across three increasingly complex settings: binary classification, multi-class classification, and structured prediction. To our knowledge, this is the first explicit construction to simultaneously achieve smoothness and linear $H$-consistency in any of these settings. Beyond their theoretical appeal, Linear-Core Surrogates offer practical advantages. In multi-class classification, their constant gradient profile near the decision boundary provides natural robustness to instance-dependent label noise, outperforming Cross-Entropy by 2.6% on corrupted CIFAR-10. In structured prediction, their smoothness enables an unbiased stochastic gradient estimator that bypasses the $O(|Y|^2)$ per-step complexity of exact inference, yielding a 23$\times$ speedup over Structured SVMs on large-vocabulary sequence tagging tasks.
View details
Optimized Deferral for Imbalanced Settings
Anqi Mao
Proceedings of the 43rd International Conference on Machine Learning (ICML 2026)
Preview abstract
Learning algorithms can be significantly improved by routing complex or uncertain inputs to specialized experts, balancing accuracy with computational cost. This approach, known as learning to defer, is essential in domains like natural language generation, medical diagnosis, and computer vision, where an effective deferral can reduce errors at low extra resource consumption. However, the two-stage learning to defer setting, which leverages existing predictors such as a collection of LLMs or other classifiers, often faces challenges due to an expert imbalance problem. This imbalance can lead to suboptimal performance, with deferral algorithms favoring the majority expert. We present a comprehensive study of two-stage learning to defer in expert imbalance settings. We cast the deferral loss optimization as a novel cost-sensitive learning problem over the input-expert domain. We derive new margin-based loss functions and guarantees tailored to this setting, and develop novel algorithms for cost-sensitive learning. Leveraging these results, we design principled deferral algorithms, MILD (Margin-based Imbalanced Learning to Defer), specifically suited for expert imbalance settings. Extensive experiments demonstrate the effectiveness of our approach, showing clear improvements over existing baselines on both image classification and real-world Large Language Model (LLM) routing tasks.
View details
A Theoretical Framework for Modular Learning of Robust Generative Models
Proceedings of the 43rd International Conference on Machine Learning (ICML 2026)
Preview abstract
Training large-scale generative models is resource-intensive and relies heavily on heuristic dataset weighting. We address two fundamental questions: Can we train Large Language Models (LLMs) modularly, combining small, domain-specific experts to match monolithic performance, and can we do so robustly for any data mixture, eliminating heuristic tuning? We present a theoretical framework for modular generative modeling where a set of pre-trained experts are combined via a gating mechanism. We define the space of normalized gating functions $\mathcal{G}_{1}$ and formulate the problem as a minimax game to find a single robust gate that minimizes divergence to the worst-case data mixture. We prove the existence of such a robust gate using Kakutani's fixed-point theorem and show that modularity acts as a strong regularizer, with generalization bounds scaling with the lightweight gate's complexity. Furthermore, we prove that this modular approach can theoretically outperform models retrained on aggregate data, with the gap characterized by the Jensen-Shannon Divergence. Finally, we introduce a scalable Stochastic Primal-Dual algorithm and a Structural Distillation method for efficient inference. Empirical results on synthetic and real-world datasets confirm that our modular architecture effectively mitigates gradient conflict and can robustly outperform monolithic baselines.
View details
Beyond Tsybakov: Model Margin Noise and H-Consistency Bounds
The Nineteenth International Symposium on Artificial Intelligence and Mathematics (ISAIM 2026)
Preview abstract
We introduce a new low-noise condition for classification, the *Model Margin Noise (MM noise)* assumption, and derive enhanced $H$-consistency bounds under this condition. MM noise is *weaker* than Tsybakov noise condition: it is implied by Tsybakov noise condition but can hold even when Tsybakov fails, because it depends on the discrepancy between a given hypothesis and the Bayes-classifier rather than on the intrinsic distributional minimal margin (see Figure 1 for an illustration of an explicit example). This hypothesis-dependent assumption yields enhanced $H$-consistency bounds for both binary and multi-class classification. Our results extend the enhanced $H$-consistency bounds of Mao, Mohri, and Zhong (2025a) with the same favorable exponents but under a weaker assumption than the Tsybakov noise condition; they interpolate smoothly between linear and square-root regimes for intermediate noise levels. We also instantiate these bounds for common surrogate loss families and provide illustrative tables.
View details
Preview abstract
We study machine unlearning in large generative models by framing the task as likelihood-ratio estimation rather than supervised fine-tuning. While classifier guidance is a standard approach for approximating the target density ratio and can succeed in general, we show it can fail to faithfully unlearn with finite samples when the forget set represents a sharp, concentrated data distribution. To address this, we introduce \textbf{Temper-Then-Tilt Unlearning (\alg)}, which freezes the base model and applies a two-step inference procedure: (i) \textit{tempering} the base distribution to flatten high-confidence spikes, and (ii) \textit{tilting} the tempered distribution using a lightweight classifier trained to distinguish retain from forget samples. Our theoretical analysis provides finite-sample guarantees linking the surrogate classifier's risk to unlearning quality, proving that tempering is necessary to successfully unlearn for concentrated distributions. Empirical evaluations on the TOFU benchmark demonstrate that \alg improves forget quality and generative utility over existing baselines, while training only a fraction of the parameters with a minimal runtime.
View details
Mind the Gap: Structure-Aware Consistency in Preference Learning
Proceedings of the 43rd International Conference on Machine Learning (ICML 2026)
Preview abstract
Aligning Large Language Models (LLMs) with human intent, whether through explicit reward modeling or direct methods such as DPO, fundamentally relies on minimizing a surrogate loss as a proxy for the true pairwise ranking objective. We prove that this reliance is flawed for the standard surrogate losses used: for the equicontinuous hypothesis sets characteristic of neural networks, no standard surrogate provides a meaningful consistency guarantee. Minimizing the surrogate loss to zero can leave the true ranking error arbitrarily high. To resolve this, we formulate LLM alignment within a margin-shifted ranking framework and derive $H$-consistency bounds showing that enforcing a confidence margin $\gamma$ is not merely beneficial but necessary for consistency. We further introduce Structure-Aware $H$-consistency and a corresponding objective (SA-DPO) that adapts the margin to the semantic distance between responses, preventing instability on near-synonymous pairs. Finally, we analyze the trade-off between the margin required for consistency and the model's finite capacity to satisfy it, revealing a strict hierarchy of surrogate losses: heavy-tailed surrogates (e.g., the Polynomial Hinge family) offer strictly superior consistency guarantees for capacity-bounded models compared to the logistic loss used in DPO. Experiments on UltraFeedback and Argilla DPO-Mix-7k confirm that SA-DPO consistently outperforms DPO and SimPO, with a 58.5% head-to-head win-rate in downstream generation quality.
View details
Enhanced $H$-Consistency Bounds
Anqi Mao
Proceedings of the 36th International Conference on Algorithmic Learning Theory (ALT 2025)
Preview abstract
Recent research has introduced a key notion of $H$-consistency bounds for surrogate losses. These bounds offer finite-sample guarantees, quantifying the relationship between the zero-one estimation error (or other target loss) and the surrogate loss estimation error for a specific hypothesis set. However, previous bounds were derived under the condition that a lower bound of the surrogate loss conditional regret is given as a convex function of the target conditional regret, without non-constant factors depending on the predictor or input instance. Can we derive finer and more favorable $H$-consistency bounds? In this work, we relax this condition and present a general framework for establishing *enhanced $H$-consistency bounds* based on more general inequalities relating conditional regrets. Our theorems not only subsume existing results as special cases but also enable the derivation of more favorable bounds in various scenarios. These include standard multi-class classification, binary and multi-class classification under Tsybakov noise conditions, and bipartite ranking.
View details
Preview abstract
We present new efficient algorithms for high-dimensional calibration via reduction to the TreeSwap algorithm of Dagan et al.
View details
Principled Algorithms for Optimizing Generalized Metrics in Binary Classification
Anqi Mao
Proceedings of the 42nd International Conference on Machine Learning (ICML 2025)
Preview abstract
In applications with significant class imbalance or asymmetric costs, metrics such as the $F_\beta$-measure, AM measure, Jaccard similarity coefficient, and weighted accuracy offer more suitable evaluation criteria than standard binary classification loss. However, optimizing these metrics present significant computational and statistical challenges. Existing approaches often rely on the characterization of the Bayes-optimal classifier, and use threshold-based methods that first estimate class probabilities and then seek an optimal threshold. This leads to algorithms that are not tailored to restricted hypothesis sets and lack finite-sample performance guarantees. In this work, we introduce principled algorithms for optimizing generalized metrics, supported by $H$-consistency and finite-sample generalization bounds. Our approach reformulates metric optimization as a generalized cost-sensitive learning problem, enabling the design of novel surrogate loss functions with provable $H$-consistency guarantees. Leveraging this framework, we develop new algorithms, METRO (*Metric Optimization*), with strong theoretical performance guarantees. We report the results of experiments demonstrating the effectiveness of our methods compared to prior baselines.
View details
Balancing the Scales: A Theoretical and Algorithmic Framework for Learning from Imbalanced Data
Anqi Mao
Proceedings of the 42nd International Conference on Machine Learning (ICML 2025)
Preview abstract
Class imbalance remains a major challenge in machine learning, especially in multi-class problems with long-tailed distributions. Existing methods, such as data resampling, cost-sensitive techniques, and logistic loss modifications, though popular and often effective, lack solid theoretical foundations. As an example, we demonstrate that cost-sensitive methods are not Bayes-consistent. This paper introduces a novel theoretical framework for analyzing generalization in imbalanced classification. We propose a new class-imbalanced margin loss function for both binary and multi-class settings, prove its strong $H$-consistency, and derive corresponding learning guarantees based on empirical loss and a new notion of class-sensitive Rademacher complexity. Leveraging these theoretical results, we devise novel and general learning algorithms, IMMAX (*Imbalanced Margin Maximization*), which incorporate confidence margins and are applicable to various hypothesis sets. While our focus is theoretical, we also present extensive empirical results demonstrating the effectiveness of our algorithms compared to existing baselines.
View details
