ABSTRACT. INVITED Paper #0659; Session Code BHRS4 - Optimal scheduling to minimize mean response time is well understood for a single-server queue. However much less is known for multi-server queueing systems. In the worst-case adversarial setting, it is impossible to get anywhere near optimal scheduling and load balancing for multi-server queueing systems. In this talk we instead approach optimality from the perspective of the stochastic setting where job sizes and arrivals are drawn from general distributions. In the stochastic setting, we derive the first optimal scheduling policies for the two most common multi-server architectures.

This talk is based on two papers, both of which won Best Student Paper Awards: 1) Grosof, Scully, Harchol-Balter. "Load Balancing Guardrails: Keeping Your Heavy Traffic on the Road to Low Response Times." POMACS/SIGMETRICS: Volume 3, Issue 2, Article 42 (June 2019), pp. 42:1 -- 42:31. 2) Grosof, Scully, Harchol-Balter. "SRPT for Multiserver Systems." Performance Evaluation, vol. 127-128, Nov. 2018, pp. 154-175. Also appeared in IFIP PERFORMANCE 2018, Toulouse, France. An earlier version of this talk was invited to STOC 2021's TheoryFest as a mini-keynote.

ABSTRACT. Today's datacenters need to serve jobs whose resource requirements vary over time. The existence of such jobs makes it hard to fully utilize resources while not exceeding capacity constraints. The exact trade-off between utilization and capacity violation is not well-understood in the literature. In this paper, we study an infinite-server computing system where each server has a finite resource capacity, and jobs have time-varying resource requirements. Our goal is to design a job assigning policy that minimizes the number of occupied servers while keeping the cost of capacity violation within a certain budget. We propose a novel framework that reduces the policy design problem under study to a problem in a single-server system through policy conversion techniques. This allows us to design an asymptotically optimal policy by solving a simple linear programming problem.

ABSTRACT. We expose the danger of reward poisoning in offline multi-agent reinforcement learning (MARL), whereby an attacker can modify the reward vectors to different learners in an offline data set while incurring a poisoning cost. Based on the poisoned data set, all rational learners using some confidence-bound-based MARL algorithm will infer that a target policy – chosen by the attacker and not necessarily a solution concept originally – is the Markov perfect dominant strategy equilibrium for the underlying Markov Game, hence they will adopt this potentially damaging target policy in the future. We characterize the exact conditions under which the attacker can install a target policy. We further show how the attacker can formulate a linear program to minimize its poisoning cost. Our work shows the need for robust MARL against adversarial attacks.

ABSTRACT. We study offline reinforcement learning (RL), which aims to learn an optimal policy based on a dataset collected a priori. Due to the lack of further interactions with the environment, offline RL suffers from the insufficient coverage of the dataset, which eludes most existing theoretical analysis. In this paper, we propose a pessimistic variant of the value iteration algorithm (PEVI), which incorporates an uncertainty quantifier as the penalty function. Such a penalty function simply flips the sign of the bonus function for promoting exploration in online RL, which makes it easily implementable and compatible with general function approximators.

Without assuming the sufficient coverage of the dataset, we establish a data-dependent upper bound on the suboptimality of PEVI for general Markov decision processes (MDPs). When specialized to linear MDPs, it matches the information-theoretic lower bound up to multiplicative factors of the dimension and horizon. In other words, pessimism is not only provably efficient but also minimax optimal. In particular, given the dataset, the learned policy serves as the "best effort" among all policies, as no other policies can do better. Our theoretical analysis identifies the critical role of pessimism in eliminating a notion of spurious correlation, which emerges from the "irrelevant" trajectories that are less covered by the dataset and not informative for the optimal policy.

Joint work with Ying Jin (Stanford) and Zhuoran Yang (Yale).

ABSTRACT. Off-chain transaction channels represent one of the leading techniques to scale the transaction throughput in cryptocurrencies. However, the economic effect of transaction channels on the system has not been explored much until now.

We study the economics of Bitcoin transaction channels, and present a framework for an economic analysis of the lightning network and its effect on transaction fees on the blockchain. Our framework allows us to reason about different patterns of demand for transactions and different topologies of the lightning network, and to derive the resulting fees for transacting both on and off the blockchain.

Our initial results indicate that while the lightning network does allow for a substantially higher number of transactions to pass through the system, it does not necessarily provide higher fees to miners, and as a result may in fact lead to lower participation in mining within the system.

ABSTRACT. This paper considers second-order achievable rate regions for two-user, single antenna, static Gaussian Broadcast channels with individual user error constraints. Even though the channel is stochastically degraded, we surprisingly show that the "usual" infinite blocklength superposition order in which the user with the higher Signal to Noise Ratio (SNR) is superimposed on top of the lower SNR user, does not necessarily lead to the largest second-order achievable rates. This suggests that a careful consideration of user requirements, in addition to channel conditions, is required in designing broadcasting schemes with a fixed blocklength and per-user reliability requirements.

ABSTRACT. The problem of multi-user commitment is one in which multiple users first commit to individual messages with a bookmaker and later reveal their messages. The objective of the bookmaker is then to decide whether the revealed messages correspond to the committed messages. We study a specific multiuser commitment model in which the users and the bookmaker have access to a noiseless channel, as well as a noisy multipleaccess channel whose inputs are controlled by the users and whose output is observed by the bookmaker. When the users are non-colluding and the channel is non-redundant, we fully characterize the commitment capacity region. When the users are colluding, we derive an achievable region and a tight converse for the sum-rate. In both cases our proposed achievable commitment schemes are constructive.

ABSTRACT. Channel assignment for wireless radios employing random access is found in several contexts, including low-power wide area network (LPWAN) protocols such as LoRaWAN. This paper considers the assignment of a set of $N$ colocated random access radios, each with offered load $\chi$, to $M$ identical wireless channels with the objective of maximizing the sum throughput, subject to the classical collision model in which a transmission attempt is successful if it is the only attempt in that time slot on that channel. The approximately optimal throughput assignment is characterized, where the approximation is due to the integrality relaxation of the combinatorial problem, in terms of $(N,M,\chi)$.

ABSTRACT. The work of Witsenhausen explores conditions under which two non-interactive users observing different coordinates of an i.i.d random process, can reach asymptotic agreement. Witsenhausen considers two scenarios: one in which both users observe a finite sequence with an error probability in the limit, and the second in which both users observe infinite-length sequences. In both cases, it turns out that perfect agreement is possible if and only if the joint distribution has a special decomposable structure known as a Gacs-Korner common part. This paper revisits Witsenhausen's work and makes two contributions. First, we show that both results are equivalent, that each implies the other. Second, we offer a new proof of the second result, that unlike the others, avoids any tensorizing arguments or manipulations of multi-letter information measures. We explain how this new converse might overcome some of the obstacles commonly encountered in the classical converse arguments.

ABSTRACT. In recent years, the Multi-message Private Information Retrieval (MPIR) problem has received significant attention from the research community. In this problem, a user wants to privately retrieve $D$ messages out of $K$ messages whose identical copies are stored on $N$ remote servers, while maximizing the download rate. The MPIR schemes can find applications in many practical scenarios and can serve as an important building block for private computation and private machine learning applications. The existing solutions for MPIR require a large degree of subpacketization, which can result in large overheads, high complexity, and impose constraints on the system parameters. These factors can limit practical applications of the existing solutions. In this paper, we present a methodology for the design of scalar-linear MPIR schemes. Such schemes are easy to implement in practical systems as they do not require partitioning of messages into smaller size sub-messages and do not impose any constraints on the minimum required size of the messages. Focusing on the case of $N=D+1$, we show that when $D$ divides $K$, our scheme achieves the capacity, where the capacity is defined as the maximum achievable download rate. When the divisibility condition does not hold, the performance of our scheme is the same or within a small additive margin compared to the best known scheme that requires a high degree of subpacketization.

ABSTRACT. CT imaging works by reconstructing an object of interest from a collection of projections. Traditional methods such as filtered-back projection (FBP) work on projection images acquired around a fixed rotation axis. However, for some CT problems, it is desirable to perform a joint reconstruction from projection data acquired from multiple rotation axes.

In this paper, we present Multi-Pose Fusion, a novel algorithm that performs a joint tomographic reconstruction from CT scans acquired from multiple poses of a single object, where each pose has a distinct rotation axis. Our approach uses multi-agent consensus equilibrium (MACE), an extension of plug-and-play, as a framework for integrating projection data from different poses. We apply our method on simulated data and demonstrate that Multi-Pose Fusion can achieve a better reconstruction result than single pose reconstruction.

ABSTRACT. We provide the first global optimization landscape analysis of Neural Collapse -- an intriguing empirical phenomenon that arises in the last-layer classifiers and features of neural networks during the terminal phase of training. As recently reported by Papyan et al., this phenomenon implies that (i) the class means and the last-layer classifiers all collapse to the vertices of a Simplex Equiangular Tight Frame (ETF) up to scaling, and (ii) cross-example within-class variability of last-layer activations collapses to zero. We study the problem based on a simplified unconstrained feature model, which isolates the topmost layers from the classifier of the neural network. In this context, we show that the classical cross-entropy loss with weight decay has a benign global landscape, in the sense that the only global minimizers are the Simplex ETFs while all other critical points are strict saddles whose Hessian exhibit negative curvature directions. In contrast to existing landscape analysis for deep neural networks which is often disconnected from practice, our analysis of the simplified model not only does it explain what kind of features are learned in the last layer, but it also shows why they can be efficiently optimized in the simplified settings, matching the empirical observations in practical deep network architectures. These findings could have profound implications for optimization, generalization, and robustness of broad interests. For example, our experiments demonstrate that one may set the feature dimension equal to the number of classes and fix the last-layer classifier to be a Simplex ETF for network training, which reduces memory cost by over 20% on ResNet18 without sacrificing the generalization performance.

ABSTRACT. Unsupervised learning from limited and corrupted measurements is a fundamental problem in signal processing and machine learning. The recent deep image prior (DIP) approach shows promising results when learning a deep network (clean) image generator directly from limited and corrupted data. However, because the network used is often highly overparameterized and is prone to overfitting the artifacts in the observations, techniques such as early stopping are needed to prevent overfitting. This phenomenon is also related to the inherent spectral bias of the generative network that makes it easier to fit lower frequency components of the data. To deal with these challenges, we propose to use very few unpaired clean images to guide the rapid learning of high-frequency content in DIP without overfitting the noise. Our studies show that the approach can enable quicker convergence of DIP and much better image estimates than current methods, and alleviate the overfitting to noise. In the meanwhile, we also control the Lipschitz constant of the network layers by orthogonal weight regularization, as inspired by recent works for alleviating overfitting. We demonstrate the superior performance of the proposed methods on several biomedical image reconstruction tasks, such as image denoising and magnetic resonance image reconstruction from limited measurements.

*Shijun Liang, Xiang Li, and Avrajit Ghosh were equal contributors.

ABSTRACT. In many inverse problems, measurements are collected at sampling rates far below Nyquist. As a result, there exist many plausible signals that are consistent with a given set of measurements. There is growing interest in designing methods that can sample from the full posterior distribution, as opposed to generating just a single (e.g., MAP or MMSE) signal estimate. The state-of-the-art methods use Langevin dynamics, which---in imaging applications---can take minutes to generate a single posterior sample. We propose a regularized conditional Wasserstein GAN that can generate hundreds of posterior samples per second. Our novel regularization uses a finite-sample L1 penalty and standard-deviation reward that are weighted such that the batches minimizing the regularization term have the same mean and variance as the true posterior. Using quantitative evaluation metrics like PSNR, SSIM, and conditional Frechet distance, we demonstrate that our method produces posterior samples of fastMRI images with quality and diversity that exceeds Langevin dynamics.

ABSTRACT. The paper concerns bias and asymptotic statistics for stochastic approximation (SA) driven by Markovian noise that is geometrically ergodic. The goal is the same as posed by Robbins and Monro in the 1950s: solve a root finding problem, subject to noisy observations. These algorithms are central to many problems in machine learning, and in particular reinforcement learning.

Recent work demonstrates a surprising approach based on a fixed step-size implementation of SA, combined with simple averaging (the famed averaging technique of Polyak and Ruppert). It is shown for linear recursions that the resulting convergence rate is optimal, with zero bias. In nonlinear settings the picture is nearly as perfect, but there is a small correction that vanishes as the square of the gain. The key assumption is that the observation noise is white.

This paper reviews these contributions, and the approximations from which they are based. It is demonstrated that these optimistic conclusions typically fail for SA with Markovian noise. The main conclusions are summarized as follows:

1. Subject to stability of the mean flow (a Lipschitz bound, or stability of the "ODE at infinity", it is shown that the pair process [parameter and Markovian state] is stable, in the sense of quick transients and a uniform exponential moment for the parameter process.

2. The bias and variance of the parameter process are each of order O(a), with a equal to the fixed step-size

3. The representations leading to stability easily lead to attractive bounds in the case of additive white noise.

4. It is argued that additive white noise is rare in many applications, and bias and variance are of order O(a). There is no evidence that averaging can improve the situation.

5. Finally, if by design a white noise model can be constructed, it is argued that far better algorithmic performance can be obtained using an alternative grounded in quasi Monte Carlo.

ABSTRACT. Deep Reinforcement Learning (RL) methods pro- duce often performance-leading controllers. Yet, in many ap- plications (e.g., when safety and assurance are critical), they cannot be deployed. Deep Neural Nets (DNN) controllers are nearly impossible to verify and their behavior hard to interpret. In this paper, we first show, through a simple example, that there exist soft decision tree (SDT) controllers that are equivalent to neural network (NN) controllers in terms of input- output behavior. Based on imitation learning, we then show via three OpenAI gym environment case studies that it is possible to distill high-performance DNN controllers into non-DNN controllers (e.g., leveraging decision tree and support vector machine architectures) that, while sacrificing performance just a bit, can be simpler, more interpretable, hence amenable to verification and validation. We thus propose the natural control design paradigm that leverages the power of deep RL methods to design reference DNN controllers, and then distill them into non-DNN controllers which can be validated and deployed in real systems. Finally, we identify some distillation metrics that can be useful in assessing the quality of the distilled controllers.

ABSTRACT. We introduce the problem of learning a distribution of user preferences over a set of items from noisy responses to distance queries. Rather than aiming to learn the preferences of each user, our goal is only to recover the overall distribution of user preferences. We show that distribution recovery can require just one response from each user. In contrast, learning the preferences of each user would require multiple responses from each user. Thus, learning preference distributions, rather than individual preferences, may be more practical in many applications. The preference distribution problem is formulated on a discrete domain in which items (e.g., products) and users' ideal preference points are located. We study both the noiseless and noisy settings in one dimension and provide sufficient conditions for identifiability of the underlying true distribution as a function of the set of items used for queries. We establish an upper bound on the total variation distance between the true distribution and the distribution learned via constrained least squares optimization problem for both noiseless and noisy settings. While the one-dimensional setting we consider is simple, our simulation results show that our proposed recovery technique extends to multidimensional settings and graph structures.

ABSTRACT. The stereotypical ML problem setup involves training and test datasets that contain the same set of features with which to make predictions. In ranking problems specifically, however, these datasets are derived from past logs of user behavior; these logs also naturally contain acausal information. In a web search setting, for example, logs contain the position of the item that was clicked on by a user; in an e-commerce setting, logs contain information about which other items a user clicked on, in addition to the item she ended up purchasing. Position, or "was clicked but not purchased", are clearly not usable features at prediction time, when a new ranked list has to be produced. In this work we show that such acausal features, while not directly usable, can be meaningfully leveraged via distillation: first train a "teacher" model = that uses these acausal features, and then use it to train a student model that does not use them. We first show empirically that this process yields a better final ranker, on 3 moderate-scale open-source ranking datasets, and a proprietary large-scale Amazon dataset. We then develop a simple analytical model to rigorously examine and explain when acausal features can help, and when they cannot.

ABSTRACT. We consider the problem of discrimination between two pure quantum states. It is well known that the optimal measurement under both the error-probability and log-loss criteria is a projection, while under an ``erasure-distortion'' criterion it is a three-outcome positive operator-valued measure (POVM). These results were derived separately. We present a unified approach which finds the optimal measurement under any distortion measure that satisfies a convexity relation with respect to the Bhattacharyya distance. Namely, whenever the measure is relatively convex (resp. concave), the measurement is the projection (resp. three-outcome POVM) above. The three above-mentioned results are obtained as special cases of this simple derivation. A special setting of great practical interest, is the discrimination between two coherent-light waveforms. In a remarkable work by Dolinar it was shown that a simple detector consisting of a photon counter and a feedback-controlled local oscillator obtains the quantum-optimal error probability. Later it was shown that the same detector (with the same local signal) is also optimal in the log-loss sense. By applying a similar convexity approach, we obtain in a unified manner the optimal signal for a variety of criteria.

ABSTRACT. Saddle-point problems appear in various settings including machine learning, zero-sum stochastic games, and regression problems. We consider decomposable saddle-point problems and study an extension of the alternating direction method of multipliers to such saddle-point problems. Instead of solving the original saddle-point problem directly, this algorithm solves smaller saddle-point problems by exploiting the decomposable structure. We show the convergence of this algorithm for convex-concave saddle-point problems under a mild assumption. We also provide a sufficient condition for which the assumption holds. We demonstrate the convergence properties of the saddle-point alternating direction method of multipliers with numerical examples on a power allocation problem in communication channels and a network routing problem with adversarial costs.

ABSTRACT. The growth in sizes of large-scale systems and data in machine learning have made distributed optimization a naturally appealing technique to solve decision problems in different contexts. In such methods, each agent iteratively carries out computations on its local objective using information received from its neighbors, and shares relevant information with neighboring agents. Though gradient-based methods are widely used because of their simplicity, they are known to have slow convergence rates. On the other hand, though Newton-type methods have better convergence properties, they are not as applicable because of the enormous computation and memory requirements. In this work, we introduce a distributed quasi-Newton method with Barzilai-Borwein step-sizes. We prove a Q-linear convergence to the optimal solution, present conditions under which the algorithm is superlinearly convergent and validate our results via numerical simulations.

ABSTRACT. Regret has been widely adopted as the metric of choice for evaluating the performance of online optimization algorithms for distributed, multi-agent systems. However, variations in data or model associated with each agent can significantly impact decisions, and requires consensus among agents. Moreover, most existing works have focused on developing approaches for (strongly) convex losses, and very few results have been obtained in terms of regret bounds in distributed online optimization for general non-convex losses. To address these two issues, we propose a novel composite regret with a new network-based metric to evaluate distributed online optimization algorithms. We concretely define static and dynamic forms of the composite regret. By leveraging the dynamic form of our composite regret, we develop a consensus-based online normalized gradient (CONGD) approach for pseudo-convex losses and then show a sublinear behavior for CONGD relating to a regularity term for the path variation of the optimizer. For general nonconvex losses, we first explore the regrets defined based on the recent advances such that no deterministic algorithm can achieve the sublinear regret. We then develop the distributed online nonconvex optimization with composite regret (DINOCO) without access to the gradients, depending on an offline optimization oracle. We show that DINOCO can achieve sublinear regret; to our knowledge, this is the first regret bound for general distributed online non-convex learning.

ABSTRACT. As the demand of plug-in electric vehicles (EVs) grows rapidly, the corresponding charging infrastructures are expanding. These charging stations are located at various places and with different congestion levels. An important choice faced by an EV driver is to decide which charging station to go in order to reduce the overall charging time. Due to the physical characteristics of an EV battery, charging rate is typically reduced as the battery charges. This feature is often overlooked in the existing literature. In this paper, we study the charging station choice problem for EV drivers in a stylized model with two charging stations with explicit modeling of charging rate variations over time. Specifically, we study how different locations and remaining battery capacities of EVs affect their choices of charging stations under various charging rate functions. We analytically characterize the equilibrium strategies and find that co-located EVs may make different decisions depending on the charging function and/or remaining battery levels. Furthermore, we investigate numerically the impact of modeling parameters on the charging decisions.

ABSTRACT. The sum-rank metric can be seen as a generalization of the rank and the Hamming metric. It is well known that sum-rank metric codes outperform rank metric codes in terms of the required field size to construct maximum distance separable codes (i.e., the codes achieving the Singleton bound in the corresponding metric). In this work, we investigate the covering property of sum-rank metric codes to enrich the theory of sum-rank metric codes. We intend to answer the question: what is the minimum cardinality of a code given a sum-rank covering radius. We show the relations of this quantity between different metrics and provide several lower and upper bounds for sum-rank metric codes.

ABSTRACT. The index coding problem is concerned with the amount of information that a sender has to transmit to multiple receivers in a way that enables each of them to retrieve its requested data relying on prior side information. For linear index coding, the problem is characterized by the minrank parameter of a graph that represents the side information map of the receivers. Previous work has shown that it is NP-hard to determine the minrank parameter of graphs. In this work, we study the computational complexity of the minrank parameter on perturbed instances, obtained from worst-case instances by a random extension of the side information available to the receivers. This setting is motivated by applications of index coding, where the side information is accumulated via repeated transmissions that suffer from loss of data due to noisy communication or storage capacity. We prove that determining the minrank parameter remains computationally hard on perturbed instances. Our contribution includes an extension of several hardness results of the minrank parameter to the perturbed setting as well as a general technique for deriving the hardness of the minrank parameter on perturbed instances from its hardness on worst-case instances.

ABSTRACT. We present a general technique for constructing schemes for a broad class of private information retrieval (PIR) problems. Our technique is inspired by polynomial code constructions utilized for secure distributed matrix multiplication and is applicable to a broad range of PIR problems. We showcase our technique by reducing the problem of scheme constructions for PIR from coded storage and colluding servers to a combinatorial problem of designing a degree table that needs to satisfy certain properties. We then present simple schemes for PIR from coded storage and colluding servers which, for certain cases, achieve the best known rates in the asymptotic regime. Our results show that the degree table is a powerful tool for constructing PIR codes for a variety of settings of practical interest.

ABSTRACT. A cumbersome operation in many scientific fields, is inverting large full-rank matrices. In this paper, we propose a coded computing approach for recovering matrix inverse approximations. We first present an approximate matrix inversion algorithm which does not require a matrix factorization, but uses a black-box least squares optimization solver as a subroutine, to give an estimate of the inverse of a real full-rank matrix. We then present a distributed framework for which our algorithm can be implemented, and show how we can leverage sparsest-balanced MDS generator matrices to devise matrix inversion coded computing schemes. We focus on balanced Reed-Solomon codes, which are optimal in terms of computational load; and communication from the workers to the master server. We also discuss how our algorithms can be used to compute the pseudoinverse of a full-rank matrix, and how the communication is secured from eavesdroppers.

ABSTRACT. We provide a new numerical procedure for constructing low coherence matrices, Trust-Region Stochastic Tuning for Matrix Incoherence (TRSTMI) and detail the results of experiments with a CPU/GPU parallelized implementation of this method. These trials suggest the superiority of this approach over other existing methods when the size of the matrix is large. We also present new conjectures on optimal complex matrices motivated and guided by the experimental results.

ABSTRACT. We present achievable error exponents for the AWGN channel with one bit noiseless feedback and an almost-sure power constraint. As in Forney's decision feedback approach for discrete memoryless channels, the backward channel is used to request retransmissions from the transmitter whenever an erasure is declared at the decoder. Our erasure/re-transmission-request scheme introduces a novel erasure decoding rule built on top of a lattice-based code inspired by De Buda. Numerically, our scheme is seen to outperform the sphere packing bound (valid for block codes) at lower rates and higher SNRs.