12 papers
Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp
Wenzhi Gao, Zhaonan Qu, Yinyu Ye +2
We revisit the Sinkhorn-Knopp (SK) algorithm for the matrix scaling problem. Despite extensive literature on the global convergence of SK and its variants, its local linear converg…
OptiMUS-0.3: Using Large Language Models to Model and Solve Optimization Problems at Scale
Ali AhmadiTeshnizi, Wenzhi Gao, Herman Brunborg +3
Optimization problems are pervasive in sectors from manufacturing and distribution to healthcare. However, most such problems are still solved heuristically by hand rather than opt…
New Results on the Polyak Stepsize: Tight Convergence Analysis and Universal Function Classes
Chang He, Wenzhi Gao, Bo Jiang +2
In this paper, we revisit a classical adaptive stepsize strategy for gradient descent: the Polyak stepsize (PolyakGD), originally proposed in Polyak (1969). We study the convergenc…
Small Gradient Norm Regret for Online Convex Optimization
Wenzhi Gao, Chang He, Madeleine Udell
This paper introduces a new problem-dependent regret measure for online convex optimization with smooth losses. The notion, which we call the regret, depends on the cumul…
A Smooth Approximation Framework for Weakly Convex Optimization
Qi Deng, Wenzhi Gao
Standard complexity analyses for weakly convex optimization rely on the Moreau envelope technique proposed by Davis and Drusvyatskiy (2019). The main insight is that nonsmooth algo…
Wait-Less Offline Tuning and Re-solving for Online Decision Making
Jingruo Sun, Wenzhi Gao, Ellen Vitercik +1
Online linear programming (OLP) has found broad applications in revenue management and resource allocation. State-of-the-art OLP algorithms achieve low regret by repeatedly solving…