More Like this

1. On Efficient Range-Summability of IID Random Variables in Two or Higher Dimensions

   Jingfan Meng, Huayi Wang (January 2023, 26th International Conference on Database Theory (ICDT 2023))

   d-dimensional (for d > 1) efficient range-summability (dD-ERS) of random variables (RVs) is a fundamental algorithmic problem that has applications to two important families of database problems, namely, fast approximate wavelet tracking (FAWT) on data streams and approximately answering range-sum queries over a data cube. Whether there are efficient solutions to the dD-ERS problem, or to the latter database problem, have been two long-standing open problems. Both are solved in this work. Specifically, we propose a novel solution framework to dD-ERS on RVs that have Gaussian or Poisson distribution. Our dD-ERS solutions are the first ones that have polylogarithmic time complexities. Furthermore, we develop a novel k-wise independence theory that allows our dD-ERS solutions to have both high computational efficiencies and strong provable independence guarantees. Finally, we show that under a sufficient and likely necessary condition, certain existing solutions for 1D-ERS can be generalized to higher dimensions. 

   more » « less
2. Generators for Large-Scale Stochastic Simulation-Optimization Experiments

   Oswalt, R; Eckman, D J (April 2025, Proceedings of SW25: The OR Society’s 12th Simulation Workshop)

   Harper, A; Luis, M; Monks, T; Mustafee, N (Ed.)

   Running stochastic simulation-optimization solvers on a testbed of diverse problem instances allows users to evaluate their empirical performance, but obtaining meaningful results requires executing many replications. When problem instances feature realistic simulators, the associated computational costs are often prohibitively expensive. Cheaper, synthetic problem instances generally fail to preserve essential aspects of simulators, and a solver’s performance on them may not be representative of its performance in practice. We propose a novel class of problem instance designed to imitate important features of simulation test problems and generate representative solver performance data at relatively low computational cost. We augment existing models predominantly used for emulation, namely, Gaussian processes, generalized lambda models, and kernel regression models, with an approximation of a Gaussian copula process. This adaptation facilitates efficient coordinated sampling across solutions (via common random numbers) and across solvers (via the sharing of sample-path functions) while keeping the number of user-specified parameters manageable. 

   more » « less
3. MRAM-based Stochastic Oscillators for Adaptive Non-Uniform Sampling of Sparse Signals in IoT Applications

   Salehi, Soheil; Zaeemzadeh, Alireza; Tatulian, Adrian; Rahnavard, Nazanin; DeMara, Ronald F. (July 2019, Symposium on VLSI Circuits)

   Recent advances to hardware integration and realization of highly-efficient Compressive Sensing (CS) approaches have inspired novel circuit and architectural-level approaches. These embrace the challenge to design more optimal nonuniform CS solutions that consider device-level constraints for IoT applications wherein lifetime energy, device area, and manufacturing costs are highly-constrained, but meanwhile the sensing environment is rapidly changing. In this manuscript, we develop a novel adaptive hardware-based approach for non-uniform compressive sampling of sparse and time-varying signals. The proposed Adaptive Sampling of Sparse IoT signals via STochastic-oscillators (ASSIST) approach intelligently generates the CS measurement matrix by distributing the sensing energy among coefficients by considering the signal characteristics such as sparsity rate and noise level obtained in the previous time step. In our proposed approach, Magnetic Random Access Memory (MRAM)-based stochastic oscillators are utilized to generate the random bitstreams used in the CS measurement matrix. SPICE and MATLAB circuit-algorithm simulation results indicate that ASSIST efficiently achieves the desired non-uniform recovery of the original signals with varying sparsity rates and noise levels. 

   more » « less
4. Bottleneck Problems: An Information and Estimation-Theoretic View

   https://doi.org/10.3390/e22111325  

   Asoodeh, Shahab; Calmon, Flavio P. (November 2020, Entropy)

   Information bottleneck (IB) and privacy funnel (PF) are two closely related optimization problems which have found applications in machine learning, design of privacy algorithms, capacity problems (e.g., Mrs. Gerber’s Lemma), and strong data processing inequalities, among others. In this work, we first investigate the functional properties of IB and PF through a unified theoretical framework. We then connect them to three information-theoretic coding problems, namely hypothesis testing against independence, noisy source coding, and dependence dilution. Leveraging these connections, we prove a new cardinality bound on the auxiliary variable in IB, making its computation more tractable for discrete random variables. In the second part, we introduce a general family of optimization problems, termed “bottleneck problems”, by replacing mutual information in IB and PF with other notions of mutual information, namely f-information and Arimoto’s mutual information. We then argue that, unlike IB and PF, these problems lead to easily interpretable guarantees in a variety of inference tasks with statistical constraints on accuracy and privacy. While the underlying optimization problems are non-convex, we develop a technique to evaluate bottleneck problems in closed form by equivalently expressing them in terms of lower convex or upper concave envelope of certain functions. By applying this technique to a binary case, we derive closed form expressions for several bottleneck problems. 

   more » « less
5. Robust Bayesian graphical regression models for assessing tumor heterogeneity in proteomic networks

   https://doi.org/10.1093/biomtc/ujae160  

   Yao, Tsung-Hung; Ni, Yang; Bhadra, Anindya; Kang, Jian; Baladandayuthapani, Veerabhadran (January 2025, Biometrics)

   ABSTRACT Graphical models are powerful tools to investigate complex dependency structures in high-throughput datasets. However, most existing graphical models make one of two canonical assumptions: (i) a homogeneous graph with a common network for all subjects or (ii) an assumption of normality, especially in the context of Gaussian graphical models. Both assumptions are restrictive and can fail to hold in certain applications such as proteomic networks in cancer. To this end, we propose an approach termed robust Bayesian graphical regression (rBGR) to estimate heterogeneous graphs for non-normally distributed data. rBGR is a flexible framework that accommodates non-normality through random marginal transformations and constructs covariate-dependent graphs to accommodate heterogeneity through graphical regression techniques. We formulate a new characterization of edge dependencies in such models called conditional sign independence with covariates, along with an efficient posterior sampling algorithm. In simulation studies, we demonstrate that rBGR outperforms existing graphical regression models for data generated under various levels of non-normality in both edge and covariate selection. We use rBGR to assess proteomic networks in lung and ovarian cancers to systematically investigate the effects of immunogenic heterogeneity within tumors. Our analyses reveal several important protein–protein interactions that are differentially associated with the immune cell abundance; some corroborate existing biological knowledge, whereas others are novel findings. 

   more » « less