# Concentration inequalities for semidefinite least squares based on data

arXiv: https://arxiv.org/abs/2509.13166 · HTML: https://mlsanity.com/paper/2509.13166/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 24 references that are in the map.
- First posted on arXiv 16 Sep 2025.

## Builds on (most cited first, 5 of 5)

- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries](https://mlsanity.com/paper/1605.07129/) (2016)
- [Hard Shape-Constrained Kernel Machines](https://mlsanity.com/paper/2005.12636/) (2020)
- [Distributed Personalized Gradient Tracking with Convex Parametric Models](https://mlsanity.com/paper/2008.04363/) (2020)
- [Finite sample performance of linear least squares estimation](https://mlsanity.com/paper/1810.06380/) (2018)

## Built on by (most cited first, 1 of 1)

- [Generalization as a robust performance property of learning-enabled dynamical systems](https://mlsanity.com/paper/2608.30431/) (2026)

## Abstract (arXiv)

We study data-driven least squares (LS) problems with semidefinite (SD) constraints and derive finite-sample guarantees on the spectrum of their optimal solutions when these constraints are relaxed. In particular, we provide a high confidence bound allowing one to solve a simpler program in place of the full SDLS problem, while ensuring that the eigenvalues of the resulting solution are varepsilon-close of those enforced by the SD constraints. The developed certificate, which consistently shrinks as the number of data increases, turns out to be easy-to-compute, distribution-free, and only requires independent and identically distributed samples. Moreover, when the SDLS is used to learn an unknown quadratic function, we establish bounds on the error between a gradient descent iterate minimizing the surrogate cost obtained with no SD constraints and the true minimizer.