An Adaptive Proximal Framework for Weakly Convex Optimization with Unknown Parameter: Deterministic and Heavy-Tailed Stochastic Guarantees

Many nonsmooth, nonconvex objectives in learning and signal recovery are $\rho$-weakly convex. We minimize such a function in deterministic and stochastic settings when the weak-convexity parameter $\rho$ is unknown. The objective is not required to be globally Lipschitz continuous or smooth. We propose the Adaptive Prox-Guided Scheme (APS), a single-trial adaptive proximal framework that adapts the proximal parameter online and bidirectionally through a descent test, allowing it to exploit favorable local structure. The framework covers adaptive proximal-point, prox-linear, and proximal-gradient methods from a model-based viewpoint. In the deterministic proximal setting, APS obtains an $O({\epsilon }^{-2})$ iteration complexity for producing an $\epsilon$-subgradient stationary point. In the stochastic setting, APS achieves a high-probability $O({\epsilon }^{-2})$ iteration bound for driving the Moreau-envelope gradient below $\epsilon$. This result holds under deliberately weak oracle assumptions: the function-difference estimates may be biased and heavy-tailed, and the stochastic candidate oracle need only be sufficiently accurate with constant probability when the proximal parameter is small, and can be arbitrary otherwise.