Abstract

Cryptocurrencies are poised to revolutionize the modern economy by democratizing commerce. These currencies operate on top of blockchain-based distributed ledgers. Existing permissionless blockchain-based protocols offer unparalleled benefits like decentralization, anonymity, and transparency. However, these protocols suffer in performance which hinders their widespread adoption. In particular, high time-to-finality and low transaction rates keep them from replacing centralized payment systems such as the Visa network. Permissioned blockchain protocols offer attractive performance guarantees, but they are not considered suitable for deploying decentralized cryptocurrencies due to their centralized nature. Researchers have developed several multi-layered blockchain protocols that combine both permissioned and permissionless blockchain protocols to achieve high performance along with decentralization. The key idea with existing layered blockchain protocols in literature is to divide blockchain operations into two layers and use different types of blockchain protocols to manage each layer. However, many such works come with the assumptions of honest majority which may not accurately reflect the real world where the participants may be self-interested or rational. These assumptions may render the protocols susceptible to security threats in the real world, as highlighted by the literature focused on exploring game-theoretic attacks on these protocols. We generalize the “layered” approach taken by existing protocols in the literature and present a framework to analyze the system in the BAR Model and provide a generalized game-theoretic analysis of such protocols. Using our analysis, we identify the critical system parameters required for a distributed ledger’s secure operation in a more realistic setting.

Abstract

Crowdsourcing is an effective method to collect data by employingdistributed human population. Researchers introduce Peer-BasedMechanisms (PBMs) in crowdsourcing settings to incentivize agentsto report accurately. We observe that with PBMs, crowdsourcingsystems may not be fair. Unfair rewards for the agents may discour-age participation. This work aims to build a general frameworkthat assures fairness for PBMs in a temporal setting, i.e., wherereports are time-sensitive. Towards this, we introduce two notionsof fairness for PBMs, namely𝛾-fairnessandqualitative fairness. Tosatisfy these notions, our framework provides trustworthy agentswith additional chances of pairing. We introduce Temporal Reputa-tion Model (TERM) to quantify agents’ trustworthiness across tasks.Having TERM, we present our iterative framework, REFORM, thatcan adopt the reward scheme of any existing PBM. We demonstrateREFORM’s significance by deploying the framework with RPTSC’sreward scheme and prove that REFORM with RPTSC considerablyimproves fairness; while incentivizing truthful and early reports.

Abstract

We consider the problem of achieving fair classification in Federated Learning (FL) under data heterogeneity. Most of the approaches pro- posed for fair classification require diverse data that represent the different demographic groups involved. In contrast, it is common for each client to own data that represents only a single demographic group. Hence the existing approaches cannot be adopted for fair classification models at the client level. To resolve this challenge, we propose several aggregation techniques. We empirically validate these techniques by comparing the resulting fairness and accuracy on CelebA and UTK datasets

Abstract

We consider a budgeted combinatorial multi-armed bandit setting where, in every round, the algorithm selects a super-arm consisting of one or more arms. The goal is to minimize the total expected regret after all rounds within a limited budget. Existing techniques in this literature either fix the budget per round or fix the number of arms pulled in each round. Our setting is more general where based on the remaining budget and remaining number of rounds, the algorithm can decide how many arms to be pulled in each round. First, we propose CBwK-Greedy-UCB algorithm, which uses a greedy technique, CBwK-Greedy, to allocate the arms to the rounds. Next, we propose a reduction of this problem to Bandits with Knapsacks (BwK) with a single pull. With this reduction, we propose CBwK-LP-UCB that uses PrimalDualBwK ingeniously. We rigorously prove regret bounds for CBwK-LP-UCB. We experimentally compare the two algorithms and observe that CBwK-Greedy- UCB performs incrementally better than CBwK-LP-UCB. We also show that for very high budgets, the regret goes to zero.

Abstract

Generative Adversarial Networks (GANs) are by far the most successful generative models. Learning the transformation which maps a low dimensional input noise to the data distribution forms the foundation for GANs. Despite their application in various domains, they are prone to certain challenges like mode collapse and unstable training. To overcome the challenges, researchers have proposed novel loss functions, architectures, and optimization methods. Unlike the previous approaches, we focus on the input noise and its role in the generation in our work here. We aim to quantitatively and qualitatively study the effect of the dimension of the input noise on the performance of GANs. For quantitative measures, typically Fréchet Inception Distance (FID) and Inception Score (IS) are used as performance measure on image data-sets. We compare the FID and IS values for DCGAN and WGAN-GP. We use three different image data-sets – each consisting of different levels of complexity. Our experiments show that the right dimension of input noise for optimal results depends on the data-set and architecture used. We also observe that the state of the art performance measures does not provide enough

Abstract

AI applications find widespread use in a variety of domains. For further acceptance, mostly when multiple agents interact with the system, we must aim to preserve the privacy of participants information in such applications. Towards this, the Yao’s Millionaires’ problem (YMP), i.e., to determine the richer among two millionaires’ privately, finds relevance. This work presents a novel, practical, and verifiable solution to YMP, namely, Secure Comparison Protocol (SCP). We show that SCP achieves this comparison in a constant number of rounds, without using encryption and not requiring the participants’ continuous involvement. SCP uses semi-trusted third parties - which we refer to as privacy accountants - for the comparison, who do not learn any information about the values. That is, the probability of information leak is negligible in the problem size. In SCP, we also leverage the Ethereum network for

Abstract

In classification models fairness can be ensured by solving a constrained optimization problem. We focus on fairness constraints like Disparate Impact, Demographic Parity, and Equalized Odds, which are non-decomposable and non-convex. Researchers define convex surrogates of the constraints and then apply convex optimization frameworks to obtain fair classifiers. Surrogates serve only as an upper bound to the actual constraints, and convexifying fairness constraints might be challenging. We propose a neural network-based framework, FNNC, to achieve fairness while maintaining high accuracy in classification. The above fairness constraints are included in the loss using Lagrangian multipliers. We prove bounds on generalization errors for the constrained losses which asymptotically go to zero. The network is optimized using two-step mini-batch stochastic gradient descent. Our experiments show that FNNC performs as good as the state of the art, if not better. The experimental evidence supplements our theoretical guarantees. In summary, we have an automated solution to achieve fairness in classification, which is easily extendable to many fairness constraints.

Abstract

Around 40% of global energy produced is consumed by buildings. By using renewable energy resources we can alleviate the dependence on electrical grids. Recent trends focus on incentivizing consumers to reduce their demand consumption during peak hours for sustainable demand response. To minimize the loss, the distributor companies should target the right set of consumers and demand the right amount of electricity reductions.This paper proposes a novel bounded integer min-knapsack algorithm and shows that the algorithm, while allowing for multiple unit reduction, also optimizes the loss to the distributor company within a factor of two (multiplicative) and a problem dependent additive constant. Existing CMAB algorithms fail to work in this setting due to nonmonotonicity of reward function and time varying optimal sets. We propose a novel algorithm (TwinMinKPDR-CB) to learn these compliance probabilities efficiently. Twin-MinKPDR-CB works for non-monotone reward functions, bounded minknapsack constraints, and time-varying optimal sets. We find that Twin-MinKPDR-CB achieves sub-linear regret of O(log T) with T being the number of rounds demand response is run.

Abstract

Generative Adversarial Networks (GANs) are by far the most successful generative models. Learning the transformation which maps a low dimensional input noise to the data distribution forms the foundation for GANs. Although they have been applied in various domains, they are prone to certain challenges like mode collapse and unstable training. To overcome the challenges, researchers have proposed novel loss functions, architectures, and optimization methods. In our work here, unlike the previous approaches, we focus on the input noise and its role in the generation. We aim to quantitatively and qualitatively study the effect of the dimension of the input noise on the performance of GANs. For quantitative measures, typically Fr´echet Inception Distance (FID) and Inception Score (IS) are used as performance measure on image data-sets. We compare the FID and IS values for DCGAN and WGAN-GP. We use three different image data-sets – each consisting of different levels of complexity. Through our experiments, we show that the right dimension of input noise for optimal results depends on the data-set and architecture used. We also observe that the state of the art performance measures does not provide enough useful insights. Hence we conclude that we need further theoretical analysis for understanding the relationship between the low dimensional distribution and the generated images. We also require better performance measures.

Abstract

Bitcoin is the first of its kind, a truly decentralized and anonymous cryptocurrency. To realize it, it has developed a blockchain technology using the concept of ‘Proof of Work’ (PoW). The miners, nodes responsible for writing transaction database, solve a cryptographic puzzle to claim the right to write to the database. Though bitcoin and many other relevant cryptocurrencies such as ether use revolutionary ideas, the main criticism involves the computing resource and energy consump- tion to solve the puzzles that have otherwise no use. There are attempts to use the PoW to do something useful, commonly referred to as Proof-of-Useful-Work (PoUW). In this paper, we attempt to (i) make PoUW more usable – describe how a central problem setter can crowdsource their work as PoUW and (ii) in the true spirit of blockchains, decentralize the role of problem setter, whom we call puzzlers. We propose a formal framework to do so, namely PUPoW. PUPoW has an inbuilt provision of payments from puzzler to the miner who solves its puzzle. Additionally, miners have the option to not rely on continuous feed of the puzzles and instead use original PoW puzzles. We also propose a way to use PUPoW for solving TOR vanity URL generation and bitcoin vanity address generation problems. We call this PUPoW blockchain solving vanity address generation problems as VanityCoin. Both the problems need to generate public keys from private keys such that resultant addresses are of interest. Such key pairs are found only by a brute force search. However, there are privacy concerns that miners would know the private keys of the puzzlers. We resolve this by splitting the private keys, and the miners would know only one part of it. In summary, we are proposing how PoW can be made practically useful, and we believe such an approach is needed for PoW blockchains to survive.