Algorithmic Convergence & Generalization of ANN:

Algorithmic Convergence:

• Perceptron: Converges in finite steps if linearly separable (Novikoff theorem, mistakes $\le (R/\gamma)^2$). For non-separable, does not converge without modification (pocket algorithm).
• MLP with Backprop/GD: Non-convex loss, no guarantee of global optimum; GD converges to stationary point / local minima if learning rate $\eta <2/L$ (Lipschitz) and with decreasing schedule $\sum\eta=\infty$, $\sum\eta^2<\infty$ (Robbins-Monro). SGD converges almost surely to local minima. Practical: momentum, Adam help escape saddle points, converge faster but may not generalize optimally. Over-parameterized nets converge to zero training loss (interpolation regime).
• Factors: Weight initialization (Xavier/He), learning rate scheduling, batch size, gradient vanishing/exploding (sigmoid/tanh) mitigated by ReLU, BatchNorm, Residuals.
• Universal Approximation: Single hidden layer with enough neurons can approximate any continuous function (Cybenko 1989) — ensures representational capacity to converge to target if optimization succeeds.

Generalization Property:

• Capacity vs Generalization: More parameters → higher VC dimension, risk overfitting. Classical bias-variance U-curve: test error decreases then increases. Modern deep nets exhibit double descent — over-parameterized still generalizes due to implicit regularization.
• Measures: Generalization error $E_{test}-E_{train}$. Controlled by regularization: weight decay ($L2$), dropout, early stopping, data augmentation, batchnorm.
• Theoretical bounds: VC, Rademacher. For ANN with $W$ weights, VC $\sim O(W\log W)$.
• Empirical: Validation set, cross-validation estimate generalization; early stopping halts before validation error rises.
• Inductive bias: Smoothness, translational invariance (CNN) improve generalization to unseen data.
• Trade-off: Under-parameterized → underfit, over-parameterized without regularization → memorize noise, poor test performance. Proper tuning yields best generalization.

ANN converges algorithmically via gradient methods but generalization requires controlling complexity.