Bound-Guided Randomized Block Coordinate Descent for Group-Sparse Models

Many statistical models are fit by solving an optimization problem whose answer is mostly zeros. A sparse group lasso model is one example: it zeroes out whole groups of features and individual features within groups. Block coordinate descent, which updates one group of variables at a time, is the standard solver for these models. Its randomized form picks the next group uniformly at random. That choice is simple and backed by clean theory, but on a problem where 99% of groups are zero at the solution, it spends nearly all of its iterations computing an update only to find the group should stay at zero. The fastest exact solvers for these models avoid this waste with cheap upper bounds that certify "this group stays zero" without running the expensive check. However, those bounds were derived for fixed cyclic sweeps and for squared loss only.

This note proposes a single mechanism that serves two purposes in randomized block coordinate descent. It certifies which zero groups can be skipped safely, and it decides how often each remaining group is sampled. The key observation is that every group's bound can be written as a fixed per-group number plus a per-group constant times one shared scalar: the distance the solver's residual vector has drifted since the last exact refresh. Because the drift is shared, it can be updated in time proportional to the nonzeros touched by each update. Skipping and nonuniform sampling then cost $O(\log B)$ per draw over $B$ groups, with no Gram matrix and no restriction to squared loss. The method aims to keep the exact optimum and the "never worse than uniform" property of randomized descent, while approaching the efficiency of greedy group selection.

Core Claim

Consider minimizing $F(\beta)=\sum_i \ell(y_i, x_i^\top\beta)+\lambda_1\|\beta\|_1+\lambda_2\sum_g w_g\|\beta_g\|_2$ by randomized block coordinate descent. Here $\beta_g$ is the coefficient block for group $g$, $X_g$ is the matching column block of the data matrix, and $w_g$ is the group weight. Write $r$ for the derivative of the loss with respect to the predictions. For squared loss this is the residual; for logistic loss it is $\sigma(X\beta)-y$. Every coordinate descent solver already maintains $r$.

A group that sits at zero stays at zero exactly when $v_g=\|S_{\lambda_1}(X_g^\top r)\|_2\le\lambda_2 w_g$, where $S_{\lambda_1}$ is soft-thresholding. Checking this costs $O(n p_g)$, with $p_g$ the group size. Soft-thresholding never increases distances. So if $\bar r$ is a snapshot of $r$ from the last exact refresh, then

$$v_g \;\le\; a_g + c_g D,\qquad a_g=\|S_{\lambda_1}(X_g^\top \bar r)\|_2,\quad c_g=\|X_g\|_2,\quad D=\|r-\bar r\|_2 .$$

Here $a_g$ is computed at refresh time and $c_g$ is a spectral norm computed once. The drift $D$ is a single scalar updated incrementally. After a block update changes $r$ by a sparse vector $\delta$, the expansion $\|r+\delta-\bar r\|^2=\|r-\bar r\|^2+2\langle r-\bar r,\delta\rangle+\|\delta\|^2$ updates $D$ in time proportional to the nonzeros of $\delta$. The bound holds for any smooth loss, because $r$ is tracked exactly rather than approximated through a Hessian.

The proposal uses this bound in two ways. First, a zero group with $a_g+c_g D_{\max}<\lambda_2 w_g$, where $D_{\max}$ is the running maximum of the drift since the refresh, is certified to stay at zero and gets sampling probability exactly zero. Second, every uncertified zero group is sampled with probability proportional to its bound, $p_g\propto a_g+c_g D$, mixed with a fixed fraction of draws from the small pool of currently nonzero groups.

Sort the zero groups by their entry threshold $(\lambda_2 w_g-a_g)/c_g$. The uncertified set is then a prefix that grows as $D_{\max}$ grows. Prefix sums of $a_g$ and $c_g$ let us sample proportionally to $a_g+c_g D$ within that prefix by binary search. The method refreshes exactly, at cost $O(\mathrm{nnz}(X))$, when $D$ exceeds a set fraction of the smallest certification margin.

The claim to be tested has two parts. On group-sparse problems, this sampler should reach a given duality gap with several times fewer full group evaluations than uniform randomized block descent with dynamic safe screening. It should also match or beat the cyclic bound-skipping solver of Ida et al. on squared loss. And it should be the first exact skipping method of this kind for logistic sparse group lasso.

Relation to Prior Work

Two papers supply the method. Fast Block Coordinate Descent for Sparse Group Lasso, with its conference version Fast Sparse Group Lasso, derives an incremental $O(p_g)$ upper bound that lets cyclic block descent skip the zero-check safely. It reports skipping the check over 90% of the time on boston and cutting bottleneck evaluations from 114,100 to 3,168 on abalone. Its bound is built for squared loss and a deterministic sweep, and it is used only to skip, not to choose what to update. Our shared-drift bound applies to any smooth loss and is used to set sampling probabilities.

Approximate Steepest Coordinate Descent keeps per-coordinate gradient bounds, prunes coordinates whose upper bound is small, and samples uniformly within the survivors. It proves the rate lies between uniform and steepest descent, and its authors leave block extensions open. We borrow its "no-lose" style of argument. We differ in three ways: our bounds are block-level and penalty-aware, they share one drift scalar so we never touch every bound after each update, and we sample in proportion to the bound rather than uniformly over the survivors.

Several papers motivate the gap. Accelerating Greedy Coordinate Descent Methods measures $\gamma\approx 0.016$ on rcv1, meaning the greedy step is about 60 times more effective than an average step. That is direct evidence that uniform sampling leaves a lot of progress unused on real data. Doubly Greedy Primal-Dual Coordinate Descent exploits greedy selection with heuristic active sets that carry no safety guarantee. We keep randomization and certification instead. The research file also lists Richtárik and Takáč's complexity analysis of randomized block descent (On the Complexity Analysis of Randomized Block-Coordinate Descent Methods). It underpins the static, Lipschitz-weighted nonuniform sampling that serves as one of our ablations.

Other papers constrain the design. Dynamic Gap Safe rules (Ndiaye et al.) work with any solver that produces a primal-dual pair, including randomized ones. So "safe screening plus randomized block descent" is not new in itself, and our contribution has to come from the sampling and the between-screen skipping. Gap Safe certifies zeros at the optimum. Our bound certifies zeros under the current residual, which happens much earlier in a run but must be re-verified after each refresh.

Celer shows that dual extrapolation tightens safe regions but depends on cyclic order. That rules out pairing our randomized sampler with trajectory extrapolation. We therefore pair it with plain residual-rescaled Gap Safe screening and treat Celer as an external competitor.

When Cyclic Coordinate Descent Outperforms Randomized Coordinate Descent proves cyclic order is about 2 times faster than uniform random order on 2-cyclic and M-matrix quadratics. This result cuts directly against randomization. We test against it rather than set it aside.

Research Program

The first deliverable is the solver. It handles sparse group lasso with squared, logistic, and smoothed-hinge losses, and it treats the lasso as the special case of singleton groups. It includes the prefix-sum sampler, drift tracking, and refresh logic. Gap Safe screening runs at each refresh, so groups proven zero at the optimum leave the pool permanently.

The second deliverable is analysis. We will show three things. First, iterates converge to the exact minimizer: certified groups have zero current violation, so skipping them loses no progress, and refreshes keep every uncertified group's probability bounded away from zero. Second, the expected one-step decrease is at least that of uniform sampling over the uncertified set. Third, the decrease approaches that of a block Gauss-Southwell rule as $D/\min_g a_g\to 0$. Throughout, the analysis must deal with a sampling distribution that depends on past iterates, using the same supermartingale argument that ASCD uses.

The third deliverable is an accounting of where time goes: refresh cost, sampling cost, wasted draws, and full group evaluations. This shows which regimes the method helps in and which it does not.

Baselines

The naive reference is uniform randomized block coordinate descent. It runs in the same C++ code with the same block update and the same residual maintenance, and has no skipping or screening. Every speedup is measured against it in both wall-clock time and number of full $O(np_g)$ group evaluations.

The strongest existing exact method for squared-loss sparse group lasso is the cyclic fast block coordinate descent of Ida et al.. Its paper reports skipping the zero-check over 90% of the time on boston and reducing bottleneck executions on abalone from 114,100 to 3,168. No reported wall-clock result for this method was found on Lacuna. We will reimplement it in the same codebase, run it on the same polynomially expanded LIBSVM datasets with the same regularization path, and use the same convergence tolerance. To beat it, our method must reach duality gap $10^{-6}$ along a 100-value path in less total time, and it must evaluate no more groups than this baseline's reported 3,168 bottleneck executions on abalone, normalized to the same tolerance.

The strongest screening competitor is uniform randomized block descent combined with dynamic Gap Safe screening (Ndiaye et al.), refreshed on the same schedule as ours. This is the "obvious combination," and it isolates what our sampler adds beyond screening. For the lasso special case we add Celer. On Finance it reports solving nearly 3 times faster than BLITZ and reaching safe identification in 70 seconds versus 290 for standard Gap Safe. We will run Celer's public settings on the same machine.

For singleton-group logistic regression on rcv1 we include ASCD, which reports shrinking the active set to about 0.1% of coordinates. We compare our certified-set size and time against it.

Two ablations isolate the key ingredient. In the first, we keep the certification but sample uniformly over the uncertified set. This separates the value of skipping from the value of bound-proportional sampling. In the second, we drop certification and sample in proportion to the static $c_g$ alone, which recovers Lipschitz-style nonuniform sampling. This tests whether the dynamic term $a_g$ matters. All methods get identical hyperparameter search budgets, here only the refresh threshold and the active-pool mixing fraction, tuned on a held-out λ value.

Why not just…?

Why not just use cyclic order with Ida et al.'s bounds, given that cyclic can be provably faster? This is a real threat. On squared-loss sparse group lasso the cyclic solver may simply win. The cyclic-versus-random result (Gürbüzbalaban et al.) covers unregularized quadratics with special structure. Wright's survey (Coordinate Descent Algorithms) documents cyclic stalling on poorly conditioned problems. Neither addresses order effects once most blocks are inactive, which is our regime. We settle this by direct comparison, including on synthetic group designs built from 2-cyclic and M-matrix Hessians where cyclic order should be favored. If cyclic wins on squared loss, the contribution narrows to the loss generality of the shared-drift bound. We would then also report a cyclic variant that uses our bound, so the bound itself is evaluated separately from the sampling order.

Why not just run Gap Safe screening inside uniform randomized descent? Gap Safe certifies zeros only once the duality gap is small. Early in a run, and at small λ, most groups survive, and uniform sampling wastes draws on them. Celer's Finance comparison (70 versus 290 seconds for standard Gap Safe) shows how loose plain dual points can be. The certification-only ablation and this baseline together measure how much of the cost falls between screens. If bound-proportional sampling adds nothing there, the ablation will show it.

Why not just use greedy block selection with exact gradients? Exact Gauss-Southwell selection needs $X^\top r$ at every step, which costs as much as a full gradient. As Stich et al. and Lei et al. note, the greedy step pays off only with caching or heuristic active sets. Our method tries to capture most of the greedy gain measured by Lu et al. at logarithmic selection cost. We report the progress per step of exact greedy selection as an upper reference, which shows how close we get.

Why not just use a glmnet-style heuristic active set? Heuristics can wrongly drop groups that belong in the solution, and then they need full verification sweeps. Our certification is exact. We report final objectives and supports to confirm they match unskipped descent, as Ida et al. do. We also count the verification sweeps the heuristic needs.

Proposed Experiments

The main benchmark follows Ida et al.: sparse group lasso on abalone, cpusmall, boston, bodyfat, eunite2001, and pyrim, each expanded with second-order polynomial features into hundreds of groups. We solve a 100-value regularization path with warm starts and report time and group evaluations to duality gap $10^{-6}$. We repeat with logistic loss on binarized targets, where no exact skipping baseline exists. The lasso special case runs on Finance (E2006-tfidf) and leukemia against Celer. Singleton-group sparse logistic regression runs on rcv1 and gisette against ASCD and uniform descent.

The first decisive check is a group-sparsity sweep on synthetic data. We vary the fraction of active groups from 1% to 50%. The speedup over uniform sampling should grow roughly in proportion to the fraction of inactive groups and disappear as the problem becomes dense. If it does not disappear, the gain is coming from something other than skipping, and we will diagnose it.

The second decisive check uses the adversarial cyclic-favoring designs described above.

The third decisive check measures bound tightness. We log the ratio of true violation $v_g$ to its bound across refreshes. This tells us whether the single shared drift scalar is too loose on correlated designs, where per-group drift could be needed. That case would cost $O(B)$ per update and would limit the method's reach.

Every run also verifies that the final coefficients match those of plain block descent, to solver tolerance.