论文标题
Houdini：逃离中等约束的马鞍
HOUDINI: Escaping from Moderately Constrained Saddles
论文作者
论文摘要
我们给出了第一个多项式时间算法，用于在适度的约束下从高维鞍点逃脱。给定对平滑函数的梯度访问$ f \ colon \ mathbb r^d \ to \ mathbb r $我们表明（嘈杂的）梯度下降方法可以在对数数量的不等式约束下从鞍点中逃脱。这构成了GE等人突破性工作的主要开放问题，这构成了第一个切实的进步（不依赖NP孔或更改定义仅考虑某些约束）。他对不受限制和平等约束的问题显示出类似的结果。我们的结果适用于常规和随机梯度下降。
We give the first polynomial time algorithms for escaping from high-dimensional saddle points under a moderate number of constraints. Given gradient access to a smooth function $f \colon \mathbb R^d \to \mathbb R$ we show that (noisy) gradient descent methods can escape from saddle points under a logarithmic number of inequality constraints. This constitutes the first tangible progress (without reliance on NP-oracles or altering the definitions to only account for certain constraints) on the main open question of the breakthrough work of Ge et al. who showed an analogous result for unconstrained and equality-constrained problems. Our results hold for both regular and stochastic gradient descent.
