用高斯随机预言机优化子模函数，兼顾收敛性与动态适应性。
Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oracles
- 通过高斯平滑随机预言机估计梯度，实现零阶优化。
- 离线时收敛至全局ε近似解，在线时动态后悔上界为O(√(NP*ₙ))。
- 适合需要低阶信息的动态优化场景，如在线学习与自适应系统。
本文研究子模函数的最小化问题，提出一种基于高斯平滑随机预言机估计平滑函数梯度的零阶方法。在离线情况下，证明算法可收敛至全局ε-近似解；在在线情况下，对静态后悔实现Hannan一致性，并达到O(√(NP_N^*))的动态后悔上界，其中N为迭代次数，P_N^*为路径长度。文章给出了各类情况下的复杂度分析与超参数选择策略，并通过数值实验验证了理论结果。
原文摘要 · Abstract (English)
We consider the minimisation problem of submodular functions and investigate the application of a zeroth-order method to this problem. The method is based on exploiting a Gaussian smoothing random oracle to estimate the smoothed function gradient. We prove the convergence of the algorithm to a global $ε$-approximate solution in the offline case and show that the algorithm is Hannan-consistent in the online case with respect to static regret. Moreover, we show that the algorithm achieves $O(\sqrt{NP_N^\ast})$ dynamic regret, where $N$ is the number of iterations and $P_N^\ast$ is the path length. The complexity analysis and hyperparameter selection are presented for all the cases. The theoretical results are illustrated via numerical examples.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。