heavy-tailed noise

Normalized-step stochastic SQP methods for nonconvex constrained optimization under heavy-tailed noise

Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , ,

In this paper, we study nonconvex constrained optimization with expectation equality constraints and non-negative bounds under heavy-tailed noise. The objective gradients, constraint values, and constraint Jacobian are accessed through stochastic oracles whose errors have bounded $p$th central moments for some $p\in(1,2)$. These conditions allow infinite-variance errors for the three types of stochastic oracles, rendering traditional … Read more

Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications

Categories Convex Optimization, Nonsmooth Optimization Tags , ,

In Online Convex Optimization (OCO), when the stochastic gradient has a finite variance, many algorithms provably work and guarantee a sublinear regret. However, limited results are known if the gradient estimate has a heavy tail, i.e., the stochastic gradient only admits a finite \(\mathsf{p}\)-th central moment for some \(\mathsf{p}\in\left(1,2\right]\). Motivated by it, this work examines … Read more

Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noise

Categories Nonlinear Optimization, Optimization in Data Science, Unconstrained Optimization Tags , , ,

In this paper, we propose practical normalized stochastic first-order methods with Polyak momentum, multi-extrapolated momentum, and recursive momentum for solving unconstrained optimization problems. These methods employ dynamically updated algorithmic parameters and do not require explicit knowledge of problem-dependent quantities such as the Lipschitz constant or noise bound. We establish first-order oracle complexity results for finding … Read more