Zhaosong Lu

A first-order method for nonconvex-nonconcave minimax problems under a local Kurdyka-Łojasiewicz condition

  • Zhaosong Lu
  • Xiangyuan Wang
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Other Topics Tags , , , ,

    We study a class of nonconvex–nonconcave minimax problems in which the inner maximization problem satisfies a local Kurdyka–Łojasiewicz (KL) condition that may vary with the outer minimization variable. In contrast to the global KL or Polyak–Łojasiewicz (PL) conditions commonly assumed in the literature—which are significantly stronger and often too restrictive in practice—this local KL condition … Read more

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

  • Chuan He
  • Zhaosong Lu
  • Defeng Sun
  • Zhanwang Deng
    • 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

    First-order methods for stochastic and finite-sum convex optimization with deterministic constraints

  • Zhaosong Lu
  • Yifeng Xiao
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Stochastic Programming Tags , , , , , ,

    In this paper, we study a class of stochastic and finite-sum convex optimization problems with deterministic constraints. Existing methods typically aim to find an \(\epsilon\)-expectedly feasible stochastic optimal solution, in which the expected constraint violation and expected optimality gap are both within a prescribed tolerance ϵ. However, in many practical applications, constraints must be nearly … Read more

    Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees

  • Zhaosong Lu
  • Sanyou Mei
  • Yifeng Xiao
    • Categories Constrained Nonlinear Optimization, Stochastic Programming Tags , , , , ,

    In this paper, we study a class of deterministically constrained stochastic optimization problems. Existing methods typically aim to find an \(\epsilon\)-stochastic stationary point, where the expected violations of both constraints and first-order stationarity are within a prescribed accuracy \(\epsilon\). However, in many practical applications, it is crucial that the constraints be nearly satisfied with certainty, … Read more

    A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization

  • Chuan He
  • Zhaosong Lu
    • Categories Cone Programming, Nonlinear Optimization Tags , , , , , ,

    In this paper we consider finding an approximate second-order stationary point (SOSP) of general nonconvex conic optimization that minimizes a twice differentiable function subject to nonlinear equality constraints and also a convex conic constraint. In particular, we propose a Newton-conjugate gradient (Newton-CG) based barrier-augmented Lagrangian method for finding an approximate SOSP of this problem. Under … Read more

    A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guarantees

  • Chuan He
  • Zhaosong Lu
  • Ting Kei Pong
    • Categories Constrained Nonlinear Optimization Tags , , , , ,

    In this paper we consider finding a second-order stationary point (SOSP) of nonconvex equality constrained optimization when a nearly feasible point is known. In particular, we first propose a new Newton-CG method for finding an approximate SOSP of unconstrained optimization and show that it enjoys a substantially better complexity than the Newton-CG method [56]. We … Read more

    A first-order augmented Lagrangian method for constrained minimax optimization

  • Zhaosong Lu
  • Sanyou Mei
    • Categories Constrained Nonlinear Optimization, Robust Optimization Tags , , ,

    In this paper we study a class of constrained minimax problems. In particular, we propose a first-order augmented Lagrangian method for solving them, whose subproblems turn out to be a much simpler structured minimax problem and are suitably solved by a first-order method recently developed in [26] by the authors. Under some suitable assumptions, an … Read more

    First-order penalty methods for bilevel optimization

  • Zhaosong Lu
  • Sanyou Mei
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    In this paper we study a class of unconstrained and constrained bilevel optimization problems in which the lower-level part is a convex optimization problem, while the upper-level part is possibly a nonconvex optimization problem. In particular, we propose penalty methods for solving them, whose subproblems turn out to be a structured minimax problem and are … Read more

    A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guarantees

  • Chuan He
  • Zhaosong Lu
    • Categories Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , , ,

    In this paper we consider finding an approximate second-order stationary point (SOSP) of nonconvex conic optimization that minimizes a twice differentiable function over the intersection of an affine subspace and a convex cone. In particular, we propose a Newton-conjugate gradient (Newton-CG) based barrier method for finding an $(\epsilon,\sqrt{\epsilon})$-SOSP of this problem. Our method is not … Read more

    Primal-dual extrapolation methods for monotone inclusions under local Lipschitz continuity with applications to variational inequality, conic constrained saddle point, and convex conic optimization problems

  • Zhaosong Lu
  • Sanyou Mei
    • Categories Convex and Nonsmooth Optimization Tags , , , , , , , ,

    In this paper we consider a class of structured monotone inclusion (MI) problems that consist of finding a zero in the sum of two monotone operators, in which one is maximal monotone while another is locally Lipschitz continuous. In particular, we first propose a primal-dual extrapolation (PDE) method for solving a structured strongly MI problem … Read more