Learning rate is a crucial parameter in training of neural networks. A properly tuned learning rate leads to faster training and higher test accuracy. In this paper, we propose a Lipschitz bandit-driven approach for tuning the learning rate of neural networks. The proposed approach is compared with the popular HyperOpt technique used extensively for hyperparameter optimization and the recently developed bandit-based algorithm BLiE. The results for multiple neural network architectures indicate that our method finds a better learning rate using a) fewer evaluations and b) lesser number of epochs per evaluation, when compared to both HyperOpt and BLiE. Thus, the proposed approach enables more efficient training of neural networks, leading to less training time and less computational cost.

We consider a queue-channel model that captures the waiting time-dependent degradation of information bits as they wait to be transmitted. Such a scenario arises naturally in quantum communications, where quantum bits tend to decohere rapidly. Trailing the capacity results obtained recently for certain queue-channels, this paper aims to construct practical channel codes for the erasure queue-channel (EQC)—a channel characterized by highly correlated erasures, governed by the underlying queuing dynamics. Our main contributions in this paper are twofold: (i) We propose a generic ‘wrapper’ based on interleaving across renewal blocks of the queue to convert any capacity-achieving block code for a memoryless erasure channel to a capacity-achieving code for the EQC. Next, due to the complexity involved in implementing interleaved systems, (ii) we study the performance of LDPC and Polar codes without any interleaving. We show that standard Arıkan’s Polar transform polarizes the EQC for certain restricted class of erasure probability functions. We also highlight some possible approaches and the corresponding challenges involved in proving the polarization of a general EQC.

We consider maximizing the long-term average reward in a single server queuing system, where the reward obtained for a job is a non-increasing, possibly nonlinear function of its sojourn time. The motivation behind this work comes from delay-sensitive applications, including quantum information processing and multimedia streaming. Although the goal of optimizing the total sojourn time is well-studied, optimizing a nonlinear function of the sojourn times remains unexplored to the best of our knowledge. We consider two arrival models - the first is a ‘burst arrival’ model, wherein all jobs arrive at the server at the same instant. We show that shortest job first (SJF) maximizes the average reward for any monotonic function of the sojourn times. In the second setting, jobs arrive according to some stochastic process with i.i.d. service requirements. This setting is significantly more challenging to analyze, and identifying an optimal discipline remains elusive. We introduce a new service discipline, shortest predicted sojourn time (SPST), and provide analytical guarantees under specific settings. Numerically, we demonstrate that SPST outperforms well-known disciplines across multiple settings.

User dissatisfaction due to buffering pause during streaming is a significant cost to the system, which we model as a non-decreasing function of the frequency of buffering pause. Minimization of the total user dissatisfaction in a multi-channel cellular network leads to a non-convex problem. By utilizing a combinatorial structure in the problem, we first propose a polynomial time joint admission control and channel allocation algorithm which is provably (almost) optimal. This scheme assumes that the base station (BS) knows the multimedia frame statistics of the streams. In a more practical setting, where these statistics are not available a priori at the BS, a learning based scheme with provable guarantees is developed. This learning based scheme is related to regret minimization in multi-armed bandits with non-i.i.d. and delayed reward (cost). All these algorithms require none to minimal feedback from the user equipment to the base station regarding the states of the media player buffer at the application layer, and hence, are of practical interest.

We propose a methodology to perform process variation-aware device and circuit design using fully physics-based simulations within limited computational resources, without developing a compact model. Machine learning (ML), specifically a support vector regression (SVR) model, has been used. The SVR model has been trained using a dataset of devices simulated a priori, and the accuracy of prediction by the trained SVR model has been demonstrated. To produce a switching time distribution from the trained ML model, we only had to generate the dataset to train and validate the model, which needed ∼500 hours of computation. On the other hand, if 10 6 samples were to be simulated using the same computation resources to generate a switching time distribution from micromagnetic simulations, it would have taken ∼250 days. Spin-transfer-torque random access memory (STTRAM) has been used to demonstrate the method. However, different physical systems may be considered, different ML models can be used for different physical systems and/or different device parameter sets, and similar ends could be achieved by training the ML model using measured device data.

Consider the information-theoretic limits of reliable communication in a multiuser setting of transmission through a system with queue-length dependent service quality. Multiple transmitters dispatch encoded symbols using renewal processes over a system that is a superposition of GIk/GI/1 queues, and a noisy server processes symbols in order of arrival with error probability depending on the queue-length. First, the information capacities of the single-user and multiuser continuous-time queue-length dependent system are found. When the number of transmitters is large and each is sparse, the superposition of arrivals approaches a Poisson point process. In characterizing the Poisson approximation, we show that the individual and sum capacities of the multiuser system converges to the capacity of a single-user M/GI/1 queue-length dependent system. The speed of convergence in the number of users is explicitly given. Further, the best and worst server behaviors of M / G I /1 queues from the single-user case are preserved in the multiuser case.

Due to the unprecedented success of deep neural networks in inference tasks like speech and image recognition, there has been increasing interest in using them in mobile and in-sensor applications. As most current deep neural networks are very large in size, a major challenge lies in storing the network in devices with limited memory. Consequently there is growing interest in compressing deep networks by quantizing synaptic weights, but most prior work is heuristic and lacking theoretical foundations. Here we develop an approach to quantizing deep networks using functional high-rate quantization theory. Under certain technical conditions, this approach leads to an optimal quantizer that is computed using the celebrated backpropagation algorithm. In all other cases, a heuristic quantizer with certain regularization guarantees can be computed.

Due to process variation in nanoscale manufacturing, there may be permanently missing connections in information processing hardware. Due to timing errors in circuits, there may be missed messages in intra-chip communications, equivalent to transiently missing connections. In this paper, we investigate the performance of message-passing LDPC decoders in the presence of missing connections. We prove concentration and convergence theorems that validate the use of density evolution performance analysis. Arbitrarily small error probability is not possible with missing connections, but we find suitably defined decoding thresholds for communication systems with binary erasure channels under peeling decoding, as well as binary symmetric channels under Gallager A and B decoding. We see that decoding is robust to missing wires, as decoding thresholds degrade smoothly. Moreover, there is a stochastic facilitation effect in Gallager B decoders with missing connections. We also conduct finite-length simulations, compare the decoding sensitivity to channel noise and to missing wiring, and perform preliminary error-tolerant manufacturing yield analysis.

We study the information-theoretic limit of reliable information processing by a server with queue-length dependent quality of service. We define the capacity for such a system as the number of bits reliably processed per unit time, and characterize it in terms of queuing system parameters. We also characterize the distributions of the arrival and service processes that maximize and minimize the capacity of such systems in a discrete-time setting. For arrival processes with at most one arrival per time slot, we observed a minimum around the memoryless distribution. We also studied the case of multiple arrivals per time slot, and observed that burstiness in arrival has adverse effects on the system. The problem is theoretically motivated by an effort to incorporate the notion of reliability in queuing systems, and is applicable in the contexts of crowdsourcing, multimedia communication, and stream computing.

Crowdsourcing of jobs to online freelance platforms is rapidly gaining popularity. Most crowdsourcing platforms are uncontrolled and offer freedom to customers and freelancers to choose each other. This works well for unskilled jobs (e.g., image classification) with no specific quality requirement since freelancers are functionally identical. For skilled jobs (e.g., software development) with specific quality requirements, however, this does not ensure that the maximum number of job requests is satisfied. In this paper, we determine the capacity of regulated freelance systems, in terms of maximum satisfied job requests, and propose centralized schemes that achieve capacity. To ensure decentralized operation and freedom for customers and freelancers, we propose simple schemes compatible with the operation of current crowdsourcing platforms that approximately achieve capacity. Furthermore, for settings where the number of job requests exceeds capacity, we propose a scheme that is agnostic of that information, but is optimal and fair in declining jobs without wait.

Many companies now use crowdsourcing to leverage external (as well as internal) crowds to perform specialized work, and so methods of improving efficiency are critical. Tasks in crowdsourcing systems with specialized work have multiple steps and each step requires multiple skills. Steps may have different flexibilities in terms of obtaining service from one or multiple agents, due to varying levels of dependency among parts of steps. Steps of a task may have precedence constraints among them. Moreover, there are variations in loads of different types of tasks requiring different skill-sets and availabilities of different types of agents with different skill-sets. Considering these constraints together necessitates the design of novel schemes to allocate steps to agents. In addition, large crowdsourcing systems require allocation schemes that are simple, fast, decentralized and offer customers (task requesters) the freedom to choose agents. In this work we study the performance limits of such crowdsourcing systems and propose efficient allocation schemes that provably meet the performance limits under these additional requirements. We demonstrate our algorithms on data from a crowdsourcing platform run by a non-profit company and show significant improvements over current practice.

Due to process variation in nanoscale manufacturing, there may be permanently missing connections in information processing hardware. Due to timing errors in circuits, there may be missed messages in intra-chip communications, equivalent to transiently missing connections. In this work, we investigate the performance of message-passing LDPC decoders in the presence of missing connections. We prove concentration and convergence theorems that validate the use of density evolution performance analysis. Arbitrarily small error probability is not possible under miswiring, but we find suitably defined decoding thresholds for communication systems with binary erasure channels and peeling decoders, as well as binary symmetric channels and Gallager A decoders. We see that decoding is robust to missing connections, as decoding thresholds degrade smoothly.

Traditional models in opinion dynamics involve agents updating their opinions based on the opinions of their neighbors in a static social-graph, regardless of their differences in opinions. In contrast, the bounded confidence opinion dynamics does not presume a static interaction graph, and instead models interactions between those agents that share similar opinions (i.e., are close to one another, capturing online discussion groups and conventional meetings). We generalize the bounded confidence opinion dynamics model by incorporating pairwise stochastic interactions based on opinion differences as well as the self or endogenous evolution of the agent opinions, which is represented by a random process. We analytically characterize the conditions under which this stochastic dynamics is stable in an appropriate sense. This characterization relates well to what is observed in social systems. Moreover, this generalization sheds light on dynamics that combine aspects of graph-based updates and bounded confidence models.

Crowdsourcing of jobs to online freelance markets is rapidly gaining popularity. Most crowdsourcing platforms are uncontrolled and offer freedom to customers and freelancers to choose each other. This works well for unskilled jobs (e.g., image classification) with no specific quality requirement since freelancers are functionally identical. For skilled jobs (e.g., software development) with specific requirements, however, this does not ensure the maximum number of job requests is satisfied. In this work we determine the capacity of freelance markets, in terms of maximum satisfied job requests, and propose centralized schemes that achieve capacity. To ensure decentralized operation and freedom of choice for customers and freelancers, we propose simple schemes compatible with the operation of current crowd-sourcing platforms that approximately achieve capacity. Further, for settings where job requests exceed capacity, we propose an optimal and fair scheme for declining jobs without wait.

We study the effect of external infection sources on phase transitions in epidemic processes. In particular, we consider an epidemic spreading on a network via the SIS/SIR dynamics, which in addition is aided by external agents - sources unconstrained by the graph, but possessing a limited infection rate or virulence. Such a model captures many existing models of externally aided epidemics, and finds use in many settings - epidemiology, marketing and advertising, network robustness, etc. We provide a detailed characterization of the impact of external agents on epidemic thresholds. In particular, for the SIS model, we show that any external infection strategy with constant virulence either fails to significantly affect the lifetime of an epidemic, or at best, sustains the epidemic for a lifetime which is polynomial in the number of nodes. On the other hand, a random external-infection strategy, with rate increasing linearly in the number of infected nodes, succeeds under some conditions to sustain an exponential epidemic lifetime. We obtain similar sharp thresholds for the SIR model, and discuss the relevance of our results in a variety of settings.

Recent trends suggest that cognitive radio based wireless networks will be frequency agile and the nodes will be equipped with multiple radios capable of tuning across large swaths of spectrum. The MAC scheduling problem in such networks refers to making intelligent decisions on which communication links to activate at which time instant and over which frequency band. The challenge in designing a low-complexity distributed MAC, that achieves low delay, is posed by two additional dimensions of cognitive radio networks: interference graphs and data rates that are frequency-band dependent, and explosion in number of feasible schedules due to large number of available frequency-bands. In this paper, we propose MAXIMAL-GAIN MAC, a distributed MAC scheduler for frequency agile multi-band networks that simultaneously achieves the following: (i) optimal network-delay scaling with respect to the number of communicating pairs, (ii) low computational complexity of O(log2(maximum degree of the interference graphs)) which is independent of the number of frequency bands, number of radios per node, and overall size of the network, and (iii) robustness, i.e., it can be adapted to a scenario where nodes are not synchronized and control packets could be lost. Our proposed MAC also achieves a throughput provably within a constant fraction (under isotropic propagation) of the maximum throughput. Due to a recent impossibility result, optimal delay-scaling could only be achieved with some amount of throughput loss . Extensive simulations using OMNeT++ network simulator shows that, compared to a multi-band extension of a state-of-art CSMA algorithm (namely, Q-CSMA), our asynchronous algorithm achieves a 2.5x reduction in delay while achieving at least 85% of the maximum achievable throughput. Our MAC algorithms are derived from a novel local search based technique.