Optimization under Persistent State-Dependent Bias: Gradient-based Method and Complexity Analysis
arXiv:2607.26032
The paper analyzes how stochastic gradient descent behaves when updates are consistently distorted by state-dependent scaling, shows this leads to a biased solution, and introduces a bilevel gradient method called Residual Learning that recovers the true optimum while characterizing the impact of hardware-induced bias on convergence complexity.
Abstract
This paper studies the convergence of stochastic gradient descent (SGD) when the implemented updates are subject to a persistent and state-dependent bias, in which the desired update is scaled by response functions component-wise. Our first contribution is to demonstrate that SGD in this setting implicitly optimizes a penalized problem whose minimizer does not coincide with the true minimizer. To mitigate this convergence failure, we reformulate the original task as an equivalent bilevel optimization problem and propose a gradient-based algorithm, termed Residual Learning. Theoretical analysis shows that Residual Learning finds a solution to the original, unbiased optimization problem despite the hardware imperfections. Beyond exact convergence, we quantify how the response functions affect convergence complexity via the hardware condition number and show that a polynomial dependence on it is unavoidable in general, via a construction of a hard instance. The theoretical results are supported by numerical simulations that demonstrate the effectiveness of the proposed algorithm.