Timezone: »

 
Spotlight
On the Finite-Time Complexity and Practical Computation of Approximate Stationarity Concepts of Lipschitz Functions
Lai Tian · Kaiwen Zhou · Anthony Man-Cho So

Tue Jul 19 01:50 PM -- 01:55 PM (PDT) @ Room 310
in Theory »
We report a practical finite-time algorithmic scheme to compute approximately stationary points for nonconvex nonsmooth Lipschitz functions. In particular, we are interested in two kinds of approximate stationarity notions for nonconvex nonsmooth problems, i.e., Goldstein approximate stationarity (GAS) and near-approximate stationarity (NAS). For GAS, our scheme removes the unrealistic subgradient selection oracle assumption in (Zhang et al., 2020, Assumption 1) and computes GAS with the same finite-time complexity. For NAS, Davis & Drusvyatskiy (2019) showed that $\rho$-weakly convex functions admit finite-time computation, while Tian & So (2021) provided the matching impossibility results of dimension-free finite-time complexity for first-order methods. Complement to these developments, in this paper, we isolate a new class of functions that could be Clarke irregular (and thus not weakly convex anymore) and show that our new algorithmic scheme can compute NAS points for functions in that class within finite time. To demonstrate the wide applicability of our new theoretical framework, we show that $\rho$-margin SVM, $1$-layer, and $2$-layer ReLU neural networks, all being Clarke irregular, satisfy our new conditions.
Keywords: OPT: First-order · OPT: Non-Convex · T: Optimization

Author Information

Lai Tian (The Chinese University of Hong Kong)
Kaiwen Zhou (The Chinese University of Hong Kong)
Anthony Man-Cho So (The Chinese University of Hong Kong)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors