Fetching the paper…
Reading the bibliography…
Empirical risk minimization (ERM) is ubiquitous in machine learning and underlies most supervised learning methods.
Problem Complexity and Method Efficiency in Optimization
Arkadii S. Nemirovski and David B. Yudin · 1983
Earlier work this paper cites.
Statistical learning theory
Vlamimir Vapnik · 1998
Earlier work this paper cites.
On the complexity of k-sat
Russell Impagliazzo and Ramamohan Paturi · 2001
Earlier work this paper cites.
Which problems have strongly exponential complexity?
Russell Impagliazzo, Ramamohan Paturi, and Francis Zane · 2001
Earlier work this paper cites.
An introduction to kernel-based learning algorithms
Klaus-Robert Müller, Sebastian Mika, Gunnar Rätsch, Koji Tsuda, and Bernhard Schölkopf · 2001
Earlier work this paper cites.
Learning with kernels: support vector machines, regularization, optimization, and beyond
Bernhard Schölkopf and Alexander J. Smola · 2001
Earlier work this paper cites.
Using the nyström method to speed up kernel machines
Christopher K. Williams and Matthias Seeger · 2001
Earlier work this paper cites.
Introductory Lectures on Convex Optimization: A Basic Course
Yurii Nesterov · 2004
Earlier work this paper cites.
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
Alexandr Andoni and Piotr Indyk · 2006
Earlier work this paper cites.
The tradeoffs of large scale learning
Léonand Bottou and Olivier Bousquet · 2007
Earlier work this paper cites.
Pegasos: Primal estimated sub-gradient solver for SVM
Shai Shalev-Shwartz, Yoram Singer, and Nathan Srebro · 2007
Earlier work this paper cites.
Random features for large-scale kernel machines
Ali Rahimi and Benjamin Recht · 2008
Earlier work this paper cites.
Machine Learning: A Probabilistic Perspective
Kevin P. Murphy · 2012
Cited alongside, same era.
Finding correlations in subquadratic time, with applications to learning parities and juntas
Gregory Valiant · 2012
Cited alongside, same era.
Fast approximation algorithms for the diameter and radius of sparse graphs
Liam Roditty and Virginia Vassilevska Williams · 2013
Cited alongside, same era.
Consequences of faster alignment of sequences
Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann · 2014
Cited alongside, same era.
Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails
Karl Bringmann · 2014
Cited alongside, same era.
Better approximation algorithms for the graph diameter
Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert E. Tarjan, and Virginia Vassilevska Williams · 2014
Optimal data-dependent hashing for approximate near neighbors
Alexandr Andoni and Ilya Razenshteyn · 2015
Later among the works it cites.
Probabilistic polynomials and hamming nearest neighbors
Josh Alman and Ryan Williams · 2015
Later among the works it cites.
Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
Arturs Backurs and Piotr Indyk · 2015
Later among the works it cites.
Quadratic conditional lower bounds for string problems and dynamic time warping
Karl Bringmann and Marvin Künnemann · 2015
Later among the works it cites.
On the complexity of learning with kernels
Nicolo Cesa-Bianchi, Yishay Mansour, and Ohad Shamir · 2015
Later among the works it cites.
Hardness of easy problems: Basing hardness on popular conjectures such as the Strong Exponential Time Hypothesis (invited talk)
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Cnn features off-the-shelf: An astounding baseline for recognition
Ali Sharif Razavian, Hossein Azizpour, Josephine Sullivan, and Stefan Carlsson · 2014
Cited alongside, same era.
Understanding Machine Learning: From Theory to Algorithms
Shai Shalev-Shwartz and Shai Ben-David · 2014
Cited alongside, same era.
A lower bound for the optimization of finite sums
Alekh Agarwal and Léon Bottou · 2015
Cited alongside, same era.
Tight hardness results for LCS and other sequence similarity measures
Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams · 2015
Cited alongside, same era.
Practical and optimal lsh for angular distance
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt · 2015
Cited alongside, same era.
Virginia Vassilevska Williams · 2015
Later among the works it cites.
Polynomial Representations of Threshold Functions and Algorithmic Applications
Josh Alman, Timothy M Chan, and Ryan Williams · 2016
Later among the works it cites.
Dimension-free iteration complexity of finite sum optimization problems
Yossi Arjevani and Ohad Shamir · 2016
Later among the works it cites.
Oracle complexity of second-order methods for finite-sum problems
Yossi Arjevani and Ohad Shamir · 2016
Later among the works it cites.
Stochastic optimization: Beyond stochastic gradients and convexity
Francis Bach and Suvrit Sra · 2016
Later among the works it cites.
Tight complexity bounds for optimizing composite objectives
Blake E. Woodworth and Nathan Srebro · 2016
Later among the works it cites.