The objectives of this technical report is to provide additional results on the generalized conditional gradient methods introduced by [BLM05]. Indeed , when the objective function is smooth, we provide a novel certificate of optimality and we show that the algorithm has a linear convergence rate. Applications of this algorithm are also discussed.
Finally our approach is also closely related to projected gradient descent and its spectral variant @cite_21 . As discussed more in detail in section , when @math is an euclidean distance, the solving problem boils down to a projection onto the convex @math . In practice the method is more general since it can be used for any problem as long as problem can be efficiently solved.
@cite_21
2301983558
We consider the fundamental problem in non-convex optimization of efficiently reaching a stationary point. In contrast to the convex case, in the long history of this basic problem, the only known theoretical results on first-order non-convex optimization remain to be full gradient descent that converges in @math iterations for smooth objectives, and stochastic gradient descent that converges in @math iterations for objectives that are sum of smooth functions. We provide the first improvement in this line of research. Our result is based on the variance reduction trick recently introduced to convex optimization, as well as a brand new analysis of variance reduction that is suitable for non-convex optimization. For objectives that are sum of smooth functions, our first-order minibatch stochastic method converges with an @math rate, and is faster than full gradient descent by @math . We demonstrate the effectiveness of our methods on empirical risk minimizations with non-convex loss functions and training neural nets.