Concentration Inequalities for Semidefinite Least Squares Based on Data

We study data-driven least squares (LS) problemswith semidefinite (SD) constraints and derive finite-sample guar-antees on the spectrum of their optimal solutions when these con-straints are relaxed. In particular, we provide a high confidencebound allowing one to solve a simpler program in place of the fullSDLS problem, while ensuring that the eigenvalues of the resultingsolution are ε-close of those enforced by the SD constraints. Thedeveloped certificate, which consistently shrinks as the number ofdata increases, turns out to be easy-to-compute, distribution-free,and only requires independent and identically distributed samples.Moreover,