Learning and Smoothed Analysis

By Adam Tauman Kalai, Alex Samorodnitsky, Shang-Hua Teng. 2009

256 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Scaling & Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Scaling & Learning Theory

Citations in the corpus

Reliability and Learnability of Human Bandit Feedback for Sequence-to-Sequence Reinforcement Learning (2018, background): “Learnability is understood by a slight misuse of the machine learning notion of learnability (Shalev-Shwartz et al., 2010) as the question how well reward estimates can approximate human rewards.”
Distillation as a Defense to Adversarial Perturbations Against Deep Neural Networks (2015, background): “An interesting result to progress in our discussion is the following Theorem mentioned previously and proved in [34].”
Adaptive Gradient-Based Meta-Learning Methods (2019, background): “[49] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan.”
On the Computational Efficiency of Training Neural Networks (2014, background): “We note that algorithms for efﬁciently learning (real-valued) sparse or low-degree polynomials has been studied in several previous works (e.g. [13, 14, 8, 2, 1]).”
Preserving Statistical Validity in Adaptive Data Analysis (2014, background): “An important line of work [11, 33, 34, 40] establishes connections between the stability of a learning algorithm and its ability to generalize.”
Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle (2015, methodology): “The optimal risk for any continuous distribution is 1 because any finite subset is of measure 0, output ∅ is 0-consistent and 0-generalizing, but not AERM, since the minimum empirical risk is 0.”
Privacy Risk in Machine Learning: Analyzing the Connection to Overfitting (2017, background): “[27], who show that an algorithm’s ability to achieve a given generalization error (as a function of n) is equivalent to its ARO-stability rate.”
An Information-Theoretic View for Deep Learning (2018, methodology): “5 Stability and Risk Bound of Deep Learning It is known that the expected generalization error is equivalent to the notion of stability of the learning algorithm (Shalev-Shwartz et al. 2010).”
Differentially Private Feature Selection via Stability Arguments, and the Robustness of the Lasso (2013, methodology): “Following the generic template in the previous section, the algorithm Asamp finally adds Laplace noise to d̂ and outputs f̂(D) if the noise distance estimate is sufficiently high.”
The Interplay Between Stability and Regret in Online Learning (2012, methodology): “Moreover, our knowledge of the connection between stability and generalization is beginning to achieve a fair degree of maturity (see, for instance, [4, 13, 18, 22]).”
A survey of Algorithms and Analysis for Adaptive Online Learning (2014, methodology): “These per-round terms can be seen as measuring the stability of the algorithm , an online analog to the role of stability in the stochastic setting (Bousquet and Elisseeff, 2002, Rakhlin et al., 2005, Shalev-Shwartz et al., 2010).”
Generalization in Adaptive Data Analysis and Holdout Reuse (2015, background): “An important line of work [3, 15, 18] establishes connections between the stability of a learning algorithm and its ability to generalize.”
Uniform convergence may be unable to explain generalization in deep learning (2019, background): “On the other hand, Shalev-Shwartz et al. (2010) proved that uniform convergence is not necessary for learnability of a general learning problem, which includes a larger class of problems besides binary classification (thus, their negative result relies on an example stochastic optimization problem).”
Controlling Bias in Adaptive Data Analysis Using Information Theory (2015, methodology): “e selection rule Tcould represent the choice made by a data-analyst, like Bob, after performing several rounds of exploratory analysis. A powerful line of work in computer science and learning theory [12, 13, 14] has explored the role of algorithmic stability in preventing overﬁtting. Related to sta”
Generalization Bounds for Uniformly Stable Algorithms (2018, background): “For example, ERM solution to convex learning problems can be made uniformly stable by adding a strongly convex term to the objective [26].”
Differentially Private Model Selection via Stability Arguments and the Robustness of the Lasso (2013, background): “A variant of the notion of perturbation stability that we consider have been studied previously (Bousquet and Elisseeff, 2002; Shalev-Shwartz et al., 2010; Xu et al., 2010; Dwork and Lei, 2009).”