Connectivity Shapes Implicit Regularization in Matrix Factorization Models for Matrix Completion

• URL: http://arxiv.org/abs/2405.13721v1
• Date: Wed, 22 May 2024 15:12:14 GMT
• Title: Connectivity Shapes Implicit Regularization in Matrix Factorization Models for Matrix Completion
• Authors: Zhiwei Bai, Jiajie Zhao, Yaoyu Zhang,
• Abstract summary: We investigate the implicit regularization of matrix factorization for solving matrix completion problems. We empirically discover that the connectivity of observed data plays a crucial role in the implicit bias. Our work reveals the intricate interplay between data connectivity, training dynamics, and implicit regularization in matrix factorization models.
• Score: 2.8948274245812335
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Matrix factorization models have been extensively studied as a valuable test-bed for understanding the implicit biases of overparameterized models. Although both low nuclear norm and low rank regularization have been studied for these models, a unified understanding of when, how, and why they achieve different implicit regularization effects remains elusive. In this work, we systematically investigate the implicit regularization of matrix factorization for solving matrix completion problems. We empirically discover that the connectivity of observed data plays a crucial role in the implicit bias, with a transition from low nuclear norm to low rank as data shifts from disconnected to connected with increased observations. We identify a hierarchy of intrinsic invariant manifolds in the loss landscape that guide the training trajectory to evolve from low-rank to higher-rank solutions. Based on this finding, we theoretically characterize the training trajectory as following the hierarchical invariant manifold traversal process, generalizing the characterization of Li et al. (2020) to include the disconnected case. Furthermore, we establish conditions that guarantee minimum nuclear norm, closely aligning with our experimental findings, and we provide a dynamics characterization condition for ensuring minimum rank. Our work reveals the intricate interplay between data connectivity, training dynamics, and implicit regularization in matrix factorization models.

Related papers

• Synergistic eigenanalysis of covariance and Hessian matrices for enhanced binary classification [72.77513633290056]
  We present a novel approach that combines the eigenanalysis of a covariance matrix evaluated on a training set with a Hessian matrix evaluated on a deep learning model. Our method captures intricate patterns and relationships, enhancing classification performance.
  arXiv  Detail & Related papers  (2024-02-14T16:10:42Z)
• A phase transition between positional and semantic learning in a solvable model of dot-product attention [30.96921029675713]
  Morelinear model dot-product attention is studied as a non-dimensional self-attention layer with trainable and low-dimensional query and key data. We show that either a positional attention mechanism (with tokens each other based on their respective positions) or a semantic attention mechanism (with tokens tied to each other based their meaning) or a transition from the former to the latter with increasing sample complexity.
  arXiv  Detail & Related papers  (2024-02-06T11:13:54Z)
• Disentanglement via Latent Quantization [60.37109712033694]
  In this work, we construct an inductive bias towards encoding to and decoding from an organized latent space. We demonstrate the broad applicability of this approach by adding it to both basic data-re (vanilla autoencoder) and latent-reconstructing (InfoGAN) generative models.
  arXiv  Detail & Related papers  (2023-05-28T06:30:29Z)
• A Unified Analysis of Multi-task Functional Linear Regression Models with Manifold Constraint and Composite Quadratic Penalty [0.0]
  The power of multi-task learning is brought in by imposing additional structures over the slope functions. We show the composite penalty induces a specific norm, which helps to quantify the manifold curvature. A unified convergence upper bound is obtained and specifically applied to the reduced-rank model and the graph Laplacian regularized model.
  arXiv  Detail & Related papers  (2022-11-09T13:32:23Z)
• The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks [51.1848572349154]
  neural network models that perfectly fit noisy data can generalize well to unseen test data. We consider interpolating two-layer linear neural networks trained with gradient flow on the squared loss and derive bounds on the excess risk.
  arXiv  Detail & Related papers  (2021-08-25T22:01:01Z)
• Error Bounds of the Invariant Statistics in Machine Learning of Ergodic It\^o Diffusions [8.627408356707525]
  We study the theoretical underpinnings of machine learning of ergodic Ito diffusions. We deduce a linear dependence of the errors of one-point and two-point invariant statistics on the error in the learning of the drift and diffusion coefficients.
  arXiv  Detail & Related papers  (2021-05-21T02:55:59Z)
• Accounting for Unobserved Confounding in Domain Generalization [107.0464488046289]
  This paper investigates the problem of learning robust, generalizable prediction models from a combination of datasets. Part of the challenge of learning robust models lies in the influence of unobserved confounders. We demonstrate the empirical performance of our approach on healthcare data from different modalities.
  arXiv  Detail & Related papers  (2020-07-21T08:18:06Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)
• Generalisation error in learning with random features and the hidden manifold model [23.71637173968353]
  We study generalised linear regression and classification for a synthetically generated dataset. We consider the high-dimensional regime and using the replica method from statistical physics. We show how to obtain the so-called double descent behaviour for logistic regression with a peak at the threshold. We discuss the role played by correlations in the data generated by the hidden manifold model.
  arXiv  Detail & Related papers  (2020-02-21T14:49:41Z)
• Kernel and Rich Regimes in Overparametrized Models [69.40899443842443]
  We show that gradient descent on overparametrized multilayer networks can induce rich implicit biases that are not RKHS norms. We also demonstrate this transition empirically for more complex matrix factorization models and multilayer non-linear networks.
  arXiv  Detail & Related papers  (2020-02-20T15:43:02Z)

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.