Non-quadratic Mirror Descent exhibits exponential initialization sensitivity in convex settings, shown via 3D constructions and KL-regularized simplex examples, with Bregman anchoring proposed for stabilization.
SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
abstract
Neural networks exhibit good generalization behavior in the over-parameterized regime, where the number of network parameters exceeds the number of observations. Nonetheless, current generalization bounds for neural networks fail to explain this phenomenon. In an attempt to bridge this gap, we study the problem of learning a two-layer over-parameterized neural network, when the data is generated by a linearly separable function. In the case where the network has Leaky ReLU activations, we provide both optimization and generalization guarantees for over-parameterized networks. Specifically, we prove convergence rates of SGD to a global minimum and provide generalization guarantees for this global minimum that are independent of the network size. Therefore, our result clearly shows that the use of SGD for optimization both finds a global minimum, and avoids overfitting despite the high capacity of the model. This is the first theoretical demonstration that SGD can avoid overfitting, when learning over-specified neural network classifiers.
representative citing papers
Continual classification in homogeneous models is sequential projections onto margin sets, with local linear convergence under regularity properties for random and cyclic tasks, extended to regression.
ID3 learns log n-juntas in polynomial time under the smoothed analysis model for product distributions.
GRAIN is a gradient aggregation method using min-norm objectives to ensure non-negative inner products with group gradients, yielding tighter uniform stability bounds than SGD under smoothness assumptions.
Empirical study finds multi-block ADMM outperforms two-block ADMM on optimization and prediction in multi-task learning across all tested datasets and dual step sizes.
citing papers explorer
-
Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity
Non-quadratic Mirror Descent exhibits exponential initialization sensitivity in convex settings, shown via 3D constructions and KL-regularized simplex examples, with Bregman anchoring proposed for stabilization.
-
Convergence of Continual Learning in Homogeneous Deep Networks
Continual classification in homogeneous models is sequential projections onto margin sets, with local linear convergence under regularity properties for random and cyclic tasks, extended to regression.
-
ID3 Learns Juntas for Smoothed Product Distributions
ID3 learns log n-juntas in polynomial time under the smoothed analysis model for product distributions.
-
GRAIN: Group Aggregation via Min-Norm Objective
GRAIN is a gradient aggregation method using min-norm objectives to ensure non-negative inner products with group gradients, yielding tighter uniform stability bounds than SGD under smoothness assumptions.
-
Two-block vs. Multi-block ADMM: An empirical evaluation of convergence
Empirical study finds multi-block ADMM outperforms two-block ADMM on optimization and prediction in multi-task learning across all tested datasets and dual step sizes.