An official website of the United States government
Many applications of representation learning, such as privacy preservation, algorithmic fairness, and domain adaptation, desire explicit control over semantic information being discarded. This goal is formulated as satisfying two objectives: maximizing utility for predicting a target attribute while simultaneously being invariant (independent) to a known semantic attribute. Solutions to invariant representation learning (IRepL) problems lead to a trade-off between utility and invariance when they are competing. While existing works study bounds on this trade-off, two questions remain outstanding: 1) What is the exact trade-off between utility and invariance? and 2) What are the encoders (mapping the data to a representation) that achieve the trade-off, and how can we estimate it from training data? This paper addresses these questions for IRepLs in reproducing kernel Hilbert spaces (RKHS)s. Under the assumption that the distribution of a low-dimensional projection of high-dimensional data is approximately normal, we derive a closed-form solution for the global optima of the underlying optimization problem for encoders in RKHSs. This yields closed formulae for a near-optimal trade-off, corresponding optimal representation dimensionality, and the corresponding encoder(s). We also numerically quantify the trade-off on representative problems and compare them to those achieved by baseline IRepL algorithms.
more »
« less
Efficient Splitting of Test and Simulation Cases for the Verification of Highly Automated Driving Functions
We address the question of feasibility of tests to verify highly automated driving functions by optimizing the trade-off between virtual tests for verifying safety properties and physical tests for validating the models used for such verification. We follow a quantitative approach based on a probabilistic treatment of the different quantities in question. That is, we quantify the accuracy of a model in terms of its probabilistic prediction ability. Similarly, we quantify the compliance of a system with its requirements in terms of the probability of satisfying these requirements. Depending on the costs of an individual virtual and physical test we are then able to calculate an optimal trade-off between physical and virtual tests, yet guaranteeing a probability of satisfying all requirements.
more »
« less
- Award ID(s):
- 1743772
- PAR ID:
- 10076312
- Date Published:
- Journal Name:
- SAFECOMP 2018: Computer Safety, Reliability, and Security
- Page Range / eLocation ID:
- 139 - 153
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Probabilistic programs often trade accuracy for efficiency, and thus may, with a small probability, return an incorrect result. It is important to obtain precise bounds for the probability of these errors, but existing verification approaches have limitations that lead to error probability bounds that are excessively coarse, or only apply to first-order programs. In this paper we present Eris, a higher-order separation logic for proving error probability bounds for probabilistic programs written in an expressive higher-order language. Our key novelty is the introduction of error credits, a separation logic resource that tracks an upper bound on the probability that a program returns an erroneous result. By representing error bounds as a resource, we recover the benefits of separation logic, including compositionality, modularity, and dependency between errors and program terms, allowing for more precise specifications. Moreover, we enable novel reasoning principles such as expectation-preserving error composition, amortized error reasoning, and error induction. We illustrate the advantages of our approach by proving amortized error bounds on a range of examples, including collision probabilities in hash functions, which allow us to write more modular specifications for data structures that use them as clients. We also use our logic to prove correctness and almost-sure termination of rejection sampling algorithms. All of our results have been mechanized in the Coq proof assistant using the Iris separation logic framework and the Coquelicot real analysis library.more » « less
-
Abstract China increasingly relies on agricultural imports, driven by its rising population and income, as well as dietary shifts. International trade offers an opportunity to relieve pressures on resource depletion and pollution, such as nitrogen (N) pollution, while it poses multiple socioeconomic challenges, such as food availability. To quantify such trade-offs considering the roles of different crop types, we developed a unique crop-specific N budget database and assessed the impacts of the crop trade on multiple sustainability concerns including N pollution caused by crop production, crop land area, independence of food supply, and trade expenditures. We quantified the ‘virtual’ N inputs and harvested areas, which are the amount of N inputs and land resources used in exporting countries for China’s crop import. In addition, we proposed the concepts of ‘alternative’ N inputs and harvested area to quantify the resources needed if imported crops were produced in China. By comparing results from ‘alternative’ and ‘virtual’ concepts, we assessed the role of trade in Chinese crops over the past 30 years (i.e. 1986–2015) in alleviating N pollution and saving cropland in China and the world. Crop imports accounted for 31% of Chinese crop N consumption in 2015, and these crop imports eased the need for an additional cropland area of 62 million ha. It also avoided an N surplus by 56 and 36 Tg (Tg = 109kg) for China and the world respectively but led to $621 billion crop trade expenditures over the 30 year period. The N pollution damage avoided by crop imports in economic terms was priced at $22 ± 16 billion in 2015, which is lower than the crop trade expenditures but may be surpassed in the future with the development of the Chinese economy. Optimizing a crop trade portfolio can shift domestic production from N-intensive crop production (e.g. maize, fruits, and vegetables) to N-efficient crop production (e.g. soybeans), and consequently mitigate an N surplus by up to 12%. Improving N use efficiency for individual crops can further increase the mitigation potential of N surplus to 30%–50%, but requires technology advancement and policy incentives.more » « less
-
null (Ed.)The {\sc Acceptance Probability Estimation Problem} (APEP) is to additively approximate the acceptance probability of a Boolean circuit. This problem admits a probabilistic approximation scheme. A central question is whether we can design a {\em pseudodeterministic} approximation algorithm for this problem: a probabilistic polynomial-time algorithm that outputs a canonical approximation with high probability. Recently, it was shown that such an algorithm would imply that {\em every approximation algorithm can be made pseudodeterministic} (Dixon, Pavan, Vinodchandran; ITCS 2021). The main conceptual contribution of this work is to establish that the existence of a pseudodeterministic algorithm for APEP is fundamentally connected to the relationship between probabilistic promise classes and the corresponding standard complexity classes. In particular, we show the following equivalence: {\em every promise problem in PromiseBPP has a solution in BPP if and only if APEP has a pseudodeterministic algorithm}. Based on this intuition, we show that pseudodeterministic algorithms for APEP can shed light on a few central topics in complexity theory such as circuit lowerbounds, probabilistic hierarchy theorems, and multi-pseudodeterminism.more » « less
-
The energy and latency demands of critical workload execution, such as object detection, in embedded systems vary based on the physical system state and other external factors. Many recent mobile and autonomous System-on-Chips (SoC) embed a diverse range of accelerators with unique power and performance characteristics. The execution flow of the critical workloads can be adjusted to span into multiple accelerators so that the trade-off between performance and energy fits to the dynamically changing physical factors. In this study, we propose running neural network (NN) inference on multiple accelerators of an SoC. Our goal is to enable an energy-performance trade-off with an by distributing layers in a NN between a performance- and a power-efficient accelerator. We first provide an empirical modeling methodology to characterize execution and inter-layer transition times. We then find an optimal layers-to-accelerator mapping by representing the trade-off as a linear programming optimization constraint. We evaluate our approach on the NVIDIA Xavier AGX SoC with commonly used NN models. We use the Z3 SMT solver to find schedules for different energy consumption targets, with up to 98% prediction accuracy.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1007/978-3-319-99130-6_10
