The computational complexity of finding stationary points in non-convex optimization
<p>Finding approximate stationary points, i.e., points where the gradient is approximately zero, of non-convex but smooth objective functions f over unrestricted d-dimensional domains is one of the most fundamental problems in classical non-convex optimization. Nevertheless, the computational...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Springer
2024
|
| _version_ | 1811141258714808320 |
|---|---|
| author | Hollender, A Zampetakis, M |
| author_facet | Hollender, A Zampetakis, M |
| author_sort | Hollender, A |
| collection | OXFORD |
| description | <p>Finding approximate stationary points, i.e., points where the gradient is approximately zero, of non-convex but smooth objective functions f over unrestricted d-dimensional domains is one of the most fundamental problems in classical non-convex optimization. Nevertheless, the computational and query complexity of this problem are still not well understood when the dimension d of the problem is independent of the approximation error. In this paper, we show the following computational and query complexity results:</p>
<ol>
<li>The problem of finding approximate stationary points over unrestricted domains is PLScomplete.</li>
<li>For d = 2, we provide a zero-order algorithm for finding ε-approximate stationary points that requires at most O(1/ε) value queries to the objective function.</li>
<li>We show that any algorithm needs at least Ω(1/ε) queries to the objective function and/or its gradient to find ε-approximate stationary points when d = 2. Combined with the above, this characterizes the query complexity of this problem to be Θ(1/ε).</li>
<li>For d = 2, we provide a zero-order algorithm for finding ε-KKT points in constrained optimization problems that requires at most O(1/ √ ε) value queries to the objective function. This closes the gap between the works of Bubeck and Mikulincer [2020] and Vavasis [1993] and characterizes the query complexity of this problem to be Θ(1/ √ ε).</li>
<li>Combining our results with the recent result of Fearnley et al. [2022], we show that finding approximate KKT points in constrained optimization is reducible to finding approximate stationary points in unconstrained optimization but the converse is impossible.</li>
</ol> |
| first_indexed | 2024-09-25T04:35:01Z |
| format | Journal article |
| id | oxford-uuid:6b2097c3-63c4-436d-a027-8878c31566b1 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-09-25T04:35:01Z |
| publishDate | 2024 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:6b2097c3-63c4-436d-a027-8878c31566b12024-09-13T12:04:02ZThe computational complexity of finding stationary points in non-convex optimizationJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:6b2097c3-63c4-436d-a027-8878c31566b1EnglishSymplectic ElementsSpringer2024Hollender, AZampetakis, M<p>Finding approximate stationary points, i.e., points where the gradient is approximately zero, of non-convex but smooth objective functions f over unrestricted d-dimensional domains is one of the most fundamental problems in classical non-convex optimization. Nevertheless, the computational and query complexity of this problem are still not well understood when the dimension d of the problem is independent of the approximation error. In this paper, we show the following computational and query complexity results:</p> <ol> <li>The problem of finding approximate stationary points over unrestricted domains is PLScomplete.</li> <li>For d = 2, we provide a zero-order algorithm for finding ε-approximate stationary points that requires at most O(1/ε) value queries to the objective function.</li> <li>We show that any algorithm needs at least Ω(1/ε) queries to the objective function and/or its gradient to find ε-approximate stationary points when d = 2. Combined with the above, this characterizes the query complexity of this problem to be Θ(1/ε).</li> <li>For d = 2, we provide a zero-order algorithm for finding ε-KKT points in constrained optimization problems that requires at most O(1/ √ ε) value queries to the objective function. This closes the gap between the works of Bubeck and Mikulincer [2020] and Vavasis [1993] and characterizes the query complexity of this problem to be Θ(1/ √ ε).</li> <li>Combining our results with the recent result of Fearnley et al. [2022], we show that finding approximate KKT points in constrained optimization is reducible to finding approximate stationary points in unconstrained optimization but the converse is impossible.</li> </ol> |
| spellingShingle | Hollender, A Zampetakis, M The computational complexity of finding stationary points in non-convex optimization |
| title | The computational complexity of finding stationary points in non-convex optimization |
| title_full | The computational complexity of finding stationary points in non-convex optimization |
| title_fullStr | The computational complexity of finding stationary points in non-convex optimization |
| title_full_unstemmed | The computational complexity of finding stationary points in non-convex optimization |
| title_short | The computational complexity of finding stationary points in non-convex optimization |
| title_sort | computational complexity of finding stationary points in non convex optimization |
| work_keys_str_mv | AT hollendera thecomputationalcomplexityoffindingstationarypointsinnonconvexoptimization AT zampetakism thecomputationalcomplexityoffindingstationarypointsinnonconvexoptimization AT hollendera computationalcomplexityoffindingstationarypointsinnonconvexoptimization AT zampetakism computationalcomplexityoffindingstationarypointsinnonconvexoptimization |