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.