Cover Image

Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Stöger, Dominik, Zhu, Yizhe
Format:	Preprint
Published:	2024
Subjects:	Machine Learning Information Theory Optimization and Control Probability Statistics Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization
by: Chandrasekher, Kabir Aladin, et al.
Published: (2022)

A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression
by: Zhang, Yixuan, et al.
Published: (2025)

Linear regression with overparameterized linear neural networks: Tight upper and lower bounds for implicit $\ell^1$-regularization
by: Matt, Hannes, et al.
Published: (2025)

High-probability sample complexities for policy evaluation with linear function approximation
by: Li, Gen, et al.
Published: (2023)

Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
by: Li, Gen, et al.
Published: (2020)

Markov Kernels, Distances and Optimal Control: A Parable of Linear Quadratic Non-Gaussian Distribution Steering
by: Teter, Alexis M. H., et al.
Published: (2025)

To spike or not to spike: the whims of the Wonham filter in the strong noise regime
by: Bernardin, Cédric, et al.
Published: (2022)

Convergence of coordinate ascent variational inference for log-concave measures via optimal transport
by: Arnese, Manuel, et al.
Published: (2024)

4+3 Phases of Compute-Optimal Neural Scaling Laws
by: Paquette, Elliot, et al.
Published: (2024)

Fast Spawn\&Prune (FS\&P): Global convergence of stochastic conic particle gradient descent via birth/death process
by: De Castro, Yohann, et al.
Published: (2026)

Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regression
by: Agrawalla, Bhavya, et al.
Published: (2023)

High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariance
by: Balasubramanian, Krishnakumar, et al.
Published: (2023)

Optimal and instance-dependent guarantees for Markovian linear stochastic approximation
by: Mou, Wenlong, et al.
Published: (2021)

Early Stopping in Contextual Bandits and Inferences
by: Cui, Zihan
Published: (2025)

Orlicz regrets to consistently bound statistics of random variables with an application to environmental indicators
by: Yoshioka, Hidekazu, et al.
Published: (2023)

Statistical guarantees for continuous-time policy evaluation: blessing of ellipticity and new tradeoffs
by: Mou, Wenlong
Published: (2025)

Is RL fine-tuning harder than regression? A PDE learning approach for diffusion models
by: Mou, Wenlong
Published: (2025)

Randomstrasse101: Open Problems of 2024
by: Bandeira, Afonso S., et al.
Published: (2025)

Randomstrasse101: Open Problems of 2025
by: Bandeira, Afonso S., et al.
Published: (2026)

Optimal transport natural gradient for statistical manifolds with continuous sample space
by: Chen, Yifan, et al.
Published: (2018)

Hyperparameter tuning via trajectory predictions: Stochastic prox-linear methods in matrix sensing
by: Lou, Mengqi, et al.
Published: (2024)

Convergence rate of random scan Coordinate Ascent Variational Inference under log-concavity
by: Lavenant, Hugo, et al.
Published: (2024)

Efficient Online Learning in Interacting Particle Systems
by: Sharrock, Louis, et al.
Published: (2026)

Exact objectives of random linear programs and mean widths of random polyhedrons
by: Stojnic, Mihailo
Published: (2024)

Convergence of linear programming hierarchies for Gibbs states of spin systems
by: Fawzi, Hamza, et al.
Published: (2025)

High dimensional analysis reveals conservative sharpening and a stochastic edge of stability
by: Agarwala, Atish, et al.
Published: (2024)

Long-time dynamics and universality of nonconvex gradient descent
by: Han, Qiyang
Published: (2025)

Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis
by: Li, Gen, et al.
Published: (2021)

Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequality
by: Wibisono, Andre
Published: (2025)

Optimal estimators of cross-partial derivatives and surrogates of functions
by: Lamboni, Matieyendou
Published: (2024)

Propagation of Chaos in Contextual Flow Maps
by: Chen, Shi, et al.
Published: (2026)

The Risk Quadrangle in Optimization: An Overview with Recent Results and Extensions
by: Grechuk, Bogdan, et al.
Published: (2026)

New algorithms for sampling and diffusion models
by: Zhang, Xicheng
Published: (2024)

Gradient descent inference in empirical risk minimization
by: Han, Qiyang, et al.
Published: (2024)

Ensemble-Conditional Gaussian Processes (Ens-CGP): Representation, Geometry, and Inference
by: Ravela, Sai, et al.
Published: (2026)

Non-asymptotic convergence bounds for modified tamed unadjusted Langevin algorithm in non-convex setting
by: Neufeld, Ariel, et al.
Published: (2022)

Risk reversal for least squares estimators under nested convex constraints
by: Al-Ghattas, Omar
Published: (2026)

Learning linear dynamical systems under convex constraints
by: Tyagi, Hemant, et al.
Published: (2023)

On Universality of Non-Separable Approximate Message Passing Algorithms
by: Lovig, Max, et al.
Published: (2025)

Contributions to Robust and Efficient Methods for Analysis of High Dimensional Data
by: Yang, Kai
Published: (2025)