Regularizing Exact AUC Sweeps Without Losing Constant-Time Updates

Some optimizers find the exact best solution to a discrete objective by sweeping through every candidate and updating the score in constant time as they go, instead of recomputing it for each candidate. Does It Pay to Optimize AUC? built one of these for AUC (area under the ROC curve, the fraction of positive–negative pairs a scorer ranks correctly). Its method, AUC-opt, rotates a linear separator through every direction in the plane. The ranking of points changes only when the direction crosses a critical angle where two points swap order, so AUC changes by one pair at a time. The result is striking. AUC-opt beat standard classifiers on training data for 40 of 50 imbalanced UCI datasets, but in 3D it beat balanced logistic regression on test data for only 4 of 50. The authors conclude that exact optimization of the raw metric lacks the structural risk control that regularized models have. They leave open how to put regularization or early stopping inside the sweep without destroying its incremental update property.

This note proposes a way to do that. The sweep already visits every critical angle in order, so it can maintain more than the training AUC at almost no extra cost. It can also track held-out fold AUCs, and a smoothed "angular margin" version of training AUC that rewards directions whose neighbors are also good. Each is updated in constant time per event. The resulting optimizer is still exact, but it optimizes a regularized criterion chosen by internal cross-validation run inside a single sweep. The internal validation acts as a cheap pilot screen, and the untouched test split serves as the confirmation stage. The experiment also answers a question the original paper could not: was the overfitting caused by optimizing the wrong metric, or by optimizing the right metric with no regularization?

Core Claim

Two regularizers can be computed inside the topological sweep with only a constant-factor slowdown. The first is K-fold held-out AUC. The second is a window-smoothed training AUC over angle, which acts as a margin measured in angle. Selecting the separator by these regularized criteria should close most of the train–test gap that the original paper documents. The regularizers are built from counters and carry no parameters of their own.

The mechanism is simple. In 2D a direction is an angle $\theta$, and AUC as a function of $\theta$ is piecewise constant. It changes only at events where a positive–negative pair swaps order, and each such event shifts it by $\pm 1/(n_+ n_-)$. Now suppose all points are assigned to K folds before sweeping. A pair whose two points both lie outside fold $k$ updates the training counter for fold $k$. A pair whose two points both lie inside fold $k$ updates the held-out counter for fold $k$. Pairs that straddle folds update neither. Each event therefore costs $O(K)$ counter updates.

The smoothed criterion is

$$\tilde A_\delta(\theta) = \frac{1}{2\delta}\int_{\theta-\delta}^{\theta+\delta} A(\phi)\, d\phi,$$

where $A$ is training AUC and $\delta$ is a half-width in radians. Because $A$ is piecewise constant over the sorted event list, $\tilde A_\delta$ can be maintained with a sliding window, using two pointers that advance monotonically. It prefers wide plateaus of good ranking over narrow spikes. This is the angular analogue of preferring large-margin separators, and the spike-chasing that it penalizes is the behavior the original paper identifies as overfitting. The width $\delta$ is chosen by the fold counters within the same pass. The overall cost stays at the sort cost of the original algorithm times a factor of K.

Research Program

The first step is to reimplement AUC-opt in 2D and in the recursive-projection form it uses for 3D, and to match its reported training behavior on the 50-dataset UCI imbalanced suite with t-SNE projections to 2D and 3D. We then add the fold counters and the sliding-window smoother to every 2D sweep, including the inner sweeps of the 3D recursion.

The 3D case needs care. The recursive scheme fixes a projection and sweeps within it, so smoothing covers only one angular coordinate at a time. We will report whether smoothing along one angular coordinate at a time is enough, or whether a second smoothing pass across projections is needed. The 3D setting is where the failure (4 of 50) was worst, so this is where the proposal succeeds or fails.

The second step is a controlled study of which ingredient matters. We compare three variants: selection by held-out fold AUC alone, selection by $\tilde A_\delta$ with $\delta$ fixed, and selection by $\tilde A_\delta$ with $\delta$ chosen by folds. We also record the generalization gap (training AUC minus test AUC) as a function of $\delta$. If the gap shrinks steadily as $\delta$ grows, that directly confirms the overfitting diagnosis.

The third step is a short feasibility check on a second exact incremental optimizer. Learning Certifiably Optimal Rule Lists supplies the method here. CORELS computes objectives and lower bounds incrementally over a prefix tree and already penalizes rule count, and fold counters can be carried along the tree in the same way. We treat this only as evidence that the counter trick transfers, on COMPAS, and not as a main result.

The broader literature on incremental evaluation motivates the construction but does not supply it. A Joint Python/C++ Library for Efficient yet Accessible Black-Box and Gray-Box Optimization with GOMEA and Bayesian Structure Learning with Generative Flow Networks both use decomposable scores to update only the affected parts of an objective. Both assume the score being optimized is the one that should be optimized. Lithography Solvent Discovery using Neuro-Symbolic Search Agent shows the cost of that assumption: a surrogate-guided baseline maximized its proxy score and still had a 0% environment, health and safety (EHS) pass rate. Our contribution is to make the check against over-optimization itself incremental, rather than bolting it on afterward.

Baselines

The naive reference points are unbalanced logistic regression and plain AUC-opt. Plain AUC-opt is reported to win on training data for 40 of 50 datasets while generalizing poorly (Does It Pay to Optimize AUC?). Reproducing that gap is a precondition for the rest of the study.

The strongest existing competitor is balanced logistic regression (B-LR), which weights classes by inverse frequency and adds an $L_2$ penalty. The paper reports that in 3D, AUC-opt beat B-LR on test data for only 4 of 50 datasets. B-LR is the strongest competitor because it is exactly the regularized convex alternative the authors say makes exact optimization redundant. It will be run on identical t-SNE projections and identical splits, with its $L_2$ strength tuned by the same K-fold partition our method uses. Beating it means winning on clearly more datasets than we lose, confirmed by a paired Wilcoxon signed-rank test on test AUC across the 50 datasets in 3D. Matching it rather than beating it would still be informative, and the Why-not section explains why.

We also run the surrogate AUC optimizers from the same paper, SVM-Perf and SPAUC. For these the file gives no scalar test numbers, so no reported result was found on Lacuna for SVM-Perf or SPAUC test AUC. They get the same splits and the same tuning grid budget.

A post-hoc selection baseline isolates the key ingredient, which is regularizing inside the sweep. It runs plain AUC-opt, keeps the top-M directions by training AUC, and picks one using a holdout. The fold-only and smoothing-only variants from the research program serve as further ablations.

Why not just…?

Why not just use balanced logistic regression? This is the real threat. In 3D, B-LR generalized better than exact AUC optimization on nearly every dataset (Does It Pay to Optimize AUC?), and it is cheap. If our regularized sweep only ties B-LR, we will say so. That outcome would still establish that the original failure came from missing regularization, not from the AUC metric itself. It would also leave an exact optimizer that is no worse, whose selection criterion can be inspected directly as a plateau width in angle. If the regularized sweep still loses to B-LR, the conclusion is stronger: optimizing the discrete metric exactly is not worth it in low dimensions.

Why not just pick among AUC-opt's top solutions with a holdout afterward? The best training directions tend to be neighboring spikes in the same narrow region of angle. A post-hoc holdout picks the best of a correlated, overfit set and never considers the plateaus that score slightly lower on training data. The top-M ablation tests this directly. If it matches the in-sweep version, the in-sweep machinery is unnecessary, and we will report that.

Why not just bag AUC-opt over bootstrap resamples? Bagging costs B full sweeps, where B is the number of resamples, while our method costs one sweep with K counters. Averaging directions from bagged runs also has no exactness guarantee for any criterion. We include bagging with B equal to K so the compute is matched. If bagging wins, smoothing inside the sweep is the wrong regularizer.

Proposed Experiments

The main experiment uses the 50 UCI imbalanced datasets with t-SNE projections to 2D and 3D and a positive rate of at most 0.1, following the published protocol. Every method uses the same outer train/test splits over repeated seeds. For each method we report test AUC, per-dataset win/tie/loss against B-LR with paired tests, the train–test gap, and wall-clock time. The paper reports roughly 3.7 seconds per dataset for plain AUC-opt in 2D, so we can check that our overhead stays near a factor of K.

There are three decisive checks. The first is whether 3D wins against B-LR rise well above the reported 4 of 50. The second is whether the train–test gap shrinks as $\delta$ grows, with folds choosing an intermediate $\delta$. The third is whether the in-sweep variant beats the post-hoc top-M selection; if it does not, the core ingredient has failed and the proposal reduces to ordinary holdout tuning. The CORELS extension on COMPAS is reported only as a transfer check, measuring test accuracy and runtime with and without the fold counters.