Duality Based Generalization Bounds for Parallel Positively Homogeneous Networks

Authors: Uday Kiran Reddy Tadipatri, Benjamin David Haeffele, Joshua Agterberg, Rene Vidal
Primary area: learning theory
Keywords: statistical learning theory, non-convex optimization, high dimension, sample complexity, matrix sensing, neural network, positively homogeneous, generalization

Abstract:
We propose a general framework for deriving generalization bounds for parallel positively homogeneous neural
networks--a class of neural networks whose input-output map decomposes as the sum of positively homogeneous maps. 
Examples of such networks include matrix factorization/sensing, two-layer linear/ReLU networks, 
single-layer multi-head attention mechanisms, and tensor factorization.
Our general framework is based on linking the non-convex empirical risk minimization (ERM) problem of interest to a 
closely related convex optimization problem over prediction functions, which provides a global, achievable 
lower-bound to the original ERM problem. We exploit this convex lower-bound to perform generalization
analysis in the convex space while controlling the discrepancy between the convex model and its non-convex
counterpart. We apply our general framework to a wide variety of models ranging from low-rank matrix sensing,
to structured matrix sensing, two-layer linear networks, two-layer ReLU networks, and single-layer 
multi-head attention mechanisms, achieving generalization bounds with a sample complexity that scales nearly
linear with the network width.

Decision: reject

Reviews and discussion:

Metareview: