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

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

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.

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

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

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

A blockchain, such as Bitcoin, is an append-only, secure, transparent, distributed ledger. A fair blockchain is expected to have healthy metrics; high honest mining power, low processing latency, ie, low wait times for transactions and stable price of consumption, ie, the minimum transaction fee required to have a transaction processed. As Bitcoin matures, the influx of transactions increases and the block rewards become insignificant. We show that under these conditions, it becomes hard to maintain the health of the blockchain. In Bitcoin, under these mature operating conditions (MOC), the miners would find it challenging to cover their mining costs as there would be no more revenue from merely mining a block. It may cause miners not to continue mining, threatening the blockchain's security. Further, as we show in this paper using simulations, the cost of acting in favor of the health of the blockchain, under MOC, is very high in Bitcoin, causing all miners to process transactions greedily. It leads to stranded transactions, ie, transactions offering low transaction fees, experiencing unreasonably high processing latency. To make matters worse, a compounding effect of these stranded transactions is the rising price of consumption. Such phenomena not only induce unfairness as experienced by the miners and the users but also deteriorate the health of the blockchain.

Abstract

For sponsored search auctions, we consider contextual multi-armed bandit problem in the presence of strategic agents. In this setting, at each round, an advertising platform (center) runs an auction to select the best-suited ads relevant to the query posted by the user. It is in the best interest of the center to select an ad that has a high expected value (ie, probability of getting a click value it derives from a click of the ad). The probability of getting a click (CTR) is unknown to the center and depends on the user's profile (context) posting the query. Further, the value derived for a click is the private information to the advertiser and thus needs to be elicited truthfully. The existing solution in this setting is not practical as it suffers from very high regret ().

Abstract

In this paper, we introduce Ballooning Multi-Armed Bandits (BL-MAB), a novel extension to the classical stochastic MAB model. In BL-MAB model, the set of available arms grows (or balloons) over time. In contrast to the classical MAB setting where the regret is computed with respect to the best arm overall, the regret in a BL-MAB setting is computed with respect to the best available arm at each time. We first observe that the existing MAB algorithms are not regret-optimal for the BL-MAB model. We show that if the best arm is equally likely to arrive at any time, a sub-linear regret cannot be achieved, irrespective of the arrival of other arms. We further show that if the best arm is more likely to arrive in the early rounds, one can achieve sub-linear regret. Our proposed algorithm determines (1) the fraction of the time horizon for which the newly arriving arms should be explored and (2) the sequence of arm pulls in the exploitation phase from among the explored arms. Making reasonable assumptions on the arrival distribution of the best arm in terms of the thinness of the distribution's tail, we prove that the proposed algorithm achieves sub-linear instance-independent regret. We further quantify the explicit dependence of regret on the arrival distribution parameters. We reinforce our theoretical findings with extensive simulation results.

Abstract

Despite advances in deep learning and facial recognition techniques, the problem of fault-intolerant facial recognition remains challenging. With the current state of progress in the field of automatic face recognition and the in-feasibility of fully manual recognition, the situation calls for human-machine collaborative methods. We design a system that uses machine predictions for a given face to generate queries that are answered by human experts to provide the system with the information required to predict the identity of the face correctly. We use a Markov Decision Process for which we devise an appropriate query structure and a reward structure to generate these queries in a budget or accuracy-constrained setting. Finally, as we do not know the capabilities of the human experts involved, we model each human as a bandit and adopt a multi-armed bandit approach with consensus queries to efficiently estimate …