Asymptotic Normality of Generalized Low-Rank Matrix Sensing via Riemannian Geometry

• URL: http://arxiv.org/abs/2407.10238v2
• Date: Thu, 13 Feb 2025 18:22:34 GMT
• Title: Asymptotic Normality of Generalized Low-Rank Matrix Sensing via Riemannian Geometry
• Authors: Osbert Bastani,
• Abstract summary: We prove an normality guarantee for generalized low-rank matrix sensing.<n>We parameterize the manifold of low-rank matrices by $barthetabarthetatop$.<n>We prove $sqrtn(phi0-phi*)xrightarrowDN(0,(H*)-1)$ as $ntoinfty$, where $phi0$ and $phi*$ are representations of $bartheta*$ and $barthe
• Score: 37.53442095760427
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove an asymptotic normality guarantee for generalized low-rank matrix sensing -- i.e., matrix sensing under a general convex loss $\bar\ell(\langle X,M\rangle,y^*)$, where $M\in\mathbb{R}^{d\times d}$ is the unknown rank-$k$ matrix, $X$ is a measurement matrix, and $y^*$ is the corresponding measurement. Our analysis relies on tools from Riemannian geometry to handle degeneracy of the Hessian of the loss due to rotational symmetry in the parameter space. In particular, we parameterize the manifold of low-rank matrices by $\bar\theta\bar\theta^\top$, where $\bar\theta\in\mathbb{R}^{d\times k}$. Then, assuming the minimizer of the empirical loss $\bar\theta^0\in\mathbb{R}^{d\times k}$ is in a constant size ball around the true parameters $\bar\theta^*$, we prove $\sqrt{n}(\phi^0-\phi^*)\xrightarrow{D}N(0,(H^*)^{-1})$ as $n\to\infty$, where $\phi^0$ and $\phi^*$ are representations of $\bar\theta^*$ and $\bar\theta^0$ in the horizontal space of the Riemannian quotient manifold $\mathbb{R}^{d\times k}/\text{O}(k)$, and $H^*$ is the Hessian of the true loss in the same representation.

Related papers

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion [21.846732043706318]
  We show that the vanilla gradient descent provably converges to the ground truth $rmXstar$ without requiring any explicit regularization. Surprisingly, neither the convergence rate nor the final accuracy depends on the over- parameterized search rank $r'$, and they are only governed by the true rank $r$.
  arXiv  Detail & Related papers  (2024-02-09T19:39:23Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• The Sample Complexity Of ERMs In Stochastic Convex Optimization [13.896417716930687]
  We show that in fact $tildeO(fracdepsilon+frac1epsilon2)$ data points are also sufficient. We further generalize the result and show that a similar upper bound holds for all convex bodies.
  arXiv  Detail & Related papers  (2023-11-09T14:29:25Z)
• Universality for the global spectrum of random inner-product kernel matrices in the polynomial regime [12.221087476416056]
  In this paper, we show that this phenomenon is universal, holding as soon as $X$ has i.i.d. entries with all finite moments. In the case of non-integer $ell$, the Marvcenko-Pastur term disappears.
  arXiv  Detail & Related papers  (2023-10-27T17:15:55Z)
• How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization [46.55524654398093]
  We show how over- parameterization changes the convergence behaviors of descent. The goal is to recover an unknown low-rank ground-rank ground-truth matrix from near-isotropic linear measurements. We propose a novel method that only modifies one step of GD and obtains a convergence rate independent of $alpha$.
  arXiv  Detail & Related papers  (2023-10-03T03:34:22Z)
• $O(k)$-Equivariant Dimensionality Reduction on Stiefel Manifolds [2.0818404738530525]
  Many real-world datasets live on high-dimensional Stiefel and Grassmannian manifold, $V_k(mathbbRN)$ and $Gr(k, mathbbRN)$ respectively. We propose an algorithm called textitPrincipal Stiefel Coordinates (PSC) to reduce data dimensionality from $ V_k(mathbbRN)$ to $V_k(mathbbRn)$ in an textit$O(k)$-equivariant manner
  arXiv  Detail & Related papers  (2023-09-19T17:21:12Z)
• Mirror Natural Evolution Strategies [10.495496415022064]
  We focus on the theory of zeroth-order optimization which utilizes both the first-order and second-order information approximated by the zeroth-order queries. We show that the estimated covariance matrix of textttMiNES converges to the inverse of Hessian matrix of the objective function.
  arXiv  Detail & Related papers  (2023-08-01T11:45:24Z)
• Effective Minkowski Dimension of Deep Nonparametric Regression: Function Approximation and Statistical Theories [70.90012822736988]
  Existing theories on deep nonparametric regression have shown that when the input data lie on a low-dimensional manifold, deep neural networks can adapt to intrinsic data structures. This paper introduces a relaxed assumption that input data are concentrated around a subset of $mathbbRd$ denoted by $mathcalS$, and the intrinsic dimension $mathcalS$ can be characterized by a new complexity notation -- effective Minkowski dimension.
  arXiv  Detail & Related papers  (2023-06-26T17:13:31Z)
• A General Algorithm for Solving Rank-one Matrix Sensing [15.543065204102714]
  The goal of matrix sensing is to recover a matrix $A_star in mathbbRn times n$, based on a sequence of measurements. In this paper, we relax that rank-$k$ assumption and solve a much more general matrix sensing problem.
  arXiv  Detail & Related papers  (2023-03-22T04:07:26Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  We show that the eigenspectrum of $bf K$ is independent of the distribution of the i.i.d. entries of $bf w$. We propose a novel random technique, called Ternary Random Feature (TRF) The computation of the proposed random features requires no multiplication and a factor of $b$ less bits for storage compared to classical random features.
  arXiv  Detail & Related papers  (2021-10-05T09:33:49Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)
• On the computational and statistical complexity of over-parameterized matrix sensing [30.785670369640872]
  We consider solving the low rank matrix sensing problem with Factorized Gradient Descend (FGD) method. By decomposing the factorized matrix $mathbfF$ into separate column spaces, we show that $|mathbfF_t - mathbfF_t - mathbfX*|_F2$ converges to a statistical error.
  arXiv  Detail & Related papers  (2021-01-27T04:23:49Z)
• Sparse sketches with small inversion bias [79.77110958547695]
  Inversion bias arises when averaging estimates of quantities that depend on the inverse covariance. We develop a framework for analyzing inversion bias, based on our proposed concept of an $(epsilon,delta)$-unbiased estimator for random matrices. We show that when the sketching matrix $S$ is dense and has i.i.d. sub-gaussian entries, the estimator $(epsilon,delta)$-unbiased for $(Atop A)-1$ with a sketch of size $m=O(d+sqrt d/
  arXiv  Detail & Related papers  (2020-11-21T01:33:15Z)
• Optimal Measurement of Field Properties with Quantum Sensor Networks [0.0]
  We consider a quantum sensor network of qubit sensors coupled to a field $f(vecx;vectheta)$ analytically parameterized by the vector of parameters $vectheta$. We derive saturable bounds on the precision of measuring an arbitrary analytic function $q(vectheta)$ of these parameters.
  arXiv  Detail & Related papers  (2020-11-02T19:02:28Z)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  In compressed sensing, the restricted isometry property (RIP) on $M times N$ sensing matrices guarantees efficient reconstruction of sparse vectors. We investigate the exact average-case time complexity of certifying the RIP property for $Mtimes N$ matrices with i.i.d. $mathcalN(0,1/M)$ entries.
  arXiv  Detail & Related papers  (2020-05-22T16:55:01Z)
• Support recovery and sup-norm convergence rates for sparse pivotal estimation [79.13844065776928]
  In high dimensional sparse regression, pivotal estimators are estimators for which the optimal regularization parameter is independent of the noise level. We show minimax sup-norm convergence rates for non smoothed and smoothed, single task and multitask square-root Lasso-type estimators.
  arXiv  Detail & Related papers  (2020-01-15T16:11: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.