- | ||||
|
![]()
|
Tensor Methods for Finding Approximate Stationary Points of Convex Functions
Geovani Grapiglia (grapiglia Abstract: In this paper we consider the problem of finding \epsilon-approximate stationary points of convex functions that are p-times differentiable with \nu-Hölder continuous pth derivatives. We present tensor methods with and without acceleration. Specifically, we show that the non-accelerated schemes take at most O(\epsilon^{-1/(p+\nu-1)}) iterations to reduce the norm of the gradient of the objective below a given \epsilon\in (0,1). For accelerated tensor schemes we establish improved complexity bounds of O(\epsilon^{-(p+\nu)/[(p+\nu-1)(p+\nu+1)]}) and O(|\log(\epsilon)|\epsilon^{-1/(p+\nu)}), when the Hölder parameter \nu\in [0,1] is known. For the case in which \nu is unknown, we obtain a bound of O(\epsilon^{-(p+1)/[(p+\nu-1)(p+2)]}) for a universal accelerated scheme. Finally, we also obtain a lower complexity bound of O(\epsilon^{-2/[3(p+\nu)-2]}) for finding \epsilon-approximate stationary points using p-order tensor methods. Keywords: unconstrained minimization, high-order methods, tensor methods, Hölder condition, worst-case complexity Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Optimization Methods and Software (2020), DOI: 10.1080/10556788.2020.1818082 Download: [PDF] Entry Submitted: 07/13/2019 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |