零阶优化可逼近一阶收敛速度，突破维度诅咒
From Cursed to Competitive: Closing the ZO-FO Gap via Input-to-State Stability
- 从动态系统视角分析零阶算法的平均行为
- 理论上证明其收敛率与一阶方法一致
- 适合研究优化算法稳定性与高维优化的学者
尽管通常认为零阶（ZO）算法在任意参数选择下都比一阶（FO）算法多出对迭代次数的依赖，本文表明，在若干条件下，期望意义上ZO方法的收敛率并不比其FO counterparts 多出维度依赖。本文从动力系统角度分析优化算法，揭示了在何种条件下，可以将ZO算法的平均行为视为其FO对应物在有界扰动下的平均，且扰动大小依赖于设计参数。利用输入到状态稳定（input-to-state stability）性质，证明了ZO方法的衰减速率与FO方法相同，并收敛至FO方法不动点的邻域，其半径取决于扰动范数的上界，该上界可任意小。数值实验验证了理论结论。
原文摘要 · Abstract (English)
While it is generally understood that zeroth-order (ZO) algorithms have an extra dependency on their number of iterations for any choice of parameters, compared to their first-order (FO) counterparts, in this work, we show that under several conditions, in expectation, ZO methods do not suffer from extra dimension dependencies in their convergence rates with respect to their FO counterparts. We look at optimisation algorithms from the dynamical systems perspective and analyse the conditions under which one can formulate the average of a ZO algorithm as the average of its FO counterpart with bounded perturbations with values dependent on design parameters. Then, using input-to-state stability properties, we show ZO methods follow the same decay rate as their FO counterparts and converge to a neighbourhood of the fixed point of FO methods, where its radius depends on the bound of the norm of the perturbations, which can be made arbitrarily small. The theoretical findings are illustrated via numerical examples.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。