Paperlane

no. 12 · Tuesday 10 November 2026

A stochastic gradient algorithm for non-separable optimization with convergence guarantee

Yingzhou Li and Ruofan Wu

math.OC · v2

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
pdf ↗ page arXiv:2606.10383 ↗