A Parameter-Free Conditional Gradient Method for Composite Minimization under Hölder Condition
Masaru Ito, Zhaosong Lu, Chuan He; 24(166):1−34, 2023.
Abstract
This paper addresses a composite optimization problem that involves minimizing the sum of a weakly smooth function and a convex function, where the domain is either bounded or has a uniformly convex structure. The authors introduce a parameter-dependent conditional gradient method for solving this problem, which requires prior knowledge of the parameters associated with the Hölder continuity of the gradient of the weakly smooth function. The convergence rate of this method is established. However, since these parameters may be unknown or overly conservative, the implementation of this method may encounter issues or result in slow convergence. To overcome this limitation, a parameter-free conditional gradient method is proposed. This method determines the step size using a constructive local quadratic upper approximation and an adaptive line search scheme, without relying on any problem parameter. It is shown that the parameter-free method achieves the same convergence rate as the parameter-dependent method. Preliminary experiments are conducted to demonstrate the superior performance of the parameter-free conditional gradient method compared to methods with other step size rules.
[abs]