Search

We study the problem of bounding the posterior distribution of discrete probabilistic programs with unbounded support, loops, and conditioning. Loops pose the main difficulty in this setting: even if exact Bayesian inference is possible, the state of the art requires user-provided loop invariant templates. By contrast, we aim to find guaranteed bounds, which sandwich the true distribution. They are fully automated, applicable to more programs and provide more provable guarantees than approximate sampling-based inference. Since lower bounds can be obtained by unrolling loops, the main challenge is upper bounds, and we attack it in two ways. The first is called residual mass semantics, which is a flat bound based on the residual probability mass of a loop. The approach is simple, efficient, and has provable guarantees. The main novelty of our work is the second approach, called geometric bound semantics. It operates on a novel family of distributions, called eventually geometric distributions (EGDs), and can bound the distribution of loops with a new form of loop invariants called contraction invariants. The invariant synthesis problem reduces to a system of polynomial inequality constraints, which is a decidable problem with automated solvers. If a solution exists, it yields an exponentially decreasing bound on the whole distribution, and can therefore bound moments and tail asymptotics as well, not just probabilities as in the first approach. Both semantics enjoy desirable theoretical properties. In particular, we prove soundness and convergence, i.e. the bounds converge to the exact posterior as loops are unrolled further. On the practical side, we describe Diabolo, a fully-automated implementation of both semantics, and evaluate them on a variety of benchmarks from the literature, demonstrating their general applicability and the utility of the resulting bounds., Comment: Full version of the POPL 2025 article, including proofs and other supplementary material

We consider $\mathbb{Z}_q$-valued clock models on a regular tree, for general classes of ferromagnetic nearest neighbor interactions which have a discrete rotational symmetry. It has been proved recently that, at strong enough coupling, families of homogeneous Markov chain Gibbs states $\mu_A$ coexist whose single-site marginals concentrate on $A\subset \mathbb{Z}_q$, and which are not convex combinations of each other [AbHeKuMa24]. In this note, we aim at a description of the extremal decomposition of $\mu_A$ for $|A|\geq 2$ into all extremal Gibbs measures, which may be spatially inhomogeneous. First, we show that in regimes of very strong coupling, $\mu_A$ is not extremal. Moreover, $\mu_A$ possesses a single-site reconstruction property which holds for spin values sent from the origin to infinity, when these initial values are chosen from $A$. As our main result, we show that $\mu_A$ decomposes into uncountably many extremal inhomogeneous states. The proof is based on multi-site reconstruction which allows to derive concentration properties of branch overlaps. Our method is based on a new good site/bad site decomposition adapted to the $A$-localization property, together with a coarse graining argument in local state space., Comment: 32 pages, 3 figures

In this paper, we prove the restricted isometry property of block diagonal random matrices with elements from $\varphi$-sub-Gaussian variables, which extends the previously known results for the sub-Gaussian case. A crucial ingredient of our proof is an improved uniform Hanson-Wright deviation inequality, which should be of independent interest., Comment: 13 pages

We propose a novel coupling inequality of the min-max type for two random matrices with finite absolute third moments, which generalizes the quantitative versions of the well-known inequalities by Gordon. Previous results have calculated the quantitative bounds for pairs of Gaussian random matrices. Through integrating the methods utilized by Chatterjee-Meckes and Reinert-R\"ollin in adapting Stein's method of exchangeable pairs for multivariate normal approximation, this study eliminates the Gaussian restriction on random matrices, enabling us to achieve more extensive results., Comment: 11 pages

We study stationary online bipartite matching, where both types of nodes--offline and online--arrive according to Poisson processes. Offline nodes wait to be matched for some random time, determined by an exponential distribution, while online nodes need to be matched immediately. This model captures scenarios such as deceased organ donation and time-sensitive task assignments, where there is an inflow of patients and workers (offline nodes) with limited patience, while organs and tasks (online nodes) must be assigned upon arrival. We present an efficient online algorithm that achieves a $(1-1/e+\delta)$-approximation to the optimal online policy's reward for a constant $\delta > 0$, simplifying and improving previous work by Aouad and Sarita\c{c} (2022). Our solution combines recent online matching techniques, particularly pivotal sampling, which enables correlated rounding of tighter linear programming approximations, and a greedy-like algorithm. A key technical component is the analysis of a stochastic process that exploits subtle correlations between offline nodes, using renewal theory. A byproduct of our result is an improvement to the best-known competitive ratio--that compares an algorithm's performance to the optimal offline policy--via a $(1-1/\sqrt{e} + \eta)$-competitive algorithm for a universal constant $\eta > 0$, advancing the results of Patel and Wajc (2024).

Entropic optimal transport offers a computationally tractable approximation to the classical problem. In this note, we study the approximation rate of the entropic optimal transport map (in approaching the Brenier map) when the regularization parameter $\varepsilon$ tends to zero in the semidiscrete setting, where the input measure is absolutely continuous while the output is finitely discrete. Previous work shows that the approximation rate is $O(\sqrt{\varepsilon})$ under the $L^2$-norm with respect to the input measure. In this work, we establish faster, $O(\varepsilon^2)$ rates up to polylogarithmic factors, under the dual Lipschitz norm, which is weaker than the $L^2$-norm. For the said dual norm, the $O(\varepsilon^2)$ rate is sharp. As a corollary, we derive a central limit theorem for the entropic estimator for the Brenier map in the dual Lipschitz space when the regularization parameter tends to zero as the sample size increases.

Understanding how individuals' beliefs and attitudes evolve within a population is crucial for explaining social phenomena such as polarization and consensus formation. We explore a persuasive arguments model incorporating confirmation bias, where individuals preferentially accept information aligning with their existing beliefs. By employing a mean-field approach, widely used in statistical physics, we simplify complex processes of argument exchange within the population. Our analysis proceeds by projecting the model onto continuous opinion dynamics and further reducing it through mean-field reasoning. The findings highlight the robustness of mean-field predictions and their compatibility with agent-based simulations, capturing the transition from consensus to polarization induced by confirmation bias.

We consider the problem of detecting deviations from a white noise assumption in time series. Our approach differs from the numerous methods proposed for this purpose with respect to two aspects. First, we allow for non-stationary time series. Second, we address the problem that a white noise test, for example checking the residuals of a model fit, is usually not performed because one believes in this hypothesis, but thinks that the white noise hypothesis may be approximately true, because a postulated models describes the unknown relation well. This reflects a meanwhile classical paradigm of Box(1976) that "all models are wrong but some are useful". We address this point of view by investigating if the maximum deviation of the local autocovariance functions from 0 exceeds a given threshold $\Delta$ that can either be specified by the user or chosen in a data dependent way. The formulation of the problem in this form raises several mathematical challenges, which do not appear when one is testing the classical white noise hypothesis. We use high dimensional Gaussian approximations for dependent data to furnish a bootstrap test, prove its validity and showcase its performance on both synthetic and real data, in particular we inspect log returns of stock prices and show that our approach reflects some observations of Fama(1970) regarding the efficient market hypothesis.

Large Language Models (LLMs) are increasingly adopted for complex scientific text generation tasks, yet they often suffer from limitations in accuracy, consistency, and hallucination control. This thesis introduces a Parameter-Efficient Fine-Tuning (PEFT) approach tailored for GPT-like models, aiming to mitigate hallucinations and enhance reproducibility, particularly in the computational domain of mass spectrometry. We implemented Low-Rank Adaptation (LoRA) adapters to refine GPT-2, termed MS-GPT, using a specialized corpus of mass spectrometry literature. Through novel evaluation methods applied to LLMs, including BLEU, ROUGE, and Perplexity scores, the fine-tuned MS-GPT model demonstrated superior text coherence and reproducibility compared to the baseline GPT-2, confirmed through statistical analysis with the Wilcoxon rank-sum test. Further, we propose a reproducibility metric based on cosine similarity of model outputs under controlled prompts, showcasing MS-GPT's enhanced stability. This research highlights PEFT's potential to optimize LLMs for scientific contexts, reducing computational costs while improving model reliability., Comment: 73 pages, 6 figures

Portfolio diversification, traditionally measured through asset correlations and volatilitybased metrics, is fundamental to managing financial risk. However, existing diversification metrics often overlook non-numerical relationships between assets that can impact portfolio stability, particularly during market stresses. This paper introduces the lexical ratio (LR), a novel metric that leverages textual data to capture diversification dimensions absent in standard approaches. By treating each asset as a unique document composed of sectorspecific and financial keywords, the LR evaluates portfolio diversification by distributing these terms across assets, incorporating entropy-based insights from information theory. We thoroughly analyze LR's properties, including scale invariance, concavity, and maximality, demonstrating its theoretical robustness and ability to enhance risk-adjusted portfolio returns. Using empirical tests on S&P 500 portfolios, we compare LR's performance to established metrics such as Markowitz's volatility-based measures and diversification ratios. Our tests reveal LR's superiority in optimizing portfolio returns, especially under varied market conditions. Our findings show that LR aligns with conventional metrics and captures unique diversification aspects, suggesting it is a viable tool for portfolio managers.

Imbalanced learning occurs in classification settings where the distribution of class-labels is highly skewed in the training data, such as when predicting rare diseases or in fraud detection. This class imbalance presents a significant algorithmic challenge, which can be further exacerbated when privacy-preserving techniques such as differential privacy are applied to protect sensitive training data. Our work formalizes these challenges and provides a number of algorithmic solutions. We consider DP variants of pre-processing methods that privately augment the original dataset to reduce the class imbalance; these include oversampling, SMOTE, and private synthetic data generation. We also consider DP variants of in-processing techniques, which adjust the learning algorithm to account for the imbalance; these include model bagging, class-weighted empirical risk minimization and class-weighted deep learning. For each method, we either adapt an existing imbalanced learning technique to the private setting or demonstrate its incompatibility with differential privacy. Finally, we empirically evaluate these privacy-preserving imbalanced learning methods under various data and distributional settings. We find that private synthetic data methods perform well as a data pre-processing step, while class-weighted ERMs are an alternative in higher-dimensional settings where private synthetic data suffers from the curse of dimensionality., Comment: 14 pages

This paper combines a techno-economic energy system model with an econometric model to maximise electricity price forecasting accuracy. The proposed combination model is tested on the German day-ahead wholesale electricity market. Our paper also benchmarks the results against several econometric alternatives. Lastly, we demonstrate the economic value of improved price estimators maximising the revenue from an electric storage resource. The results demonstrate that our integrated model improves overall forecasting accuracy by 18 %, compared to available literature benchmarks. Furthermore, our robustness checks reveal that a) the Ensemble Deep Neural Network model performs best in our dataset and b) adding output from the techno-economic energy systems model as econometric model input improves the performance of all econometric models. The empirical relevance of the forecast improvement is confirmed by the results of the exemplary storage optimisation, in which the integration of the techno-economic energy system model leads to a revenue increase of up to 10 %.

Models based on recursive partitioning such as decision trees and their ensembles are popular for high-dimensional regression as they can potentially avoid the curse of dimensionality. Because empirical risk minimization (ERM) is computationally infeasible, these models are typically trained using greedy algorithms. Although effective in many cases, these algorithms have been empirically observed to get stuck at local optima. We explore this phenomenon in the context of learning sparse regression functions over $d$ binary features, showing that when the true regression function $f^*$ does not satisfy the so-called Merged Staircase Property (MSP), greedy training requires $\exp(\Omega(d))$ to achieve low estimation error. Conversely, when $f^*$ does satisfy MSP, greedy training can attain small estimation error with only $O(\log d)$ samples. This performance mirrors that of two-layer neural networks trained with stochastic gradient descent (SGD) in the mean-field regime, thereby establishing a head-to-head comparison between SGD-trained neural networks and greedy recursive partitioning estimators. Furthermore, ERM-trained recursive partitioning estimators achieve low estimation error with $O(\log d)$ samples irrespective of whether $f^*$ satisfies MSP, thereby demonstrating a statistical-computational trade-off for greedy training. Our proofs are based on a novel interpretation of greedy recursive partitioning using stochastic process theory and a coupling technique that may be of independent interest.

Human mobility modeling from GPS-trajectories and synthetic trajectory generation are crucial for various applications, such as urban planning, disaster management and epidemiology. Both of these tasks often require filling gaps in a partially specified sequence of visits - a new problem that we call "controlled" synthetic trajectory generation. Existing methods for next-location prediction or synthetic trajectory generation cannot solve this problem as they lack the mechanisms needed to constrain the generated sequences of visits. Moreover, existing approaches (1) frequently treat space and time as independent factors, an assumption that fails to hold true in real-world scenarios, and (2) suffer from challenges in accuracy of temporal prediction as they fail to deal with mixed distributions and the inter-relationships of different modes with latent variables (e.g., day-of-the-week). These limitations become even more pronounced when the task involves filling gaps within sequences instead of solely predicting the next visit. We introduce TrajGPT, a transformer-based, multi-task, joint spatiotemporal generative model to address these issues. Taking inspiration from large language models, TrajGPT poses the problem of controlled trajectory generation as that of text infilling in natural language. TrajGPT integrates the spatial and temporal models in a transformer architecture through a Bayesian probability model that ensures that the gaps in a visit sequence are filled in a spatiotemporally consistent manner. Our experiments on public and private datasets demonstrate that TrajGPT not only excels in controlled synthetic visit generation but also outperforms competing models in next-location prediction tasks - Relatively, TrajGPT achieves a 26-fold improvement in temporal accuracy while retaining more than 98% of spatial accuracy on average., Comment: 10 pages, 3 figures, 32nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2024)

How hard is it to estimate a discrete-time signal $(x_{1}, ..., x_{n}) \in \mathbb{C}^n$ satisfying an unknown linear recurrence relation of order $s$ and observed in i.i.d. complex Gaussian noise? The class of all such signals is parametric but extremely rich: it contains all exponential polynomials over $\mathbb{C}$ with total degree $s$, including harmonic oscillations with $s$ arbitrary frequencies. Geometrically, this class corresponds to the projection onto $\mathbb{C}^{n}$ of the union of all shift-invariant subspaces of $\mathbb{C}^\mathbb{Z}$ of dimension $s$. We show that the statistical complexity of this class, as measured by the squared minimax radius of the $(1-\delta)$-confidence $\ell_2$-ball, is nearly the same as for the class of $s$-sparse signals, namely $O\left(s\log(en) + \log(\delta^{-1})\right) \cdot \log^2(es) \cdot \log(en/s).$ Moreover, the corresponding near-minimax estimator is tractable, and it can be used to build a test statistic with a near-minimax detection threshold in the associated detection problem. These statistical results rest upon an approximation-theoretic one: we show that finite-dimensional shift-invariant subspaces admit compactly supported reproducing kernels whose Fourier spectra have nearly the smallest possible $\ell_p$-norms, for all $p \in [1,+\infty]$ at once., Comment: 29 pages

With the increasing maturity and expansion of the cryptocurrency market, understanding and predicting its price fluctuations has become an important issue in the field of financial engineering. This article introduces an innovative Genetic Algorithm-generated Alpha Sentiment (GAS) blending ensemble model specifically designed to predict Bitcoin market trends. The model integrates advanced ensemble learning methods, feature selection algorithms, and in-depth sentiment analysis to effectively capture the complexity and variability of daily Bitcoin trading data. The GAS framework combines 34 Alpha factors with 8 news economic sentiment factors to provide deep insights into Bitcoin price fluctuations by accurately analyzing market sentiment and technical indicators. The core of this study is using a stacked model (including LightGBM, XGBoost, and Random Forest Classifier) for trend prediction which demonstrates excellent performance in traditional buy-and-hold strategies. In addition, this article also explores the effectiveness of using genetic algorithms to automate alpha factor construction as well as enhancing predictive models through sentiment analysis. Experimental results show that the GAS model performs competitively in daily Bitcoin trend prediction especially when analyzing highly volatile financial assets with rich data.

The paper describes and compares three approaches to modeling an epidemic spread. The first approach is a well-known system of SIR ordinary differential equations. The second is a mean-field model, in which an isolation strategy for each epidemiological group (Susceptible, Infected, and Removed) is chosen as an optimal control. The third is another meanfield model, in which isolation strategy is common for the entire population. The considered models have been compared analytically, their sensitivity analysis has been carried out and their predictive capabilities have been estimated using sets of synthetic and real data. For one of the meanfield models, its finite-difference analogue has been devised. The models have also been assessed in terms of their applicability for predicting a viral epidemic spread., Comment: 32 pages, 22 figures

Rahimi and Recht [31] introduced the idea of decomposing shift-invariant kernels by randomly sampling from their spectral distribution. This famous technique, known as Random Fourier Features (RFF), is in principle applicable to any shift-invariant kernel whose spectral distribution can be identified and simulated. In practice, however, it is usually applied to the Gaussian kernel because of its simplicity, since its spectral distribution is also Gaussian. Clearly, simple spectral sampling formulas would be desirable for broader classes of kernel functions. In this paper, we propose to decompose spectral kernel distributions as a scale mixture of $\alpha$-stable random vectors. This provides a simple and ready-to-use spectral sampling formula for a very large class of multivariate shift-invariant kernels, including exponential power kernels, generalized Mat\'ern kernels, generalized Cauchy kernels, as well as newly introduced kernels such as the Beta, Kummer, and Tricomi kernels. In particular, we show that the spectral densities of all these kernels are scale mixtures of the multivariate Gaussian distribution. This provides a very simple way to modify existing Random Fourier Features software based on Gaussian kernels to cover a much richer class of multivariate kernels. This result has broad applications for support vector machines, kernel ridge regression, Gaussian processes, and other kernel-based machine learning techniques for which the random Fourier features technique is applicable., Comment: 16 pages, 16 figures

We study rare transitions in Markovian open quantum systems driven with Gaussian noise, applying transition path and interface sampling methods to trajectories generated by stochastic Schr\"odinger dynamics. Interface and path sampling offer insights into rare event transition mechanisms while simultaneously establishing a quantitative measure of the associated rate constant. Here, we extend their domain to systems described by stochastic Schr\"odinger equations. As a specific example, we explore a model of quantum Brownian motion in a quartic double well, consisting of a particle coupled to a Caldeira-Leggett oscillator bath, where we note significant departures from the Arrhenius law at low temperatures due to the presence of an anti-Zeno effect., Comment: 13 Pages, 12 Figures

Efficient learning from streaming data is important for modern data analysis due to the continuous and rapid evolution of data streams. Despite significant advancements in stream pattern mining, challenges persist, particularly in managing complex data streams like sequential and weighted itemsets. While reservoir sampling serves as a fundamental method for randomly selecting fixed-size samples from data streams, its application to such complex patterns remains largely unexplored. In this study, we introduce an approach that harnesses a weighted reservoir to facilitate direct pattern sampling from streaming batch data, thus ensuring scalability and efficiency. We present a generic algorithm capable of addressing temporal biases and handling various pattern types, including sequential, weighted, and unweighted itemsets. Through comprehensive experiments conducted on real-world datasets, we evaluate the effectiveness of our method, showcasing its ability to construct accurate incremental online classifiers for sequential data. Our approach not only enables previously unusable online machine learning models for sequential data to achieve accuracy comparable to offline baselines but also represents significant progress in the development of incremental online sequential itemset classifiers., Comment: Accepted at 2024 IEEE International Conference on Big Data

Discovering valuable insights from data through meaningful associations is a crucial task. However, it becomes challenging when trying to identify representative patterns in quantitative databases, especially with large datasets, as enumeration-based strategies struggle due to the vast search space involved. To tackle this challenge, output space sampling methods have emerged as a promising solution thanks to its ability to discover valuable patterns with reduced computational overhead. However, existing sampling methods often encounter limitations when dealing with large quantitative database, resulting in scalability-related challenges. In this work, we propose a novel high utility pattern sampling algorithm and its on-disk version both designed for large quantitative databases based on two original theorems. Our approach ensures both the interactivity required for user-centered methods and strong statistical guarantees through random sampling. Thanks to our method, users can instantly discover relevant and representative utility pattern, facilitating efficient exploration of the database within seconds. To demonstrate the interest of our approach, we present a compelling use case involving archaeological knowledge graph sub-profiles discovery. Experiments on semantic and none-semantic quantitative databases show that our approach outperforms the state-of-the art methods., Comment: Accepted at 2024 IEEE International Conference on Big Data

A variational Bayesian inference for measured wave intensity, such as X-ray intensity, is proposed in this paper. The data is popular to obtain information about unobservable features of an object, such as a material sample and the components of it. The proposed method assumes particles represent the wave, and their behaviors are stochastically modeled. The inference is accurate even if the data is noisy because of a smooth prior setting. Moreover, in this paper, two experimental results show feasibility of the proposed method.

Branch and bound algorithms have been developed for reliability analysis of coherent systems. They exhibit a set of advantages; in particular, they can find a computationally efficient representation of a system failure or survival event, which can be re-used when the input probability distributions change over time or when new data is available. However, existing branch-and-bound algorithms can handle only a limited set of system performance functions, mostly network connectivity and maximum flow. Furthermore, they run redundant analyses on component vector states whose system state can be inferred from previous analysis results. This study addresses these limitations by proposing branch and bound for reliability analysis of general coherent systems} (BRC) algorithm: an algorithm that automatically finds minimal representations of failure/survival events of general coherent systems. Computational efficiency is attained by dynamically inferring importance of component events from hitherto obtained results. We demonstrate advantages of the BRC method as a real-time risk management tool by application to the Eastern Massachusetts highway benchmark network., Comment: Preprint for peer-reviewed article

The Greenland Ice Sheet may be nearing a tipping point, transitioning to permanent melting. This article analyses two melt rate time series using the Bayesian Langevin estimation (BLE), providing further evidence for destabilizing melt dynamics, along with new insights from the method's nonlinear parameterisation. Comparing the results for Western Central Greenland and the Nuussuaq peninsula suggests that inland melt dynamics may approach less stable coastal dynamics on slow and fast scales. Both datasets show a significant increase in fast-scale amplitudes since the 1970s, possibly driven by large-scale atmospheric fluctuations. Additionally, the BLE's nonlinear drift proves crucial for obtaining these results, as a linear Ornstein-Uhlenbeck process fails to capture these dynamics due to the oversimplification of a strictly positive autocorrelation function., Comment: 8 pages, 2 figures. Supplementary information, data, and code available online

Gradient-based dimension reduction decreases the cost of Bayesian inference and probabilistic modeling by identifying maximally informative (and informed) low-dimensional projections of the data and parameters, allowing high-dimensional problems to be reformulated as cheaper low-dimensional problems. A broad family of such techniques identify these projections and provide error bounds on the resulting posterior approximations, via eigendecompositions of certain diagnostic matrices. Yet these matrices require gradients or even Hessians of the log-likelihood, excluding the purely data-driven setting and many problems of simulation-based inference. We propose a framework, derived from score-matching, to extend gradient-based dimension reduction to problems where gradients are unavailable. Specifically, we formulate an objective function to directly learn the score ratio function needed to compute the diagnostic matrices, propose a tailored parameterization for the score ratio network, and introduce regularization methods that capitalize on the hypothesized low-dimensional structure. We also introduce a novel algorithm to iteratively identify the low-dimensional reduced basis vectors more accurately with limited data based on eigenvalue deflation methods. We show that our approach outperforms standard score-matching for problems with low-dimensional structure, and demonstrate its effectiveness for PDE-constrained Bayesian inverse problems and conditional generative modeling., Comment: 23 pages, 9 figures, 1 table

A major limitation of machine learning (ML) prediction models is that they recover associational, rather than causal, predictive relationships between variables. In high-stakes automation applications of ML this is problematic, as the model often learns spurious, non-causal associations. This paper proposes mechanism learning, a simple method which uses front-door causal bootstrapping to deconfound observational data such that any appropriate ML model is forced to learn predictive relationships between effects and their causes (reverse causal inference), despite the potential presence of multiple unknown and unmeasured confounding. Effect variables can be very high dimensional, and the predictive relationship nonlinear, as is common in ML applications. This novel method is widely applicable, the only requirement is the existence of a mechanism variable mediating the cause (prediction target) and effect (feature data), which is independent of the (unmeasured) confounding variables. We test our method on fully synthetic, semi-synthetic and real-world datasets, demonstrating that it can discover reliable, unbiased, causal ML predictors where by contrast, the same ML predictor trained naively using classical supervised learning on the original observational data, is heavily biased by spurious associations. We provide code to implement the results in the paper, online., Comment: 12 pages, 6 figures

We incorporate prior graph topology information into a Neural Controlled Differential Equation (NCDE) to predict the future states of a dynamical system defined on a graph. The informed NCDE infers the future dynamics at the vertices of simulated advection data on graph edges with a known causal graph, observed only at vertices during training. We investigate different positions in the model architecture to inform the NCDE with graph information and identify an outer position between hidden state and control as theoretically and empirically favorable. Our such informed NCDE requires fewer parameters to reach a lower Mean Absolute Error (MAE) compared to previous methods that do not incorporate additional graph topology information., Comment: Accepted as a workshop paper at the NeurIPS 2024 workshop on Data-driven and Differentiable Simulations, Surrogates, and Solvers (D3S3)

The world is evolving and so is the vocabulary used to discuss topics in speech. Analysing political speech data from more than 30 years requires the use of flexible topic models to uncover the latent topics and their change in prevalence over time as well as the change in the vocabulary of the topics. We propose the temporal Poisson factorisation (TPF) model as an extension to the Poisson factorisation model to model sparse count data matrices obtained based on the bag-of-words assumption from text documents with time stamps. We discuss and empirically compare different model specifications for the time-varying latent variables consisting either of a flexible auto-regressive structure of order one or a random walk. Estimation is based on variational inference where we consider a combination of coordinate ascent updates with automatic differentiation using batching of documents. Suitable variational families are proposed to ease inference. We compare results obtained using independent univariate variational distributions for the time-varying latent variables to those obtained with a multivariate variant. We discuss in detail the results of the TPF model when analysing speeches from 18 sessions in the U.S. Senate (1981-2016)., Comment: main paper: 19 pages (2 single figures, 3 double figures, 3 tables) appendix: 9 pages (3 quadruple figures, 1 table) references: 3 pages

The problem of detecting fake data inspires the following seemingly simple mathematical question. Sample a data point $X$ from the standard normal distribution in $\mathbb{R}^n$. An adversary observes $X$ and corrupts it by adding a vector $rt$, where they can choose any vector $t$ from a fixed set $T$ of the adversary's "tricks", and where $r>0$ is a fixed radius. The adversary's choice of $t=t(X)$ may depend on the true data $X$. The adversary wants to hide the corruption by making the fake data $X+rt$ statistically indistinguishable from the real data $X$. What is the largest radius $r=r(T)$ for which the adversary can create an undetectable fake? We show that for highly symmetric sets $T$, the detectability radius $r(T)$ is approximately twice the scaled Gaussian width of $T$. The upper bound actually holds for arbitrary sets $T$ and generalizes to arbitrary, non-Gaussian distributions of real data $X$. The lower bound may fail for not highly symmetric $T$, but we conjecture that this problem can be solved by considering the focused version of the Gaussian width of $T$, which focuses on the most important directions of $T$., Comment: 16 pages

We present a probabilistic ranking model to identify the optimal treatment in multiple-response experiments. In contemporary practice, treatments are applied over individuals with the goal of achieving multiple ideal properties on them simultaneously. However, often there are competing properties, and the optimality of one cannot be achieved without compromising the optimality of another. Typically, we still want to know which treatment is the overall best. In our framework, we first formulate overall optimality in terms of treatment ranks. Then we infer the latent ranking that allow us to report treatments from optimal to least optimal, provided ideal desirable properties. We demonstrate through simulations and real data analysis how we can achieve reliability of inferred ranks in practice. We adopt a Bayesian approach and derive an associated Markov Chain Monte Carlo algorithm to fit our model to data. Finally, we discuss the prospects of adoption of our method as a standard tool for experiment evaluation in trials-based research.

Federated learning (FL) enables multiple devices to collaboratively train a global model while maintaining data on local servers. Each device trains the model on its local server and shares only the model updates (i.e., gradient weights) during the aggregation step. A significant challenge in FL is managing the feature distribution of novel, unbalanced data across devices. In this paper, we propose an FL approach using few-shot learning and aggregation of the model weights on a global server. We introduce a dynamic early stopping method to balance out-of-distribution classes based on representation learning, specifically utilizing the maximum mean discrepancy of feature embeddings between local and global models. An exemplary application of FL is orchestrating machine learning models along highways for interference classification based on snapshots from global navigation satellite system (GNSS) receivers. Extensive experiments on four GNSS datasets from two real-world highways and controlled environments demonstrate that our FL method surpasses state-of-the-art techniques in adapting to both novel interference classes and multipath scenarios.

The problem of measuring conditional dependence between two random phenomena arises when a third one (a confounder) has a potential influence on the amount of information shared by the original pair. A typical issue in this challenging problem is the inversion of ill-conditioned autocorrelation matrices. This paper presents a novel measure of conditional dependence based on the use of incomplete unbiased statistics of degree two, which allows to re-interpret independence as uncorrelatedness on a finite-dimensional feature space. This formulation enables to prune data according to the observations of the confounder itself, thus avoiding matrix inversions altogether. Moreover, the proposed approach is articulated as an extension of the Hilbert-Schmidt independence criterion, which becomes expressible through kernels that operate on 4-tuples of data., Comment: Submitted to the IEEE for possible publication. 5 pages, 2 figures

We present a computer assisted proof for a result concerning a three player betting game, introduced by Angel and Holmes. The three players start with initial capital $x, y, z > 0$ respectively. At each step of this game two players are selected at random to bet on the outcome of a fair coin toss, with the size of the bet being the largest possible, namely the total capital held by the poorer of the two players at that time. The main quantity of interest is the probability of player 1 being eliminated (reaching 0 capital) first. Angel and Holmes have shown that this probability is not monotone decreasing as a function of the initial capital $x$ of player 1. They conjecture that if $x < y < z$ then player 1 would be better off (less likely to be eliminated first) by swapping their capital with another player. In this paper we present a computer-assisted proof of this conjecture. To achieve this, we introduce the theoretical framework MeshItUp, and then perform a two-stage reduction to make MeshItUp computationally feasible, through the use of mixed-integer programming., Comment: 17 pages, 3 figures; for associated implementation, see https://github.com/7angel4/betting-game-proof

Background: In Kreuz et al., J Neurosci Methods 381, 109703 (2022) two methods were proposed that perform latency correction, i.e., optimize the spike time alignment of sparse neuronal spike trains with well defined global spiking events. The first one based on direct shifts is fast but uses only partial latency information, while the other one makes use of the full information but relies on the computationally costly simulated annealing. Both methods reach their limits and can become unreliable when successive global events are not sufficiently separated or even overlap. New Method: Here we propose an iterative scheme that combines the advantages of the two original methods by using in each step as much of the latency information as possible and by employing a very fast extrapolation direct shift method instead of the much slower simulated annealing. Results: We illustrate the effectiveness and the improved performance, measured in terms of the relative shift error, of the new iterative scheme not only on simulated data with known ground truths but also on single-unit recordings from two medial superior olive neurons of a gerbil. Comparison with Existing Method(s): The iterative scheme outperforms the existing approaches on both the simulated and the experimental data. Due to its low computational demands, and in contrast to simulated annealing, it can also be applied to very large datasets. Conclusions: The new method generalizes and improves on the original method both in terms of accuracy and speed. Importantly, it is the only method that allows to disentangle global events with overlap., Comment: 21 pages, 14 Figures

We consider the problem of sampling from the ferromagnetic $q$-state Potts model on the random $d$-regular graph with parameter $\beta>0$. A key difficulty that arises in sampling from the model is the existence of a metastability window $(\beta_u,\beta_u')$ where the distribution has two competing modes, the so-called disordered and ordered phases, causing MCMC-based algorithms to be slow mixing from worst-case initialisations. To this end, Helmuth, Jenssen and Perkins designed a sampling algorithm that works for all $\beta$ when $q$ is large, using cluster expansion methods; more recently, their analysis technique has been adapted to show that random-cluster dynamics mixes fast when initialised more judiciously. However, a bottleneck behind cluster-expansion arguments is that they inherently only work for large $q$, whereas it is widely conjectured that sampling is possible for all $q,d\geq 3$. The only result so far that applies to general $q,d\geq 3$ is by Blanca and Gheissari who showed that the random-cluster dynamics mixes fast for $\beta<\beta_u$. For $\beta>\beta_u$, certain correlation phenomena emerge because of the metastability which have been hard to handle, especially for small $q$ and $d$. Our main contribution is to perform a delicate analysis of the Potts distribution and the random-cluster dynamics that goes beyond the threshold $\beta_u$. We use planting as the main tool in our proofs, and combine it with the analysis of random-cluster dynamics. We are thus able to show that the random-cluster dynamics initialised from all-out mixes fast for all integers $q,d\geq 3$ beyond the uniqueness threshold $\beta_u$; our analysis works all the way up to the threshold $\beta_c\in (\beta_u,\beta_u')$ where the dominant mode switches from disordered to ordered. We also obtain an algorithm in the ordered regime $\beta>\beta_c$ that refines significantly the range of $q,d$., Comment: Abstract shortened to meet arXiv requirements

As illustrated by the success of integer linear programming, linear integer arithmetic is a powerful tool for modelling combinatorial problems. Furthermore, the probabilistic extension of linear programming has been used to formulate problems in neurosymbolic AI. However, two key problems persist that prevent the adoption of neurosymbolic techniques beyond toy problems. First, probabilistic inference is inherently hard, #P-hard to be precise. Second, the discrete nature of integers renders the construction of meaningful gradients challenging, which is problematic for learning. In order to mitigate these issues, we formulate linear arithmetic over integer-valued random variables as tensor manipulations that can be implemented in a straightforward fashion using modern deep learning libraries. At the core of our formulation lies the observation that the addition of two integer-valued random variables can be performed by adapting the fast Fourier transform to probabilities in the log-domain. By relying on tensor operations we obtain a differentiable data structure, which unlocks, virtually for free, gradient-based learning. In our experimental validation we show that tensorising probabilistic linear integer arithmetic and leveraging the fast Fourier transform allows us to push the state of the art by several orders of magnitude in terms of inference and learning times.

In the trace reconstruction problem, one attempts to reconstruct a fixed but unknown string $x$ of length $n$ from a given number of traces $\tilde{x}$ drawn iid from the application of a noisy process (such as the deletion channel) to $x$. The best known algorithm for the trace reconstruction from the deletion channel is due to Chase, and recovers the input string whp given $\exp(\tilde{O}(n^{1/5}))$ traces [Cha21b]. The main component in Chase's algorithm is a procedure for k-mer estimation, which, for any marker $w$ in $\{0, 1\}^k$ of length $k$, computes a "smoothed" distribution of its appearances in the input string $x$ [CGL+23, MS24]. Current k-mer estimation algorithms fail when the deletion probability is above $1/2$, requiring a more complex analysis for Chase's algorithm. Moreover, the only known extension of these approaches beyond the deletion channels is based on numerically estimating high-order differentials of a multivariate polynomial, making it highly impractical [Rub23]. In this paper, we construct a simple Monte Carlo method for k-mer estimation which can be easily applied to a much wider variety of channels. In particular, we solve k-mer estimation for any combination of insertion, deletion, and bit-flip channels, even in the high deletion probability regime, allowing us to directly apply Chase's algorithm for this wider class of channels. To accomplish this, we utilize an approach from the field of quantum error mitigation (the process of using many measurements from noisy quantum computers to simulate a clean quantum computer), called the quasi-probability method (also known as probabilistic error cancellation) [TBG17, PSW22]. We derive a completely classical version of this technique, and use it to construct a k-mer estimation algorithm. No background in quantum computing is needed to understand this paper., Comment: 26 pages, 0 figures

The question that drives this research is: "How to discover the number of respondents that are necessary to validate items of a questionnaire as actually essential to reach the questionnaire's proposal?" Among the efforts in this subject, \cite{Lawshe1975, Wilson2012, Ayre_CVR_2014} approached this issue by proposing and refining the Content Validation Ratio (CVR) that looks to identify items that are actually essentials. Despite their contribution, these studies do not check if an item validated as "essential" should be also validated as "not essential" by the same sample, which should be a paradox. Another issue is the assignment a probability equal a 50\% to a item be randomly checked by a respondent as essential, despite an evaluator has three options to choose. Our proposal faces these issues, making it possible to verify if a paradoxical situation occurs, and being more precise in recommending whether an item should either be retained or discarded from a questionnaire., Comment: 17 pages, 1 figure

This paper establishes statistical properties of deep neural network (DNN) estimators under dependent data. Two general results for nonparametric sieve estimators directly applicable to DNN estimators are given. The first establishes rates for convergence in probability under nonstationary data. The second provides non-asymptotic probability bounds on $\mathcal{L}^{2}$-errors under stationary $\beta$-mixing data. I apply these results to DNN estimators in both regression and classification contexts imposing only a standard H\"older smoothness assumption. The DNN architectures considered are common in applications, featuring fully connected feedforward networks with any continuous piecewise linear activation function, unbounded weights, and a width and depth that grows with sample size. The framework provided also offers potential for research into other DNN architectures and time-series applications., Comment: 85 pages, 2 figures, removed partially linear model section and uploaded as a separate paper (arXiv:2410.22574v1)

This paper explores the practical approach to portfolio selection methods for investments. The study delves into portfolio theory, discussing concepts such as expected return, variance, asset correlation, and opportunity sets. It also presents the efficient frontier and its application in the Markowitz model, which employs mean-variance optimization techniques. An alternative approach based on the mean-semivariance model is introduced. This model accounts for the skewness and kurtosis of the asset return distribution, providing a more comprehensive view of risk and return. The study also addresses the practical implementation of these models, including the use of genetic algorithms to optimize portfolio selection. Additionally, transaction costs and integer constraints in portfolio optimization are considered, demonstrating the applicability of the Markowitz model. -- Este documento explorar la aproximaci\'on pr\'actica a los m\'etodos de selecci\'on de portafolios para inversiones. El estudio profundiza en la teor\'ia de los portafolios, discutiendo conceptos como el rendimiento esperado, la varianza, la correlaci\'on entre activos y los conjuntos de oportunidades. Tambi\'en presenta la frontera eficiente y su aplicaci\'on en el modelo de Markowitz, que utiliza t\'ecnicas de optimizaci\'on media-varianza. Se introduce un enfoque alternativo basado en el modelo media-semivarianza. Este modelo tiene en cuenta la asimetr\'ia y la curtosis de la distribuci\'on de retornos de los activos, proporcionando una visi\'on m\'as completa de riesgo y rendimiento. El estudio tambi\'en aborda la implementaci\'on pr\'actica de estos modelos, incluyendo el uso de algoritmos gen\'eticos para optimizar la selecci\'on de portafolios. Adem\'as, se consideran los costos de transacci\'on y las restricciones enteras en la optimizaci\'on del portafolio., Comment: 78 pages, in Spanish

Scaling political actors based on their individual characteristics and behavior helps profiling and grouping them as well as understanding changes in the political landscape. In this paper we introduce the Structural Text-Based Scaling (STBS) model to infer ideological positions of speakers for latent topics from text data. We expand the usual Poisson factorization specification for topic modeling of text data and use flexible shrinkage priors to induce sparsity and enhance interpretability. We also incorporate speaker-specific covariates to assess their association with ideological positions. Applying STBS to U.S. Senate speeches from Congress session 114, we identify immigration and gun violence as the most polarizing topics between the two major parties in Congress. Additionally, we find that, in discussions about abortion, the gender of the speaker significantly influences their position, with female speakers focusing more on women's health. We also see that a speaker's region of origin influences their ideological position more than their religious affiliation., Comment: 22 pages including 2.5 pages of references, 7 figures 20 additional pages of appendix (supplement), 5 figures, 2 tables

This paper investigates a partially linear spatial autoregressive panel data model that incorporates fixed effects, constant and time-varying regression coefficients, and a time-varying spatial lag coefficient. A two-stage least squares estimation method based on profile local linear dummy variables (2SLS-PLLDV) is proposed to estimate both constant and time-varying coefficients without the need for first differencing. The asymptotic properties of the estimator are derived under certain conditions. Furthermore, a residual-based goodness-of-fit test is constructed for the model, and a residual-based bootstrap method is used to obtain p-values. Simulation studies show the good performance of the proposed method in various scenarios. The Chinese provincial carbon emission data set is analyzed for illustration., Comment: 26 pages, 3 figures, codes

Deep learning methods - consisting of a class of deep neural networks (DNNs) trained by a stochastic gradient descent (SGD) optimization method - are nowadays key tools to solve data driven supervised learning problems. Despite the great success of SGD methods in the training of DNNs, it remains a fundamental open problem of research to explain the success and the limitations of such methods in rigorous theoretical terms. In particular, even in the standard setup of data driven supervised learning problems, it remained an open research problem to prove (or disprove) that SGD methods converge in the training of DNNs with the popular rectified linear unit (ReLU) activation function with high probability to global minimizers in the optimization landscape. In this work we answer this question negatively. Specifically, in this work we prove for a large class of SGD methods that the considered optimizer does with high probability not converge to global minimizers of the optimization problem. It turns out that the probability to not converge to a global minimizer converges at least exponentially quickly to one as the width of the first hidden layer of the ANN and the depth of the ANN, respectively, increase. The general non-convergence results of this work do not only apply to the plain vanilla standard SGD method but also to a large class of accelerated and adaptive SGD methods such as the momentum SGD, the Nesterov accelerated SGD, the Adagrad, the RMSProp, the Adam, the Adamax, the AMSGrad, and the Nadam optimizers., Comment: 91 pages

Generative Flow Networks (GFlowNets) are amortized inference models designed to sample from unnormalized distributions over composable objects, with applications in generative modeling for tasks in fields such as causal discovery, NLP, and drug discovery. Traditionally, the training procedure for GFlowNets seeks to minimize the expected log-squared difference between a proposal (forward policy) and a target (backward policy) distribution, which enforces certain flow-matching conditions. While this training procedure is closely related to variational inference (VI), directly attempting standard Kullback-Leibler (KL) divergence minimization can lead to proven biased and potentially high-variance estimators. Therefore, we first review four divergence measures, namely, Renyi-$\alpha$'s, Tsallis-$\alpha$'s, reverse and forward KL's, and design statistically efficient estimators for their stochastic gradients in the context of training GFlowNets. Then, we verify that properly minimizing these divergences yields a provably correct and empirically effective training scheme, often leading to significantly faster convergence than previously proposed optimization. To achieve this, we design control variates based on the REINFORCE leave-one-out and score-matching estimators to reduce the variance of the learning objectives' gradients. Our work contributes by narrowing the gap between GFlowNets training and generalized variational approximations, paving the way for algorithmic ideas informed by the divergence minimization viewpoint., Comment: Accepted at NeurIPS 2024, https://openreview.net/forum?id=N5H4z0Pzvn

A $k$-height on a graph $G=(V, E)$ is an assignment $V\to\{0, \ldots, k\}$ such that the value on ajacent vertices differs by at most $1$. We study the Markov chain on $k$-heights that in each step selects a vertex at random, and, if admissible, increases or decreases the value at this vertex by one. In the cases of $2$-heights and $3$-heights we show that this Markov chain is rapidly mixing on certain families of grid-like graphs and on planar cubic $3$-connected graphs. The result is based on a novel technique called block coupling, which is derived from the well-established monotone coupling approach. This technique may also be effective when analyzing other Markov chains that operate on configurations of spin systems that form a distributive lattice. It is therefore of independent interest., Comment: 31 pages, 8 figures. Supplemental code available at Zenodo, doi:10.5281/zenodo.13912818

We propose the $\textit{lifted linear model}$, and derive model-free prediction intervals that become tighter as the correlation between predictions and observations increases. These intervals motivate the $\textit{Lifted Coefficient of Determination}$, a model comparison criterion for arbitrary loss functions in prediction-based settings, e.g., regression, classification or counts. We extend the prediction intervals to more general error distributions, and propose a fast model-free outlier detection algorithm for regression. Finally, we illustrate the framework via numerical experiments., Comment: 14 pages, 5 figures

The MultiQueue is a relaxed concurrent priority queue consisting of $n$ internal priority queues, where an insertion uses a random queue and a deletion considers two random queues and deletes the minimum from the one with the smaller minimum. The rank error of the deletion is the number of smaller elements in the MultiQueue. Alistarh et al. [2] have demonstrated in a sophisticated potential argument that the expected rank error remains bounded by $O(n)$ over long sequences of deletions. In this paper we present a simpler analysis by identifying the stable distribution of an underlying Markov chain and with it the long-term distribution of the rank error exactly. Simple calculations then reveal the expected long-term rank error to be $\tfrac{5}{6}n-1+\tfrac{1}{6n}$. Our arguments generalize to deletion schemes where the probability to delete from a given queue depends only on the rank of the queue. Specifically, this includes deleting from the best of $c$ randomly selected queues for any $c>1$.

It has recently been discovered that the conclusions of many highly influential econometrics studies can be overturned by removing a very small fraction of their samples (often less than $0.5\%$). These conclusions are typically based on the results of one or more Ordinary Least Squares (OLS) regressions, raising the question: given a dataset, can we certify the robustness of an OLS fit on this dataset to the removal of a given number of samples? Brute-force techniques quickly break down even on small datasets. Existing approaches which go beyond brute force either can only find candidate small subsets to remove (but cannot certify their non-existence) [BGM20, KZC21], are computationally intractable beyond low dimensional settings [MR22], or require very strong assumptions on the data distribution and too many samples to give reasonable bounds in practice [BP21, FH23]. We present an efficient algorithm for certifying the robustness of linear regressions to removals of samples. We implement our algorithm and run it on several landmark econometrics datasets with hundreds of dimensions and tens of thousands of samples, giving the first non-trivial certificates of robustness to sample removal for datasets of dimension $4$ or greater. We prove that under distributional assumptions on a dataset, the bounds produced by our algorithm are tight up to a $1 + o(1)$ multiplicative factor., Comment: 65 pages, 2 figures

We consider the problem of estimating a structured multivariate density, subject to Markov conditions implied by an undirected graph. In the worst case, without Markovian assumptions, this problem suffers from the curse of dimensionality. Our main result shows how the curse of dimensionality can be avoided or greatly alleviated under the Markov property, and applies to arbitrary graphs. While existing results along these lines focus on sparsity or manifold assumptions, we introduce a new graphical quantity called "graph resilience" and show how it controls the sample complexity. Surprisingly, although one might expect the sample complexity of this problem to scale with local graph parameters such as the degree, this turns out not to be the case. Through explicit examples, we compute uniform deviation bounds and illustrate how the curse of dimensionality in density estimation can thus be circumvented. Notable examples where the rate improves substantially include sequential, hierarchical, and spatial data., Comment: Work accepted to NeurIPS 2024

Mutual information provides a powerful, general-purpose metric for quantifying the amount of shared information between variables. Estimating normalized mutual information using a k-Nearest Neighbor (k-NN) based approach involves the calculation of the scaling-invariant k-NN radius. Calculation of the radius suffers from numerical overflow when the joint dimensionality of the data becomes high, typically in the range of several hundred dimensions. To address this issue, we propose a logarithmic transformation technique that improves the numerical stability of the radius calculation in high-dimensional spaces. By applying the proposed transformation during the calculation of the radius, numerical overflow is avoided, and precision is maintained. Proposed transformation is validated through both theoretical analysis and empirical evaluation, demonstrating its ability to stabilize the calculation without compromizing the precision of the results., Comment: 4+1 pages, 2 figures, 20 equations