Xiao Wang

Nonconvex stochastic zeroth-order optimization with decision-dependent distributions: from momentum tracking to coupled sampling

Categories Nonlinear Optimization, Stochastic Programming, Unconstrained Optimization

In this paper, we study nonconvex stochastic optimization with {decision-dependent distributions}, where the decision variable influences the underlying sampling distribution and only stochastic function-value feedback is available. We address two challenges {induced by decision-dependent distributions}: transport error in momentum-based gradient tracking and variance inflation in zeroth-order estimation. We first develop a Polyak-momentum zeroth-order method that … Read more

Lower Bounds for Feasibility and Stationarity in First-Order Nonconvex Constrained Optimization

Categories Constrained Nonlinear Optimization, Nonlinear Optimization

We study oracle-complexity lower bounds for first-order methods applied to smooth equality-constrained nonconvex optimization, separating two components of approximate KKT accuracy: feasibility and stationarity. Under iteration-wise Jacobian regularity, we prove a lower bound of order \(\Omega(\frac{L_c\Delta_c}{\sigma^2}+\log\log(\frac{\sigma^2}{L_c\epsilon}))\) to achieve \(\epsilon\)-feasibility. For stationarity, we construct a nonlinear equality-constrained hard instance whose multiplier-minimized stationarity residual reduces exactly to … Read more

A Fletcher’s Augmented Lagrangian-Based Stochastic First-Order Method for Nonconvex Equality-Constrained Optimization

Categories Constrained Nonlinear Optimization, Nonlinear Optimization

In this paper, we study nonconvex equality-constrained optimization problems in which only stochastic first-order approximations of the objective and constraint functions are available. Owing to the stochasticity in both objective and constraints, most existing stochastic first-order methods incur relatively high oracle complexity, particularly in terms of stochastic constraint function evaluations. To address this issue, we … Read more

Normalized stochastic proximal approximation methods for nonsmooth composite optimization under heavy-tailed noise

Categories Nonlinear Optimization, Nonsmooth Optimization

In this paper, we study nonsmooth composite optimization problems under heavy-tailed noise, with the objective being a summation of a nested function and a nonsmooth convex regularizer. We propose stochastic proximal approximation methods incorporating a normalization technique to handle the potential challenges caused by the nonsmooth regularizer and heavy-tailed noise. For the case where the … Read more

Curvature-oriented variance reduction methods for nonconvex stochastic optimization

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

When pursuing an approximate second-order stationary point in nonconvex constrained stochastic optimization, is it possible to design a stochastic second-order method that achieves the same sample complexity order as in the unconstrained setting? To address this question in this paper, we first introduce Carme, a curvature-oriented variance reduction method designed for unconstrained nonconvex stochastic optimization. … Read more

Non-convex stochastic compositional optimization under heavy-tailed noise

Categories Nonlinear Optimization

This paper investigates non-convex stochastic compositional optimization under heavy-tailed noise, where the stochastic noise exhibits bounded $p$th moment with $p\in(1,2]$. The main challenges arise from biased gradient estimates of the objective and the violation of the standard bounded-variance assumption. To address these issues, we propose a generic algorithm framework of Normalized Stochastic Compositional Gradient methods … Read more

An Exact Penalty Method for Stochastic Equality-Constrained Optimization

Categories Constrained Nonlinear Optimization, Nonlinear Optimization

In this paper, we study a penalty method for stochastic equality-constrained optimization, where both the objective and constraints are expressed in general expectation form. We introduce a novel adaptive strategy for updating the penalty parameter, guided by iteration progress to balance reductions in the penalty function with improvements in constraint violation, while each penalty subproblem … Read more

Continuous-time Analysis of a Stochastic ADMM Method for Nonconvex Composite Optimization

Categories Nonlinear Optimization, Unconstrained Optimization

In this paper, we focus on nonconvex composite optimization, whose objective is the sum of a smooth but possibly nonconvex function and a composition of a weakly convex function coupled with a linear operator. By leveraging a smoothing technique based on Moreau envelope, we propose a stochastic proximal linearized ADMM algorithm (SPLA). To understand its … Read more

An adaptive single-loop stochastic penalty method for nonconvex constrained stochastic optimization

Categories Constrained Nonlinear Optimization, Nonlinear Optimization

Adaptive update schemes for penalty parameters are crucial to enhancing robustness and practical applicability of penalty methods for constrained optimization. However, in the context of general constrained stochastic optimization, additional challenges arise due to the randomness introduced by adaptive penalty parameters. To address these challenges, we propose an Adaptive Single-loop Stochastic Penalty method (AdaSSP) in … Read more