1 citations · 1 across the 2 of their papers we have counts for
6 papers
Higher-order methods for convex-concave min-max optimization and monotone variational inequalities
Brian Bullins, Kevin A. Lai
We provide improved convergence rates for constrained convex-concave min-max problems and monotone variational inequalities with higher-order smoothness. In min-max settings where…
Fast Convergence of Fictitious Play for Diagonal Payoff Matrices
Jacob Abernethy, Kevin A. Lai, Andre Wibisono
Fictitious Play (FP) is a simple and natural dynamic for repeated play in zero-sum games. Proposed by Brown in 1949, FP was shown to converge to a Nash Equilibrium by Robinson in 1…
Last-iterate convergence rates for min-max optimization
Jacob Abernethy, Kevin A. Lai, Andre Wibisono
While classic work in convex-concave min-max optimization relies on average-iterate convergence results, the emergence of nonconvex applications such as training Generative Adversa…
Faster Rates for Convex-Concave Games
Jacob Abernethy, Kevin A. Lai, Kfir Y. Levy +1
We consider the use of no-regret algorithms to compute equilibria for particular classes of convex-concave games. While standard regret bounds would lead to convergence rates on th…
Differential Privacy for Growing Databases
Rachel Cummings, Sara Krehbiel, Kevin A. Lai +1
We study the design of differentially private algorithms for adaptive analysis of dynamically growing databases, where a database accumulates new data entries while the analysis is…
Amortized Rotation Cost in AVL Trees
Mahdi Amani, Kevin A. Lai, Robert E. Tarjan
An AVL tree is the original type of balanced binary search tree. An insertion in an -node AVL tree takes at most two rotations, but a deletion in an -node AVL tree can take $…