CS Paper Radar

Sparse Experimental Design for Nonsmooth Estimators via Bilevel Optimization

Antonio G. Marques, Samuel Rey

eess.SP ·submitted 2026-10-01 07:36 UTC · v1
code/data

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

A Nonconvex Framework for Joint Sparse Sample Weighting and Parameter Estimation

cs.LG math.OCstat.ML ·2026-10-25 ·Hassan Nojavan, Chul Moon, Miju Ahn
benchmark similarity 0.63
Abstract · 40 pages, 5 figures

We propose a joint sparse sample weighting and parameter estimation (SWAPE) framework that jointly optimizes model parameters and sample weights to train a model while simultaneously assigning an individual weight to each training data point. Our framework accommodates several widely used loss functions for the model parameters, including convex, weakly convex, and difference-of-convex loss, and weakly convex sparsity functions to control the complexity of the sample weights. To solve the resulting bivariate problem, we propose an alternating minimization method in which the subproblems for updating the model parameters and weights are each approximated using majorize-minimize techniques. We provide several approximation methods for the loss functions considered in this paper, and show the overall algorithm's convergence. Numerical experiments on various learning tasks and data anomaly settings demonstrate the effectiveness of the proposed framework in minimizing the impact of undesirable data points compared to benchmark methods.

0.16

Lower-Level Agnostic Bilevel Optimization

cs.LG math.OCstat.ML ·2026-11-06 ·Peiwen Qiu, Prashant Khanduri, Jia Liu
similarity 0.62
Abstract

Bilevel optimization is a fundamental framework for machine learning problems, where an upper-level (UL) objective depends on the solution of a nested lower-level (LL) problem. Existing bilevel algorithms typically assume that the LL objective is available for evaluation, differentiation, or unrolling. However, this assumption can fail when the LL response is produced by a black-box solver, simulator, adversary, or learned predictor. In this paper, we study LL agnostic bilevel optimization, where the UL learner has access only to an approximate LL solution $\bar{\mathbf{y}}(\mathbf{x})$ and cannot query the LL objective, its gradients, Hessian/Jacobian information, or the procedure that generates the LL response. We propose LeGo-BiO, a coordinate-wise pseudo-hypergradient method that estimates the missing Jacobian $\nabla _{\mathbf{x}}\bar{\mathbf{y}}(\mathbf{x})$ using finite differences of $\bar{\mathbf{y}}(\cdot)$. For each UL coordinate, LeGo-BiO constructs a decision vector subject to 1-sparse updates, thereby isolating the corresponding Jacobian column needed in the UL gradient computation. This avoids the directional-projection limitation of full-parameter response differences and, unlike derivative-free/zeroth-order approximations of the entire UL gradient, preserves the available first-order gradient information with respect to the UL variables for more accurate UL gradient evaluation. We establish convergence guarantees for LeGo-BiO in both deterministic and stochastic settings under an LL error-bound/Polyak-Lojasiewicz-type condition, without requiring LL strong convexity. Our bounds yield an $O(T^{-1})$ rate in the deterministic setting and an $O(T^{-1/2})$ rate in the stochastic setting when the LL approximation error decreases geometrically. Experiments demonstrate competitive performance of LeGo-BiO despite being agnostic to the LL objective.

0.09

Convex Optimization Is Free When Accuracy Is Expensive

cs.LG math.OCstat.ML ·2026-09-28 ·Arthur Paing, Arthur Jacot
similarity 0.62
Abstract

This paper studies convex optimization when the gradient cannot be evaluated exactly, but only approximated by a hierarchy of algorithms whose compute grows like $δ^{-γ}$ in the accuracy $δ$. When $γ>2$, falling into the Harder-Than-Monte-Carlo (HTMC) regime, the price of accuracy outruns the variance reduction that Monte Carlo would buy and we show that minimizing a loss function costs no more, up to a factor depending only on $γ$, than a single evaluation of its gradient at the accuracy the problem demands. A randomized multilevel oracle replaces the deterministic approximation of accuracy $δ$ by an unbiased estimator of it, whose variance $σ^2$ becomes a second, independently priced dial: the cost of one call drops from $δ^{-γ}$ to $δ^{2-γ}σ^{-2}$. Plain inexact gradient descent driven by that oracle reaches loss $\varepsilon$ at expected compute $Θ(\varepsilon^{-γ})$ in the convex case, against $Θ(\varepsilon^{-(γ+1)})$ for the same method run at a fixed accuracy: randomization buys a full power of $\varepsilon$. Under $μ$-strong convexity the exponent halves, to $\varepsilon^{-γ/2}$, because the iterates settle at a noise floor and the bias budget relaxes accordingly. Both bounds are independent of the step size, and hence of the smoothness constant, and we show that the cost is a functional of the underlying gradient flow rather than of any discretization of it.

0.23

Probabilistic Multi-Source Data Selection via Learnable Categorical Priors: Variance Reduction and Guaranteed Derandomization

cs.LG cs.AI ·2026-10-10 ·Shizhan Cai, Qixin Zhang, Siyuan Ma, Siyuan Liang, Yongcheng Jing +1 more
similarity 0.60
Abstract

Bilevel data selection is a fundamental task with numerous applications in machine learning and statistics. A common strategy for tackling this problem is to relax the original bilevel combinatorial optimization into a continuous one. However, existing methods, including 0-1 relaxation and probabilistic relaxation, still suffer from several limitations, such as unstable gradient estimation and infeasible rounding. To address these issues, this paper proposes a new probabilistic relaxation for the multi-source bilevel data selection problem. Our key idea is to introduce multiple learnable categorical priors to parameterize a probability distribution supported only on feasible data subsets, thus naturally yielding a lossless rounding scheme. We further show that our proposed relaxation admits an effective two-point gradient estimator, which can simultaneously avoid the inverse-Hessian computation required by existing 0-1 relaxation and the unbounded score term appearing in prior probabilistic relaxation. Furthermore, we develop a reducible representation of this estimator, which substantially reduces the number of lower-level retrainings required for gradient computation. Built upon this reducible two-point estimator, we then design a novel stochastic gradient algorithm, termed ReSGD, for multi-source bilevel data selection problem, and establish a rigorous approximation guarantee for the subset returned by ReSGD under weak submodularity. Finally, extensive experiments are conducted to validate the effectiveness of our proposed ReSGD.

0.25

Computationally Constrained First-Order Prediction-Correction Approach for Time-Varying Convex Optimization

eess.SY ·2026-10-28 ·Negin Musavi, Oscar Jed R. Chuy, Melkior Ornik, Matthew T. Hale
similarity 0.60
Abstract · 8 pages, 2 figures, Submitted to ECC

Time-varying optimization methods often predict the locations of time-varying optima, then sample the objective function being minimized, and then compute corrections to those predictions. However, existing methods typically do not account for settings in which the number of computations is limited. Therefore, in this work we formulate a prediction-correction algorithm that is designed to obey a budget constraint on the total number of iterations it can execute over a given time horizon. We first identify a threshold on the average number of computations between samples of the objective, above which a bound from prior work certifies contraction of iterates toward a minimizer. Below this threshold, we introduce a finite-horizon contraction certificate, which we use to give budget conditions under which the tracking error admits an explicit bound that decays at a prescribed rate. We also present an algorithm to determine how many prediction and correction steps should be executed for each sample of the objective, while obeying a given budget on the allowable number of computations. Empirically, we show in a simulation that our approach reduces cumulative tracking error by 45.5 % relative to a comparable baseline approach.

0.32

Risk-Aware Goal-Oriented Bayesian Optimal Experimental Design

cs.CE stat.MEstat.CO ·2026-09-07 ·John D. Jakeman, Rebekah White, Bart van Bloemen Waanders, Drew P. Kouri, Alen Alexanderian
similarity 0.60
Abstract

Traditional Bayesian optimal experimental design (OED) selects measurements that best inform a model's parameters. However, such measurements can be suboptimal for downstream predictions. Goal-oriented OED targets the prediction directly. However, the existing goal-oriented criteria value all reductions in predictive uncertainty equally, with no way to prioritize rare, high-consequence outcomes. In this article, we develop a risk-aware framework that composes risk at three levels, each generalizing an ingredient of classical $I$- and $G$-optimal design: a deviation measure of the posterior predictive uncertainty (generalizing the predictive variance), a risk measure across the prediction domain (interpolating $I$-optimal averaging and $G$-optimal worst-case selection), and a risk measure over datasets (generalizing the expectation). We generate each level from a regret function in the risk quadrangle, so that one triple specifies a practitioner's risk preference. We relax the design to continuous weights on the unit simplex and construct a nested-quadrature estimator that is differentiable in the design variable. This enables solving the optimal design problem with gradient-based methods, avoiding a combinatorial search over candidate designs. For a linear-Gaussian lognormal model and a nonlinear extension, we derive closed-form objectives. These give exact references against which we verify that the estimator converges. We demonstrate this framework for finding optimal sensor placements in an inverse problem governed by an advection-diffusion equation. We find that the risk-aware designs substantially outperform the expected-information-gain baseline, which is statistically indistinguishable from a random allocation.

0.28

Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking

cs.LG ·2026-10-09 ·El Mahdi Chayti, Alireza Mirrokni, Martin Jaggi
similarity 0.60
Abstract

Many optimization problems provide direct access to only part of the gradient, while the remaining component must be inferred from function evaluations. This structure arises in performative prediction, performative reinforcement learning, and bilevel optimization with a black-box lower level. We introduce Partially Informed Stochastic Optimization (PISO), which combines the available gradient component with a running estimate of the residual. By centring each zeroth-order observation on this estimate, PISO makes the variance due to random probing depend on the tracking error rather than the residual's magnitude. This yields a randomized sketch iteration with an explicit contraction mechanism and a principled interpretation of momentum. For smooth nonconvex objectives, we establish convergence guarantees that depend on the residual's variation and initial magnitude, without requiring a uniform bound on the unavailable gradient component. With independently sampled function evaluations and Gaussian or spherical probes, PISO attains leading function-evaluation complexities of \(O(d^{2}\varepsilon^{-6})\) under Lipschitz gradients and \(O(d^{2}\varepsilon^{-5})\) under an additional Lipschitz-Hessian assumption. These rates require only one probe direction, two function samples, and one known-component sample per update. The analysis also quantifies how batching trades observations for fewer deployments. Across five settings, PISO variants improve on the tested baselines with comparable oracle access in three, reach a comparable solution faster in bilevel routing, and perform best among methods without response-model derivatives in performative reinforcement learning.

0.30

Calibrated Target Noise Recovers Curvature from the Gradients

cs.LG ·2026-11-05 ·Arash Jamshidi, Katsiaryna Haitsiukevich, Aristides Gionis, Kai Puolamäki
top venue similarity 0.59
Abstract · Accepted at NeurIPS 2026. 39 pages

Estimating curvature information from gradients alone is a fundamental problem in machine learning. The challenge becomes particularly acute in settings where only aggregate mini-batch gradients are available, yet curvature information is still required for applications such as preconditioning in optimisation, sampling, and early stopping. Perhaps surprisingly, we show that a simple target-perturbation scheme suffices to recover such curvature information from gradients alone. Our method injects zero-mean noise into the targets, with variance calibrated to the local output curvature. The covariance of the resulting noisy batch gradients then recovers practical curvature matrices, without requiring per-sample gradients, second-order derivatives, or other internal network quantities. For a broad class of non-linear models, our scheme recovers the Generalised Gauss--Newton (GGN) matrix; for feed-forward ReLU networks, it additionally recovers the diagonal blocks of the population Hessian. We demonstrate that the resulting estimator is simple, lightweight, provably optimal, and easy to integrate into existing training pipelines. Experiments demonstrate accurate curvature recovery, faster optimisation when the estimator is used for preconditioning, and the utility of the estimated GGN for early stopping.

0.31