Exponential Deterministic Query Complexity of Goldstein Stationarity
We study the deterministic query complexity of finding approximate Goldstein stationary points of globally Lipschitz functions that may be nonsmooth and nonconvex. Under prescribed bounds on the Lipschitz constant and on the difference between the initial function value and the infimum, we prove a lower bound on the worst-case number of oracle calls that is exponential in the dimension at fixed sufficiently small accuracy parameters. The result holds for a local oracle and gives explicit dependence on the accuracy parameters. A complementary deterministic algorithm using only function values…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.38082
curl -X POST /api/v1/records/arxiv/2609.38082/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.38082/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'