提出可验证的半定约束最小二乘解谱误差界，数据越多越紧。
Concentration inequalities for semidefinite least squares based on data
- 基于独立同分布数据推导半定约束最小二乘解的谱误差上界
- 解的特征值与半定约束要求相差不超过ε，且随数据量增大而收紧
- 无需分布假设，计算简单，适合学习未知二次函数的优化场景
研究带有半定约束的随机最小二乘问题，推导其最优解在约束松弛下的有限样本谱保证。特别地，提供一个高置信度上界，可在替换完整半定最小二乘（SDLS）问题时，确保解的特征值与半定约束要求的差距在ε以内。该验证证书随数据量增加持续收紧，计算简便、无需分布假设，仅需独立同分布样本。此外，当将半定最小二乘用于学习未知二次函数时，建立了无半定约束的代理代价函数梯度下降迭代解与真实最小值之间的误差界。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。