Many machine-learning problems are solved by optimizers whose answers should contain exact zeros. Examples include lasso regression, where most coefficients should vanish, ℓ1-regularized support vector machines, and sparse signal recovery. Several optimizers can solve these problems: plain and accelerated proximal gradient (ISTA, FISTA), coordinate descent, dual-averaging methods, proximal-point methods and primal-dual methods. They behave very differently from one problem to the next. The field of algorithm selection, which learns to pick the best solver for each problem instance from cheap descriptive features, has shown large gains in SAT, routing and black-box optimization. It has essentially never been applied to these structured, white-box problems.
Copying it over would also measure the wrong thing. Algorithm selectors are trained to minimize runtime or final objective error. For sparse problems, the objective value and the correctness of the zero pattern come apart. A method can reach a small objective gap early and still have the wrong set of nonzero coordinates (the support) in its current iterate, and averaging iterates actively smears supports together. This note proposes an algorithm selector whose target is time until the solver's current iterate settles on the correct support. Its inputs are features read from a few iterations of a cheap probe solver, whose last iterate then warm-starts whichever solver is chosen, so the probe's work is not thrown away.
Core Claim
The claim has three parts, and the first is a measurable fact that could turn out false. First, on realistic lasso, elastic-net and ℓ1-SVM instances, the solver that reaches a fixed objective accuracy first often differs from the solver that first identifies the correct support. If this disagreement is rare, structure-aware selection adds nothing over runtime-based selection, and the project should stop at that finding. Second, the dynamics of a short probe predict which solver will identify the support first better than static instance statistics do. The probe dynamics we have in mind are how often coordinates enter and leave the support, and how many coordinates sit near the thresholding boundary. Third, because every solver in the portfolio converges from an arbitrary starting point and its guarantee concerns its own last iterate, handing the probe's last iterate to the selected solver leaves its convergence guarantee intact. The cost is only the initial distance to the solution. This gives a principled "probe then commit" scheme rather than a heuristic switch.
What is new is the selection target and the probe features. Nobody has proposed a portfolio of sparse solvers chosen per instance. Even if someone did, standard practice would label instances by runtime or by penalized average runtime (PAR10, which charges unsolved runs ten times the cutoff). We argue that this label is wrong for problems whose purpose is the zero pattern.
Grounding in Prior Work
The motivation comes from the sparsity-preserving optimization literature, which shows that averaging iterates destroys exact zeros and that last-iterate methods recover structure better. Optimal Regularized Dual Averaging Methods for Stochastic Optimization extracts the primal point by applying a proximal map to accumulated gradients rather than averaging iterates. On synthetic sparse regression it reports a support-recovery F1 of 0.92, against 0.67–0.83 for averaging-based competitors. This is direct evidence that solver choice changes structural quality, not only speed.
Three other lines of work supply portfolio members with last-iterate guarantees, and each wins in a different regime:
- An adaptive primal-dual framework for nonsmooth convex minimization uses smoothing with restarts and proves an O(1/k) last-iterate rate. It reaches 10⁻¹⁰ accuracy faster than ADMM and Chambolle–Pock on LIBSVM ℓ1-SVMs.
- A Tight Convergence Analysis of Inexact Stochastic Proximal Point Algorithm for Stochastic Composite Optimization Problems proves O(k^-β) last-iterate rates without global smoothness. It does so at the price of an inner subproblem solve at every step.
- New analysis and results for the Frank-Wolfe method keeps individual iterates sparse by construction.
A Survey of Numerical Algorithms that can Solve the Lasso Problems compares ISTA, FISTA, coordinate descent and path-following, and observes that coordinate descent wins on very sparse solutions while FISTA's acceleration helps elsewhere. The comparison is qualitative and offline. We turn that observation into a learned, per-instance decision.
The method comes from the algorithm-selection literature:
- AutoFolio: An Automatically Configured Algorithm Selector tunes an entire selection pipeline with Sequential Model-based Algorithm Configuration (SMAC). It reports 1.3–15.4× average speedups over the single best solver on ASlib 1.0, and it introduced a cap on feature-computation time.
- ASlib: A Benchmark Library for Algorithm Selection supplies the data format. It also reports that regression forests beat direct classification on 13 of 17 scenarios, and that very few features and solvers often suffice.
- Algorithm Selection via Ranking and Neural Solver Selection for Combinatorial Optimization train with pairwise ranking losses. The second cuts the TSP optimality gap from 2.33% to 1.51%.
All of this work is discrete or black-box. Its features, such as clause statistics, graph encoders and the landscape features surveyed in A Survey of Meta-features Used for Automated Selection of Algorithms for Black-box Single-objective Continuous Optimization, either do not apply or become too costly in high dimension, as that survey itself notes.
One constraint shapes the design. A single first-order pass over a lasso instance is cheap, so a singular value decomposition, or any landscape sampling, can cost more than solving the problem. Features must therefore cost a handful of data passes at most. This is the reason we read features off the probe trajectory itself, in the spirit of the trajectory features the black-box survey describes, but here built from support dynamics.
Research Program
Building the scenario. We first build the missing benchmark: an ASlib-format scenario for sparse composite optimization. Instances are generated by crossing datasets with regularization levels and subsamples. The datasets are UCI abalone7 and space_ga9 (used by the isPPA paper), the LIBSVM collection including rcv1 and covtype (used for ℓ1-SVMs by the primal-dual paper), RCV1-v2 from RCV1: A New Benchmark Collection for Text Categorization Research, the movie-review basis-pursuit problem, and synthetic sparse regression matching the ORDA setup (100 dimensions, 50 relevant features) with varied correlation and noise. Regularization is set as a grid of ratios λ/λ_max. The models are lasso, elastic net and ℓ1-SVM.
Reference supports. For real data, the reference support of each instance is the support of a 10⁻¹⁰-accurate solution computed by the primal-dual solver. For synthetic data, we use both the solver-reference support and the planted support.
Portfolio and label. The portfolio contains ISTA, FISTA, cyclic coordinate descent, ORDA, isPPA, the adaptive primal-dual method and Frank–Wolfe. We add one deliberately structure-blind member: regularized dual averaging with an averaged output followed by thresholding. Every run is measured in data passes and in wall-clock time. The selection label is support-identification cost:
$$ T_{\text{supp}}(a, x) = \min \{\, t : \operatorname{supp}(x^a_s) = S^\star(x) \ \text{for all } s \ge t \text{ up to the budget} \,\}, $$
where $x^a_s$ is solver $a$'s current iterate after $s$ passes on instance $x$, and $S^\star(x)$ is the reference support. Runs that never stabilize are charged ten times the budget, in the PAR10 style. A relaxed version replaces exact equality with support F1 ≥ 0.95. We record the usual objective-accuracy runtime alongside, so the two labels can be compared on identical runs.
Features. Static features are things computable in one pass: n/p, λ/λ_max (which needs Xᵀy anyway), the spread of column norms, and sampled column coherence. Probe features come from K ≈ 5 passes of ISTA:
- the support churn rate, meaning coordinates entering or leaving the support per pass;
- the fraction of coordinates whose gradient magnitude lies within a small margin of λ, i.e. near the soft-thresholding boundary;
- the slope of objective decrease;
- the size and growth of the current support.
The selector is a regression forest with one model per solver, which is the configuration ASlib found strongest. Its whole pipeline is tuned with AutoFolio's configuration procedure under the same budget as the baselines. After the probe, the chosen solver starts from the probe's last iterate.
Analysis. We will write down when warm-starting preserves each solver's last-iterate guarantee. For the proximal-gradient, coordinate and restarted primal-dual methods the guarantee holds from any starting point. For ORDA and isPPA, the step-size schedule must be re-indexed. We will check empirically that the warm start never hurts support-identification time relative to a cold start.
Baselines
Single best solver (naive reference). The naive reference is the portfolio member with the lowest mean penalized support-identification cost on the training split, run cold, with no features and no probe. It is the honest "do nothing" option because practitioners simply call one solver, typically coordinate descent. It is run on the identical test instances with the same pass budget. The only tuning is choosing which solver is best, using training data. No reported result was found on Lacuna for single-best performance on sparse composite selection; the closest analogue is AutoFolio's 1.3–15.4× gap on discrete ASlib scenarios, which does not transfer numerically.
Oracle (upper reference). The virtual best solver picks, per instance, the solver with the lowest true cost. All results are reported as the fraction of the single-best-to-oracle gap that each method closes.
Strongest existing method. This is AutoFolio as described in AutoFolio: An Automatically Configured Algorithm Selector, trained in the standard way: objective-accuracy runtime labels and static features only. It is the strongest competitor because it represents the best existing selection practice, applied faithfully to this domain. It receives the same configuration budget measured in CPU time, the same instances and folds, and the same feature-time cap. On ASlib it reports 1.3–15.4× speedups over the single best solver. No reported result was found on Lacuna for AutoFolio on lasso or ℓ1-SVM instances. Beating it means a statistically significant reduction, by paired test across instances, in penalized support-identification cost, and a higher fraction of instances whose final iterate has the correct support within budget. We also check that its objective-runtime performance is matched within noise.
Racing. All portfolio members run for a short slice, and the leader is kept by a support-stability criterion. This is the natural low-overhead competitor in a domain where iterations are cheap. Its total probe budget is set equal to ours.
Ablations. Two ablations isolate the key ingredients. The first is the same selector with static features only, versus probe features only, versus both; this isolates the probe. The second is the full selector trained on objective labels but evaluated on support cost; this isolates the target.
Why not just…?
Why not just use coordinate descent everywhere? Coordinate descent powers glmnet and, by the Lasso survey's account, wins when solutions are very sparse. But the same survey describes no solver dominating across sample size, dimension and sparsity regime. The ORDA paper's F1 spread of 0.67–0.92 shows that structural quality varies across methods. The single-best baseline measures this directly. If coordinate descent closes most of the gap to the oracle, the honest conclusion is that per-instance selection is not worth deploying for these problems. We would report that.
Why not just average iterates and threshold afterwards? Thresholding needs a cutoff that depends on the unknown signal scale. It cannot restore a small true coefficient that smearing has blurred, and averaging-based methods trail ORDA in support F1 (0.67–0.83 against 0.92) on the ORDA paper's synthetic task. Rather than argue this, we include averaged dual averaging plus thresholding, with the threshold tuned on training instances, as a portfolio member. If the selector routinely picks it, that refutes the premise that last-iterate methods matter for selection.
Why not just race all solvers briefly instead of predicting? This is the real threat. Iterations are cheap, so racing every solver for a few passes may be as informative as one ISTA probe plus a learned model. The static parallel portfolios of Learning Static Parallel Portfolios of Algorithms make the same argument in discrete domains. Our counter-hypothesis is that support identification often happens late, after the early leader in objective value has already been decided, so short races are misleading in exactly the cases that matter. The racing baseline, run at an equal budget, settles this. If racing matches the learned selector, the contribution shrinks to the benchmark and the disagreement finding, and we would say so.
Proposed Experiments
The first decisive check is descriptive. On the full scenario, what fraction of instances have different argmins under support-identification cost and objective-runtime cost? How much support cost is lost by picking the objective-optimal solver? A disagreement rate below about 10%, together with small loss, ends the project as a negative result worth publishing, because it would justify standard runtime selection for sparse problems.
The second check is the main comparison. Every baseline is run under leave-one-dataset-out cross-validation, which probes the generalization weakness that the black-box survey flags. We report the fraction of the single-best-to-oracle gap closed in penalized support-identification passes and in wall-clock time including probe cost, support F1 at a fixed budget, and objective-runtime parity.
The third check is the pair of ablations. We expect probe features to matter most on correlated designs and near-boundary regularization levels. If static features alone suffice, the simpler pipeline wins.
The fourth check verifies warm starts. On every instance, it compares the chosen solver's support-identification time from the probe iterate against its cold start. Any systematic slowdown for ORDA or isPPA would show that the step-schedule re-indexing is inadequate.
References
- Optimal Regularized Dual Averaging Methods for Stochastic Optimization
- An adaptive primal-dual framework for nonsmooth convex minimization
- A Tight Convergence Analysis of Inexact Stochastic Proximal Point Algorithm for Stochastic Composite Optimization Problems
- New analysis and results for the Frank-Wolfe method
- A survey of numerical algorithms that can solve the Lasso problems
- AutoFolio: An Automatically Configured Algorithm Selector
- ASlib: A benchmark library for algorithm selection
- Algorithm Selection via Ranking
- Neural Solver Selection for Combinatorial Optimization
- A survey of features used for representing black-box single-objective continuous optimization
- RCV1: A New Benchmark Collection for Text Categorization Research
- Learning Static Parallel Portfolios of Algorithms