提出一种高效秩反馈零阶优化算法,理论证明其查询效率可达最优。
Explicit and Non-asymptotic Query Complexities of Rank-Based Zeroth-order Algorithm on Stochastic Smooth Functions
- 基于排序反馈设计简单高效的零阶优化算法
- 在平滑随机目标下实现最优查询复杂度,匹配已有最佳结果
- 适合人类反馈、偏好学习等需排序输入的场景
零阶(ZO)优化在需要人类反馈的场景中日益重要,如基于人类反馈的强化学习、偏好学习和进化策略。尽管基于排序的零阶算法在实践中表现优异且鲁棒性强,但在随机目标和标准平滑性假设下的理论理解仍不充分。本文研究仅能获取随机函数排序信息的零阶优化问题,提出一种简单且计算高效的秩反馈零阶算法。在函数平滑、强凸性和随机梯度二阶矩有界的假设下,我们建立了凸与非凸目标的显式非渐近查询复杂度上界。结果表明,仅使用排序信息即可达到与基于值的零阶算法相当的最佳查询效率。分析方法摆脱了传统的漂移和信息几何技术,为噪声环境下秩反馈优化提供了新工具。该研究缩小了理论与实践的差距,为人类偏好驱动的优化提供了理论基础。
原文摘要 · Abstract (English)
Zeroth-order (ZO) optimization with ordinal feedback has emerged as a fundamental problem in modern machine learning systems, particularly in human-in-the-loop settings such as reinforcement learning from human feedback, preference learning, and evolutionary strategies. While rank-based ZO algorithms enjoy strong empirical success and robustness properties, their theoretical understanding, especially under stochastic objectives and standard smoothness assumptions, remains limited. In this paper, we study rank-based zeroth-order optimization for stochastic functions where only ordinal feedback of the stochastic function is available. We propose a simple and computationally efficient rank-based ZO algorithm. Under standard assumptions including smoothness, strong convexity, and bounded second moments of stochastic gradients, we establish explicit non-asymptotic query complexity bounds for both convex and nonconvex objectives. Notably, our results match the best-known query complexities of value-based ZO algorithms, demonstrating that ordinal information alone is sufficient for optimal query efficiency in stochastic settings. Our analysis departs from existing drift-based and information-geometric techniques, offering new tools for the study of rank-based optimization under noise. These findings narrow the gap between theory and practice and provide a principled foundation for optimization driven by human preferences.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。