The Computational Advantage of Depth: Learning High-Dimensional Hierarchical Functions with Gradient Descent

• URL: http://arxiv.org/abs/2502.13961v1
• Date: Wed, 19 Feb 2025 18:58:28 GMT
• Title: The Computational Advantage of Depth: Learning High-Dimensional Hierarchical Functions with Gradient Descent
• Authors: Yatin Dandi, Luca Pesce, Lenka Zdeborová, Florent Krzakala,
• Abstract summary: We introduce a class of target functions that incorporate a hierarchy of latent subspace dimensionalities.<n>Our main theorem shows that feature learning with gradient descent reduces the effective dimensionality.<n>These findings open the way to further quantitative studies of the crucial role of depth in learning hierarchical structures with deep networks.
• Score: 28.999394988111106
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Understanding the advantages of deep neural networks trained by gradient descent (GD) compared to shallow models remains an open theoretical challenge. While the study of multi-index models with Gaussian data in high dimensions has provided analytical insights into the benefits of GD-trained neural networks over kernels, the role of depth in improving sample complexity and generalization in GD-trained networks remains poorly understood. In this paper, we introduce a class of target functions (single and multi-index Gaussian hierarchical targets) that incorporate a hierarchy of latent subspace dimensionalities. This framework enables us to analytically study the learning dynamics and generalization performance of deep networks compared to shallow ones in the high-dimensional limit. Specifically, our main theorem shows that feature learning with GD reduces the effective dimensionality, transforming a high-dimensional problem into a sequence of lower-dimensional ones. This enables learning the target function with drastically less samples than with shallow networks. While the results are proven in a controlled training setting, we also discuss more common training procedures and argue that they learn through the same mechanisms. These findings open the way to further quantitative studies of the crucial role of depth in learning hierarchical structures with deep networks.

Related papers

• An Overview of Low-Rank Structures in the Training and Adaptation of Large Models [52.67110072923365]
  Recent research has uncovered a widespread phenomenon in deep networks: the emergence of low-rank structures. These implicit low-dimensional patterns provide valuable insights for improving the efficiency of training and fine-tuning large-scale models. We present a comprehensive review of advances in exploiting low-rank structures for deep learning and shed light on their mathematical foundations.
  arXiv  Detail & Related papers  (2025-03-25T17:26:09Z)
• Global Convergence and Rich Feature Learning in $L$-Layer Infinite-Width Neural Networks under $μ$P Parametrization [66.03821840425539]
  In this paper, we investigate the training dynamics of $L$-layer neural networks using the tensor gradient program (SGD) framework. We show that SGD enables these networks to learn linearly independent features that substantially deviate from their initial values. This rich feature space captures relevant data information and ensures that any convergent point of the training process is a global minimum.
  arXiv  Detail & Related papers  (2025-03-12T17:33:13Z)
• Approximating Latent Manifolds in Neural Networks via Vanishing Ideals [20.464009622419766]
  We establish a connection between manifold learning and computational algebra by demonstrating how vanishing ideals can characterize the latent manifold of deep networks. We propose a new neural architecture that truncates a pretrained network at an intermediate layer, and approximates each class manifold via generators of the vanishing ideal. The resulting models have significantly fewer layers than their pretrained baselines, while maintaining comparable accuracy, achieving higher throughput and utilizing fewer parameters.
  arXiv  Detail & Related papers  (2025-02-20T21:23:02Z)
• Informed deep hierarchical classification: a non-standard analysis inspired approach [0.0]
  It consists in a multi-output deep neural network equipped with specific projection operators placed before each output layer. The design of such an architecture, called lexicographic hybrid deep neural network (LH-DNN), has been possible by combining tools from different and quite distant research fields. To assess the efficacy of the approach, the resulting network is compared against the B-CNN, a convolutional neural network tailored for hierarchical classification tasks.
  arXiv  Detail & Related papers  (2024-09-25T14:12:50Z)
• Convergence Analysis for Deep Sparse Coding via Convolutional Neural Networks [7.956678963695681]
  We explore intersections between sparse coding and deep learning to enhance our understanding of feature extraction capabilities.<n>We derive convergence rates for convolutional neural networks (CNNs) in their ability to extract sparse features.<n>Inspired by the strong connection between sparse coding and CNNs, we explore training strategies to encourage neural networks to learn more sparse features.
  arXiv  Detail & Related papers  (2024-08-10T12:43:55Z)
• Towards Scalable and Versatile Weight Space Learning [51.78426981947659]
  This paper introduces the SANE approach to weight-space learning. Our method extends the idea of hyper-representations towards sequential processing of subsets of neural network weights.
  arXiv  Detail & Related papers  (2024-06-14T13:12:07Z)
• Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions [20.036783417617652]
  We investigate the training dynamics of two-layer shallow neural networks trained with gradient-based algorithms.<n>We show that a simple modification of the idealized single-pass gradient descent training scenario drastically improves its computational efficiency.<n>Our results highlight the ability of networks to learn relevant structures from data alone without any pre-processing.
  arXiv  Detail & Related papers  (2024-05-24T11:34:31Z)
• Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networks [49.808194368781095]
  We show that three-layer neural networks have provably richer feature learning capabilities than two-layer networks. This work makes progress towards understanding the provable benefit of three-layer neural networks over two-layer networks in the feature learning regime.
  arXiv  Detail & Related papers  (2023-05-11T17:19:30Z)
• A neural anisotropic view of underspecification in deep learning [60.119023683371736]
  We show that the way neural networks handle the underspecification of problems is highly dependent on the data representation. Our results highlight that understanding the architectural inductive bias in deep learning is fundamental to address the fairness, robustness, and generalization of these systems.
  arXiv  Detail & Related papers  (2021-04-29T14:31:09Z)
• Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning [50.24174211654775]
  We present a novel contrastive self-supervised learning framework for anomaly detection on attributed networks. Our framework fully exploits the local information from network data by sampling a novel type of contrastive instance pair. A graph neural network-based contrastive learning model is proposed to learn informative embedding from high-dimensional attributes and local structure.
  arXiv  Detail & Related papers  (2021-02-27T03:17:20Z)
• Statistical Mechanics of Deep Linear Neural Networks: The Back-Propagating Renormalization Group [4.56877715768796]
  We study the statistical mechanics of learning in Deep Linear Neural Networks (DLNNs) in which the input-output function of an individual unit is linear. We solve exactly the network properties following supervised learning using an equilibrium Gibbs distribution in the weight space. Our numerical simulations reveal that despite the nonlinearity, the predictions of our theory are largely shared by ReLU networks with modest depth.
  arXiv  Detail & Related papers  (2020-12-07T20:08:31Z)
• Learning Connectivity of Neural Networks from a Topological Perspective [80.35103711638548]
  We propose a topological perspective to represent a network into a complete graph for analysis. By assigning learnable parameters to the edges which reflect the magnitude of connections, the learning process can be performed in a differentiable manner. This learning process is compatible with existing networks and owns adaptability to larger search spaces and different tasks.
  arXiv  Detail & Related papers  (2020-08-19T04:53:31Z)
• An Ode to an ODE [78.97367880223254]
  We present a new paradigm for Neural ODE algorithms, called ODEtoODE, where time-dependent parameters of the main flow evolve according to a matrix flow on the group O(d) This nested system of two flows provides stability and effectiveness of training and provably solves the gradient vanishing-explosion problem.
  arXiv  Detail & Related papers  (2020-06-19T22:05:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.