Flavors of Margin: Implicit Bias of Steepest Descent in Homogeneous Neural Networks

• URL: http://arxiv.org/abs/2410.22069v1
• Date: Tue, 29 Oct 2024 14:28:49 GMT
• Title: Flavors of Margin: Implicit Bias of Steepest Descent in Homogeneous Neural Networks
• Authors: Nikolaos Tsilivis, Gal Vardi, Julia Kempe,
• Abstract summary: We study the implicit bias of the general family of steepest descent algorithms, which includes gradient descent, sign descent and coordinate descent. We prove that an algorithm-dependent geometric margin starts increasing once the networks reach perfect training accuracy.
• Score: 19.185059111021854
• License:
• Abstract: We study the implicit bias of the general family of steepest descent algorithms, which includes gradient descent, sign descent and coordinate descent, in deep homogeneous neural networks. We prove that an algorithm-dependent geometric margin starts increasing once the networks reach perfect training accuracy and characterize the late-stage bias of the algorithms. In particular, we define a generalized notion of stationarity for optimization problems and show that the algorithms progressively reduce a (generalized) Bregman divergence, which quantifies proximity to such stationary points of a margin-maximization problem. We then experimentally zoom into the trajectories of neural networks optimized with various steepest descent algorithms, highlighting connections to the implicit bias of Adam.

Related papers

• Convergence Analysis of the Wasserstein Proximal Algorithm beyond Geodesic Convexity [13.468026138183623]
  The proximal descent algorithm is a powerful tool to nonlinear and nonsmooths in a general metric space. We show a faster convergence rate than the Euclidean algorithm on meanfield neural networks.
  arXiv  Detail & Related papers  (2025-01-25T00:00:50Z)
• Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm [8.329034093208826]
  We introduce a method to efficiently approximate tensor network contractions using low-rank approximations. The proposed algorithm has the flexibility to incorporate a large portion of the environment when performing low-rank approximations.
  arXiv  Detail & Related papers  (2024-06-14T07:13:52Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  We introduce UnRolled Federated learning (SURF), a method that expands algorithm unrolling to federated learning. Our proposed method tackles two challenges of this expansion, namely the need to feed whole datasets to the unrolleds and the decentralized nature of federated learning.
  arXiv  Detail & Related papers  (2023-05-24T17:26:22Z)
• Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Data [63.34506218832164]
  In this work, we investigate the implicit bias of gradient flow and gradient descent in two-layer fully-connected neural networks with ReLU activations. For gradient flow, we leverage recent work on the implicit bias for homogeneous neural networks to show that leakyally, gradient flow produces a neural network with rank at most two. For gradient descent, provided the random variance is small enough, we show that a single step of gradient descent suffices to drastically reduce the rank of the network, and that the rank remains small throughout training.
  arXiv  Detail & Related papers  (2022-10-13T15:09:54Z)
• Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks [59.142826407441106]
  We study the generalization behavior of shallow neural networks (SNNs) by leveraging the concept of algorithmic stability. We consider gradient descent (GD) and gradient descent (SGD) to train SNNs, for both of which we develop consistent excess bounds.
  arXiv  Detail & Related papers  (2022-09-19T18:48:00Z)
• Improved Overparametrization Bounds for Global Convergence of Stochastic Gradient Descent for Shallow Neural Networks [1.14219428942199]
  We study the overparametrization bounds required for the global convergence of gradient descent algorithm for a class of one hidden layer feed-forward neural networks.
  arXiv  Detail & Related papers  (2022-01-28T11:30:06Z)
• Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularization [118.50301177912381]
  We show that Adam can converge to different solutions of the objective with provably different errors, even with weight decay globalization. We show that if convex, and the weight decay regularization is employed, any optimization algorithms including Adam will converge to the same solution.
  arXiv  Detail & Related papers  (2021-08-25T17:58:21Z)
• Strong overall error analysis for the training of artificial neural networks via random initializations [3.198144010381572]
  We show that the depth of the neural network only needs to increase much slower in order to obtain the same rate of approximation. Results hold in the case of an arbitrary optimization algorithm with i.i.d. random initializations.
  arXiv  Detail & Related papers  (2020-12-15T17:34:16Z)
• A Dynamical View on Optimization Algorithms of Overparameterized Neural Networks [23.038631072178735]
  We consider a broad class of optimization algorithms that are commonly used in practice. As a consequence, we can leverage the convergence behavior of neural networks. We believe our approach can also be extended to other optimization algorithms and network theory.
  arXiv  Detail & Related papers  (2020-10-25T17:10:22Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  Simple algorithms have been shown to lead to good empirical results in many contexts. Several works have pursued rigorous analytical justification for studying non optimization problems. A key insight in these analyses is that perturbations play a critical role in allowing local descent algorithms.
  arXiv  Detail & Related papers  (2020-03-31T16:54:22Z)
• MSE-Optimal Neural Network Initialization via Layer Fusion [68.72356718879428]
  Deep neural networks achieve state-of-the-art performance for a range of classification and inference tasks. The use of gradient combined nonvolutionity renders learning susceptible to novel problems. We propose fusing neighboring layers of deeper networks that are trained with random variables.
  arXiv  Detail & Related papers  (2020-01-28T18:25:15Z)

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.