OVLR: Efficient, Scalable, and Robust Training via Output-Level Variance-Reduced Likelihood Ratio

Gradient-based optimization via backpropagation (BP) is inherently limited by the requirement of differentiability, rendering it inapplicable for piecewise-constant objectives with vanishing gradients (e.g., the hard 0-1 loss) or black-box feedback. While likelihood ratio (LR) methods offer a theoretical alternative, their high variance in high-dimensional spaces undermines training stability and scalability. We propose OVLR, a framework that makes direct optimization of gradient-agnostic objectives practical for modern deep networks by performing perturbations and antithetic sampling in the low-dimensional output space. OVLR achieves dramatic variance reduction while requiring only a single deterministic forward pass, with additional costs restricted to evaluating the loss function across multiple samples. On problems where BP provides gradients, OVLR remains competitive; on problems where BP fails to provide reliable learning signals, OVLR enables the direct optimization of objectives such as the 0-1 loss for noise-tolerant classification and truncated losses for outlier-resistant regression. Extensive empirical results across classification, generative modeling, language modeling, robot imitation learning, and black-box optimization confirm that OVLR is an effective tool for settings where standard gradient-based optimization is inapplicable. Code is available at https://github.com/MinhZou/OVLR.

Standard deep learning training requires the training objective to provide smooth gradient signals — like a hill's slope guiding each step downhill. Yet many desirable objectives, such as a simple "right or wrong" metric for classification, have flat or undefined slopes, making them impossible to optimize directly. Current workarounds use substitute objectives, but these can be fragile — for example, when training data contains mislabeled examples. We propose OVLR, a method that makes these "gradient-free" objectives practical by adding small, structured noise to the network's final output and using a mathematical technique to estimate the gradient from that noise. Unlike earlier approaches that inject noise into millions of internal parameters and suffer from extreme variability, OVLR operates in the low-dimensional output space, achieving massive variance reduction while requiring only a single pass through the network — making it nearly as efficient as standard training. OVLR enables direct optimization of robust objectives, such as noise-tolerant classification and outlier-resistant regression, where standard methods fail. Results across image classification, language modeling, robotics, and black-box optimization confirm that OVLR is both competitive with standard training and uniquely effective where standard training breaks down