3 citations · 3 across the 9 of their papers we have counts for
4 papers · 1 filter
The Oracle Complexity of Simplex-based Matrix Games
Guy Kornowski, Ohad Shamir
We study the problem of solving matrix games of the form , where is a matrix and is the pr…
Simple Relative Deviation Bounds for Covariance and Gram Matrices
Daniel Barzilai, Ohad Shamir
We provide non-asymptotic, relative deviation bounds for the eigenvalues of empirical covariance and Gram matrices in general settings. Unlike typical uniform bounds, which may fai…
On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimization
Guy Kornowski, Swati Padmanabhan, Ohad Shamir
We study the oracle complexity of nonsmooth nonconvex optimization, with the algorithm assumed to have access only to local function information. It has been shown by Davis, Drusvy…
Open Problem: Anytime Convergence Rate of Gradient Descent
Guy Kornowski, Ohad Shamir
Recent results show that vanilla gradient descent can be accelerated for smooth convex objectives, merely by changing the stepsize sequence. We show that this can lead to surprisin…