A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Properties

Abstract.

The proximal stochastic gradient method ([Formula: see text]) is one of the state-of-the-art approaches for stochastic composite-type problems. In contrast to its deterministic counterpart, [Formula: see text] has been found to have difficulties with the correct identification of underlying substructures (such as supports, low rank patterns, or active constraints) and it does not possess a finite-time manifold identification property. Existing solutions rely on convexity assumptions or the additional usage of variance reduction techniques. In this paper, we address these limitations and present a simple variant of [Formula: see text] based on Robinson’s normal map. The proposed normal map-based proximal stochastic gradient method ([Formula: see text]) is shown to converge globally; i.e., accumulation points of the generated iterates correspond to stationary points almost surely. In addition, we establish complexity bounds for [Formula: see text] that match the known results for [Formula: see text], and we prove that [Formula: see text] can almost surely identify active manifolds in finite time in a general nonconvex setting. Our derivations are built on almost sure iterate convergence guarantees and utilize analysis techniques based on the Kurdyka–Łojasiewicz inequality.