A tougher test for the search method
A new optimization method reached demanding targets in fewer iterations than the comparison methods in high-correlation tests, according to an arXiv preprint. At a target of 5 times 10 to the minus 7 in the tightest synthetic SLOPE benchmark, the DBS-I-AdaTau variant reached all three seeds at correlations of 0.99 and 0.995, with median iteration counts of 433 and 750. FISTA-L also reached all three seeds but needed 1,946 and 1,957 iterations. A cold-start DBS variant reached none of the three seeds in either setting, while 0SR1 reached all three at 0.99 with a median of 744 iterations and none at 0.995.
DBS stands for Decomposed Bilevel Search. The method is built around a compact representation of its quasi-Newton metric, the rule used to rescale search directions: a diagonal part plus a rank-one correction. It reduces each scaled proximal step, the update that handles the metric and the structured nonsmooth penalty, to a two-dimensional monotone residual system and evaluates that system with one diagonal-metric proximal map. The factors can recover zero-memory DFP/BFGS-type members of the Broyden family, according to the paper.
Lower inner cost in the reported cases
In a d = 5,000 SLOPE scaled-proximal oracle benchmark, DBS-I-AdaTau succeeded in every reported trial using 338 to 473 ordinary proximal evaluations. At the highest reported conditioning, Inner-ProxBB failed one trial and used about 1,200 evaluations and 12.6 seconds, compared with 0.19 seconds for DBS.
Warm starts also showed a large difference in the reported inner-work count. At the SLOPE outer target of 10 to the minus 4, warm-started DBS used 38.6 ordinary SLOPE proximal evaluations per outer iteration at correlation 0.99 and 51.0 at 0.995. The cold-start ablation used 198.0 and 185.7, respectively.
The paper pairs those experiments with a formal guarantee. Its certified bilevel solve is stated to reach target accuracy epsilon with work of O((d + T_p) log^2(1/epsilon)), where T_p is the cost of one diagonal-metric proximal map. In practical terms, the accuracy appears through a squared logarithm in that expression. Under strong convexity, the paper states linear outer convergence for both exact and inexact inner solves, meaning a geometric reduction in error under the stated conditions.
The method in larger benchmarks
Most default outer tests used 10,000 training examples and 2,000 features. Every method started from the zero point, x0 = 0, on the same generated train and test split. Results were generally reported as medians over three random seeds.
On the real-sim SLOPE check, with 30,000 training examples and 2,000 features, DBS-I-AdaTau reached the reported target of 5 times 10 to the minus 7 in 168 iterations and 7.99 seconds. 0SR1 reached it in 255 iterations and 11.42 seconds, while MFISTA-L needed 292 iterations and 13.19 seconds. FISTA-L and Prox-BB did not reach the target within the common 300-iteration budget.
A separate synthetic group-lasso comparison used 3,000 training examples, 500 features, groups of size 20, six active groups, seeds 42, 43 and 44, and an outer cap of 100 iterations. DBS-I-AdaTau reached the target on all three seeds at correlations of 0.9 and 0.99, with median iteration counts of 70 and 86 and target times of 2.07 and 1.91 seconds. FISTA-L took 672 and 770 iterations, with times of 1.61 and 1.97 seconds; Prox-BB succeeded on only one of three seeds in each regime.
On the real-sim group-lasso instance, which had 57,847 training examples, 2,000 features and 500 groups of four, DBS-I-AdaTau reached the 10 to the minus 6 target in 159 iterations and 31.02 seconds. 0SR1 reached it in 228 iterations and 38.65 seconds, and FISTA-L in 672 iterations and 51.79 seconds. Across the tested methods, DBS had the fewest iterations and the shortest reported target time in that instance.
A result with clear boundaries
The results need a narrow reading. Outer objective residuals were defined against Fref, the best-observed numerical reference for each instance, so the targets were measures of progress against that reference rather than demonstrations of an exact optimum. Most synthetic results were medians over three seeds; the real-sim SLOPE result was a single-seed check, and the real-sim group-lasso result came from a single instance. The 0SR1 comparison was limited to the tested seeds, grids and budgets, leaving broader performance outside those settings unresolved.
The document identifies itself as arXiv:2608.25557v1, dated 26 August 2026. The work was partially funded by the National Natural Science Foundation of China under grant 12288201, and the authors reported no potential conflict of interest.
Paper data and sources
Original title: A Decomposed Bilevel Search for Variable-Metric Proximal Gradient Methods
Authors: Xinpeng Li, Ya-xiang Yuan
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text