How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?

• URL: http://arxiv.org/abs/2006.06915v2
• Date: Thu, 12 Nov 2020 14:49:30 GMT
• Title: How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?
• Abstract summary: A non-low-rank matrix recovery problem contains no spurious local minima. We quantify the relationship between the quality of the initial guess and the corresponding reduction in data requirements.
• Score: 12.589519278962378
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a sufficiently large amount of labeled data, the non-convex low-rank matrix recovery problem contains no spurious local minima, so a local optimization algorithm is guaranteed to converge to a global minimum starting from any initial guess. However, the actual amount of data needed by this theoretical guarantee is very pessimistic, as it must prevent spurious local minima from existing anywhere, including at adversarial locations. In contrast, prior work based on good initial guesses have more realistic data requirements, because they allow spurious local minima to exist outside of a neighborhood of the solution. In this paper, we quantify the relationship between the quality of the initial guess and the corresponding reduction in data requirements. Using the restricted isometry constant as a surrogate for sample complexity, we compute a sharp threshold number of samples needed to prevent each specific point on the optimization landscape from becoming a spurious local minimum. Optimizing the threshold over regions of the landscape, we see that for initial points around the ground truth, a linear improvement in the quality of the initial guess amounts to a constant factor improvement in the sample complexity.

Related papers

• Escaping Local Minima Provably in Non-convex Matrix Sensing: A Deterministic Framework via Simulated Lifting [4.6910869230336045]
  Low-rank matrix sensing is a fundamental yet challenging non objective problem.<n>We design a framework to over-parametrized escape directions onto original parameter space to guarantee a decrease from existing minima.
  arXiv  Detail & Related papers  (2026-02-05T17:05:02Z)
• Zeroth-Order Optimization Finds Flat Minima [51.41529512093436]
  We show that zeroth-order optimization with the standard two-point estimator favors solutions with small trace of Hessian.<n>We further provide convergence rates of zeroth-order optimization to approximate flat minima for convex and sufficiently smooth functions.
  arXiv  Detail & Related papers  (2025-06-05T17:59:09Z)
• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  We introduce a new adaptive $k$-nearest neighbours ($kK$-NN) algorithm that explores the local curvature at a sample to adaptively defining the neighborhood size. Results on many real-world datasets indicate that the new $kK$-NN algorithm yields superior balanced accuracy compared to the established $k$-NN method.
  arXiv  Detail & Related papers  (2024-09-08T13:08:45Z)
• Learning minimal volume uncertainty ellipsoids [1.6795461001108096]
  We consider the problem of learning uncertainty regions for parameter estimation problems. Under the assumption of jointly Gaussian data, we prove that the optimal ellipsoid is centered around the conditional mean. In more practical cases, we propose a differentiable optimization approach for approximately computing the optimal ellipsoids.
  arXiv  Detail & Related papers  (2024-05-03T19:11:35Z)
• Characterization of Locality in Spin States and Forced Moves for Optimizations [0.36868085124383626]
  In optimization problems, the existence of local minima in energy landscapes is problematic to use to seek the global minimum. We develop an algorithm to get out of the local minima efficiently while it does not yield the exact samplings. As the proposed algorithm is based on a rejection-free algorithm, the computational cost is low.
  arXiv  Detail & Related papers  (2023-12-05T07:21:00Z)
• Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate [14.191310794366075]
  This paper is concerned with low-rank matrix optimization, which has found a wide range of applications in machine learning. We develop a framework that can deal with random corruptions to general objective functions, where the noise model is arbitrary. We characterize the geometry of the spurious local minima of the problem in a local region around ground truth in the case when the RIP constant is greater than $1/3$.
  arXiv  Detail & Related papers  (2022-03-08T07:44:47Z)
• Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning [58.79085525115987]
  Local methods are one of the promising approaches to reduce communication time. We show that the communication complexity is better than non-local methods when the local datasets is smaller than the smoothness local loss.
  arXiv  Detail & Related papers  (2022-02-12T15:12:17Z)
• Minimax rate of consistency for linear models with missing values [0.0]
  Missing values arise in most real-world data sets due to the aggregation of multiple sources and intrinsically missing information (sensor failure, unanswered questions in surveys...). In this paper, we focus on the extensively-studied linear models, but in presence of missing values, which turns out to be quite a challenging task. This eventually requires to solve a number of learning tasks, exponential in the number of input features, which makes predictions impossible for current real-world datasets.
  arXiv  Detail & Related papers  (2022-02-03T08:45:34Z)
• Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogates [0.0]
  We show that the first optimality gap of the proposed algorithm decays at the rate of the expected loss for various methods under nontens dependent data setting. We obtain first convergence point for various methods under nontens dependent data setting.
  arXiv  Detail & Related papers  (2022-01-05T15:17:35Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  Reinforcement learning aims to find an optimal policy by interaction with an environment. Policy gradients for local search are often obtained from random perturbations. We develop an algorithm utilizing a probabilistic model of the objective function and its gradient.
  arXiv  Detail & Related papers  (2021-06-22T16:07:02Z)
• Minimax Estimation for Personalized Federated Learning: An Alternative between FedAvg and Local Training? [31.831856922814502]
  Local datasets often originate from distinct yet not entirely unrelated probability distributions. In this paper, we show how the excess risks of personalized federated learning depend on data heterogeneity from a minimax point of view.
  arXiv  Detail & Related papers  (2021-03-02T17:58:20Z)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  Local features provide region-to-region rather than point-to-point correspondences. We propose guidelines for effective use of region-to-region matches in the course of a full model estimation pipeline. Experiments show that affine solvers can achieve accuracy comparable to point-based solvers at faster run-times.
  arXiv  Detail & Related papers  (2020-07-20T12:07:48Z)
• 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)
• Log-Likelihood Ratio Minimizing Flows: Towards Robust and Quantifiable Neural Distribution Alignment [52.02794488304448]
  We propose a new distribution alignment method based on a log-likelihood ratio statistic and normalizing flows. We experimentally verify that minimizing the resulting objective results in domain alignment that preserves the local structure of input domains.
  arXiv  Detail & Related papers  (2020-03-26T22:10:04Z)

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.