69 citations · 336 across the 41 of their papers we have counts for
4 papers · 1 filter
The complexity of learning halfspaces using generalized linear methods
Amit Daniely, Nati Linial, Shai Shalev-Shwartz
Many popular learning algorithms (E.g. Regression, Fourier-Transform based algorithms, Kernel SVM and Kernel ridge regression) operate by reducing the problem to a convex optimizat…
Multiclass Learning Approaches: A Theoretical Comparison with Implications
Amit Daniely, Sivan Sabato, Shai Shalev Shwartz
We theoretically analyze and compare the following five popular multiclass classification methods: One vs. All, All Pairs, Tree-based classifiers, Error Correcting Output Codes (EC…
On the practically interesting instances of MAXCUT
Yonatan Bilu, Amit Daniely, Nati Linial +1
The complexity of a computational problem is traditionally quantified based on the hardness of its worst case. This approach has many advantages and has led to a deep and beautiful…
Clustering is difficult only when it does not matter
Amit Daniely, Nati Linial, Michael Saks
Numerous papers ask how difficult it is to cluster data. We suggest that the more relevant and interesting question is how difficult it is to cluster data sets {\em that can be clu…