solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看2780次
Efficiently testing local optimality and escaping saddles for ReLU networks. (arXiv:1809.10858v1 [math.OC])
来源于:arXiv
We provide a theoretical algorithm for checking local optimality and escaping
saddles at nondifferentiable points of empirical risks of two-layer ReLU
networks. Our algorithm receives any parameter value and returns: local
minimum, second-order stationary point, or a strict descent direction. The
presence of M data points on the nondifferentiability of the ReLU divides the
parameter space into at most 2^M regions, which makes analysis difficult. By
exploiting polyhedral geometry, we reduce the total computation down to one
convex quadratic program (QP) for each hidden node, O(M) (in)equality tests,
and one (or a few) nonconvex QP. For the last QP, we show that our specific
problem can be solved efficiently, in spite of nonconvexity. In the benign
case, we solve one equality constrained QP, and we prove that projected
gradient descent solves it exponentially fast. In the bad case, we have to
solve a few more inequality constrained QPs, but we prove that the time
complexity is exponentia 查看全文>>