A Zeroth-Order Adaptive Frank–Wolfe Algorithm for Resource Allocation in Internet of Things: Convergence Analysis

A pivotal problem in the Internet of Things (IoT) is resource allocation, where the goal is to optimize allocation strategies of IoT resources. In general, resource allocation problems are formulated as constrained optimization problems, which can be effectively solved by the zeroth-order Frank-Wolfe algorithm. However, the existing zeroth-order Frank-Wolfe algorithms suffer from slow convergence since they scale the zeroth-order gradient in all directions. For this reason, we propose a faster zeroth-order Frank-Wolfe algorithm, referred to as ZO-AdaSFW, which incorporates adaptive gradient methods and the variance-reduced technique (SPIDER) into the zeroth-order Frank-Wolfe algorithm. Moreover, ZO-AdaSFW can achieve the convergence rate of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(T^{-1}) $ </tex-math></inline-formula> in the convex setting, where T is the time horizon. Meanwhile, we also prove that ZO-AdaSFW has the best-known convergence rate <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(T^{-1/2})$ </tex-math></inline-formula> among zeroth-order algorithms in the nonconvex setting. In addition, the experimental results show that the performance of ZO-AdaSFW outperforms state-of-the-art zeroth-order Frank-Wolfe algorithms on different applications.