| Abstract: | We consider the regularized empirical risk minimization (ERM) of linear predictors, which arises in a variety of problems in machine learning and statistics. After reformulating the original ERM as a bilinear saddle-point problem, we can apply stochastic primal–dual methods to solve it. Sampling the primal or dual coordinates with a fixed nonuniform distribution is usually employed to accelerate the convergence of the algorithm, but such a strategy only exploits the global information of the objective function. To capture its local structures, we propose an adaptive importance sampling strategy that chooses the coordinates based on delicately designed nonuniform and nonstationary distributions. When our adaptive coordinate sampling strategy is applied to the Stochastic Primal-Dual Coordinate (SPDC), we prove that the resulting algorithm enjoys linear convergence. Moreover, we show that the ideal form of our adaptive sampling exhibits strictly sharper convergence rate under certain conditions compared with the vanilla SPDC. We also extend our sampling strategy to other algorithms including Doubly Stochastic Primal-Dual Coordinate (DSPDC) and Stochastic Primal-Dual with O(1) per-iteration cost and Variance Reduction (SPD1-VR), where both primal and dual coordinates are randomly sampled. Our experiment results show that the proposed strategy significantly improves the convergence performance of the methods when compared with existing sampling strategies. |
