Search for: All records

We assess the Value of Information (VoI) for inspecting components in systems managed by multiple agents, using game theory and Nash equilibrium analysis. We focus on binary systems made up by binary components which can be either intact or damaged. Agents taking maintenance actions are responsible for the repair costs of their own components, and the penalty for system failure is shared among all agents. The precision of inspection is also considered, and we identify the prior and posterior Nash equilibrium with perfect or imperfect inspections. The VoI is assessed for the individual agents as well as for the whole set of agents, and the analysis consider series, parallel and general systems. A negative VoI can trigger the phenomenon of Information Avoidance (IA), where rational agents prefer not to collect free information. We discuss whether it is possible that the VoI is negative for one or for all agents, for the agents with inspected or uninspected components, and for the total sum of VoIs. 

Quaternary ammonium compounds (QACs), a large class of chemicals that includes high production volume substances, have been used for decades as antimicrobials, preservatives, and antistatic agents, and for other functions in cleaning, disinfecting, personal care products, and durable consumer goods. QAC use has accelerated in response to the COVID-19 pandemic and the banning of 19 antimicrobials from several personal care products by the US Food and Drug Administration in 2016. Studies conducted before and after the onset of the pandemic indicate increased human exposure to QACs. Environmental releases of these chemicals have also increased. Emerging information on adverse environmental and human health impacts of QACs is motivating a reconsideration of the risks and benefits across the life cycle of their production, use, and disposal. This paper presents a critical review of the literature and scientific perspective developed by a multidisciplinary, multi-institutional team of authors from academia, governmental, and nonprofit organizations. The review evaluates currently available information on the ecological and human health profile of QACs and identifies multiple areas of potential concern. Adverse ecological effects include acute and chronic toxicity to susceptible aquatic organisms, with concentrations of some QACs approaching levels of concern. Suspected or known adverse health outcomes include dermal and respiratory effects, developmental and reproductive toxicity, disruption of metabolic function such as lipid homeostasis, and impairment of mitochondrial function. QACs’ role in antimicrobial resistance has also been demonstrated. In the US regulatory system, how a QAC is managed depends on how it is used, for example, in pesticides or personal care products. This can result in the same QACs receiving different degrees of scrutiny depending on the use and the agency regulating it. Further, the EPA’s current method of grouping QACs based on structure, first proposed in 1988, is insufficient to address the wide range of QAC chemistries, potential toxicities, and exposure scenarios. Consequently, exposures to common mixtures of QACs and from multiple sources remain largely unassessed. Some restrictions on the use of QACs have been implemented in the US and elsewhere, primarily focused on personal care products. Assessing the risks posed by QACs is hampered by their vast structural diversity and a lack of quantitative data on exposure and toxicity for the majority of these compounds. This review identifies important data gaps and provides research and policy recommendations for preserving the utility of QAC chemistries while also seeking to limit adverse environmental and human health effects. 

Algorithms for noiseless collaborative PAC learning have been analyzed and optimized in recent years with respect to sample complexity. In this paper, we study collaborative PAC learning with the goal of reducing communication cost at essentially no penalty to the sample complexity. We develop communication efficient collaborative PAC learning algorithms using distributed boosting. We then consider the communication cost of collaborative learning in the presence of classification noise. As an intermediate step, we show how collaborative PAC learning algorithms can be adapted to handle classification noise. With this insight, we develop communication efficient algorithms for collaborative PAC learning robust to classification noise. 

In recent years, federated learning has been embraced as an approach for bringing about collaboration across large populations of learning agents. However, little is known about how collaboration protocols should take agents’ incentives into account when allocating individual resources for communal learning in order to maintain such collaborations. Inspired by game theoretic notions, this paper introduces a framework for incentive-aware learning and data sharing in federated learning. Our stable and envy-free equilibria capture notions of collaboration in the presence of agents interested in meeting their learning objectives while keeping their own sample collection burden low. For example, in an envy-free equilibrium, no agent would wish to swap their sampling burden with any other agent and in a stable equilibrium, no agent would wish to unilaterally reduce their sampling burden. In addition to formalizing this framework, our contributions include characterizing the structural properties of such equilibria, proving when they exist, and showing how they can be computed. Furthermore, we compare the sample complexity of incentive-aware collaboration with that of optimal collaboration when one ignores agents’ incentives. 

We study the problem of robust learning under clean-label data-poisoning attacks, where the at-tacker injects (an arbitrary set of) correctly-labeled examples to the training set to fool the algorithm into making mistakes on specific test instances at test time. The learning goal is to minimize the attackable rate (the probability mass of attackable test instances), which is more difficult than optimal PAC learning. As we show, any robust algorithm with diminishing attackable rate can achieve the optimal dependence on ε in its PAC sample complexity, i.e., O(1/ε). On the other hand, the attackable rate might be large even for some optimal PAC learners, e.g., SVM for linear classifiers. Furthermore, we show that the class of linear hypotheses is not robustly learnable when the data distribution has zero margin and is robustly learnable in the case of positive margin but requires sample complexity exponential in the dimension. For a general hypothesis class with bounded VC dimension, if the attacker is limited to add at most t >0 poison examples, the optimal robust learning sample complexity grows almost linearly with t. 

Today’s STEM classrooms have expanded the domain of computer science education from a basic two-toned terminal screen to now include helpful Integrated Development Environments(IDE) (BlueJ, Eclipse), block-based programming (MIT Scratch, Greenfoot), and even physical computing with embedded systems (Arduino, LEGO Mindstorm). But no matter which environment a student starts programming in, all students will eventually need help in finding and fixing bugs in their code. While the helpful IDE’s have debugger tools built in (breakpoints for pausing your program, ways to view/modify variable values, and "stepping" through code execution), in many of the other programming environments, students are limited to using print statements to try and "see" what is happening inside their program. Most students who learn to write code for Arduino microcontrollers will start within the Arduino IDE, but the official Arduino IDE does not currently provide any debugging tools. Instead, a student would have to move on to a professional IDE such as Atmel Studio or acquire a hardware debugger in order to add breakpoints or view their program’s variables. But each of these options has a steep learning curve, additional costs, and can require complex configurations. Based on research of student debugging practices[3, 7] and our own classroom observations, we have developed an Arduino software library, called Arduino Debugger, which provides some of these debugging tools (ex. breakpoints) while staying within the official Arduino IDE. This work continues a previous library, (redacted), which focused on features specific to e-textiles development boards. The Arduino Debugger library has been modified to support not only e-textile boards (Lilypad, Adafruit Circuit Playground) but most AVR and ARM based Arduino boards.We are also in the process of testing a set of Debugging Code Templates to see how they might increase student adoption of debugging tools. 

The e-textile landscape has enabled creators to combine textile materiality with electronic capability. However, the tools that e-textile creators use have been adapted from traditional textile or hardware tools. This puts creators at a disadvantage, as e-textile projects present new and unique challenges that currently can only be addressed using a non-specialized toolset. This paper introduces the first iteration of a wearable e-textile debugging tool to assist novice engineers in problem solving e-textile circuitry errors. These errors are often only detected after the project is fully built and are resolved only by disassembling the circuit. Our tool actively monitors the continuity of the conductive thread as the user stitches, which enables the user to identify and correct circuitry errors as they create their project. 

We study the computational complexity of finding Stackelberg Equilibria in general-sum games, where the set of pure strategies of the leader and the followers are exponentially large in a natural representation of the problem. 

We study the classic Maximum Independent Set problem under the notion of stability introduced by Bilu and Linial (2010): a weighted instance of Independent Set is γ-stable if it has a unique optimal solution that remains the unique optimal solution under multiplicative perturbations of the weights by a factor of at most γ ≥ 1. The goal then is to efficiently recover this “pronounced” optimal solution exactly. In this work, we solve stable instances of Independent Set on several classes of graphs: we improve upon previous results by solving \tilde{O}(∆/sqrt(log ∆))-stable instances on graphs of maximum degree ∆, (k − 1)-stable instances on k-colorable graphs and (1 + ε)-stable instances on planar graphs (for any fixed ε > 0), using both combinatorial techniques as well as LPs and the Sherali-Adams hierarchy. For general graphs, we give an algorithm for (εn)-stable instances, for any fixed ε > 0, and lower bounds based on the planted clique conjecture. As a by-product of our techniques, we give algorithms as well as lower bounds for stable instances of Node Multiway Cut (a generalization of Edge Multiway Cut), by exploiting its connections to Vertex Cover. Furthermore, we prove a general structural result showing that the integrality gap of convex relaxations of several maximization problems reduces dramatically on stable instances. Moreover, we initiate the study of certified algorithms for Independent Set. The notion of a γ-certified algorithm was introduced very recently by Makarychev and Makarychev (2018) and it is a class of γ-approximation algorithms that satisfy one crucial property: the solution returned is optimal for a perturbation of the original instance, where perturbations are again multiplicative up to a factor of γ ≥ 1 (hence, such algorithms not only solve γ-stable instances optimally, but also have guarantees even on unstable instances). Here, we obtain ∆-certified algorithms for Independent Set on graphs of maximum degree ∆, and (1 + ε)-certified algorithms on planar graphs. Finally, we analyze the algorithm of Berman and Fürer (1994) and prove that it is a ((∆+1)/3 + ε)-certified algorithm for Independent Set on graphs of maximum degree ∆ where all weights are equal to 1.