Deep neural networks (DNNs) are increasingly used in real-world applications (e.g. facial recognition). This has resulted concerns about the fairness of decisions made by these models. Various notions and measures have been proposed to ensure that a decision-making system does not disproportionately harm (or benefit) particular subgroups population. In this paper, we argue traditional only based on models' outputs sufficient when model is vulnerable adversarial attacks. We some cases, it may...

Traditional evaluation metrics for learned models that report aggregate scores over a test set are insufficient surfacing important and informative patterns of failure features instances. We introduce study method aimed at characterizing explaining failures by identifying visual attributes whose presence or absence results in poor performance. In distinction to previous work relies upon crowdsourced labels attributes, we leverage the representation separate robust model extract interpretable...

A key challenge in adversarial robustness is the lack of a precise mathematical characterization human perception, used very definition attacks that are imperceptible to eyes. Most current and defenses try avoid this issue by considering restrictive threat models such as those bounded $L_2$ or $L_\infty$ distance, spatial perturbations, etc. However, robust against any these still fragile other models. To resolve issue, we propose training set all examples, approximated using deep neural...

We introduce a novel framework of Prophet Inequalities for combinatorial valuation functions. For (non-monotone) submodular objective function over an arbitrary matroid feasibility constraint, we give O(1)-competitive algorithm. monotone subadditive downward-closed O(log n log2r)-competitive algorithm (where r is the cardinality largest feasible subset).Inspired by proof our prophet inequality, also obtain · Secretary Problem with subject to constraint. Even special case circumvents...

Adversarial training is one of the most effective defenses against adversarial attacks. Previous works suggest that overfitting a dominant phenomenon in leading to large generalization gap between test and train accuracy neural networks. In this work, we show observed closely related choice activation function. particular, using functions with low (exact or approximate) curvature values has regularization effect significantly reduces both standard robust gaps training. We observe for...

TTL caching models have recently regained significant research interest, largely due to their ability fit popular policies such as LRU. In this extended abstract we briefly describe our recent work on two exact methods analyze cache networks. The first method generalizes existing results for line networks under renewal requests the broad class of whereby evictions are driven by stopping times. obtained further generalized, using second method, feedforward with Markov arrival processes (MAP)...

Given an $n$-vertex graph and two straight-line planar drawings of the that have same faces outer face, we show there is a morph (i.e., continuous transformation) between preserves planarity consists $O(n)$ steps, which prove optimal in worst case. Each step unidirectional linear morph, means every vertex moves at constant speed along straight line, lines are parallel although speeds may differ. Thus provide efficient version Cairns' 1944 proof existence planarity-preserving morphs for...

Suppose we are given a submodular function f over set of elements, and want to maximize its value subject certain constraints. Good approximation algorithms known for such problems under both monotone non-monotone functions. We consider these in stochastic setting, where elements not all active only get from elements. Each element e is independently with some probability pe, but don't know the element's status priori: find it out when probe e. Moreover, sequence must satisfy prefix-closed...

A stochastic probing problem consists of a set elements whose values are independent random variables. The algorithm knows the distributions these variables, but not actual outcomes. only way to learn outcomes is probe elements. However, there constraints on which may be probed. (E.g., we have travel in some metric limited time.) These called outer constraints. We want develop an that picks maximize (expected) value, subject picked subset satisfying other constraints, inner In past, problems...

Our main contribution is a general framework to design efficient polynomial time approximation schemes (EPTAS) for fundamental stochastic combinatorial optimization problems. Given an error parameter ε>0, such algorithmic attain (1-ε)-approximation in t(ε)· poly(n) time, where t(·) some function that depends only on ε. Technically speaking, our approach relies presenting tailor-made reductions newly-introduced multi-dimensional load balancing problem. Even though the single-dimensional...

The Ontario electrical grid is sized to meet peak electricity load. If this worst-case load were reduced, the government and tax-payers could defer large infrastructural costs, reducing cost of generation prices. Storage, batteries that can store energy during times low be discharged load, one proposed solution We evaluate effect storage on under different customer pricing schemes. find for existing schemes, adopting not profitable. Furthermore, as level adoption in population increases,...

In 1944, Cairns proved the following theorem: given any two straight-line planar drawings of a triangulation with same outer face, there exists morph (i.e., continuous transformation) between so that drawing remains at all times. Cairns's original proof required exponentially many morphing steps. We prove is consists O(n2) steps, where each step linear moves vertex constant speed along straight line. Using known result on compatible triangulations this implies for general graph G and...

We introduce a novel framework of Prophet Inequalities for combinatorial valuation functions. For (non-monotone) submodular objective function over an arbitrary matroid feasibility constraint, we give O(1)-competitive algorithm. monotone subadditive downward- closed O(log n log2 r)- competitive algorithm (where r is the cardinality largest feasible subset).Inspired by proof our prophet inequality, also obtain · r)-competitive Secretary Problem with subject to downward-closed constraint. Even...

TTL caching models have recently regained significant research interest, largely due to their ability fit popular policies such as LRU. In this extended abstract we briefly describe our recent work on two exact methods analyze cache networks. The first method generalizes existing results for line networks under renewal requests the broad class of whereby evictions are driven by stopping times. obtained further generalized, using second method, feedforward with Markov arrival processes (MAP)...

A longstanding open problem in Algorithmic Mechanism Design is to design computationally-efficient truthful mechanisms for (approximately) maximizing welfare combinatorial auctions with submodular bidders. The first such mechanism was obtained by Dobzinski, Nisan, and Schapira [STOC'06] who gave an O(log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> m)-approximation where m number of items. This has been studied extensively since,...

Suppose we are given a submodular function f over set of elements, and want to maximize its value subject certain constraints. Good approximation algorithms known for such problems under both monotone non-monotone functions. We consider these in stochastic setting, where elements not all active only get from elements. Each element e is independently with some probability pe, but don't know the element's status priori: find it out when probe e. Moreover, sequence must satisfy prefix-closed...

We consider an online vector balancing question where T vectors, chosen from arbitrary distribution over [−1,1] n , arrive one-by-one and must be immediately given a ± sign. The goal is to keep the discrepancy—the ℓ∞-norm of any signed prefix-sum—as small as possible. A concrete example this interval discrepancy problem points are sampled uniformly in unit [0,1], color them such that every sub-interval remains always nearly balanced. As random coloring incurs Ω(T 1/2) discrepancy, while...

Deep learning interpretation is essential to explain the reasoning behind model predictions. Understanding robustness of methods important especially in sensitive domains such as medical applications since results are often used downstream tasks. Although gradient-based saliency maps popular for deep interpretation, recent works show that they can be vulnerable adversarial attacks. In this paper, we address problem and provide a certifiable defense method interpretation. We sparsified...

Deep neural networks can be unreliable in the real world especially when they heavily use {\it spurious} features for their predictions. Focusing on image classifications, we define core features} as set of visual that are always a part object definition while spurious ones likely to co-occur} with but not it (e.g., attribute "fingers" class "band aid"). Traditional methods discovering either require extensive human annotations (thus, scalable), or useful specific models. In this work,...