94 citations · 188 across the 15 of their papers we have counts for
16 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…
Boosting Simple Learners
Noga Alon, Alon Gonen, Elad Hazan +1
Boosting is a celebrated machine learning approach which is based on the idea of combining weak and moderately inaccurate hypotheses to a strong and accurate one. We study boosting…
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…
Smooth Sensitivity Based Approach for Differentially Private Principal Component Analysis
Ran Gilad-Bachrach, Alon Gonen
Currently known methods for this task either employ the computationally intensive \emph{exponential mechanism} or require an access to the covariance matrix, and therefore fail to…
Fast Rates for Empirical Risk Minimization of Strict Saddle Problems
Alon Gonen, Shai Shalev-Shwartz
We derive bounds on the sample complexity of empirical risk minimization (ERM) in the context of minimizing non-convex risks that admit the strict saddle property. Recent progress…
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)…
Solving Ridge Regression using Sketched Preconditioned SVRG
Alon Gonen, Francesco Orabona, Shai Shalev-Shwartz
We develop a novel preconditioning method for ridge regression, based on recent linear sketching methods. By equipping Stochastic Variance Reduced Gradient (SVRG) with this precond…
Average Stability is Invariant to Data Preconditioning. Implications to Exp-concave Empirical Risk Minimization
Alon Gonen, Shai Shalev-Shwartz
We show that the average stability notion introduced by \cite{kearns1999algorithmic, bousquet2002stability} is invariant to data preconditioning, for a wide class of generalized li…
Faster SGD Using Sketched Conditioning
Alon Gonen, Shai Shalev-Shwartz
We propose a novel method for speeding up stochastic optimization algorithms via sketching methods, which recently became a powerful tool for accelerating algorithms for numerical…
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…
Subspace Learning with Partial Information
Alon Gonen, Dan Rosenbaum, Yonina Eldar +1
The goal of subspace learning is to find a -dimensional subspace of , such that the expected squared distance between instance vectors and the subspace is as small…
Efficient Active Learning of Halfspaces: an Aggressive Approach
Alon Gonen, Sivan Sabato, Shai Shalev-Shwartz
We study pool-based active learning of half-spaces. We revisit the aggressive approach for active learning in the realizable case, and show that it can be made efficient and practi…
Active Learning of Halfspaces under a Margin Assumption
Alon Gonen, Sivan Sabato, Shai Shalev-Shwartz
We derive and analyze a new, efficient, pool-based active learning algorithm for halfspaces, called ALuMA. Most previous algorithms show exponential improvement in the label comple…
Large-Scale Convex Minimization with a Low-Rank Constraint
Shai Shalev-Shwartz, Alon Gonen, Ohad Shamir
We address the problem of minimizing a convex function over the space of large matrices with low rank. While this optimization problem is hard in general, we propose an efficient g…