Fast minimization of structured convex quartics

MaRDI QIDQ6311637zbMATH OpenFDO

Authors Brian Bullins

Publication date 26 December 2018

Abstract: We propose faster methods for unconstrained optimization of emph{structured convex quartics}, which are convex functions of the form �egin{equation*} f(x) = c^ op x + x^ op mathbf{G} x + mathbf{T}[x,x,x] + frac{1}{24} mathopen| mathbf{A} x mathclose|_4^4 end{equation*} for $cinmathbb{R}^d$, $mathbfGinmathbb{R}^{dimesd}$, $mathbfTinmathbb{R}^{dimesdimesd}$, and $mathbfAinmathbb{R}^{nimesd}$ such that $mathbf{A}^{o}pmathbfAsucc0$. In particular, we show how to achieve an $epsilon$-optimal minimizer for such functions with only $O(n^{1/5}lo{g}^{O(1)}(mathcalZ/epsilon))$ calls to a gradient oracle and linear system solver, where $mathcalZ$ is a problem-dependent parameter. Our work extends recent ideas on efficient tensor methods and higher-order acceleration techniques to develop a descent method for optimizing the relevant quartic functions. As a natural consequence of our method, we achieve an overall cost of $O(n^{1/5}lo{g}^{O(1)}(mathcalZ/epsilon))$ calls to a gradient oracle and (sparse) linear system solver for the problem of $el{l}_4$-regression when $mathbf{A}^{o}pmathbfAsucc0$, providing additional insight into what may be achieved for general $el{l}_p$-regression. Our results show the benefit of combining efficient higher-order methods with recent acceleration techniques for improving convergence rates in fundamental convex optimization problems.

This page was built for publication: Fast minimization of structured convex quartics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6311637)