Approximate Supermodularity Bounds for Experimental Design
This work provides performance guarantees for the greedy solution of experimental design problems. In particular, it focuses on A- and E-optimal designs, for which typical guarantees do not apply since the mean-square error and the maximum eigenvalue of the estimation error covariance matrix are not supermodular. To do so, it leverages the concept of approximate supermodularity to derive non-asymptotic worst-case suboptimality bounds for these greedy solutions. These bounds reveal that as the SNR of the experiments decreases, these cost functions behave increasingly as supermodular functions. As such, greedy A- and E-optimal designs approach (1-1/e)-optimality. These results reconcile the empirical success of greedy experimental design with the non-supermodularity of the A- and E-optimality criteria.
Code (0)
등록된 구현이 없습니다.
Tasks
Experimental DesignSimilar Papers 제목 키워드 기반
Batch greedy maximization of non-submodular functions: Guarantees and applications to experimental design
We propose and analyze batch greedy heuristics for cardinality constrained maximization of non-submodular non-decreasing set functions. We consider the standard greedy paradigm, along with its distributed greedy and stoc…
Experimental DesignGreedy Sampling of Graph Signals
Sampling is a fundamental topic in graph signal processing, having found applications in estimation, clustering, and video compression. In contrast to traditional signal processing, the irregularity of the signal domain …
ClusteringVideo CompressionOn the Supermodularity of Active Graph-based Semi-supervised Learning with Stieltjes Matrix Regularization
Active graph-based semi-supervised learning (AG-SSL) aims to select a small set of labeled examples and utilize their graph-based relation to other unlabeled examples to aid in machine learning tasks. It is also closely …
Community DetectionGeneral ClassificationNeural Network Architecture Optimization through Submodularity and Supermodularity
Deep learning models' architectures, including depth and width, are key factors influencing models' performance, such as test accuracy and computation time. This paper solves two problems: given computation time budget, …
Interval Dominance based Structural Results for Markov Decision Process
Structural results impose sufficient conditions on the model parameters of a Markov decision process (MDP) so that the optimal policy is an increasing function of the underlying state. The classical assumptions for MDP s…
Decision Making