Lifeng Lai

Efficiently Escaping Saddle Points in Bilevel Optimization

  • Minhui Huang
  • Kaiyi Ji
  • Lifeng Lai
  • Shiqian Ma
    • Categories Nonlinear Optimization Tags , , ,

    Bilevel optimization is one of the fundamental problems in machine learning and optimization. Recent theoretical developments in bilevel optimization focus on finding the first-order stationary points for nonconvex-strongly-convex cases. In this paper, we analyze algorithms that can escape saddle points in nonconvex-strongly-convex bilevel optimization. Specifically, we show that the perturbed approximate implicit differentiation (AID) with … Read more

    On the Convergence of Projected Alternating Maximization for Equitable and Optimal Transport

  • Minhui Huang
  • Shiqian Ma
  • Lifeng Lai
    • Categories Convex Optimization Tags , , , , , ,

    This paper studies the equitable and optimal transport (EOT) problem, which has many applications such as fair division problems and optimal transport with multiple agents etc. In the discrete distributions case, the EOT problem can be formulated as a linear program (LP). Since this LP is prohibitively large for general LP solvers, Scetbon \etal \cite{scetbon2021equitable} … Read more

    A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance

  • Minhui Huang
  • Shiqian Ma
  • Lifeng Lai
    • Categories Nonlinear Optimization Tags , , ,

    The Wasserstein distance has become increasingly important in machine learning and deep learning. Despite its popularity, the Wasserstein distance is hard to approximate because of the curse of dimensionality. A recently proposed approach to alleviate the curse of dimensionality is to project the sampled data from the high dimensional probability distribution onto a lower-dimensional subspace, … Read more

    Projection Robust Wasserstein Barycenters

  • Minhui Huang
  • Shiqian Ma
  • Lifeng Lai
    • Categories Nonlinear Optimization Tags , ,

    Collecting and aggregating information from several probability measures or histograms is a fundamental task in machine learning. One of the popular solution methods for this task is to compute the barycenter of the probability measures under the Wasserstein metric. However, approximating the Wasserstein barycenter is numerically challenging because of the curse of dimensionality. This paper … Read more