📊 statistics

Exact Reformulation and Optimization for Direct Metric Optimization in Binary Imbalanced Classification

This paper introduces an exact constrained reformulation and optimization (ERO) framework that enables the direct and effective optimization of precision, recall, and F1-score in binary imbalanced classification without relying on smooth approximations, demonstrating superior performance over state-of-the-art methods across multiple benchmark datasets.

Original authors: Le Peng, Yash Travadi, Chuan He, Ying Cui, Ju Sun

Published 2026-08-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Le Peng, Yash Travadi, Chuan He, Ying Cui, Ju Sun

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of machine learning, computers learn to sort things into categories, much like a librarian organizing books by genre. This process, known as classification, is a cornerstone of modern technology, powering everything from medical diagnosis to fraud detection. However, the real world is rarely a perfect balance of categories. In many critical situations, one group is vastly smaller than the other. A bank might see millions of legitimate transactions but only a handful of fraudulent ones; a hospital might treat thousands of healthy patients but only a few with a rare disease. This imbalance creates a trap for standard computer programs. If a system simply guesses the majority class every time, it will appear highly accurate by sheer volume, yet it will fail completely at its most important job: finding the rare, critical cases.

To fix this, scientists have long tried to teach computers to care more about the rare group. They have developed various ways to measure success that go beyond simple accuracy, focusing instead on how well the system finds the rare items (a measure called recall) and how sure it is when it claims to have found one (a measure called precision). The challenge lies in the fact that these goals often pull in opposite directions. A system that is overly cautious might miss many rare cases to avoid false alarms, while a system that is too eager might catch every case but also flag too many innocent ones. For decades, researchers have struggled to build algorithms that can directly optimize these specific goals, particularly when they need to guarantee a certain level of performance, such as catching at least 95% of all frauds while keeping false alarms low. The mathematical tools required to do this have been notoriously difficult to use because the rules governing these decisions are jagged and discontinuous, making them resistant to the smooth, step-by-step improvements that most computer learning relies on.

A team of researchers has now developed a new approach that cuts through this mathematical difficulty to solve these problems directly. Instead of smoothing over the rough edges of the decision rules, as previous methods have done, they found a way to rewrite the problem so that the computer can navigate the jagged terrain exactly as it is. Their work focuses on three specific scenarios that matter deeply to real-world applications: maximizing the discovery of rare items while ensuring a high level of certainty, maximizing certainty while ensuring a high level of discovery, and finding the best possible balance between the two. By creating a precise mathematical reformulation of these tasks, they enabled the use of powerful optimization tools that were previously unable to handle the sharp, binary nature of these decisions.

The researchers tested their new method on a variety of real-world datasets, including medical images, text records, and financial transaction logs. In these tests, they compared their approach against the best existing tools currently available. The results were striking. While the older methods often failed to meet the strict requirements set for them—sometimes producing solutions that were mathematically impossible to use in practice—the new method consistently found solutions that satisfied the constraints. For instance, when tasked with finding at least 90% of positive cases while maintaining high precision, the new approach succeeded where others failed, delivering models that were both feasible and highly effective. In scenarios where the goal was to balance precision and recall, the new method again outperformed its competitors, finding better trade-offs that led to more reliable systems.

The core of this success lies in how the researchers handled the "indicator" function, a mathematical switch that turns on or off depending on whether a prediction is correct. Previous attempts to solve these problems replaced this sharp switch with a smooth, curved approximation, similar to trying to draw a square circle to make it easier to calculate. While this made the math easier, it introduced errors that made the final results unreliable, especially when strict rules were involved. The new method avoids this trap entirely. It introduces a set of auxiliary variables that act as a bridge, allowing the computer to work with the sharp, exact rules without losing the ability to calculate gradients, or directions of improvement. This allows the algorithm to climb toward the best possible solution without getting stuck or wandering off course due to approximation errors.

The team also demonstrated that their method is robust across different types of data. Whether dealing with images of bones, text describing medical conditions, or records of credit card usage, the approach held up. In many cases, the older methods produced models that looked good on paper but failed to meet the basic requirements when tested on new, unseen data. The new method, by contrast, maintained its performance, finding solutions that were not only optimal for the training data but also held their ground when applied to new situations. This suggests that the method does not just find a mathematical trick to fit the data, but actually learns a more reliable way to make decisions.

While the researchers acknowledge that their current work is deterministic and may need further development to scale to massive datasets, the results presented are a significant step forward. They have shown that it is possible to optimize these difficult, real-world metrics directly, without relying on the shaky ground of approximations. This opens the door for more reliable AI systems in high-stakes fields where missing a rare event or raising a false alarm can have serious consequences. By providing a framework that can handle the exact, unsmoothed nature of these problems, the work offers a clearer path for building intelligent systems that can be trusted to perform exactly as needed, even when the data is heavily skewed and the stakes are high.

Technical Summary: Exact Reformulation and Optimization for Direct Metric Optimization in Binary Imbalanced Classification

Problem Statement
In binary imbalanced classification (IC), standard metrics like accuracy are often misleading. While existing methods frequently optimize balanced accuracy or use smooth approximations to handle the non-differentiable nature of metrics like precision, recall, and the F1-score, these approaches face significant limitations. Specifically, when the significance of classes varies or specific metric levels must be guaranteed (e.g., ensuring recall $\ge$ 95% while maximizing precision), smooth approximations can lead to infeasible solutions or suboptimal operating points due to numerical discrepancies and vanishing gradients.

The paper addresses three Direct Metric Optimization (DMO) problems for binary IC:

FPOR: Fix Precision, Optimize Recall (maximize recall subject to precision $\ge \alpha$ ).
FROP: Fix Recall, Optimize Precision (maximize precision subject to recall $\ge \alpha$ ).
OFOS: Optimize F1-score (maximize the F1 metric directly).

The core technical challenge is that these metrics involve indicator functions ( $1\{f_\theta(x) > t\}$ ), which have zero gradients almost everywhere, rendering standard gradient-based optimization inapplicable. Furthermore, the constraints in FPOR and FROP are non-convex and non-linear, making it difficult to find feasible points.

Methodology
The authors propose an Exact Reformulation and Optimization (ERO) framework that avoids smooth approximations entirely. The methodology consists of three main components:

Exact Continuous Reformulation:
Instead of approximating the indicator function with a sigmoid, the authors introduce auxiliary continuous variables $s \in [0, 1]^N$ and reformulate the indicator constraint $s_i = 1\{f_\theta(x_i) > t\}$ using a novel equivalence based on piecewise linear functions.
- They establish that for $a \neq t$ , the condition $s = 1\{a > t\}$ is equivalent to $s + [s + a - 1 - t]_+ - [s + a - t]_+ = 0$ , where $[\cdot]_+ = \max(\cdot, 0)$ .
- This transformation replaces the discontinuous indicator with a continuous, piecewise linear function ( $H_t$ ) that possesses non-zero gradients almost everywhere, enabling the use of gradient-based methods.
- To ensure computational stability and avoid singular points where $f_\theta(x_i) = t$ , the equality constraints are relaxed to inequality constraints, and a barrier-style regularization term (based on cross-entropy) is added to the objective to encourage $s$ and $f_\theta$ to align at extreme values (0 or 1).
Theoretical Equivalence:
The paper proves that under mild conditions (specifically, non-singularity where $f_\theta(x_i) \neq t$ ), the global solutions of the reformulated problems are equivalent to the global solutions of the original DMO problems. This ensures that optimizing the reformulated problem yields valid solutions for the original metric constraints.
Exact Penalty Optimization:
To solve the resulting constrained optimization problem, the authors employ an exact penalty method with an $\ell_1$ -type penalty function. Unlike quadratic penalty methods or Lagrangian methods (used in frameworks like TFCO), which may only guarantee feasibility asymptotically or require specific multiplier conditions, the exact penalty method ensures that a feasible solution can be obtained for a sufficiently large (but finite) penalty parameter. The algorithm iteratively solves unconstrained subproblems using projected gradient methods (e.g., ADAM).

Key Contributions

Novel Reformulation: The first exact constrained reformulation for DMO problems that handles indicator functions without smooth approximations, inducing non-trivial gradients almost everywhere.
Theoretical Guarantees: Proof of equivalence between the original DMO problems and the reformulated versions, establishing that global solutions to one correspond to global solutions of the other.
Algorithmic Framework: A unified optimization framework using exact penalty methods that reliably finds feasible points for non-convex, non-linear constraints.
Empirical Superiority: Extensive experiments on four benchmark datasets (Eyepacs, MURA, ADE-Corpus-V2, and CreditCard) covering image, text, and tabular data.

Results
The ERO method was compared against state-of-the-art (SOTA) methods, including the TensorFlow Constrained Optimization (TFCO) library (which uses smooth approximations and Lagrangian methods) and various loss-based or sampling-based baselines (WCE, Focal Loss, LDAM, etc.).

Optimization Performance: ERO consistently outperformed all competing methods in finding feasible solutions that satisfy the metric constraints (e.g., precision $\ge$ 0.9). In contrast, non-DMO baselines often failed to produce feasible solutions, and TFCO frequently remained infeasible, particularly on the FPOR task.
Generalization: ERO achieved the best or near-best performance on test sets across all tasks. While generalization gaps existed (a common issue in IC), ERO maintained the most competitive trade-offs between the objective and the constraints.
Specific Findings:
- On FPOR (Fix Precision), ERO was the only method to consistently achieve feasibility across all datasets.
- On FROP (Fix Recall), ERO achieved the highest objective values among feasible solutions.
- On OFOS (Optimize F1), ERO consistently achieved the highest F1 scores during training and remained top-tier on test sets.

Significance and Claims
The paper claims that the ERO framework represents a significant advancement over existing DMO approaches by eliminating the reliance on smooth approximations, which are prone to numerical discrepancies and vanishing gradients. By providing an exact reformulation, the method ensures that the optimized metrics strictly adhere to the user-defined constraints, a critical requirement for high-stakes applications like healthcare and finance.

The authors note that while their current work focuses on binary IC and three specific metrics, the underlying technique is generalizable to other metrics (e.g., accuracy, NDCG, precision@k) and other learning settings (multiclass, object detection). They identify future work in extending these methods to stochastic optimization for large-scale datasets and understanding the generalization properties of constrained deep learning with overparameterized models. The code is made available to facilitate further research.

Technical Summary: Exact Reformulation and Optimization for Direct Metric Optimization in Binary Imbalanced Classification

More like this