HOUDINI: Escaping from Moderately Constrained Saddles
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.