论文标题
在确定性非平滑优化中非概念性的成本
The cost of nonconvexity in deterministic nonsmooth optimization
论文作者
论文摘要
我们研究了非凸性对非平滑优化复杂性的影响，强调了诸如分段线性函数之类的目标，这可能不是弱凸。我们专注于独立的分析，稍微修改了Zhang等人的黑盒算法。 （2020）使用$ o（ε^{ - 4}）$调用$ o（ε^{ - 4}）$呼叫的任何方向区分Lipschitz物镜的$ε$ - 定位点呼叫与专门的子级别甲骨文和随机线路搜索。我们简单的黑盒确定性版本，对于任何一个差异目标，就可以实现$ o（ε^{ - 5}）$，对于弱凸情况，$ o（ε^{ - 4}）$。我们的复杂性结合取决于自然的非概念模量，这是相关的，有趣的是，在分布意义上理解了物镜的定向第二个衍生物的负部分。
We study the impact of nonconvexity on the complexity of nonsmooth optimization, emphasizing objectives such as piecewise linear functions, which may not be weakly convex. We focus on a dimension-independent analysis, slightly modifying a black-box algorithm of Zhang et al. (2020) that approximates an $ε$-stationary point of any directionally differentiable Lipschitz objective using $O(ε^{-4})$ calls to a specialized subgradient oracle and a randomized line search. Our simple black-box deterministic version, achieves $O(ε^{-5})$ for any difference-of-convex objective, and $O(ε^{-4})$ for the weakly convex case. Our complexity bound depends on a natural nonconvexity modulus, related, intriguingly, to the negative part of directional second derivatives of the objective, understood in the distributional sense.
