Accelerated Variance Reduced Block Coordinate Descent
This work addresses the big data optimization problem for machine learning practitioners by providing a fast and efficient algorithm, though it appears incremental as it builds on existing variance-reduced and accelerated methods.
The paper tackles the challenge of efficiently solving optimization problems with large sample sizes and ultra-high dimensions by proposing a method that achieves an accelerated convergence rate of O(1/k^2). Empirical results on datasets with over one million features demonstrate its effectiveness.
Algorithms with fast convergence, small number of data access, and low per-iteration complexity are particularly favorable in the big data era, due to the demand for obtaining \emph{highly accurate solutions} to problems with \emph{a large number of samples} in \emph{ultra-high} dimensional space. Existing algorithms lack at least one of these qualities, and thus are inefficient in handling such big data challenge. In this paper, we propose a method enjoying all these merits with an accelerated convergence rate $O(\frac{1}{k^2})$. Empirical studies on large scale datasets with more than one million features are conducted to show the effectiveness of our methods in practice.