94 citations · 107 across the 5 of their papers we have counts for
7 papers
Towards a combinatorial characterization of bounded memory learning
Alon Gonen, Shachar Lovett, Michal Moshkovitz
Combinatorial dimensions play an important role in the theory of machine learning. For example, VC dimension characterizes PAC learning, SQ dimension characterizes weak learning wi…
Private Learning Implies Online Learning: An Efficient Reduction
Alon Gonen, Elad Hazan, Shay Moran
We study the relationship between the notions of differentially private learning and online learning in games. Several recent works have shown that differentially private learning…
Learning in Non-convex Games with an Optimization Oracle
Naman Agarwal, Alon Gonen, Elad Hazan
We consider online learning in an adversarial, non-convex setting under the assumption that the learner has an access to an offline optimization oracle. In the general setting of p…
Optimal Sketching Bounds for Exp-concave Stochastic Minimization
Naman Agarwal, Alon Gonen
We derive optimal statistical and computational complexity bounds for exp-concave stochastic minimization in terms of the effective dimension. For common eigendecay patterns of the…
Faster Low-rank Approximation using Adaptive Gap-based Preconditioning
Alon Gonen, Shai Shalev-Shwartz
We propose a method for rank approximation to a given input matrix which runs in time \[ \tilde{O} \left(d ~\cdot~ \min\left\{n + \tilde{sr}(X)…
Strongly Adaptive Online Learning
Amit Daniely, Alon Gonen, Shai Shalev-Shwartz
Strongly adaptive algorithms are algorithms whose performance on every time interval is close to optimal. We present a reduction that can transform standard low-regret algorithms t…