证明了非凸非凹极小极大优化需指数级查询次数

Min-Max Optimization Requires Exponentially Many Queries

• 分析极小极大优化的查询复杂度，给出理论下界
• 无论是否用梯度，求解精度ε需指数级查询
• 对高维或高精度问题有警示意义

我们研究在 $[0,1]^d \times [0,1]^d$ 上对非凸非凹函数 $f$ 进行极小极大优化的查询复杂度。给定对 $f$ 及其梯度 $ abla f$ 的黑盒访问权限，任何寻找 $varepsilon$-近似驻点的算法，其查询次数在 $1/varepsilon$ 或 $d$ 上必须是指数级的。

原文摘要 · Abstract (English)

We study the query complexity of min-max optimization of a nonconvex-nonconcave function $f$ over $[0,1]^d \times [0,1]^d$. We show that, given oracle access to $f$ and to its gradient $\nabla f$, any algorithm that finds an $\varepsilon$-approximate stationary point must make a number of queries that is exponential in $1/\varepsilon$ or $d$.

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。