Spotlight Talk
in
Workshop: Order up! The Benefits of Higher-Order Optimization in Machine Learning
Quartic Polynomial Sub-problem Solutions in Tensor Methods for Nonconvex Optimization
Wenqi Zhu
Abstract:
There has been growing interest in high-order tensor methods for nonconvex optimization in machine learning as these methods provide better/optimal worst-case evaluation complexity, stability to parameter tuning, and robustness to problem conditioning. The well-known th-order adaptive regularization (AR) method relies crucially on repeatedly minimising a nonconvex multivariate Taylor-based polynomial sub-problem. It remains an open question to find efficient techniques to minimise such a sub-problem for .In this paper, we propose a second-order method (SQO) for the AR (AR with ) sub-problem. SQO approximates the special-structure quartic polynomial sub-problem from above and below by using second-order models that can be minimised efficiently and globally.We prove that SQO finds a local minimiser of a quartic polynomial, but in practice, due to its construction, it can find a much lower minimum than cubic regularization approaches. This encourages us to continue our quest for algorithmic techniques that find approximately global solutions for such polynomials.
Chat is not available.