Timezone: »

 
Poster
Adaptive Negative Curvature Descent with Applications in Non-convex Optimization
Mingrui Liu · Zhe Li · Xiaoyu Wang · Jinfeng Yi · Tianbao Yang

Thu Dec 06 07:45 AM -- 09:45 AM (PST) @ Room 210 #81
in Thu Poster Session A »
Negative curvature descent (NCD) method has been utilized to design deterministic or stochastic algorithms for non-convex optimization aiming at finding second-order stationary points or local minima. In existing studies, NCD needs to approximate the smallest eigen-value of the Hessian matrix with a sufficient precision (e.g., $\epsilon_2\ll 1$) in order to achieve a sufficiently accurate second-order stationary solution (i.e., $\lambda_{\min}(\nabla^2 f(\x))\geq -\epsilon_2)$. One issue with this approach is that the target precision $\epsilon_2$ is usually set to be very small in order to find a high quality solution, which increases the complexity for computing a negative curvature. To address this issue, we propose an adaptive NCD to allow for an adaptive error dependent on the current gradient's magnitude in approximating the smallest eigen-value of the Hessian, and to encourage competition between a noisy NCD step and gradient descent step. We consider the applications of the proposed adaptive NCD for both deterministic and stochastic non-convex optimization, and demonstrate that it can help reduce the the overall complexity in computing the negative curvatures during the course of optimization without sacrificing the iteration complexity.
Keywords: Optimization · Non-Convex Optimization
[ Paper] 

Author Information

Mingrui Liu (The University of Iowa)
Zhe Li (Apple)
Xiaoyu Wang (NEC Labs America)
Jinfeng Yi (JD AI Research)
Tianbao Yang (The University of Iowa)

More from the Same Authors