In this paper we propose a unified two-phase scheme to accelerate any high-order regularized tensor approximation approach on the smooth part of a composite convex optimization model. The proposed scheme has the advantage of not needing to assume any prior knowledge of the Lipschitz constants for the gradient, the Hessian and or high-order derivatives. This is achieved by tuning the parameters used in the algorithm in its process of progression, which can be viewed as a relaxation over the existing algorithms in the literature. Under the assumption that the sub-problems can be solved approximately, we establish the overall iteration complexity bounds for three specific algorithms to obtain an @math -optimal solution. In general, we show that the adaptive high-order method has an iteration bound of @math if the first @math -th order derivative information is used in the approximation, which has the same iteration complexity as in (Nesterov, 2018) where the Lipschitz constants are assumed to be known and subproblems are assumed to be solved exactly. Thus, our results answer an open problem raised by Nesterov on adaptive strategies for high-order accelerated methods. Specifically, we show that the gradient method achieves an iteration complexity in the order of @math , which is known to be best possible, while the adaptive cubic regularization methods with the exact inexact Hessian matrix both achieve an iteration complexity in the order of @math , which matches that of the original accelerated cubic regularization method presented in assuming the availability of the exact Hessian information and the Lipschitz constants, and the global solution of the sub-problems.
 A general, inexact, efficient proximal quasi-Newton algorithm for composite optimization problems has been proposed by Scheinberg and Tang (Math Program 160:495–529, 2016) and a sublinear global convergence rate has been established. In this paper, we analyze the global convergence rate of this method, in the both exact and inexact settings, in the case when the objective function is strongly convex. We also investigate a practical variant of this method by establishing a simple stopping criterion for the subproblem optimization. Furthermore, we consider an accelerated variant, based on FISTA of Beck and Teboulle (SIAM 2:183–202, 2009), to the proximal quasi-Newton algorithm. (SIAM 22:1042–1064, 2012) considered a similar accelerated method, where the convergence rate analysis relies on very strong impractical assumptions on Hessian estimates. We present a modified analysis while relaxing these assumptions and perform a numerical comparison of the accelerated proximal quasi-Newton algorithm and the regular one. Our analysis and computational results show that acceleration may not bring any benefit in the quasi-Newton setting. In this paper, we study accelerated regularized Newton methods for minimizing objectives formed as a sum of two functions: one is convex and twice differentiable with Holder-continuous Hessian, and... We introduce a framework for quasi-Newton forward--backward splitting algorithms (proximal quasi-Newton methods) with a metric induced by diagonal @math rank- @math symmetric positive definite matrices. This special type of metric allows for a highly efficient evaluation of the proximal mapping. The key to this efficiency is a general proximal calculus in the new metric. By using duality, formulas are derived that relate the proximal mapping in a rank- @math modified metric to the original metric. We also describe efficient implementations of the proximity calculation for a large class of functions; the implementations exploit the piece-wise linear nature of the dual problem. Then, we apply these results to acceleration of composite convex minimization problems, which leads to elegant quasi-Newton methods for which we prove convergence. The algorithm is tested on several numerical examples and compared to a comprehensive list of alternatives in the literature. Our quasi-Newton splitting algorithm with the prescribed metric compares favorably against state-of-the-art. The algorithm has extensive applications including signal processing, sparse recovery, machine learning and classification to name a few. We generalize Newton-type methods for minimizing smooth functions to handle a sum of two convex functions: a smooth function and a nonsmooth function with a simple proximal mapping. We show that the resulting proximal Newton-type methods inherit the desirable convergence behavior of Newton-type methods for minimizing smooth functions, even when search directions are computed inexactly. Many popular methods tailored to problems arising in bioinformatics, signal processing, and statistical learning are special cases of proximal Newton-type methods, and our analysis yields new convergence results for some of these methods. Recently several methods were proposed for sparse optimization which make careful use of second-order information [10, 28, 16, 3] to improve local convergence rates. These methods construct a composite quadratic approximation using Hessian information, optimize this approximation using a first-order method, such as coordinate descent and employ a line search to ensure sufficient descent. Here we propose a general framework, which includes slightly modified versions of existing algorithms and also a new algorithm, which uses limited memory BFGS Hessian approximations, and provide a novel global convergence rate analysis, which covers methods that solve subproblems via coordinate descent.