{"ID":2870493,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.13166","arxiv_id":"2509.13166","title":"Concentration inequalities for semidefinite least squares based on data","abstract":"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.","short_abstract":"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 probl...","url_abs":"https://arxiv.org/abs/2509.13166","url_pdf":"https://arxiv.org/pdf/2509.13166v2","authors":"[\"Filippo Fabiani\",\"Andrea Simonetto\"]","published":"2025-09-16T15:17:37Z","proceeding":"eess.SY","tasks":"[\"eess.SY\",\"cs.LG\",\"eess.SP\",\"math.OC\"]","methods":"[]","has_code":false}