Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle

• URL: http://arxiv.org/abs/2008.13777v2
• Date: Mon, 15 Nov 2021 19:38:28 GMT
• Title: Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle
• Authors: Lijun Ding, Yuqian Zhang, Yudong Chen
• Abstract summary: Existing results for low-rank matrix recovery largely behaved on quadratic loss. We show that a critical component in provable low-rank recovery with non-quadratic loss is a regularity projection.
• Score: 23.84884127542249
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Existing results for low-rank matrix recovery largely focus on quadratic loss, which enjoys favorable properties such as restricted strong convexity/smoothness (RSC/RSM) and well conditioning over all low rank matrices. However, many interesting problems involve more general, non-quadratic losses, which do not satisfy such properties. For these problems, standard nonconvex approaches such as rank-constrained projected gradient descent (a.k.a. iterative hard thresholding) and Burer-Monteiro factorization could have poor empirical performance, and there is no satisfactory theory guaranteeing global and fast convergence for these algorithms. In this paper, we show that a critical component in provable low-rank recovery with non-quadratic loss is a regularity projection oracle. This oracle restricts iterates to low-rank matrices within an appropriate bounded set, over which the loss function is well behaved and satisfies a set of approximate RSC/RSM conditions. Accordingly, we analyze an (averaged) projected gradient method equipped with such an oracle, and prove that it converges globally and linearly. Our results apply to a wide range of non-quadratic low-rank estimation problems including one bit matrix sensing/completion, individualized rank aggregation, and more broadly generalized linear models with rank constraints.

Related papers

• Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization [48.65416821017865]
  This chapter introduces a new algorithmic approach, dubbed scaled gradient (ScaledGD) It converges linearly at a constant rate independent of the condition number of the low-rank object. It maintains the low periteration cost of gradient descent for a variety of tasks.
  arXiv  Detail & Related papers  (2023-10-09T21:16:57Z)
• A Generalized Alternating Method for Bilevel Learning under the Polyak-{\L}ojasiewicz Condition [63.66516306205932]
  Bilevel optimization has recently regained interest owing to its applications in emerging machine learning fields. Recent results have shown that simple alternating iteration-based iterations can match interest owing to convex lower-level objective.
  arXiv  Detail & Related papers  (2023-06-04T17:54:11Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization [4.7464518249313805]
  Sub-gradient method (SubGM) is used to recover a low-rank matrix from a limited number of measurements. We show that SubGM converges to the true solution, even under arbitrarily large and arbitrarily dense noise values.
  arXiv  Detail & Related papers  (2022-02-17T17:50:04Z)
• Provable Low Rank Plus Sparse Matrix Separation Via Nonconvex Regularizers [0.0]
  This paper considers a large problem where we seek to recover a low rank matrix/or sparse vector from some set of measurements. While methods based on convex bias estimators suffer from bias the rank or sparsity to be known as a priori, we use non regularizers. We present a novel analysis of the proximal alternating bias descent algorithm applied to such problems.
  arXiv  Detail & Related papers  (2021-09-26T22:09:42Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  We solve a weakly supervised regression problem. Under "weakly" we understand that for some training points the labels are known, for some unknown, and for others uncertain due to the presence of random noise or other reasons such as lack of resources. In the numerical section, we applied the suggested method to artificial and real datasets using Monte-Carlo modeling.
  arXiv  Detail & Related papers  (2021-04-13T23:21:01Z)
• Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number [34.0533596121548]
  Many problems in data science can be treated as estimating a low-rank from highly incomplete, sometimes even corrupted, observations. One popular approach is to resort to matrix factorization, where the low-rank matrix factors are optimized via first-order methods over a smooth loss.
  arXiv  Detail & Related papers  (2020-10-26T06:21:14Z)
• A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion [60.52730146391456]
  We propose a new non scalable low-rank regularizer called "nuclear Frobenius norm" regularizer, which is adaptive and sound. It bypasses the computation of singular values and allows fast optimization by algorithms. It obtains state-of-the-art recovery performance while being the fastest in existing matrix learning methods.
  arXiv  Detail & Related papers  (2020-08-14T18:47:58Z)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  We consider the fundamental problem of ReLU regression. The goal is to output the best fitting ReLU with respect to square loss given to draws from some unknown distribution.
  arXiv  Detail & Related papers  (2020-05-26T16:26:17Z)
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent [34.0533596121548]
  Low-rank matrix estimation converges convex problem that finds numerous applications in signal processing, machine learning and imaging science. We show that ScaledGD achieves the best of the best in terms of the number of the low-rank matrix. Our analysis is also applicable to general loss that are similar to low-rank gradient descent.
  arXiv  Detail & Related papers  (2020-05-18T17:17:16Z)
• On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems [19.24470467199451]
  We revisit the use of Gradient Descent (SGD) for solving convex optimization problems that serve as highly popular convex relaxations. We show that SGD may indeed be practically applicable to solving large-scale convex relaxations of low-rank matrix recovery problems.
  arXiv  Detail & Related papers  (2020-01-31T06:00:34Z)

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.