Convergence of difference inclusions: a diameter criterion and step-size conditions

Abstract

We study bounded realizations of discrete difference inclusions with set-valued increments and additive errors. Our results have two parts. First, we give a general convergence criterion in which changes in a convergent scalar quantity control the diameters of local sequence segments near an accumulation point. We also develop a stratified descent framework for verifying this control. For convergent realizations, the framework yields a stationarity condition for the limit from outer limits of the scaled update map. When applied to first-order methods for minimizing locally Lipschitz objectives definable in polynomially bounded o-minimal structures, the framework yields convergence to critical points for bounded sequences generated by the inexact subgradient, momentum, and stochastic subgradient methods with step sizes of order $k^{-1}$, under the corresponding error and noise conditions. Second, we study first-order methods with polynomial step sizes of order $k^{-a}$. At the square-summability boundary \(a=1/2\), we construct a locally Lipschitz semialgebraic objective for which the exact subgradient method generates a bounded, nonconvergent sequence whose accumulation points satisfy our active-geometry assumptions. Under these assumptions, bounded sequences generated by the momentum method converge for \(1/2<a\leq1\), while bounded sequences generated by the stochastic subgradient method converge almost surely for \(2/3<a\leq1\). The momentum range is sharp for this method class, while the stochastic range matches recent full-sequence convergence results for smooth nonconvex objectives.

76 pages