Learning Kernel-Based Halfspaces with the 0-1 Loss

By Shai Shalev-Shwartz, Ohad Shamir, Karthik Sridharan. 2011

62 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition

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 Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

Deriving Neural Architectures from Sequence and Graph Kernels (2017, background): “It turns out that many activations are also functions in the reproducing kernel Hilbert space (RKHS) of certain kernel functions (see Shalev-Shwartz et al. (2011); Zhang et al. (2016)).”
Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks (2017, background): “Another line of research [18], [42], [56] focuses on improper learning models using kernel-based approaches.”
On the Computational Efficiency of Training Neural Networks (2014, methodology): “The proof relies on an approximation of the sigmoid function based on Chebyshev polynomials, as was done in [21], and is given in the appendix.”
ℓ1-regularized Neural Networks are Improperly Learnable in Polynomial Time (2015, methodology): “Therefore, we have Shalev-Shwartz et al. [20, Corollary C] provide an upper bound on the right-hand side of Eq.”
Variance Reduction for Faster Non-Convex Optimization (2016, background): “tion| is not only a more natural choice than articial ones such as hinge loss, logistic loss, squared loss, but also generalize better in terms of testing accuracy especially when there are outliers [25]. However, since sigmoid loss is non-convex, it was previously considered hard to train an ERM pr”
Learning Neural Networks with Two Nonlinear Layers in Polynomial Time (2017, methodology): “,...,in) = X k1,...,kj∈[n]j j∈{0,...,d} v(k 1,...,kj). Here, v(·) is used to index the corresponding entry in v. The following lemma is due to [GKKT16], following an argument of Shalev-Shwartz et al. [SSSS11]: Lemma 1. Let p(t) = Pd i=0βit i be a given univariate polynomial with Pd i=1β 2 i ≤ B 2. F”
Convergence Results for Neural Networks via Electrodynamics (2017, methodology): “Kernel methods, ridge regression, and even boosting were explored for regularized neural networks with smooth activation functions in [SSSS11, ZLWJ15, ZLJ16].”
Learning Halfspaces and Neural Networks with Random Initialization (2015, background): “Shalev-Shwartz et al. (2011) study the problem of minimizing the objective (2) with function h deﬁned by (3), and show that under a certain cryptographic assumption, there is no poly( L )-time algorithm for (approximate) minimization.”
Improper Deep Kernels (2016, background): “Again, exponential dependence on margin for such problems is manifested in related works [1, 10, 19, 13].”
Probably Approximately Metric-Fair Learning (2018, result): “(Shalev-Shwartz et al., 2011) to show that taking B to be sufficiently large ensures that the accuracy of the set of (α, γ)-AMF predictors in Hφ,L is comparable to the accuracy of the set of (α, γ)-AMF predictors in HB .”
On the Quality of the Initial Basin in Overspecified Neural Networks (2015, background): “on function. Propagating the input forward through the graph, the net returns its value via the output of the ﬁnal layer in the graph. Artiﬁcial neural nets are a known to have broad expressive power [17, 18, 20]. A recent breakthrough in the effectiveness of neural networks has led to very impressi”
Reliably Learning the ReLU in Polynomial Time (2016, methodology): “[31] who used tools from Reproducing Kernel Hilbert Spaces (RKHS) to learn low-weight polynomials efficiently (Shalev-Shwartz et al.”