Wenzhi Gao

Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent

  • Wenzhi Gao
    • Categories Convex Optimization, Nonlinear Optimization Tags

    This paper investigates the convergence properties of the hypergradient descent method (HDM), a 25-year-old heuristic originally proposed for adaptive stepsize selection in stochastic first-order methods. We provide the first rigorous convergence analysis of HDM using the online learning framework of [Gao24] and apply this analysis to develop new state-of-the-art adaptive gradient methods with empirical and … Read more

    When Does Primal Interior Point Method Beat Primal-dual in Linear Optimization?

  • Wenzhi Gao
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , ,

    The primal-dual interior point method (IPM) is widely regarded as the most efficient IPM variant for linear optimization. In this paper, we demonstrate that the improved stability of the pure primal IPM can allow speedups relative to a primal-dual solver, particularly as the IPM approaches convergence.  The stability of the primal scaling matrix makes it … Read more

    Gradient Methods with Online Scaling

  • Wenzhi Gao
    • Categories Convex Optimization, Nonlinear Optimization, Other Topics Tags , ,

    We introduce a framework to accelerate the convergence of gradient-based methods with online learning. The framework learns to scale the gradient at each iteration through an online learning algorithm and provably accelerates gradient-based methods asymptotically. In contrast with previous literature, where convergence is established based on worst-case analysis, our framework provides a strong convergence guarantee … Read more