Survey Descent: A Multipoint Generalization of Gradient Descent for Nonsmooth Optimization
针对非光滑优化问题，提出一种多点梯度下降迭代方法，在目标函数为光滑函数最大值时证明线性收敛，实验表明更广泛适用性。
.For strongly convex objectives that are smooth, the classical theory of gradient descent ensures linear convergence relative to the number of gradient evaluations. An analogous nonsmooth theory is challenging. Even when the objective is smooth at every iterate, the corresponding local models are unstable, and the number of cutting planes invoked by traditional remedies is difficult to bound, leading to convergence guarantees that are sublinear relative to the cumulative number of gradient evaluations. We instead propose a multipoint generalization of the gradient descent iteration for local optimization. While our iteration was designed with general objectives in mind, we are motivated by a "max-of-smooth" model that captures the subdifferential dimension at optimality. We prove linear convergence when the objective is itself max-of-smooth, and experiments suggest a more general phenomenon.Keywordsfirst-order methodnonsmooth optimizationgradient descentlocal linear convergenceMSC codes90C2565K0549M37