72 citations · 263 across the 31 of their papers we have counts for
22 papers · 1 filter
On the Geometry and Refined Rate of Primal-Dual Hybrid Gradient for Linear Programming
Haihao Lu, Jinwen Yang
We study the convergence behaviors of primal-dual hybrid gradient (PDHG) for solving linear programming (LP). PDHG is the base algorithm of a new general-purpose first-order method…
On a Unified and Simplified Proof for the Ergodic Convergence Rates of PPM, PDHG and ADMM
Haihao Lu, Jinwen Yang
We present a unified viewpoint of proximal point method (PPM), primal-dual hybrid gradient (PDHG) and alternating direction method of multipliers (ADMM) for solving convex-concave…
On the Infimal Sub-differential Size of Primal-Dual Hybrid Gradient Method and Beyond
Haihao Lu, Jinwen Yang
Primal-dual hybrid gradient method (PDHG, a.k.a. Chambolle and Pock method) is a well-studied algorithm for minimax optimization problems with a bilinear interaction term. Recently…
Analysis of Dual-Based PID Controllers through Convolutional Mirror Descent
Santiago R. Balseiro, Haihao Lu, Vahab Mirrokni +1
Dual-based proportional-integral-derivative (PID) controllers are often employed in practice to solve online allocation problems with global constraints, such as budget pacing in o…
A -Symmetric Quasi-Newton Method for Minimax Problems
Azam Asl, Haihao Lu, Jinwen Yang
Minimax problems have gained tremendous attentions across the optimization and machine learning community recently. In this paper, we introduce a new quasi-Newton method for minima…
On the Linear Convergence of Extra-Gradient Methods for Nonconvex-Nonconcave Minimax Problems
Saeed Hajizadeh, Haihao Lu, Benjamin Grimmer
Recently, minimax optimization received renewed focus due to modern applications in machine learning, robust optimization, and reinforcement learning. The scale of these applicatio…
Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for Linear Programming
Haihao Lu, Jinwen Yang
There is a recent interest on first-order methods for linear programming (LP). In this paper,we propose a stochastic algorithm using variance reduction and restarts for solving sha…
Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient
David Applegate, Mateo Díaz, Oliver Hinder +4
We present PDLP, a practical first-order method for linear programming (LP) that can solve to the high levels of accuracy that are expected in traditional LP applications. In addit…
Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness
David Applegate, Oliver Hinder, Haihao Lu +1
First-order primal-dual methods are appealing for their low memory overhead, fast iterations, and effective parallelization. However, they are often slow at finding high accuracy s…
Infeasibility detection with primal-dual hybrid gradient for large-scale linear programming
David Applegate, Mateo Díaz, Haihao Lu +1
We study the problem of detecting infeasibility of large-scale linear programming problems using the primal-dual hybrid gradient method (PDHG) of Chambolle and Pock (2011). The lit…
Frank-Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning
Haoyue Wang, Haihao Lu, Rahul Mazumder
The Frank-Wolfe (FW) method is a popular algorithm for solving large-scale convex optimization problems appearing in structured statistical learning. However, the traditional Frank…
Limiting Behaviors of Nonconvex-Nonconcave Minimax Optimization via Continuous-Time Systems
Benjamin Grimmer, Haihao Lu, Pratik Worah +1
Unlike nonconvex optimization, where gradient descent is guaranteed to converge to a local optimizer, algorithms for nonconvex-nonconcave minimax optimization can have topologicall…
Regularized Online Allocation Problems: Fairness and Beyond
Santiago Balseiro, Haihao Lu, Vahab Mirrokni
Online allocation problems with resource constraints have a rich history in operations research. In this paper, we introduce the \emph{regularized online allocation problem}, a var…
The Landscape of the Proximal Point Method for Nonconvex-Nonconcave Minimax Optimization
Benjamin Grimmer, Haihao Lu, Pratik Worah +1
Minimax optimization has become a central tool in machine learning with applications in robust optimization, reinforcement learning, GANs, etc. These applications are often nonconv…
Dual Mirror Descent for Online Allocation Problems
Haihao Lu, Santiago Balseiro, Vahab Mirrokni
We consider online allocation problems with concave revenue functions and resource constraints, which are central problems in revenue management and online advertising. In these se…
Contextual Reserve Price Optimization in Auctions via Mixed-Integer Programming
Joey Huchette, Haihao Lu, Hossein Esfandiari +1
We study the problem of learning a linear model to set the reserve price in an auction, given contextual information, in order to maximize expected revenue from the seller side. Fi…
An -Resolution ODE Framework for Understanding Discrete-Time Algorithms and Applications to the Linear Convergence of Minimax Problems
Haihao Lu
There has been a long history of using ordinary differential equations (ODEs) to understand the dynamics of discrete-time algorithms (DTAs). Surprisingly, there are still two funda…
Generalized Stochastic Frank-Wolfe Algorithm with Stochastic "Substitute" Gradient for Structured Convex Optimization
Haihao Lu, Robert M. Freund
The stochastic Frank-Wolfe method has recently attracted much general interest in the context of optimization for statistical and machine learning due to its ability to work with a…
Accelerating Greedy Coordinate Descent Methods
Haihao Lu, Robert M. Freund, Vahab Mirrokni
We study ways to accelerate greedy coordinate descent in theory and in practice, where "accelerate" refers either to convergence in theory, in practice, or both. We intr…
"Relative-Continuity" for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent
Haihao Lu
The usual approach to developing and analyzing first-order methods for non-smooth (stochastic or deterministic) convex optimization assumes that the objective function is uniformly…
Relatively-Smooth Convex Optimization by First-Order Methods, and Applications
Haihao Lu, Robert M. Freund, Yurii Nesterov
The usual approach to developing and analyzing first-order methods for smooth convex optimization assumes that the gradient of the objective function is uniformly smooth with some…
New Computational Guarantees for Solving Convex Optimization Problems with First Order Methods, via a Function Growth Condition Measure
Robert M. Freund, Haihao Lu
Motivated by recent work of Renegar, we present new computational methods and associated computational guarantees for solving convex optimization problems using first-order methods…