34 citations · 68 across the 7 of their papers we have counts for
9 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…
Regression using Lewis Weights Preconditioning and Stochastic Gradient Descent
David Durfee, Kevin A. Lai, Saurabh Sawlani
We present preconditioned stochastic gradient descent (SGD) algorithms for the minimization problem in the overdetermined case, where there are far…
Agnostic Estimation of Mean and Covariance
Kevin A. Lai, Anup B. Rao, Santosh Vempala
We consider the problem of estimating the mean and covariance of a distribution from iid samples in , in the presence of an fraction of malicious noise; this is i…
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 $…
Label optimal regret bounds for online local learning
Pranjal Awasthi, Moses Charikar, Kevin A. Lai +1
We resolve an open question from (Christiano, 2014b) posed in COLT'14 regarding the optimal dependency of the regret achievable for online local learning on the size of the label s…