Adaptive Proximal Methods for Weakly Convex Optimization with Unknown Parameter: Deterministic and Stochastic Guarantees
This work provides the first one-trial adaptive proximal method for weakly convex optimization with unknown parameter, addressing a practical bottleneck in nonsmooth nonconvex learning and signal recovery.
The paper proposes an adaptive proximal algorithm (APS) for minimizing ρ-weakly convex functions without knowing ρ, achieving O(ε^{-2}) iteration complexity for both deterministic and stochastic settings, even under weak oracle assumptions.
Many nonsmooth, nonconvex objectives in learning and signal recovery are $ρ$-weakly convex. We minimize such a function in deterministic and stochastic settings when the weak-convexity parameter $ρ$ is unknown. The objective is not required to be globally Lipschitz continuous or smooth. We propose the Adaptive Prox-Guided Scheme (APS), a one-trial proximal algorithm that adapts the proximal parameter online and bidirectionally through a descent test, allowing it to exploit favorable local structure. In the deterministic setting, APS obtains an $O(\varepsilon^{-2})$ iteration complexity for producing an $\varepsilon$-subgradient stationary point. In the stochastic setting, APS achieves a high-probability $O(\varepsilon^{-2})$ iteration bound for driving the Moreau-envelope gradient below $\varepsilon$. This result holds under deliberately weak oracle assumptions: the function-difference estimates may be biased and heavy-tailed, and the stochastic proximal oracle need only be sufficiently accurate with constant probability when the proximal parameter lies below $1/(2ρ)$ (unknown to the algorithm), and can be arbitrary otherwise.