Non-Gaussianity

Follow this topic Ask about this topic

Momentum

6 papers in the last four weeks, with none the four weeks before. 0.1% of all new papers.

Jul 6Week of Sep 21

Latest papers 20

Sep 27, 2026cs.LG

Benign Overfitting for General Norms and Distributions

Understanding why predictors can generalize despite interpolating noisy training data is a central puzzle in machine learning. Most work on such "benign overfitting" studies minimum-2-norm linear regression, reflecting the inductive bias of gradient descent. However, modern optimizers such as Adam and Muon use non-Euclidean update geometries, favoring solutions associated with other norms. Analyzing regression for non-Euclidean norms is substantially more difficult, with known results essentially limited to Gaussians. In this paper, we develop a method to analyze benign overfitting in linear regression for general norms and general (sub-Gaussian) distributions. As a special case, we prove that minimum-p-norm interpolation with p>1 can benignly overfit even for non-Gaussian distributions, under suitable conditions. Perhaps surprisingly, for the 1-norm, benign overfitting does not hold in general for well-behaved (but non-Gaussian) distributions, showing that existing positive 1-norm results rely crucially on Gaussianity. Our proof analyzes the geometry of the dual optimization problem, using concentration and central limit tools to show it is approximately Euclidean in many high-dimensional cases.

Daniel Barzilai, Ohad Shamir

Weizmann Institute of Science · University of Toronto & Vector Institute

Overfitting Spectral Norm Exponential Family Non-Gaussianity Norm Gradient Descent+2

Sep 22, 2026math.ST

Statistical Rates for Entropic Optimal Transport in the Discrete to SubGaussian Regime

We study statistical rates in entropic optimal transport in the semi-discrete regime where one measure has finite support and the other is subGaussian. Our main result establishes parametric convergence rates for the empirical dual potentials to their population counterparts, with no dimension dependence in the leading term. Our result relies on tailored strong concavity analysis of the semi-dual objective, coupled with specialized bounds for the semi-discrete potentials. As a consequence, we obtain fast rates for downstream quantities derived from the optimal coupling. Chiefly, the empirical barycentric projection achieves a squared-error rate

n^{-1}

, matching the fully compact case and improving over the less favorable

n^{-1/2}

rate known for fully subGaussian settings. Altogether, these results may indicate a lower complexity adaptation phenomenon whereby the statistical complexity of the barycentric projection is governed by the discrete measure. As an application, we analyze Sinkhorn-EM, an EM-type algorithm in which the E-step is replaced by an entropic optimal transport problem. In a well-specified and balanced two-component Gaussian mixture model, we prove

\sqrt{n}

-consistency of the empirical iterates to their population counterparts for any fixed number of iterations, matching classical EM rates up to a

\sqrt{\log n}

factor. Simulations support the theory.

Tomas Gonzalez, Gonzalo Mena

Department of Machine Learning, Carnegie Mellon University · Department of Statistics & Data Science, Carnegie Mellon University

Optimal Transport Approach Non-Gaussianity Convergence Discrete

Sep 14, 2026cs.IT

Zero-SNR Analyticity of the Scalar MMSE Is Equivalent to Gaussianity

Let

Y_s=\sqrt{s}X+Z

, where

Z

is standard Gaussian and independent of the real random variable

X

. We prove that, under the square-exponential moment condition

\mathbb{E}e^{βX^2}<\infty

for some

β>0

, the scalar minimum mean-square error

\operatorname{mmse}_X(s)

is analytic at zero signal-to-noise ratio if and only if

X

is Gaussian, with constant random variables included as degenerate Gaussians. The proof converts estimation in the Gaussian channel into a backward heat flow acting on the moment-generating function

M(z)=\mathbb{E}e^{zX}

. Under the stated tail condition, every non-Gaussian input forces

M

to have a nonzero complex zero. We show that each zero cluster produces a finite singularity in its localized Borel transform at the action

ξ=z_0^2/2

. After removing the action scale, the Borel coefficients have a nonzero

n^{-1/2}

prefactor for a simple zero. A zero of multiplicity

m\geq 2

splits according to the roots of a Hermite polynomial and instead contributes a prefactor

n^{-m/2}e^{r_m\sqrt{2n}}

. A finite-disc localization and relative-cycle continuation argument then show that at least one such singularity survives in the full Borel transform. Thus, for every non-Gaussian input in the stated class, the formal zero-SNR expansion is Gevrey-1 but divergent. Rational-MMSE rigidity and the analogous analyticity criterion for mutual information follow as corollaries.

Yixing Zhang

Non-Gaussianity Probability Measures Gaussian Primitives Regularization

Sep 7, 2026stat.CO

Thermodynamic Cyclic Processes with Markov Samplers in Bayesian Inference

The concept of Markov chain Monte Carlo (MCMC) cycles, an analogy to cyclic processes in heat engines, is presented in order to examine Bayesian inference problems. In this effort, we develop adaptive ensemble schedulers that allow the tuning of external parameters of a Bayesian canonical ensemble during an MCMC run, realising the MCMC cycles in practice. We run these cycles on different statistical models. As a fundamental insight, we find (both theoretically and in practice) that such systems can produce a non-zero net work output if and only if the considered model is non-Gaussian. As such, they may serve as a measure of non-Gaussianity in Bayesian inference, which we test on an example from supernova cosmology.

Heinrich von Campe, Bjoern Malte Schaefer

Interdisziplinäres Zentrum für wissenschaftliches Rechnen, Universität Heidelberg · Tübingen AI Center, University of Tübingen · ELLIS Institute Tübingen +2

Bayesian Inference Markov Chain Monte Carlo Markovian Sampling Non-Gaussianity Thermodynamics Cosmology

Sep 3, 2026cs.LG

Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails

Restricted eigenvalue (RE) bounds govern stable recovery by norm-regularized estimators. For isotropic sub-Gaussian measurements, the benchmark sample size is

1+w(A)^2

, where

w(A)

is the Gaussian width of the normalized descent cone. The COLT 2015 open-problem note (Banerjee et al., 2015) asked whether the same law follows for heavy-tailed designs from a uniform small-ball condition alone. We give an explicit and systematic negative answer to the general question as formulated there: the proposed law fails in its full dimension-free, arbitrary-set form, and the missing obstruction is simultaneous threshold occupancy. A constant-width polyhedral descent cone with fixed small-ball constants has zero empirical RE on every sample path up to half the ambient dimension. More generally, every finite range space admits exact threshold encoding in an arbitrarily narrow spherical cap and a lift to a full polyhedral descent-cone section. For every fixed threshold VC dimension

d

, as

β\downarrow0

, the sharp worst-case sample complexity is

Θ(β^{-1}[d\log(1/β)+\log(1/δ)])

. The separation persists under exact isotropy and all finite moments: on the same constant-width cone, Gaussian measurements succeed with

O(1+\log(1/δ))

samples, whereas an isotropic heavy-tailed design fails pathwise for

n\lesssim\sqrt{p/\log p}

. Gaussian smoothing yields an everywhere-positive

C^\infty

density while retaining arbitrarily poor RE. Under isotropy, a distribution-free fallback governed by affine dimension times squared enclosing radius is sharp on this family.

Shi Fu, Huibo Xu, Qixin Zhang +1

Generative AI Lab, College of Computing and Data Science, Nanyang Technological University, Singapore

Non-Gaussianity Long-Tailed Distribution Spectral Norm Spectral Decomposition Gaussian Primitives Decision Thresholds

Sep 1, 2026cs.LG

Generative Diffusion Surrogates with Analytical Variance Schedule

Stochastic transport describes physical systems in which an initially structured distribution spreads under unresolved forcing, scattering, or heterogeneous media. Useful surrogates for such systems should be probabilistic, time-resolved, and able to represent non-Gaussian distributional structure. Generative diffusion models, which corrupt data with Gaussian noise and learn a reverse flow back to structured states, have these properties. Their noise schedules, however, are usually chosen heuristically: image and audio generation---the canonical use cases---provide no physical clock. In transport, by contrast, the variance, or mean-square displacement, is often known from macroscopic theory or empirical scaling even when the full distribution is not. Here we prescribe the forward noising rate as the time derivative of this variance, turning generative time into a calibrated transport clock. The variance path is enforced by construction, while the learned score field represents how non-Gaussian structure inherited from entrance data is smoothed along that path, requiring no intermediate-time physical transport data. For ballistic-to-diffusive transport in turbulent plasmas, the surrogate matches test-particle distributions, reproduces the laboratory-measured variance scale, and tracks the simulated kurtosis evolution without schedule tuning, enabling calibrated emulation and likelihood-based inference.

Patrick Reichherzer, Gianluca Gregori, David N. Hosking +1

Department of Physics, University of Oxford, Oxford OX1 3PU, UK. · Department of Astrophysical Sciences, Princeton University, Princeton NJ 08544, USA. · Max Planck Institute for Security and Privacy, Bochum 44799, Germany. +2

Diffusion Dynamics Diffusion Models Latent Transport Variance Non-Gaussianity

Jul 15, 2026cs.LG

Linear Independent Component Analysis via Optimal Transport

Linear Independent Component Analysis (ICA) recovers jointly independent source signals from their linear mixtures. To achieve this, classical ICA algorithms attempt to maximize non-Gaussianity, measured by negentropy, which is linked to independence by information theory. Because exact negentropy optimization is intractable, they rely on proxy contrast functions, such as fourth-order cumulants, and parametric log-likelihoods. We propose instead to measure non-Gaussianity using the squared Wasserstein distance

W_2^2

to a standard Gaussian. We prove that the Wasserstein distance between a standard normal distribution and linear projections of the data is maximized when the projection recovers an independent component. Based on this observation, we propose the OT-ICA algorithm which finds this projection by gradient-based optimization. Empirical evaluation on simulated data shows that OT-ICA outperforms proxy-based methods for different distributions of the latent variables. Application to EEG artifact removal and econometric price discovery confirm OT-ICA can be used for applied ICA tasks without distributional assumptions.

Ashutosh Jha, Michel Besserve, Simon Buchholz

Methods Center, University of Tübingen · Max Planck Institute for Intelligent Systems, Tübingen · Institute of Artificial Intelligence, TU Braunschweig

Independent Component Analysis Wasserstein Distance Non-Gaussianity

Jun 25, 2026cs.LG

Learning Probabilistic Filters with Strictly Proper Scoring Rules

Bayesian filtering of partially and noisily observed dynamical systems seeks to infer the evolving conditional distribution of the state of a dynamical system, given observations, in an online fashion. This Bayesian filtering distribution is the natural object for uncertainty quantification, but it is rarely available as a supervised learning target. However, one can often use the forecast model to generate synthetic system trajectories, along with synthetic observations. We introduce the proper scoring ensemble filter (PSEF), an ensemble data assimilation method based on training an analysis map to approximate the filtering distribution using only synthetic state--observation trajectories. The analysis step is represented as a permutation-invariant, transformer-based map that takes as input a forecast ensemble and observations, producing an analysis ensemble. Training is based on strictly proper scoring rules -- with the energy score used in our implementation -- so that probabilistic accuracy is rewarded over the whole probability distribution. We prove that, under a realizability assumption, the population objective is minimized by the true Bayesian filtering distribution. We also derive the finite-ensemble empirical objective used in training and relate its single state--observation trajectory form to the population objective, using a mean-field consistency argument. Numerical experiments show that the learned filter accurately approximates challenging filtering distributions, including nonlinear, non-Gaussian, and multi-modal posteriors, and achieves stronger performance in data assimilation tasks than classical methods or learning-based methods with mean-squared-error objectives. For close-to-Gaussian problems, learning a correction to the EnKF is the best approach, while for highly non-Gaussian problems an end-to-end approach that discards this inductive bias is superior.

Eviatar Bach, Ricardo Baptista, Jochen Bröcker +2

Department of Meteorology, University of Reading Brian Hoskins Building, Reading, RG6 6ET, UK · Department of Mathematics and Statistics, University of Reading Pepper Lane, Reading, RG6 6AX, UK · National Centre for Earth Observation Brian Hoskins Building, University of Reading, Reading, RG6 6ET, UK +5

Bayesian Filtering Data Assimilation Non-Gaussianity Student-Generated Trajectories

Jun 21, 2026stat.ML

Statistical Inference for Misspecified Contextual Bandits

Contextual bandit algorithms have transformed modern experimentation by enabling real-time adaptation for personalized treatment. Yet these advantages create challenges for statistical inference due to adaptivity. We study inference with contextual-bandit data without assuming a well-specified outcome model. In this setting, we show a previously overlooked issue: standard algorithms such as LinUCB may fail to stabilize under misspecified working models, leading to non-Gaussian estimator behavior and invalid inference. This issue is practically important, as misspecified working models -- such as approximations of complex dynamical systems -- are often employed by online agents in real-world adaptive experiments to balance reward, computational tractability, and robustness. We develop an inverse-probability-weighted Z-estimation framework for a broad class of marginal moment targets, including projection parameters, structural parameters with noisy contexts, and off-policy values. We identify a stability condition tailored to this framework, scaled inverse-propensity convergence, under which the IPW-Z estimator is consistent and asymptotically normal with a consistent sandwich variance estimator. We further establish sufficient conditions for scaled inverse-propensity convergence for several policy classes, including multi-armed bandit algorithms and smooth contextual allocation policies. Simulations and a HeartSteps V1 real-data-calibrated application show reliable coverage and competitive performance across multiple targets. Overall, our results highlight the importance of stability-aware adaptive design for valid post-experiment inference.

Yongyi Guo, Ziping Xu

Department of Statistics, University of Wisconsin–Madison · School of Data Science and Society, University of North Carolina at Chapel Hill

Contextual Bandit Framework Statistical Inference Non-Gaussianity

Jun 18, 2026cs.LG

$Ω$ : Operator-based Mixture Ensemble for Generative Assimilation

Characterizing non-Gaussian posterior distributions in partially observed high-dimensional nonlinear systems remains a fundamental challenge in data assimilation. Ensemble Kalman filters rely on Gaussian approximations that can be inaccurate for strongly non-Gaussian posteriors, whereas particle filters suffer from severe scalability limitations. Recent score-based generative approaches improve posterior characterization but typically require supervised training with ground-truth posterior samples, which are unavailable in most practical applications. We introduce

Ω

(Operator-based Mixture Ensemble for Generative Assimilation), a scalable framework that integrates conditional Gaussian surrogate modeling, unsupervised score learning, and generative sampling. The conditional Gaussian surrogate provides a nonlinear non-Gaussian baseline approximation while admitting closed-form conditional posterior distributions for the unresolved variables. First,

Ω

exploits these closed-form conditional distributions to analytically recover the high-dimensional unobserved component, reducing computational cost and mitigating the curse of dimensionality. Second,

Ω

learns only the residual discrepancy beyond an analytical baseline through denoising score matching using ensemble trajectories alone, eliminating the need for ground-truth posterior samples and substantially reducing the learning burden. Third,

Ω

reconstructs the full non-Gaussian posterior distribution of both observed and unobserved variables via a Gaussian mixture representation, capturing multimodal, skewed, and heavy-tailed statistics. Finally,

Ω

employs annealed Langevin sampling to iteratively refine ensemble members from the baseline toward the target posterior.

Ω

is validated on several turbulent models with intermittency and extreme events, consistently improving posterior accuracy.

Pouria Behnoudfar, Nan Chen

University of Wisconsin-Madison, Department of Mathematics, Madison, WI, USA

Data Assimilation Non-Gaussianity Extended Kalman Filter Ensemble

Jun 6, 2026cs.LG

How Deep Are Deep GPs, Really? A Sharp Threshold and a Non-Gaussian Limit for Compositional GPs

Compositional priors describe the generic properties of layered functions in deep Bayesian models, where deep neural networks with random weights are a canonical example.In the wide-network limit, the prior is a Gaussian process with a depth-dependent kernel, and its behaviour as depth grows has been extensively studied through this kernel. Here, we study another case, where each layer itself is a vector valued Gaussian process, and our aim is similarly to understand the limiting behaviour of the prior as depth grows. Previous GP work has established that for the RBF kernel and a certain range of bandwidths

r

, the prior degenerates in the limit, converging to the set of constant functions -- which is not useful as a probabilistic model. In this paper we establish several new results. First, we identify a sharp bandwidth threshold

r_c(d) = Θ(\sqrt{d})

above which the limit is degenerate, strengthening the earlier bounds. Second, and more importantly, we show that for

r

below the threshold

r_c(d)

the prior converges to a limit distribution

π_{\bar{Z}}

. We also prove that these distributions are non-degenerate and non-Gaussian, with non-vanishing dependence between coordinates. In contrast to the previously known degenerate regime, deep Gaussian process priors can therefore admit non-trivial limits. Empirically, we verify the threshold across a range of dimensions

d

, and demonstrate a complex multimodal behaviour of the limit distributions

π_{\bar{Z}}

-- a regime that becomes increasingly narrow with

d

and would be hard to identify without knowing the threshold.

Mark Kozdoba, Shie Mannor

Technion, IIT · NVIDIA

Gaussian Process Non-Gaussianity Large Deviation Principle Prior Knowledge Integration Convergence Rtk-Gnss

May 26, 2026math.PR

On the Subgaussianity of Quantized Linear Maps: An AI-Assisted Note

This short note presents a dimension-independent subgaussian concentration bound for Gaussian vectors under coordinate-wise nonlinear mappings. Discovered by Gemini 3.5 Flash, this result applies to any bounded function under a well-conditioned covariance. We apply this tool to answer a question of Simone Bombari on sign-quantized linear maps

Y = \text{sgn}(Wx)

.

Guangyi Zou, Roman Vershynin

Department of Mathematics, University of California, Irvine

Non-Gaussianity Gaussian Primitives Concentration Bounds Covariance Nonlinearity

May 10, 2026cs.LG

On Uniform Error Bounds for Kernel Regression under Non-Gaussian Noise

Providing non-conservative uncertainty quantification for function estimates derived from noisy observations remains a fundamental challenge in statistical machine learning, particularly for applications in safety-critical domains. In this work, we propose novel non-asymptotic probabilistic uniform error bounds for kernel-based regression. Compared to related bounds in the literature that are restricted to (conditionally) independent sub-Gaussian noise, our bounds allow to consider a broad class of non-Gaussian distributions, such as sub-Gaussian, bounded, sub-exponential, and variance/moment-bounded noise. Moreover, our results apply to correlated and uncorrelated noise. We compare our proposed error bounds with existing results in terms of the induced uncertainty region and their performance in safe control, demonstrating the tightness of the proposed bounds.

Johannes Teutsch, Oleksii Molodchyk, Marion Leibold +2

Chair of Automatic Control Engineering, Department of Computer Engineering, Technical University of Munich, 80333 Munich, Germany · Institute of Control Systems, Hamburg University of Technology, 21073 Hamburg, Germany · Department of Electrical and Computer Engineering, National University of Singapore, 117583 Singapore

Non-Gaussianity Uncertainty Quantification Confidence Intervals

May 6, 2026cs.LG

Graph-SND: Sparse Aggregation for Behavioral Diversity in Multi-Agent Reinforcement Learning

System Neural Diversity (SND) measures behavioral heterogeneity in multi-agent reinforcement learning by averaging pairwise distances over all

\binom{n}{2}

agent pairs, making each call quadratic in team size. We introduce Graph-SND, which replaces this complete-graph average with a weighted average over the edges of an arbitrary graph

G

. Three regimes follow:

G=K_n

recovers SND exactly; a fixed sparse

G

defines a localized diversity measure at

O(|E|)

cost; and random edge samples yield an unbiased Horvitz-Thompson estimator and a normalized sample mean with

O(1/\sqrt{m})

concentration in the sampled edge count

m

. For fixed sparse graphs we prove forwarding-index distortion bounds for expanders and a spectral refinement under low-rank distance structure; for random

d

-regular graphs we prove an unconditional probabilistic

\widetilde{\mathcal{O}}(D_{\max}/\sqrt{n})

bound. On VMAS we verify recovery, unbiasedness, concentration, and wall-clock scaling, with a PettingZoo TVD panel checking non-Gaussian transfer. In a 500-iteration

n=100

PPO run, Bernoulli-

0.1

Graph-SND tracks full SND while reducing per-call metric time by about

10\times

, and frozen-policy GPU timing up to

n=500

follows the predicted

\binom{n}{2}/|E|

speedup. Random

d

-regular expanders empirically achieve

\mathrm{SND}_{G}^{\mathrm{u}}/\mathrm{SND} \in [0.9987, 1.0013]

at

Θ(n \log n)

edges. In DiCo diversity control at

n=50

, Bernoulli-

0.1

Graph-SND preserves set-point tracking with paired reward differences indistinguishable from zero across nine matched cells while cutting per-call metric cost by

{\sim}9.5\times

. Together, these results show that the SND aggregation bottleneck can be removed without changing the metric's semantics, yielding a drop-in sparse alternative that scales beyond complete-graph SND and supports both passive measurement and closed-loop diversity control.

Shawn Ray

Carnegie Mellon University

Multi-Agent Reinforcement Learning Inhomogeneous Random Graphs Graph Representations Diversity Heterogeneity Non-Gaussianity

Apr 24, 2026stat.ML

Mixed Membership sub-Gaussian Models

The Gaussian mixture model is widely used in unsupervised learning, owing to its simplicity and interpretability. However, a fundamental limitation of the classical Gaussian mixture model is that it forces each observation to belong to exactly one component. In many practical applications, such as genetics, social network analysis, and text mining, an observation may naturally belong to multiple components or exhibit partial membership in several latent components. To overcome this limitation, we propose the mixed membership sub-Gaussian model, which extends the classical Gaussian mixture framework by allowing each observation to belong to multiple components. This model inherits the interpretability of the classical Gaussian mixture model while offering greater flexibility for capturing complex overlapping structures. We develop an efficient spectral algorithm to estimate the mixed membership of each individual observation, and under mild separation conditions on the component centres, we prove that the estimation error of the per-individual membership vector can be made arbitrarily small with high probability. To our knowledge, this is the first work to provide a computationally efficient estimator with such a vanishing-error guarantee for a mixed-membership extension of the Gaussian mixture model. Extensive experimental studies demonstrate that our method outperforms existing approaches that ignore mixed memberships.

Huan Qing

School of Economics and Finance, Chongqing University of Technology, Chongqing, 400054, China

Gaussian Mixture Models Non-Gaussianity Unsupervised

Dec 8, 2025stat.ML

High-Dimensional Change Point Detection via Graph Spanning Ratio

Inspired by graph-based methodologies, we introduce a novel graph-spanning algorithm designed to identify changes in both offline and online data across low to high dimensions. This versatile approach is applicable to Euclidean and graph-structured data with unknown distributions, while maintaining control over error probabilities. Theoretically, we demonstrate that the algorithm achieves high detection power when the magnitude of the change surpasses the lower bound of the minimax separation rate, which scales on the order of

\sqrt{nd}

. Our method outperforms other techniques in terms of accuracy for both Gaussian and non-Gaussian data. Notably, it maintains strong detection power even with small observation windows, making it particularly effective for online environments where timely and precise change detection is critical.

Katerina Papagiannouli, Yang-wen Sun, Vladimir Spokoiny

Department of Mathematics, University or Pisa · Department of Mathematics, Humboldt University of Berlin · Weierstrass Institut

Change-Point Detection Change Detection Non-Gaussianity Change

Aug 5, 2025eess.SP

Robust Sparse Bayesian Learning Based on Minimum Error Entropy for Noisy High-Dimensional Brain Activity Decoding

Objective: Sparse Bayesian learning provides an effective framework to solve high-dimensional problems in brain signal decoding. However, conventional likelihoods regarding data distributions, such as Gaussian or Bernoulli, are potentially inadequate for handling the noisy recordings of brain activity. Hence, this work aims to formulate a robust sparse Bayesian learning framework to address noisy high-dimensional brain activity decoding. Methods: Motivated by the commendable robustness of the minimum error entropy learning criterion for addressing non-Gaussian signals, this study reformulated the sparse Bayesian learning framework under a generalized Bayesian paradigm, in which the model parameter is regulated with the minimum error entropy loss rather than a conventional likelihood function. Results: Our developed SBL-MEE algorithm was evaluated with two real-world brain decoding tasks of regression and classification scenarios, respectively. Experimental results demonstrated that our approach not only realizes superior brain decoding performance than existing methods, but also presents more physiologically interpretable decoder patterns. Conclusion: Although minimum error entropy is not constructed from an arbitrary probabilistic distribution, it is effective to establish noise-robust inference in sparse Bayesian learning method. Significance: This work provides a powerful tool to improve brain activity decoding capability, particularly regarding the noisy high-dimensional setting, thus promoting biomedical engineering applications such as brain-computer interface.

Yuanhao Li, Badong Chen, Wenjun Bai +2

Center for Advanced Intelligence Project, RIKEN, Tokyo 103-0027, Japan · Department of Computational Brain Imaging, ATR Neural Information Analysis Laboratories, Kyoto 619-0237, Japan · Institute of Artificial Intelligence and Robotics (IAIR), Xi’an Jiaotong University, Xi’an 710049, China +1

Bayesian Networks Non-Gaussianity

Feb 27, 2025cs.LG

Multi-View Causal Discovery without Non-Gaussianity: Identifiability and Algorithms

Causal discovery is a difficult problem that typically relies on strong assumptions on the data-generating model, such as non-Gaussianity. In practice, many modern applications provide multiple related views of the same system, which has rarely been considered for causal discovery. Here, we leverage this multi-view structure to achieve causal discovery with weak assumptions. We propose a multi-view linear Structural Equation Model (SEM) that extends the well-known framework of non-Gaussian disturbances by alternatively leveraging correlation over views. We prove the identifiability of the model for acyclic SEMs. Subsequently, we propose several multi-view causal discovery algorithms, inspired by single-view algorithms (DirectLiNGAM, PairwiseLiNGAM, and ICA-LiNGAM). The new methods are validated through simulations and applications on neuroimaging data, where they enable the estimation of causal graphs between brain regions.

Ambroise Heurtebise, Omar Chehab, Pierre Ablin +2

Inria, CEA, University of Paris-Saclay, France · University of Carnegie Mellon, Pittsburgh PA, USA · Apple +1

Causal Discovery Methods Linear Structural Equation Models Identifiability Non-Gaussianity Spurious Correlations

Sep 27, 2024math.NA

Probabilistic Analysis of Least Squares, Orthogonal Projection, and QR Factorization Algorithms Subject to Gaussian Noise

We consider the effect of Gaussian perturbations on least-squares residuals, orthogonal projections, and QR-type algorithms. The problem that motivated our investigations is as follows: suppose that a full column-rank matrix

B\in\mathbb{R}^{m\times n}

has already been computed, and suppose that a new normalized column

q=(x+y)/\|x+y\|_2

is to be appended to

B

, where

x\perp\operatorname{span}(B)

is the ideal orthogonal component and

y

represents the orthogonalization error. How large can the condition number

κ([B,q])

of the resulting matrix

[B,q]

become? While we provide a Weyl-type bound on the singular values of

[B,q]

, in terms of the extremal singular values of

B

and the quantity

\|B^T y\|_2/\|x+y\|_2

, we also derive exact probability laws for norms and projection residuals under Gaussian perturbations. Finally, we use these probability laws to derive probabilistic condition-number bounds for QR-type processes with imperfect orthogonalization and exact normalization.

Ali Lotfi, Julien Langou, Mohammad Meysami

Department of Computer Science, University of Saskatchewan, Saskatoon, SK S7N 5A2, Canada · Department of Applied Mathematics, University of Colorado Denver, Denver, Colorado2026 80201, USA · Department of Mathematics, The University of Tulsa, Tulsa, OK 74104, USA

Spectral Norm Singular Value Decomposition Orthogonality Least Squares Non-Gaussianity Gaussian Noise+1

Jan 16, 2024stat.ML

Semidefinite programming relaxations and debiasing for MAXCUT-based clustering

In this paper, we consider the problem of partitioning a small data sample of size

n

drawn from a mixture of

2

sub-gaussian distributions in

\mathbb{R}^p

. We consider semidefinite programming relaxations of an integer quadratic program that is formulated essentially as finding the maximum cut on a graph, where edge weights in the cut represent dissimilarity scores between two nodes based on their

p

features. We define the signal-to-noise ratio (SNR) as

s^2 := \min\{n p γ^2, Δ^2\}

, where

Δ^2 := p γ

denotes the

\ell_2^2

distance between the two cluster centers. Our contributions are twofold. First, we provide a unified framework for analyzing three computationally efficient algorithms: SDP1, BalancedSDP, and Spectral clustering, yielding universal polynomial-rate misclassification guarantees for all three algorithms. Moreover, our theory allows for partial recovery (success rate

< 100\%

) as long as

s^2

is lower bounded by a constant. Second, we prove that the misclassification errors for SDP1 and BalancedSDP decay exponentially with respect to the SNR

s^2

and the BalancedSDP requires no explicit debiasing when the two clusters have equal sizes. To our knowledge, this is the first time such results are obtained for semidefinite relaxations of MAX CUT in population clustering. We provide simulation evidence illuminating the theoretical predictions.

Shuheng Zhou

University of California, Riverside, CA 92521

Convex Relaxation Maximum Independent Set Non-Gaussianity Separability