Initialization-Dependent Sample Complexity of Linear Predictors and Neural Networks
We provide several new results on the sample complexity of vector-valued linear predictors (parameterized by a matrix), and more generally neural networks. Focusing on size-independent bounds, where only the Frobenius norm distance of the parameters from some fixed reference matrix $W_0$ is controlled, we show that the sample complexity behavior can be surprisingly different than what we may expect considering the well-studied setting of scalar-valued linear predictors. This also leads to new sample complexity bounds for feed-forward neural networks, tackling some open questions in the literature, and establishing a new convex linear prediction problem that is provably learnable without uniform convergence.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
The Sample Complexity of Learning Linear Predictors with the Squared Loss
In this short note, we provide a sample complexity lower bound for learning linear predictors with respect to the squared loss. Our focus is on an agnostic setting, where no assumptions are made on the data distribution.…
Bagging Robustly Learns VC Classes with Linear Sample Complexity
We revisit the problem of learning predictors robust to adversarial examples at test-time. We prove that VC classes are adversarially robustly learnable with sample complexity linear in the VC dimension $d$, providing an…
Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence
We propose a randomized second-order method for optimization known as the Newton Sketch: it is based on performing an approximate Newton step using a randomly projected or sub-sampled Hessian. For self-concordant functio…
De-randomized PAC-Bayes Margin Bounds: Applications to Non-convex and Non-smooth Predictors
In spite of several notable efforts, explaining the generalization of deterministic non-smooth deep nets, e.g., ReLU-nets, has remained challenging. Existing approaches for deterministic non-smooth deep nets typically ne…
Generalization BoundsOn the Rademacher Complexity of Linear Hypothesis Sets
Linear predictors form a rich class of hypotheses used in a variety of learning algorithms. We present a tight analysis of the empirical Rademacher complexity of the family of linear hypothesis classes with weight vector…