通过轻量级零次近位梯度算法获得较低的查询复杂性

科学领域:

• 机器学习 机器学习
• 优化理论 优化理论

背景情况:

• 零级 (ZO) 优化对于机器学习至关重要,当梯度无法访问时.
• 现有的减少差异的ZO近位算法经常使用协调估计器,这些估计器在计算上昂贵 (O(d)).
• 随机ZO估计器提供了计算节省 (O(1)),但也带来了趋同分析的挑战.

研究的目的:

• 为了利用随机ZO估计器的计算效率.
• 为分析ZO优化算法开发新的理论框架.
• 改进非平滑的ZO优化问题的最先进的融合率.

主要方法:

• 引入了零级目标下降 (ZOOD) 属性来处理估计器错误.
• 提出了两种通用的减少框架,用于凸和非凸问题的收结果.
• 开发了ZOR-ProxSVRG和ZOR-ProxSAGA,使用完全随机估计器减少差异的ZO近位算法.

主要成果:

• 实现了非形问题的函数查询复杂度的改进,从O{\displaystyle O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O} 至O{\displaystyle O}
• 改进了形问题的函数查询复杂性,从O{\displaystyle O} dε-2到O{\displaystyle O} n log{\displaystyle O} 1/ε) +dε-1 .
• 实验结果证实了拟议方法的优越性.

结论:

• 拟议的ZOOD属性和减少框架有效地使用随机估计器分析ZOO优化.
• 新的算法和框架显著提高了非光滑ZO优化的效率.
• 这项工作为ZO优化在机器学习中的更实际应用铺平了道路.