Inexact high-order proximal-point methods with auxiliary search procedure
(2020) , 23 pages
Files
coredp2020_10web.pdf
Open Access - Adobe PDF
- 2.13 MB
Details
- Authors
- Abstract
- In this paper, we complement the framework of Bi-Level Unconstrained Minimization (BLUM)[21] by a new pth-order proximal-point method convergent as O(k^{−(3p+1)/2}), where k is the iteration counter. As compared with [21], we replace the auxiliary line search by a convex segment search. This allows us to bound its complexity of by a logarithm of the desired accuracy. Each step in this search needs an approximate computation of the proximal-point operator. Under assumption on boundedness of (p+1)st derivative of the objective function, this can be done by one step of the pth-order augmented tensor method. In this way, for p = 2, we get a new second-order method with the rate of convergence O(^{k−7/2}) and logarithmic complexity of the auxiliary search at each iteration. Another possibility is to compute the proximal-point operator by lower-order minimization methods. As an example, for p = 3, we consider the upper-level process convergent as O^{(k−5)}. Assuming the boundedness of fourth derivative, an appropriate approximation of the proximal-point operator can be computed by a second-order method in logarithmic number of iterations. This combination gives a second-order scheme with much better complexity than the existing theoretical limits.
- Affiliations
Citations
Nesterov, Y. (2020). Inexact high-order proximal-point methods with auxiliary search procedure (CORE Discussion Papers 2020/10). https://hdl.handle.net/2078.5/169289