The Forgetron: A Kernel-Based Perceptron on a Fixed Budget

By Ofer Dekel, Shai Shalev-Shwartz, Yoram Singer. 2005

126 citations recorded by the source corpus.

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

A discriminative language model with pseudo-negative samples (2007, methodology): “We would like to see more refined online learning methods with kernels (Cheng et al., 2006; Dekel et al., 2005) that we could apply in these areas.”
Hash Kernels (2009, methodology): “This has applications to estimation on strings and graphs.”
Nyström Method vs Random Fourier Features: A Theoretical and Empirical Comparison (2012, background): “Other approaches such as online learning [9] and budget learning [7] have also been developed for large-scale kernel learning, but they tend to yield performance worse performance than batch learning.”
Sparse Online Learning via Truncated Gradient (2008, methodology): “We apply the approach to several datasets and nd that for datasets with large numbers of features, substantial sparsity is discoverable.”
Non-parametric Stochastic Approximation with Large Step sizes (2014, background): “Several authors have considered expanding gn on a subset of all (Kxi), which allows to bring down the complexity of each iteration and obtain an overall linear complexity is n [38, 39], but this comes at the expense of not obtaining the sharp generalization errors that we obtain in this paper.”
Minimax Classification under Concept Drift with Multidimensional Adaptation and Performance Guarantees (2022, unknown): “…risk minimization algorithm (NORMA) (Kivinen et al., 2004), Nystr¨om online gradient descent (NOGD), Fourier online gradient descent (FOGD) (Lu et al., 2016), λ - perceptron (Pavlidis et al., 2011), dynamic weighted majority (DWM) (Kolter & Maloof, 2007), and Forgetron (Dekel et al., 2006).”
Hash Kernels for Structured Data (2009, unknown): “Work on estimation on a budget (Dekel et al., 2006) tries to ensure that this problem does not arise in the ﬁrst place by ensuring that the number of kernel functions used in the expansion never exceeds a given budget or by using an !”
Online Learning: A Comprehensive Survey (2018, methodology): “Instead of choosing randomly, another way as used in “Forgetron” (Dekel et al., 2005) is to discard the oldest SV by assuming an older SV is less representative for the distribution of fresh training data streams.”
Large-scale Online Kernel Learning with Random Feature Reparameterization (2017, methodology): “Various attempts had been proposed to overcome this problem, which relies on developing effective budget maintenance strategy, such as: removal [Dekel et al., 2005], projection [Orabona et al.”