no. 12 · Tuesday 10 November 2026
A stochastic gradient algorithm for non-separable optimization with convergence guarantee
Abstract
We study smooth parameterized non-separable objectives of the form $\mathcal L(θ)=F(Y(θ))$, where a global operator couples the outputs of all training samples. We analyze two stochastic gradient constructions within this output-space framework: the ideal per-batch gradient $G$, obtained by row sampling of the full output gradient, and a cached surrogate $H$ for parameterized updates in which full-data quantities are expensive to evaluate. For uniformly sampled batches, the ideal estimator has a deterministic batch-size scaling and a second moment controlled by the full output gradient. Using this structure, we establish local high-probability confinement and convergence for fixed positive step sizes on a prescribed parameter neighborhood under a power-type gradient inequality, with linear and polynomial regimes determined by its exponent. For the cached surrogate, a Lyapunov function couples the objective gap with the cache error and yields analogous local results on the corresponding non-exit event. The theory includes explicit path-length, confinement, and rate bounds; numerical experiments illustrate finite-budget decay trends and the effects of global output-gradient sampling, batch restriction, and cache tracking.
- fields
- Optimization and Control, Numerical Analysis