多种重尾、非 Lipschitzian 及高维情况下,(正则化的) 样本平均逼近的新样本复杂性界
原文中文,约500字,阅读约需1分钟。发表于: 。本文研究了在重尾性、非 Lipschitz 性和 / 或高维度下解决凸随机规划问题中样本平均逼近(SAA)及其简单变形,即正则化 SAA(RSAA)的样本复杂度。通过三组结果,论文表明 (R) SAA 在目标函数不一定是 Lipschitz 的情况下,且底层分布仅在(近)最优解处具有一些有界的中心矩时仍然有效。当 SP 的目标函数是平滑项和 Lipschitz 项的和时,(R) SAA...
本文研究了凸随机规划问题中样本平均逼近(SAA)及其简单变形的样本复杂度。实验证明,即使目标函数不是Lipschitz的且底层分布仅在最优解处具有有界的中心矩,(R) SAA仍然有效。当目标函数是平滑项和Lipschitz项的和时,(R) SAA的样本复杂度与可行域的复杂性度量完全独立。此外,当底层分布的中心矩有界时,所需样本量的增长速率不会超过O(p*d^(2/p))。这些结果与SAA典型的随维度d多项式增长的样本复杂度不同。