Zeroth-Order Optimization for Composite Problems with Functional Constraints
Zeroth-Order Optimization for Composite Problems with Functional Constraints
复制标题
DOI：
10.1609/aaai.v36i7.20709
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Zichong Li;Pin-Yu Chen;Sijia Liu;Songtao Lu;Yangyang Xu
中科院分区：
文献类型：
--
作者：
Zichong Li;Pin-Yu Chen;Sijia Liu;Songtao Lu;Yangyang Xu
在许多现实世界的问题中，一阶导数的计算过于昂贵，甚至难以实现。为了解决这些问题，只需要函数求值的零阶（ZO）方法通常比FO方法更有效，有时是唯一的选择。在本文中，我们提出了一种新的零阶非精确增广拉格朗日方法（ZO-iALM）来解决涉及复合（即光滑+非光滑）目标和功能约束的黑盒优化问题。这似乎是第一个为功能约束优化开发基于iom的ZO方法的工作，同时实现了与最著名的FO复杂性结果匹配的查询复杂性结果，直到可变维度的因子。通过广泛的实验研究，我们证明了该方法的有效性。我们的方法的应用范围从经典的优化问题到实际的机器学习示例，如传感器网络中的资源分配和对抗性示例生成。
In many real-world problems, first-order (FO) derivative evaluations are too expensive or even inaccessible. For solving these problems, zeroth-order (ZO) methods that only need function evaluations are often more efficient than FO methods or sometimes the only options. In this paper, we propose a novel zeroth-order inexact augmented Lagrangian method (ZO-iALM) to solve black-box optimization problems, which involve a composite (i.e., smooth+nonsmooth) objective and functional constraints. This appears to be the first work that develops an iALM-based ZO method for functional constrained optimization and meanwhile achieves query complexity results matching the best-known FO complexity results up to a factor of variable dimension. With an extensive experimental study, we show the effectiveness of our method. The applications of our method span from classical optimization problems to practical machine learning examples such as resource allocation in sensor networks and adversarial example generation.