A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Properties
This addresses limitations in stochastic optimization for composite-type problems, offering a method with improved identification properties, though it is incremental as it builds on existing PSGD frameworks.
The paper tackles the problem of proximal stochastic gradient methods failing to correctly identify underlying substructures and lacking finite-time manifold identification, presenting a variant based on Robinson's normal map that achieves global convergence and finite-time manifold identification in nonconvex settings.
The proximal stochastic gradient method (PSGD) is one of the state-of-the-art approaches for stochastic composite-type problems. In contrast to its deterministic counterpart, PSGD 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 on the additional usage of variance reduction techniques. In this paper, we address these limitations and present a simple variant of PSGD based on Robinson's normal map. The proposed normal map-based proximal stochastic gradient method (NSGD) 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 NSGD that match the known results for PSGD and we prove that NSGD 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-Lojasiewicz inequality.