Source-linked AI summary
Sparse Experimental Design for Nonsmooth Estimators via Bilevel Optimization
Antonio G. Marques, Samuel Rey
TL;DR
Classical OED scores a linear-Gaussian model, but many deployed nonsmooth estimators lack a closed-form solution and are not captured by its information criteria. This paper optimizes design through a bilevel formulation using the deployed estimator, validation risk, and a concave sparsity price. Experiments report gains over selection baselines in sparse recovery and image reconstruction.
Problem
Method
The method optimizes a bilevel design using the deployed nonsmooth estimator, held-out prediction risk, and a concave sparsity price, with a value-function penalty avoiding differentiation through the solution map.
Source: §1 · p. 1, §3.1 · p. 2, §3.2 · p. 2Results
For sparse recovery designs with M1 < 40, the proposed method attains lower NMSE than all baselines; on image data, it improves on every baseline below 48 pixels.
Source: §5 · p. 4Takeaways & Limitations
The price rule retains a measurement only when its estimator-aware value exceeds its marginal price, while increasing the price explores the cardinality-accuracy frontier.
Source: §1 · p. 1, §3.1 · p. 2The framework assumes design weights enter only smooth, strongly convex losses and that the nonsmooth lower-level term is design-independent and proximable.
Source: §2 · p. 2
Abstract
from arXiv · showhide
Optimal experimental design (OED) decides which measurements to acquire for downstream estimation. Classically, this is done by optimizing an information criterion derived from a linear-Gaussian model, for which the estimator is available in closed form. Many modern estimators such as Lasso, elastic net, or total-variation-based estimators, however, are nonsmooth and lack a closed-form solution. To extend OED to these scenarios, we recast the problem as what it implicitly is: a bilevel program whose lower level computes the deployed nonsmooth estimator and whose upper level scores its validation prediction risk. Rather than fixing the number of measurements in advance, we charge each continuous acquisition weight a concave sparsity price. As a result, how many and which measurements to keep are both outcomes of the optimization. A measurement survives only if its estimator-aware value exceeds its price, and progressively increasing the price yields a sequence of designs that explores the trade-off between measurement cardinality and estimation accuracy. Using a value-function penalty reformulation, we develop a single-loop proximal-gradient algorithm that avoids differentiating the nonsmooth solution map and establish its convergence to an (approximate) stationary point. Experiments on synthetic sparse recovery and image reconstruction demonstrate the benefits of the proposed method.
1. INTRODUCTION
Classical OED scores a forward model, while modern nonsmooth estimators have behavior that information matrices do not explicitly capture. The paper recasts design around the deployed estimator and lets optimization determine which measurements to retain.
1. INTRODUCTION
- Classical OED optimizes information criteria for a linear-Gaussian model, but does not score the nonsmooth estimator used in many contemporary pipelines.Estimator performance can depend on active-set behavior, shrinkage bias, and support instabilities.Source: §1 · p. 1
- Nonsmooth lower-level estimators make OED a genuine bilevel problem, unlike the closed-form linear-Gaussian case.Existing approaches for related problems may smooth the lower level, differentiate through a truncated solver, or rely on support identification.Source: §1 · p. 1
- The proposed formulation uses the deployed nonsmooth estimator, validation prediction risk, and a concave sparsity price to select measurements without a fixed cardinality budget.A value-function penalty yields a single-loop proximal-gradient scheme that avoids differentiating the solution map and has an O(1/K) stationarity guarantee.Source: §1 · p. 1
2. OED IS A BILEVEL PROBLEM
Classical OED can eliminate its lower-level estimator because the linear-Gaussian solution is closed form and its information criteria depend on the design. Nonsmooth estimators generally lack that simplification, leaving a bilevel problem with structural requirements on the lower-level cost.
2. OED IS A BILEVEL PROBLEM
- Acquisition weights w lie in [0, 1]^M, with w_i = 0 indicating that candidate measurement i is not acquired.The upper-level design selects observations, while the lower level computes the estimate for that design.Source: §2 · pp. 1–2
- In classical linear-Gaussian OED, a closed-form weighted ridge estimator and design-only information criteria decouple the upper and lower levels.The resulting problem is optimized over design variables alone.Source: §2 · p. 2
- For the design-weighted elastic-net estimator, the generic lower-level problem has no closed form and its solution map is nonsmooth.Thus the design must be handled as a bilevel program.Source: §2 · p. 2
- The framework requires the design to enter through smooth, uniformly strongly convex per-measurement losses, while the nonsmooth term is design-independent and proximable.The template includes Lasso with positive strong-convexity regularization and can cover TV or fused-Lasso regularizers by replacing the proximal operator.Source: §2 · p. 2
3. SPARSITY-PROMOTING ESTIMATOR-AWARE DESIGN
The design objective combines held-out prediction risk for the deployed estimator with a concave price on acquisition weights. A value-function penalty then replaces the lower-level optimality constraint, enabling optimization without differentiating the nonsmooth solution map.
3.1. Upper level: validation risk plus a sparsity price
- Held-out prediction risk scores reconstructions without ground-truth signals and is estimator-aware, requiring neither Gaussianity nor a forward-model Jacobian.The validation pairs are drawn for the same instances used in the design problem.Source: §3.1 · p. 2
- The concave sparsity price drives small acquisition weights to exact zeros, so the active measurement count emerges from optimization and the price path traces a cardinality-performance frontier.Unlike the linear price, its derivative is small near weight 1 and large near 0.Source: §3.1 · p. 2
3.2. Value-function penalty reformulation
- The value functions have Lipschitz-continuous gradients despite the ℓ1 term, allowing the method to use lower-level residuals instead of differentiating the nonsmooth solution map.The design multiplies only the smooth, strongly convex fidelity term.Source: §3.2 · p. 2
- A penalized optimality gap replaces the lower-level optimality constraint; each gap vanishes exactly when its reconstruction copy solves the lower-level problem.The penalty parameter γ controls bilevel feasibility, and sufficiently large γ yields approximate solutions of the original problem.Source: §3.2 · p. 2
4. SINGLE-LOOP ALGORITHM AND GUARANTEES
The algorithm couples design weights to estimator copies through a value-function penalty and updates them with proximal-gradient steps using inexact lower-level solves. A progressive concave-price path produces deployable binary designs, with convergence guarantees under stated regularity and solve-accuracy conditions.
4. SINGLE-LOOP ALGORITHM AND GUARANTEES
- The proximal-gradient step updates estimator copies by soft-thresholding and design weights by projection onto [0, 1]^M, with inexact lower-level solves from warm-started forward-backward steps.The lower-level estimator is solved only in those forward-backward steps.Source: §4 · p. 3
- Increasing the concave price progressively prunes the design, while settled active sets yield deployable designs across the cardinality-performance frontier.An adaptive safeguard rolls back stages that remove more than a fraction of active sensors.Source: §4 · p. 3
- A sensor remains discarded when its estimator-aware marginal value does not exceed its marginal price, so the deployed estimator drives measurement selection.The value is the aggregate improvement in measurement fit from upper-level-corrected reconstructions, weighted by noise level.Source: §4 · p. 3
- Under strong-convexity, smoothness, Lipschitz, and inner-solve accuracy conditions, the proximal-gradient mapping has an O(1/K) rate, and sufficiently large γ yields ε-approximate bilevel feasibility.The feasibility guarantee applies to stationary points of the penalized problem.Source: §4 · p. 3
- For deployment, weights above τ = 10^-3 define the support, and surviving fractional weights are set to one at matched cardinality.The box proximal operator returns exact zeros, so the threshold formalizes support; the binary conversion is described as conservative.Source: §4 · p. 3
5. NUMERICAL EXPERIMENTS
Across sparse recovery and Fashion-MNIST, the proposed designs outperform information-based selection at low measurement counts. The experiments compare methods using the same deployed estimator on independent test instances.
Experimental design
- Methods are evaluated with the same deployed estimator on independent test instances, using medians and interquartile ranges over 10 random draws.Baselines include random selection, leverage sampling, and greedy D- and A-optimal selection.Source: §5 · p. 3
Sparse linear inverse problem
- 41% vs D-optimal and 43% vs A-optimal median relative NMSE reductions for 67 designs with M1≤40; both won 67/67 comparisons.The proposed designs also reduced NMSE by 35% vs leverage sampling and 51% vs random selection.Source: Figure 1 · p. 4, §5 · p. 4
- The sparse linear test case uses 240 candidate sensors, 80 unknowns, sparse signals, and white noise at 20 dB SNR.Each draw has 64 training, 64 validation, and 512 test instances.Source: §5 · p. 4
Pixel selection on Fashion-MNIST
- Below 48 pixels, proposed designs improve on every baseline in every case; above 64, they tie random sampling and improve on information criteria by 10–41%.Table 1 reports paired test-NMSE reductions and counts of designs with lower NMSE than each baseline.Source: Table 1 · p. 4, §5 · p. 4
6. CONCLUSIONS
The paper formulates OED for nonsmooth estimators as continuous bilevel optimization and develops a single-loop value-function penalty algorithm. Experiments report that estimator-aware designs outperform classical information-driven selection at matched cardinality.
Conclusions
- The single-loop value-function penalty algorithm avoids differentiating the nonsmooth solution map and retains the O(1/K) guarantee of bilevel problems with smooth lower levels.The lower level computes the deployed estimator, while the upper level scores the resulting estimate.Source: §6 · p. 4
- A concave sparsity price makes sensor selection a value-versus-price test, and one price homotopy traces the cardinality-performance frontier.The formulation does not fix the measurement budget in advance.Source: §6 · p. 4
- Experiments on sparse recovery and public image data show that estimator-aware designs outperform classical information-driven selection at matched cardinality.The journal version develops budgeted designs, rounding guarantees, other estimator-aware criteria, and TV-type regularizers.Source: §6 · p. 4
7. COMPLIANCE WITH ETHICAL STANDARDS
The experiments are numerical simulation studies, for which the paper states that ethical approval was not required.
Compliance with ethical standards
- The paper reports that ethical approval was not required for its numerical simulation studies.Source: §7 · p. 5