Duality Based Generalization Bounds for Parallel Positively Homogeneous Networks

Uday Kiran Reddy Tadipatri, Benjamin David Haeffele, Joshua Agterberg, Rene VidalOpenReview 2025 · Submission to ICLR 2025 · Withdrawn · OpenReview

Its authors withdrew this paper, so there is no full text to read or summarize.

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.
BibTeX
@misc{tadipatri2025duality,
  author = {Uday Kiran Reddy Tadipatri and Benjamin David Haeffele and Joshua Agterberg and Rene Vidal},
  title = {{Duality Based Generalization Bounds for Parallel Positively Homogeneous Networks}},
  year = {2025},
  url = {https://openreview.net/forum?id=LWKHLHroPk},
  howpublished = {OpenReview},
  note = {Submitted to ICLR 2025},
}
Figure