SGD with Coordinate Sampling: Theory and Practice
This addresses the challenge of optimizing non-convex functions in large-scale machine learning, though it appears incremental as it builds on existing SGD methods with a novel sampling strategy.
The paper tackled the problem of improving stochastic gradient descent by developing a framework for adaptive coordinate sampling to leverage data structure, resulting in the MUSKETEER algorithm that shows effectiveness in large-scale problems with established convergence and non-asymptotic bounds.
While classical forms of stochastic gradient descent algorithm treat the different coordinates in the same way, a framework allowing for adaptive (non uniform) coordinate sampling is developed to leverage structure in data. In a non-convex setting and including zeroth order gradient estimate, almost sure convergence as well as non-asymptotic bounds are established. Within the proposed framework, we develop an algorithm, MUSKETEER, based on a reinforcement strategy: after collecting information on the noisy gradients, it samples the most promising coordinate (all for one); then it moves along the one direction yielding an important decrease of the objective (one for all). Numerical experiments on both synthetic and real data examples confirm the effectiveness of MUSKETEER in large scale problems.