RECORD
Minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity
Optimization and Control · Submitted 27 Feb 2019
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim It is shown that this algorithm needs at most $O(|\log(\epsilon)|\,\epsilon^{-2})$ evaluations of the problem's functions and their derivatives for finding an $\epsilon$-approximate first-order stationary point.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
An adaptive regularization algorithm using inexact function and derivatives evaluations is proposed for the solution of composite nonsmooth nonconvex optimization. It is shown that this algorithm needs at most $O(|\log(\epsilon)|\,\epsilon^{-2})$ evaluations of the problem's functions and their derivatives for finding an $\epsilon$-approximate first-order stationary point. This complexity bound therefore generalizes that provided by [Bellavia, Gurioli, Morini and Toint, 2018] for inexact methods for smooth nonconvex problems, and is within a factor $|\log(\epsilon)|$ of the optimal bound known for smooth and nonsmooth nonconvex minimization with exact evaluations. A practically more restrictive variant of the algorithm with worst-case complexity $O(|\log(\epsilon)|+\epsilon^{-2})$ is also presented.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | An adaptive regularization algorithm using inexact function and derivatives evaluations is proposed for the solution of composite nonsmooth nonconvex optimization. | contribution 0.58 | 0.91 | 0.10 | asserted 0.99 |
| s1 | It is shown that this algorithm needs at most $O(|\log(\epsilon)|\,\epsilon^{-2})$ evaluations of the problem's functions and their derivatives for finding an $\epsilon$-approximate first-order stationary point. | result 0.99 | 0.93 | 0.73 | asserted 1.00 |
| s2 | This complexity bound therefore generalizes that provided by [Bellavia, Gurioli, Morini and Toint, 2018] for inexact methods for smooth nonconvex problems, and is within a factor $|\log(\epsilon)|$ of the optimal bound known for smooth and nonsmooth nonconvex minimization with exact evaluations. | interpretation 0.95 | 0.63 | 0.31 | asserted 1.00 |
| s3 | A practically more restrictive variant of the algorithm with worst-case complexity $O(|\log(\epsilon)|+\epsilon^{-2})$ is also presented. | contribution 0.80 | 0.93 | 0.06 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
An adaptive regularization algorithm using inexact function and derivatives evaluations is proposed for the solution of composite nonsmooth nonconvex optimization. It is shown that this algorithm needs at most $O(|\log(\epsilon)|\,\epsilon^{-2})$ evaluations of the problem's functions and their derivatives for finding an $\epsilon$-approximate first-order stationary point. This complexity bound therefore generalizes that provided by [Bellavia, Gurioli, Morini and Toint, 2018] for inexact methods for smooth nonconvex problems, and is within a factor $|\log(\epsilon)|$ of the optimal bound known for smooth and nonsmooth nonconvex minimization with exact evaluations. A practically more restrictive variant of the algorithm with worst-case complexity $O(|\log(\epsilon)|+\epsilon^{-2})$ is also presented.
Human review
How the literature uses it
3 arXiv papers cite this in 3 sentences
Papers citing it · 2 sentences without a confident label
Cites it as background 1 paper
-
In recent years there have been a surge of research interest in nonconvex optimization (see, for instance, [ref] ).
An Adaptive High Order Method for Finding Third-Order Critical Points of Nonconvex Optimization · Introduction · 1.00
What it cites · 16 sentences without a confident label
Builds on 1 paper
-
It also generalizes the bound derived in [ref] to the composite nonsmooth case.
Adaptive Regularization Algorithms with Inexact Evaluations for Nonconvex Optimization · Introduction · 1.00
Uses the method or tool of 1 paper
-
step1-l(Inspired by [ref] ) If the ARLDA algorithm terminates, then first-order ϕ_k ≤ϵand $x_k$ is a first-order approximate necessary minimizer.
Adaptive Regularization Algorithms with Inexact Evaluations for Nonconvex Optimization · Introduction · 0.89
Compares with 2 papers
-
If, as is usual in evaluation complexity analysis, one focuses on the maximum number of evaluations expressed as the order in $ϵ$, the bound of Theorem [ref] may be simplified to in-order O( |log(ϵ)| ϵ^-2 ) evaluations, which is identical in order to the bound obtained for the inexact first-order regularization method AR1DA in [ref] .
Adaptive Regularization Algorithms with Inexact Evaluations for Nonconvex Optimization · Introduction · 1.00
-
This complexity bound is within a factor $|log(ϵ)|$ of the known optimal bound for first-order methods using exact derivatives for smooth [ref] or nonsmooth composite [ref] problems.
Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints · Introduction · 1.00
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.