Minhui Huang

Decentralized Stochastic Bilevel Optimization with Improved Per-Iteration Complexity

  • Xuxing Chen
  • Minhui Huang
  • Shiqian Ma
  • Krishnakumar Balasubramanian
    • Categories Nonlinear Optimization, Optimization in Data Science, Stochastic Programming

    Bilevel optimization recently has received tremendous attention due to its great success in solving important machine learning problems like meta learning, reinforcement learning, and hyperparameter optimization. Extending single-agent training on bilevel problems to the decentralized setting is a natural generalization, and there has been a flurry of work studying decentralized bilevel optimization algorithms. However, it … Read more

    Decentralized Bilevel Optimization

  • Xuxing Chen
  • Minhui Huang
  • Shiqian Ma
    • Categories Nonlinear Optimization Tags , ,

    Bilevel optimization has been successfully applied to many important machine learning problems. Algorithms for solving bilevel optimization have been studied under various settings. In this paper, we study the nonconvex-strongly-convex bilevel optimization under a decentralized setting. We design decentralized algorithms for both deterministic and stochastic bilevel optimization problems. Moreover, we analyze the convergence rates of … Read more

    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