Your Hypergradient is Skewed: Antithetic Neumann Estimation for Bilevel Optimization

Bilevel optimization is a core tool in practical machine learning workflows, including hyperparameter tuning, data reweighting, robust learning, reinforcement learning, and imbalanced classification. Hypergradient computation requires the inverse of the inner Hessian, typically estimated via a truncated Neumann series. While existing analyses focus on bias and variance, we show that the product structure of the Neumann series introduces a third source of error: skewness. Unlike ordinary gradients, whose asymmetry is suppressed by mini-batch averaging, the Neumann estimator amplifies skewness across factors, with the third-moment error growing with truncation depth, inner condition number, and per-factor noise asymmetry. This arises in many practical settings such as corrupted labels, outliers, heterogeneous or class-imbalanced datasets. To address this, we introduce the Antithetic Neumann Estimator (ANE), which pairs each Hessian sample with a mirrored counterpart around a reference Hessian and averages the resulting inverse-Hessian estimates. With an exact reference, the antithetic product retains only even-order noise, eliminating all skewness; with an approximate reference, the residual skewness scales linearly with the reference error. ANE requires only a modification of the Hessian-vector step and integrates with existing stochastic or variance-reduced bilevel methods. We instantiate ANE-SGD and ANE-VR, the latter adding recursive variance reduction. Across robust regression, corrupted-label learning, offline reinforcement learning, and imbalanced classification, ANE-based methods achieve strictly better bias–variance–skewness tradeoffs than stochastic and variance-reduced baselines, reducing loss by up to 24% and improving predictive metrics by up to 27%. This establishes skewness correction as a practical and complementary mechanism for improving hypergradient quality.