Zikai Xiong

I am an MIT doctoral student at the MIT Operations Research Center. My advisor is Robert M. Freund. Previously, I obtained my B.S. in Mathematics and Applied Mathematics from Fudan University in 2020. My research focuses on optimization, and its applications in operations research and machine learning. My recent research interests include huge-scale linear programming, first-order methods for optimization, and applications in data science and statistical machine learning.

Accessible Theoretical Complexity of the Restarted Primal-Dual Hybrid Gradient Method for Linear Programs with Unique Optima

  • Zikai Xiong
    • Categories Convex Optimization, Linear Programming, Nonsmooth Optimization Tags , , ,

    The restarted primal-dual hybrid gradient method (rPDHG) has recently emerged as an important tool for solving large-scale linear programs (LPs). For LPs with unique optima, we present an iteration bound of \(\widetilde{O}\left(\kappa\Phi\cdot\ln\left(\frac{\|w^*\|}{\varepsilon}\right)\right)\), where \(\varepsilon\) is the target tolerance, \(\kappa\) is the standard matrix condition number, \(\|w^*\|\) is the norm of the optimal solution, and \(\Phi\) … Read more

    The Role of Level-Set Geometry on the Performance of PDHG for Conic Linear Optimization

  • Zikai Xiong
  • Robert M. Freund
    • Categories Convex Optimization, Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , , ,

    We consider solving huge-scale instances of (convex) conic linear optimization problems, at the scale where matrix-factorization-free methods are attractive or necessary. The restarted primal-dual hybrid gradient method (rPDHG) — with heuristic enhancements and GPU implementation — has been very successful in solving huge-scale linear programming (LP) problems; however its application to more general conic convex … Read more

    Computational Guarantees for Restarted PDHG for LP based on “Limiting Error Ratios” and LP Sharpness

  • Zikai Xiong
  • Robert M. Freund
    • Categories Convex Optimization, Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , , , , ,

    In recent years, there has been growing interest in solving linear optimization problems – or more simply “LP” – using first-order methods in order to avoid the costly matrix factorizations of traditional methods for huge-scale LP instances. The restarted primal-dual hybrid gradient method (PDHG) – together with some heuristic techniques – has emerged as a … Read more

    On the Relation Between LP Sharpness and Limiting Error Ratio and Complexity Implications for Restarted PDHG

  • Zikai Xiong
  • Robert M. Freund
    • Categories Convex Optimization, Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , , , , ,

    There has been a recent surge in development of first-order methods (FOMs) for solving huge-scale linear programming (LP) problems. The attractiveness of FOMs for LP stems in part from the fact that they avoid costly matrix factorization computation. However, the efficiency of FOMs is significantly influenced – both in theory and in practice – by … Read more

    Using Taylor-Approximated Gradients to Improve the Frank-Wolfe Method for Empirical Risk Minimization

  • Zikai Xiong
  • Robert M. Freund
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Stochastic Programming Tags , , , , ,

    The Frank-Wolfe method has become increasingly useful in statistical and machine learning applications, due to the structure-inducing properties of the iterates, and especially in settings where linear minimization over the feasible set is more computationally efficient than projection. In the setting of Empirical Risk Minimization — one of the fundamental optimization problems in statistical and … Read more