在本文中，我们开发了具有可证明的（几乎）最优样本复杂度的零阶算法，以用于随机双层优化，其中仅提供带噪声的函数评估。我们提出了两种不同的算法：第一种是受雅可比/海森矩阵方法启发，第二种则基于使用惩罚函数重构。雅可比/海森矩阵方法的样本复杂度为O(d³/ε²)，在准确度ε方面是最优的，尽管在问题维度d上具有多项式依赖性。相反，基于惩罚的方法将这一保证提高到O(d/ε²)，最优地将维度依赖性降低为线性，同时保持最佳的准确度缩放。我们的分析建立在高斯平滑技术之上，我们严格证明了在现有文献中考虑的随机双层设置下这些技术的有效性。根据我们所知，这是首次提供零阶随机逼近方法在双层优化中可证明的最优样本复杂度保证的工作。
Aghasi等（Sat，）研究了这个问题。