Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization

• URL: http://arxiv.org/abs/2203.02839v1
• Date: Sun, 6 Mar 2022 00:07:53 GMT
• Title: Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization
• Authors: Liwei Jiang, Yudong Chen, Lijun Ding
• Abstract summary: We consider the asymmetric factorization problem under a natural non formulation with arbitrary overparamatrization. We produce the best low-rank approximation to the observed matrix.
• Score: 16.325663190517773
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the asymmetric matrix factorization problem under a natural nonconvex formulation with arbitrary overparamatrization. We consider the model-free setting with no further assumption on the rank or singular values of the observed matrix, where the global optima provably overfit. We show that vanilla gradient descent with small random initialization and early stopping produces the best low-rank approximation of the observed matrix, without any additional regularization. We provide a sharp analysis on relationship between the iteration complexity, initialization size, stepsize and final error. In particular, our complexity bound is almost dimension-free and depends logarithmically on the final error, and our results have lenient requirements on the stepsize and initialization. Our bounds improve upon existing work and show good agreement with numerical experiments.

Related papers

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Symmetric Matrix Completion with ReLU Sampling [15.095194065320987]
  We study the problem of symmetric positive semi-definite low-rank matrix completion (MC) with entry-dependent sampling. In particular, we consider rectified linear unit (ReLU) sampling, where only stationary points are observed.
  arXiv  Detail & Related papers  (2024-06-09T15:14:53Z)
• The Inductive Bias of Flatness Regularization for Deep Matrix Factorization [58.851514333119255]
  This work takes the first step toward understanding the inductive bias of the minimum trace of the Hessian solutions in deep linear networks. We show that for all depth greater than one, with the standard Isometry Property (RIP) on the measurements, minimizing the trace of Hessian is approximately equivalent to minimizing the Schatten 1-norm of the corresponding end-to-end matrix parameters.
  arXiv  Detail & Related papers  (2023-06-22T23:14:57Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization. We provide novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
  arXiv  Detail & Related papers  (2022-11-03T12:40:24Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)
• Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix Completion via Gradient Descent [22.851500417035947]
  Factorization-based gradient descent is a scalable and efficient algorithm for solving the factorrank matrix completion. We show that gradient descent enjoys fast convergence to estimate a solution of the global nature problem.
  arXiv  Detail & Related papers  (2021-02-04T03:41:54Z)
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing [36.96922859748537]
  Low-rank matrix estimation plays a central role in various applications across science and engineering. Existing approaches rely on adding a metric regularization term to balance the scale of the two matrix factors. In this paper, we provide a theoretical justification for the performance in recovering a low-rank matrix from a small number of linear measurements.
  arXiv  Detail & Related papers  (2021-01-13T15:03:52Z)
• 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)
• Nonconvex Matrix Completion with Linearly Parameterized Factors [10.163102766021373]
  Parametric Factorization holds for important examples including subspace and completion simulations. The effectiveness of our unified nonconstrained matrix optimization method is also illustrated.
  arXiv  Detail & Related papers  (2020-03-29T22:40:47Z)
• Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion [101.83262280224729]
  We develop a relative error bound for nuclear norm regularized matrix completion. We derive a relative upper bound for recovering the best low-rank approximation of the unknown matrix.
  arXiv  Detail & Related papers  (2015-04-26T13:12:16Z)

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.