# Implicit Rate-Constrained Optimization of Non-decomposable Objectives

arXiv: https://arxiv.org/abs/2107.10960 · HTML: https://mlsanity.com/paper/2107.10960/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 48 references that are in the map.
- First posted on arXiv 23 Jul 2021.

## Builds on (most cited first, 19 of 19)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [BigEarthNet: A Large-Scale Benchmark Archive For Remote Sensing Image Understanding](https://mlsanity.com/paper/1902.06148/) (2019)
- [Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals](https://mlsanity.com/paper/1809.04198/) (2018)
- [Satisfying Real-world Goals with Dataset Constraints](https://mlsanity.com/paper/1606.07558/) (2016)
- [Two-Player Games for Efficient Non-Convex Constrained Optimization](https://mlsanity.com/paper/1804.06500/) (2018)
- [Learning with Average Top-k Loss](https://mlsanity.com/paper/1705.08826/) (2017)
- [Scalable Learning of Non-Decomposable Objectives](https://mlsanity.com/paper/1608.04802/) (2016)
- [Online and Stochastic Gradient Methods for Non-decomposable Loss Functions](https://mlsanity.com/paper/1410.6776/) (2014)
- [Analysis and Optimization of Loss Functions for Multiclass, Top-k, and Multilabel Classification](https://mlsanity.com/paper/1612.03663/) (2016)
- [Optimizing Non-decomposable Performance Measures: A Tale of Two Classes](https://mlsanity.com/paper/1505.06812/) (2015)
- [Binary Classification with Karmic, Threshold-Quasi-Concave Metrics](https://mlsanity.com/paper/1806.00640/) (2018)
- [Calibrated Surrogate Maximization of Linear-fractional Utility in Binary Classification](https://mlsanity.com/paper/1905.12511/) (2019)
- [AP-Perf: Incorporating Generic Performance Metrics in Differentiable Learning](https://mlsanity.com/paper/1912.00965/) (2019)
- [Surrogate Functions for Maximizing Precision at the Top](https://mlsanity.com/paper/1505.06813/) (2015)
- [Constrained Classification and Ranking via Quantiles](https://mlsanity.com/paper/1803.00067/) (2018)

## Built on by (most cited first, 9 of 9)

- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [Rank-based Decomposable Losses in Machine Learning: A Survey](https://mlsanity.com/paper/2207.08768/) (2022)
- [Optimizing Two-way Partial AUC with an End-to-end Framework](https://mlsanity.com/paper/2206.11655/) (2022)
- [Lower-Left Partial AUC: An Effective and Efficient Optimization Metric for Recommendation](https://mlsanity.com/paper/2403.00844/) (2024)
- [Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm](https://mlsanity.com/paper/2210.03967/) (2022)
- [Cost-Sensitive Self-Training for Optimizing Non-Decomposable Metrics](https://mlsanity.com/paper/2304.14738/) (2023)
- [FERI: A Multitask-based Fairness Achieving Algorithm with Applications to Fair Organ Transplantation](https://mlsanity.com/paper/2310.13820/) (2023)
- [Exact Reformulation and Optimization for Direct Metric Optimization in Binary Imbalanced Classification](https://mlsanity.com/paper/2507.15240/) (2025)
- [Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations](https://mlsanity.com/paper/2512.01213/) (2025)

## Abstract (arXiv)

We consider a popular family of constrained optimization problems arising in machine learning that involve optimizing a non-decomposable evaluation metric with a certain thresholded form, while constraining another metric of interest. Examples of such problems include optimizing the false negative rate at a fixed false positive rate, optimizing precision at a fixed recall, optimizing the area under the precision-recall or ROC curves, etc. Our key idea is to formulate a rate-constrained optimization that expresses the threshold parameter as a function of the model parameters via the Implicit Function theorem. We show how the resulting optimization problem can be solved using standard gradient based methods. Experiments on benchmark datasets demonstrate the effectiveness of our proposed method over existing state-of-the art approaches for these problems. The code for the proposed method is available at https://github.com/google-research/google-research/tree/master/implicit_constrained_optimization .