The problem of robust multi-hypothesis testing in the Bayesian setting is studied in this paper. Under the$m\geq 2$hypotheses, the data-generating distributions are assumed to belong to uncertainty sets constructed through some moment functions, i.e., the sets contain distributions whose moments are centered around empirical moments obtained from some training data sequences. The goal is to design a test that performs well under all distributions in the uncertainty sets, i.e., a test that minimizes the worst-case probability of error over the uncertainty sets. Insights on the need for optimization-based approaches to solve the robust testing problem with moment constrained uncertainty sets are provided. The optimal (robust) test based on the optimization approach is derived for the case where the observations belong to a finite-alphabet. When the size of the alphabet is infinite, the optimization problem is infinite-dimensional and intractable, and therefore a tractable finite-dimensional approximation is proposed, whose optimal value converges to the optimal value of the original problem as the size of the dimension of the approximation goes to infinity. A robust test is constructed from the solution to the approximate problem, and guarantees on its worst-case error probability over the uncertainty sets are provided. Numerical results are provided to demonstrate the performance of the proposed robust test.

The problem of robust binary hypothesis testing is studied. Under both hypotheses, the data-generating distributions are assumed to belong to uncertainty sets constructed through moments; in particular, the sets contain distributions whose moments are centered around the empirical moments obtained from training observations. The goal is to design a test that performs well under all distributions in the uncertainty sets, i.e., minimize the worst-case error probability over the uncertainty sets. In the finite-alphabet case, the optimal test is obtained. In the infinite-alphabet case, a tractable approximation to the worst-case error is derived that converges to the optimal value A test is further constructed to generalize to the entire alphabet. An exponentially consistent test for testing batch samples is also proposed. Numerical results are provided to demonstrate the performance of the proposed robust tests.

Compressed Stochastic Gradient Descent (SGD) algorithms have been proposed to address the communication bottleneck in distributed and decentralized optimization problems such as federated machine learning. Many existing compressed SGD algorithms use non-adaptive step-sizes (constant or diminishing) to provide theoretical convergence guarantees. Since non-adaptive step-sizes typically involve unknown system parameters, the step-sizes are fine-tuned in practice to obtain good empirical performance for the given dataset and learning model. Such fine-tuning might be impractical in many scenarios. Thus, it is of interest to study compressed SGD using adaptive step-sizes. Motivated by prior work that use adaptive step-sizes for uncompressed SGD, we develop an Armijo rule based step-size selection method for compressed SGD. In particular, we introduce a scaling technique for the descent step, which we use to establish order-optimal convergence rates for convex-smooth and strong convex-smooth objectives under an interpolation condition, and for non-convex objectives under a strong growth condition. We present experimental results on deep neural networks trained on real-world datasets, and compare the performance of our proposed algorithm with state-of-the-art compressed SGD methods to demonstrate improved performance at various levels of compression.

We study the problem of Out-of-Distribution (OOD) detection, that is, detecting whether a Machine Learning (ML) model's output can be trusted at inference time. While a number of tests for OOD detection have been proposed in prior work, a formal framework for studying this problem is lacking. We propose a definition for the notion of OOD that includes both the input distribution and the ML model, which provides insights for the construction of powerful tests for OOD detection. We also propose a multiple hypothesis testing inspired procedure to systematically combine any number of different statistics from the ML model using conformal p-values. We further provide strong guarantees on the probability of incorrectly classifying an in-distribution sample as OOD. In our experiments, we find that threshold-based tests proposed in prior work perform well in specific settings, but not uniformly well across different OOD instances. In contrast, our proposed method that combines multiple statistics performs uniformly well across different datasets and neural networks.

We study the problem of out-of-distribution (OOD) detection, that is, detecting whether a machine learning (ML) model's output can be trusted at inference time. While a number of tests for OOD detection have been proposed in prior work, a formal framework for studying this problem is lacking. We propose a definition for the notion of OOD that includes both the input distribution and the ML model, which provides insights for the construction of powerful tests for OOD detection. We also propose a multiple hypothesis testing inspired procedure to systematically combine any number of different statistics from the ML model using conformal p-values. We further provide strong guarantees on the probability of incorrectly classifying an in-distribution sample as OOD. In our experiments, we find that threshold-based tests proposed in prior work perform well in specific settings, but not uniformly well across different OOD instances. In contrast, our proposed method that combines multiple statistics performs uniformly well across different datasets and neural networks architectures.

We consider a fully decentralized multi-player stochastic multi-armed bandit setting where the players cannot communicate with each other and can observe only their own actions and rewards. The environment may appear differently to different players, i.e., the reward distributions for a given arm are heterogeneous across players. In the case of a collision (when more than one player plays the same arm), we allow for the colliding players to receive non-zero rewards. The time-horizon T for which the arms are played is not known to the players. Within this setup, where the number of players is allowed to be greater than the number of arms, we present a policy that achieves near order-optimal expected regret of order O(log1+δ T) for δ > 0 (however small) over a time-horizon of duration T.