Unsorted Antithetic RQMC for Relaxed Barrier Optimization: Enhanced Stability and Variance Reduction
Аннотация
Stochastic gradient descent combined with adaptive relaxed barrier functions provides a robust framework for projection-free constrained optimization. However, the reliance on standard random sampling exposes the algorithm to significant stochastic variance and slow convergence, particularly when barrier gradients become steep near the feasibility boundary. This paper addresses these limitations by introducing an enhanced sampling strategy based on unsorted antithetic randomized quasi-Monte Carlo techniques. We propose a computationally efficient scheme that leverages the stratification properties of low-discrepancy scrambled Sobol sequences to stabilize gradient estimation directly without the need for constraint sorting. Theoretically, we depart from traditional variance analyses that require monotonicity, and instead prove that our mechanism induces an intrinsic stratification that enforces distinct index selection, yielding a single-step variance reduction formally equivalent to sampling without replacement. Empirically, we observe that this structural low-discrepancy property effectively counters the gradient singularity over the long-term optimization trajectory for problems with dense affine constraints. Numerical experiments on large-scale problems demonstrate that our method effectively suppresses oscillation and lowers the asymptotic error floor, achieving an 8.35 $$\times $$ × true stability gain compared to a fair batch-size-2 sampling without replacement baseline, while retaining an amortized $$\mathcal {O}(1)$$ O ( 1 ) computational complexity per iteration. While our empirical results show significant improvements, we note that the practical benefits may be problem-dependent, highlighting the need for broader real-world validation.