Search

We show that deep neural networks achieve dimension-independent rates of convergence for learning structured densities such as those arising in image, audio, video, and text applications. More precisely, we demonstrate that neural networks with a simple $L^2$-minimizing loss achieve a rate of $n^{-1/(4+r)}$ in nonparametric density estimation when the underlying density is Markov to a graph whose maximum clique size is at most $r$, and we provide evidence that in the aforementioned applications, this size is typically constant, i.e., $r=O(1)$. We then establish that the optimal rate in $L^1$ is $n^{-1/(2+r)}$ which, compared to the standard nonparametric rate of $n^{-1/(2+d)}$, reveals that the effective dimension of such problems is the size of the largest clique in the Markov random field. These rates are independent of the data's ambient dimension, making them applicable to realistic models of image, sound, video, and text data. Our results provide a novel justification for deep learning's ability to circumvent the curse of dimensionality, demonstrating dimension-independent convergence rates in these contexts.

This manuscript describes and implementation of scripts of code aimed at reducing the influence of artifacts, specifically focused on ocular artifacts, in the measurement and processing of electroencephalogram (EEG) signals. This process is of importance because it benefits the analysis and study of long trial samples when the appearance of ocular artifacts cannot be avoided by simply discarding trials. The implementations provided to the reader illustrate, with slight modifications, previously proposed methods aimed at the partial or complete elimination of EEG channels or components are those that resemble the electro-oculogram (EOG) signals in which artifacts are detected. In addition to the description of each of the provided functions, examples of utilization and illustrative figures will be included to show the expected results and processing pipeline., Comment: 14 pages

Rapid model validation via the train-test paradigm has been a key driver for the breathtaking progress in machine learning and AI. However, modern AI systems often depend on a combination of tasks and data collection practices that violate all assumptions ensuring test validity. Yet, without rigorous model validation we cannot ensure the intended outcomes of deployed AI systems, including positive social impact, nor continue to advance AI research in a scientifically sound way. In this paper, I will show that for widely considered inference settings in complex social systems the train-test paradigm does not only lack a justification but is indeed invalid for any risk estimator, including counterfactual and causal estimators, with high probability. These formal impossibility results highlight a fundamental epistemic issue, i.e., that for key tasks in modern AI we cannot know whether models are valid under current data collection practices. Importantly, this includes variants of both recommender systems and reasoning via large language models, and neither na\"ive scaling nor limited benchmarks are suited to address this issue. I am illustrating these results via the widely used MovieLens benchmark and conclude by discussing the implications of these results for AI in social systems, including possible remedies such as participatory data curation and open science., Comment: To appear in NeurIPS'24

We provide a general theory of height-offset variables and their properties for nearest-neighbor integer-valued gradient models on trees. This notion goes back to Sheffield [25], who realized that such tail-measurable variables can be used to associate to gradient Gibbs measures also proper Gibbs measures, via the procedure of pinning at infinity. On the constructive side, our theory incorporates the existence of height-offset variables, regularity properties of their Lebesgue densities and concentration properties of the associated Gibbs measure. On the pathological side, we show that pinning at infinity necessarily comes at a cost. This phenomenon will be analyzed on the levels of translation invariance, the tree-indexed Markov chain property, and extremality. The scope of our theory incorporates free measures, and also height-periodic measures of period 2, assuming only finite second moments of the transfer operator which encodes the nearest neighbor interaction. Our proofs are based on investigations of the respective martingale limits, past and future tail-decompositions, and infinite product representations for moment generating functions., Comment: 27 pages, 2 figures

The human brain receives stimuli in multiple ways; among them, audio constitutes an important source of relevant stimuli for the brain regarding communication, amusement, warning, etc. In this context, the aim of this manuscript is to advance in the classification of brain responses to music of diverse genres and to sounds of different nature: speech and music. For this purpose, two different experiments have been designed to acquiere EEG signals from subjects listening to songs of different musical genres and sentences in various languages. With this, a novel scheme is proposed to characterize brain signals for their classification; this scheme is based on the construction of a feature matrix built on relations between energy measured at the different EEG channels and the usage of a bi-LSTM neural network. With the data obtained, evaluations regarding EEG-based classification between speech and music, different musical genres, and whether the subject likes the song listened to or not are carried out. The experiments unveil satisfactory performance to the proposed scheme. The results obtained for binary audio type classification attain 98.66% of success. In multi-class classification between 4 musical genres, the accuracy attained is 61.59%, and results for binary classification of musical taste rise to 96.96%., Comment: 12 pages

Electroencephalography (EEG) provides a way to understand, and evaluate neurotransmission. In this context, time-locked EEG activity or event-related potentials (ERPs) are often used to capture neural activity related to specific mental processes. Normally, they are considered on the basis of averages across a number of trials. However, there exist notable variability in latency jitter, jitter, and amplitude, across trials, and, also, across users; this causes the average ERP waveform to blur, and, furthermore, diminish the amplitude of underlying waves. For these reasons, a strategy is proposed for obtaining ERP waveforms based on dynamic time warping (DTW) to adapt, and adjust individual trials to the averaged ERP, previously calculated, to build an enhanced average by making use of these warped signals. At the sight of the experiments carried out on the behaviour of the proposed scheme using publicly available datasets, this strategy reduces the attenuation in amplitude of ERP components thanks to the reduction of the influence of variability of latency and jitter, and, thus, improves the averaged ERP waveforms., Comment: 11 pages

Our model for the lifespan of an enterprise is the geometric distribution. We do not formulate a model for enterprise foundation, but assume that foundations and lifespans are independent. We aim to fit the model to information about foundation and closure of German enterprises in the AFiD panel. The lifespan for an enterprise that has been founded before the first wave of the panel is either left truncated, when the enterprise is contained in the panel, or missing, when it already closed down before the first wave. Marginalizing the likelihood to that part of the enterprise history after the first wave contributes to the aim of a closed-form estimate and standard error. Invariance under the foundation distribution is achived by conditioning on observability of the enterprises. The conditional marginal likelihood can be written as a function of a martingale. The later arises when calculating the compensator, with respect some filtration, of a process that counts the closures. The estimator itself can then also be written as a martingale transform and consistency as well as asymptotic normality are easily proven. The life expectancy of German enterprises, estimated from the demographic information about 1.4 million enterprises for the years 2018 and 2019, are ten years. The width of the confidence interval are two months. Closure after the last wave is taken into account as right censored., Comment: 42 pages, 2 figures, 4 tables

The objective of the paper is to price weather derivative contracts based on temperature and precipitation as underlying climate variables. We use a neural network approach combined with time series forecast to value Pacific Rim index in Toronto and Chicago

Simulating quantum systems using classical computing equipment has been a significant research focus. This work demonstrates that circuits as large and complex as the random circuit sampling (RCS) circuits published as a part of Google's pioneering work [4-7] claiming quantum supremacy can be effectively simulated with high fidelity on classical systems commonly available to developers, using the universal quantum simulator included in the Quantum Rings SDK, making this advancement accessible to everyone. This study achieved an average linear cross-entropy benchmarking (XEB) score of 0.678, indicating a strong correlation with ideal quantum simulation and exceeding the XEB values currently reported for the same circuits today while completing circuit execution in a reasonable timeframe. This capability empowers researchers and developers to build, debug, and execute large-scale quantum circuits ahead of the general availability of low-error rate quantum computers and invent new quantum algorithms or deploy commercial-grade applications., Comment: 10 pages, 5 figures

This article is concerned with sampling from Gibbs distributions $\pi(x)\propto e^{-U(x)}$ using Markov chain Monte Carlo methods. In particular, we investigate Langevin dynamics in the continuous- and the discrete-time setting for such distributions with potentials $U(x)$ which are strongly-convex but possibly non-differentiable. We show that the corresponding subgradient Langevin dynamics are exponentially ergodic to the target density $\pi$ in the continuous setting and that certain explicit as well as semi-implicit discretizations are geometrically ergodic and approximate $\pi$ for vanishing discretization step size. Moreover, we prove that the discrete schemes satisfy the law of large numbers allowing to use consecutive iterates of a Markov chain in order to compute statistics of the stationary distribution posing a significant reduction of computational complexity in practice. Numerical experiments are provided confirming the theoretical findings and showcasing the practical relevance of the proposed methods in imaging applications.

Software security mainly studies vulnerability detection: is my code vulnerable today? This hinders risk estimation, so new approaches are emerging to forecast the occurrence of future vulnerabilities. While useful, these approaches are coarse-grained and hard to employ for project-specific technical decisions. We introduce a model capable of vulnerability forecasting at library level. Formalising source-code evolution in time together with library dependency, our model can estimate the probability that a software project faces a CVE disclosure in a future time window. Our approach is white-box and lightweight, which we demonstrate via experiments involving 1255 CVEs and 768 Java libraries, made public as an open-source artifact. Besides probabilities estimation, e.g. to plan software updates, this formal model can be used to detect security-sensitive points in a project, or measure the health of a development ecosystem.

Time series forecasting is crucial in several sectors, such as meteorology, retail, healthcare, and finance. Accurately forecasting future trends and patterns is crucial for strategic planning and making well-informed decisions. In this case, it is crucial to include many forecasting methodologies. The strengths of Auto-regressive Integrated Moving Average (ARIMA) for linear time series, Seasonal ARIMA models (SARIMA) for seasonal time series, Exponential Smoothing State Space Models (ETS) for handling errors and trends, and Long Short-Term Memory (LSTM) Neural Network model for complex pattern recognition have been combined to create a comprehensive framework called FlowScope. SARIMA excels in capturing seasonal variations, whereas ARIMA ensures effective handling of linear time series. ETS models excel in capturing trends and correcting errors, whereas LSTM networks excel in reflecting intricate temporal connections. By combining these methods from both machine learning and deep learning, we propose a deep-hybrid learning approach FlowScope which offers a versatile and robust platform for predicting time series data. This empowers enterprises to make informed decisions and optimize long-term strategies for maximum performance. Keywords: Time Series Forecasting, HybridFlow Forecast Framework, Deep-Hybrid Learning, Informed Decisions., Comment: 12 pages and 6 figures

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).

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 adaptive 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 Abbe et al. (2022)'s 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 dichotomy 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)