Block Median of Means

All benchmarks

We propose a small--tailed Bayesian median-of-means (SB--MoM) framework for robust learning under heavy-tailed and adversarial contamination, and instantiate it in a new nonnegative matrix factorisation algorithm, \emph{SB--MoM--NMF}. At the scalar level, we combine block median-of-means aggregation with a small--tailed prior on block risks, deriving deviation bounds, oracle inequalities, and a breakdown point of one half under arbitrary outliers. We then lift this construction to blockwise NMF: the data are partitioned into column blocks, losses are aggregated via SB--MoM, and multiplicative/ALS-style updates are obtained for both factors with convergence guarantees.