Session: Variance-Related Issues in Stochastic Optimization Methods
Chair: Yue Wu
Cluster: nan
Talk 1: Some Unified Theory for Variance Reduced Prox-Linear Methods
Speaker: Yue Wu
Abstract: This work considers the nonconvex, nonsmooth problem of minimizing a composite objective of the form f(g(x))+h(x) where the inner mapping g is a smooth finite summation or expectation amenable to variance reduction. In such settings, prox-linear methods can enjoy variance-reduced speed-ups despite the existence of nonsmoothness. We provide a unified convergence theory applicable to a wide range of common variance-reduced vector and Jacobian constructions. Our theory (i) only requires operator norm bounds on Jacobians (whereas prior works used potentially much larger Frobenius norms), (ii) provides state-of-the-art high probability guarantees, and (iii) allows inexactness in proximal computations.
Talk 2: An Accelerated Variance Reduced Extra-Point Approach to Finite-Sum Hemivariational Inequality Problem
Speaker: Kevin Huang
Abstract: In this paper, we develop stochastic variance reduced algorithms for solving a class of finite-sum hemivariational inequality (HVI) problem. In this HVI problem, the associated function is assumed to be differentiable, and both the vector mapping and the function are of finite-sum structure. We propose two algorithms to solve the cases when the vector mapping is either merely monotone or strongly monotone, while the function is assumed to be convex. We show how to apply variance reduction in the proposed algorithms when such an HVI problem has a finite-sum structure, and the resulting accelerated gradient complexities can match the best bound established for finite-sum VI problem, as well as the bound given by the direct Katyusha for finite-sum optimization respectively, in terms of the corresponding parameters such as (gradient) Lipschitz constants and the sizes of the finite-sums. We demonstrate the application of our algorithms through solving a finite-sum constrained finite-sum optimization problem and provide preliminary numerical results. Archival version: https://doi.org/10.48550/arXiv.2211.03269
Talk 3: Adaptive stochastic optimization algorithms for problems with biased oracles
Speaker: Yin Liu
Abstract: Motivated by multiple emerging applications, e.g., stochastic composition optimization, we consider a general optimization problem where the gradient of the objective is only available through a biased stochastic oracle where the bias magnitude can be controlled by a parameter; however, lower bias requires higher computation. Without exploiting a specific bias decay structure, we propose a couple of adaptive and nonadaptive stochastic algorithms to solve the underlying problem. We analyze the nonasymptotic performance of the proposed algorithms in the nonconvex regimes. The numerical performance of the proposed methods over three applications on composition optimization, policy optimization for infinite-horizon Markov decision processes, and distributionally robust optimization will be presented.
