More Like this

1. Convex Bounds on the Softmax Function with Applications to Robustness Verification

   Wei, Dennis; Wu, Haoze; Wu, Min; Chen, Pin-Yu; Barrett, Clark; Farchi, Eitan (April 2023, Proceedings of Machine Learning Research)

   Ruiz, Francisco; Dy, Jennifer; van de Meent, Jan-Willem (Ed.)

   The softmax function is a ubiquitous component at the output of neural networks and increasingly in intermediate layers as well. This paper provides convex lower bounds and concave upper bounds on the softmax function, which are compatible with convex optimization formulations for characterizing neural networks and other ML models. We derive bounds using both a natural exponential-reciprocal decomposition of the softmax as well as an alternative decomposition in terms of the log-sum-exp function. The new bounds are provably and/or numerically tighter than linear bounds obtained in previous work on robustness verification of transformers. As illustrations of the utility of the bounds, we apply them to verification of transformers as well as of the robustness of predictive uncertainty estimates of deep ensembles. 

   more » « less
2. Moment Multicalibration for Uncertainty Estimation

   Jung, Christopher; Lee, Changhwa; Pai, Mallesh M; Roth, Aaron; Vohra, Rakesh (January 2021, Conference on Learning Theory (COLT) 2021)

   We show how to achieve the notion of "multicalibration" from Hébert-Johnson et al. [2018] not just for means, but also for variances and other higher moments. Informally, it means that we can find regression functions which, given a data point, can make point predictions not just for the expectation of its label, but for higher moments of its label distribution as well-and those predictions match the true distribution quantities when averaged not just over the population as a whole, but also when averaged over an enormous number of finely defined subgroups. It yields a principled way to estimate the uncertainty of predictions on many different subgroups-and to diagnose potential sources of unfairness in the predictive power of features across subgroups. As an application, we show that our moment estimates can be used to derive marginal prediction intervals that are simultaneously valid as averaged over all of the (sufficiently large) subgroups for which moment multicalibration has been obtained. 

   more » « less
3. Reasoning about Uncertainties in Discrete-Time Dynamical Systems using Polynomial Forms

   Sankaranarayanan, Sriram; Chou, Yi; Goubault, Eric; and Putot, Sylvie (December 2020, Advances in Neural Information Processing System (NeurIPS))

   null (Ed.)

   In this paper, we propose polynomial forms to represent distributions of state variables over time for discrete-time stochastic dynamical systems. This problem arises in a variety of applications in areas ranging from biology to robotics. Our approach allows us to rigorously represent the probability distribution of state variables over time, and provide guaranteed bounds on the expectations, moments and probabilities of tail events involving the state variables. First we recall ideas from interval arithmetic, and use them to rigorously represent the state variables at time t as a function of the initial state variables and noise symbols that model the random exogenous inputs encountered before time t. Next we show how concentration of measure inequalities can be employed to prove rigorous bounds on the tail probabilities of these state variables. We demonstrate interesting applications that demonstrate how our approach can be useful in some situations to establish mathematically guaranteed bounds that are of a different nature from those obtained through simulations with pseudo-random numbers. 

   more » « less
4. Reasoning about Uncertainties in Discrete-Time Dynamical Systems using Polynomial Forms.

   Sankaranarayanan, Sriram; Chou, Yi; Goubault, Eric; Putot, Sylvie (December 2020, Part of Advances in Neural Information Processing Systems 33 (NeurIPS 2020))

   In this paper, we propose polynomial forms to represent distributions of state variables over time for discrete-time stochastic dynamical systems. This problem arises in a variety of applications in areas ranging from biology to robotics. Our approach allows us to rigorously represent the probability distribution of state variables over time, and provide guaranteed bounds on the expectations, moments and probabilities of tail events involving the state variables. First, we recall ideas from interval arithmetic, and use them to rigorously represent the state variables at time t as a function of the initial state variables and noise symbols that model the random exogenous inputs encountered before time t. Next, we show how concentration of measure inequalities can be employed to prove rigorous bounds on the tail probabilities of these state variables. We demonstrate interesting applications that demonstrate how our approach can be useful in some situations to establish mathematically guaranteed bounds that are of a different nature from those obtained through simulations with pseudo-random numbers. 

   more » « less
5. Fast Hausdorff Moment Transforms for Meta Distributions in Wireless Networks

   https://doi.org/10.1109/TWC.2023.3300841  

   Wang, Xinyun; Haenggi, Martin (April 2024, IEEE Transactions on Wireless Communications)

   In the analysis of wireless networks, the standard signal-to-interference (SIR) distribution does not capture the performance at the individual link level. The meta distribution (MD) of the SIR resolves this problem by separating different sources of randomness, such as fading and point process(es). While it allows for a much sharper performance characterization, it can in most cases only be calculated based on the moments of the underlying conditional distribution, i.e., by solving a Hausdorff moment problem. Several methods to reconstruct MDs from the moments have been proposed but a rigorous analysis, comparison of their performance, and practical implementations are missing. In addition, a standard is needed for a consistent and objective comparison. This paper addresses the above-mentioned important shortcomings, introduces a tweaking mapping for adjusting approximations, presents terminology to categorize the quality of approximations, proposes the use of the Fourier- Legendre method, which has not previously been applied to MDs, and provides the achievable lower and upper bounds on the MD given the first 𝑛 moments. Further, to facilitate the use of MDs, we give comprehensive guidance on the selection of the best method to determine MDs, and we offer ready-to-use implementations of the proposed algorithms. This study fills an important gap in the literature by rigorously analyzing the MDs, comparing the performance of different methods, and offering user-friendly implementations for recovering MDs from moments. 

   more » « less