Session: Recent Analysis in Proximal Algorithms and KL Exponents
Chair: Xiaopeng Li
Cluster: nan
Talk 1: Proximal random reshuffling under local Lipschitz continuity
Speaker: Xiaopeng Li
Abstract: We study proximal random reshuffling for minimizing the sum of locally Lipschitz functions and a proper lower semicontinuous convex function without assuming coercivity or the existence of limit points. The algorithmic guarantees pertaining to near approximate stationarity rely on a new tracking lemma linking the iterates to trajectories of conservative fields. One of the novelties in the analysis consists in handling conservative fields with unbounded values.
Talk 2: Normal map-based stochastic algorithms
Speaker: Junwen Qiu
Abstract: 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 additional convexity assumptions or on the usage of variance reduction techniques. 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. 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.
Talk 3: Kurdyka-Lojasiewicz exponent via square transformation
Speaker: Wenqing Ouyang
Abstract: Square transformation is a natural way to eliminate the nonnegative constraint to gain smoothness. Despite being smooth, it remains unknown about how the convergence rate would change via square transformation. We address this question by studying the connection between the Kurdyka-Lojasiewicz (KL) exponent of the transformed function and the one of the original function. We show that under strict complementarity condition, the KL exponent can be inherited perfectly. When strict complementarity condition fails, by additionally assuming convexity, we show that the KL exponent would depend on a constant that is related to an error bound condition of the solution set.
