{"id":"arxiv/2608.03246","url":"https://arxiv.org/abs/2608.03246","tags":["math.OC"],"score":0,"title":"Optimal Deterministic Oracle Complexity for Weakly Convex Optimization","domain":"math.OC","source":"arxiv","authors":["Jiajin Li","Siyu Pan"],"reviews":0,"subject":"math.OC","summary":"We study the oracle complexity of finding $ε$-stationary points of $ρ$-weakly convex and $G$-Lipschitz functions, where stationarity is measured by the gradient of the Moreau envelope. We consider a first-order oracle that returns both the function value and the full subdifferential at every query point. We prove that every deterministic first-order algorithm requires $ Ω({ρG^2Δ}/{ε^4})$ oracle queries whenever $Δ\\leq {G^2}/ρ$, where $f(\\bz)-\\inf f \\leq Δ$. This lower bound matches the best known deterministic and stochastic first-order upper bounds, up to universal constants, and…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-04","reactions":{}}