A matrix-free line-search algorithm for nonconvex optimization |
| |
Authors: | W Zhou IG Akrotirianakis S Yektamaram JD Griffin |
| |
Affiliation: | 1. SAS Institute, Cary, NC, USA;2. Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA, USA |
| |
Abstract: | In this paper, we have developed a new algorithm for solving nonconvex large-scale problems. The new algorithm performs explicit matrix modifications adaptively, mimicing the implicit modifications used by trust-region methods. Thus, it shares the equivalent theoretical strength of trust-region approaches, without needing to accommodate an explicit step-size constraint. We show that the algorithm is well suited for solving very large-scale nonconvex problems whenever Hessian-vector products are available. The numerical results on the CUTEr problems demonstrate the effectiveness of this approach in the context of a line-search method for large-scale unconstrained nonconvex optimization. Moreover, applications in deep-learning problems further illustrate the usefulness of this algorithm. It does not share any of the prohibitive traits of popular matrix-free algorithms such as truncated conjugate gradient (CG) due to the difficult nature of deep-learning problems. Thus the proposed algorithm serves to bridge the gap between the needs of data-mining community and existing state-of-the-art approaches embraced foremost by the optimization community. Moreover, the proposed approach can be realized with minimal modification to the CG algorithm itself with negligible storage and computational overhead. |
| |
Keywords: | nonlinear programming nonconvex large-scale problems trust-region methods conjugate gradient method Hessian-free methods machine learning |
|
|