ON CONVERGENCE PROOFS FOR PERCEPTRONS

By A. Novikoff. 1963

How researchers see this paper

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

Citations in the corpus

Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, methodology): “The perceptron algorithm is used for training a linear classifier for binary classification and is guaranteed to converge for linearly separable data [26].”
Deep neural networks (2012, background): “2 1.2.2 Delta rule and Novikov’s Theorem . . . . . . . . . . . . . . . .”
Gradual Learning and Convergence (2008, unknown): “The second reason that the success of Perceptron is unsurprising is that its original formulation is guaranteed to converge on a correct weighting, if it is given sufficient learning data (Novikoff 1962, Collins 2002).”
The implicit bias of gradient descent on nonseparable data (2019, background): “…from the convex optimization literature, for instance smoothness-based convergence proofs of gradient descent (Nesterov, 2004; Bubeck, 2015), and also from basic learning theory, namely an adaptation of ideas from the perceptron convergence proof in order to bound | w t | (Novikoff, 1962).”
Bayesian reasoning and machine learning (2012, unknown): “For the limiting case of the perceptron (replacing σ(x) with θ(x)) and linearly separable data, online updating converges in a finite number of steps[212, 41], but does not converge for non-linearly separable data.”
Coresets for polytope distance (2009, methodology): “For cases of large margin, our bound of 2d2Ee steps is faster than the M 2 ρ2 many steps guaranteed by the currently known bounds for (kernel) Perceptron algorithms [21, 26].”
Merging chrominance and luminance in early, medium, and late fusion using Convolutional Neural Networks (2015, background): “In 1962, Novikoff got published the article “On convergence proofs on percep1962 trons” [Novikoff, 1962] and H.”
Prediction, learning, and games (2006, methodology): “Versions of the Perceptron convergence theorem were proved by Rosenblatt [250], Block [31], and Novikoff [225].”
The Sign-Rank of AC^O (2008, background): “Halfspaces constitute one of the most studied classes in computational learning theory [6, 31, 35, 44] and a major success story of the field.”
Large Scale Machine Learning (2004, methodology): “It has been shown by Novikoff (1962) that this algorithm converges toward a solution which separates classes, if the classes are linearly separable.”
Understanding Machine Learning: From Theory to Algorithms (2014, background): “In the statistical literature, it was introduced by Pearson (1901). Besides PCA and SVD, there are additional names that refer to the same idea and are being used in different scientific communities.”
Adaptive computation and machine learning (1998, background): “For a more detailed study, the reader could consult the book of Sutton and Barto [1998], whose mathematical content is short, or those of Puterman [1994] and Bertsekas [1987], which discuss in more depth several aspects, as well as the more recent book of Szepesvári [2010].”
Training Invariant Support Vector Machines using Selective Sampling (2005, methodology): “Older variants of the Perceptron, such as minover and adatron in [27], are also very close to SVMs.”
Catastrophic Forgetting and the Pseudorehearsal Solution in Hopfield-type Networks (1998, background): “This learning algorithm has been shown to always converge in a finite time if the desired output is linearly separable (Novikoff, 1962).”
Fast Kernel Classifiers with Online and Active Learning (2005, methodology): “When a solution exists, Novikoff's Theorem (Novikoff, 1962) states that the algorithm converges after a finite number of mistakes, or equivalently after inserting a finite number of support vectors.”
On the generalization ability of on-line learning algorithms (2001, methodology): “We begin by considering the classical Perceptron algorithm [35], [36], [37] in its dual kernel form, as investigated in, e.”