Optimizes quickest change detection with bounded means under ARL constraint.
problem Quickest detection of changepoints with bounded means under ARL constraint.
method Derives universal lower and upper bounds for detection delay.
result Achieves universal lower bound in the bounded mean detection setting.
New algorithm detects changes quickly without knowing parameters, near optimally.
problem Quickest change detection with unknown parameters.
method Leverages theoretical asymptotic properties to derive a scalable approximate algorithm with near optimal performance.
result Detects changes in constant complexity with near optimal performance.
Robust quickest change detection method for unknown score functions.
problem Detecting changes in data streams with unknown pre- and post-change distributions.
method Selects least-favorable distributions and robustifies score-based detection algorithm.
result Demonstrates improved performance in simulations.
New method detects market liquidity changes using order book data.
problem Detecting changes in market liquidity.
method Marked Hawkes processes and minimax quickest detection problem for doubly-stochastic Poisson process.
result Optimal stopping rule for detecting intensity changes in market liquidity.
New CUSUM algorithm detects changes in unnormalized models.
problem Change detection in models with unknown normalization constants.
method Score-based CUSUM (SCUSUM) algorithm based on Fisher divergence and Hyvärinen score.
result Asymptotic optimality of the SCUSUM algorithm demonstrated.
Non-parametric estimators improve quickest changepoint detection under irregular sequence lengths.
problem Limited and irregular sequence lengths hinder application of ARL and ADD in QCD.
method Analogies with survival analysis to model detection probabilities under truncation.
result KM-ARL and KM-ADD non-parametric estimators are asymptotically unbiased.
Optimizes quickest detection of drift in Brownian motion with false negatives.
problem Quickest detection of drift in Brownian motion with false negatives.
method Formulated as an optimal multiple stopping problem, then equivalent to a recursive optimal stopping problem, solved using free boundary methods.
result Explicit formulae for expected cost and optimal strategy found.
Optimizes latency and false alarm probability in change detection problems.
problem Balancing latency and false alarms in non-stationary environments.
method Develops order-optimal change detectors under specified latency and false alarm levels.
result Derives a universal lower bound on latency and develops order-optimal detectors.
Master algorithm fails to detect non-stationarity in practical settings.
problem Non-Stationary Reinforcement Learning without prior knowledge.
method Master algorithm tested under various conditions, including piecewise stationary multi-armed bandits.
result Master's non-stationarity detection is ineffective for practical horizons, leading to performance similar to random restarting.
Change detection (CD) in time series data is a critical problem as it reveal changes in the underlying generative processes driving the time series. Despite having received significant attention, one important unexplored aspect is how to efficiently utilize additional correlated information to improve the detection and…
Geometric QHD tests improve hub detection in correlated data.
problem Detecting hubs in correlated data with evolving correlations.
method Geometric QHD tests combining QCD and QHD, clustering.
result Improved hub detection in correlated data.
New method detects changes in high-dimensional Markov processes without explicit likelihood evaluation.
problem Quickest change detection in Markov processes with unknown transition kernels.
method Learn conditional score from sample pairs, develop score-based CUSUM procedure.
result Exponential lower bounds on mean time to false alarm and asymptotic upper bounds on detection delay.
Optimizes sensor usage for detecting abrupt changes in sensor data.
problem Efficiently detect abrupt changes in sensor data with limited resources.
method Proposes a computationally efficient online sensing scheme that balances exploration and exploitation.
result Expected delay bounds match information-theoretic lower bounds, establishing optimality of the method.
This paper combines data-driven and model-driven methods for real-time misinformation detection. Our algorithm, named QuickStop, is an optimal stopping algorithm based on a probabilistic information spreading model obtained from labeled data. The algorithm consists of an offline machine learning algorithm for learning …
We consider the problem of quickest change-point detection in data streams. Classical change-point detection procedures, such as CUSUM, Shiryaev-Roberts and Posterior Probability statistics, are optimal only if the change-point model is known, which is an unrealistic assumption in typical applied problems. Instead we p…
Algorithm detects causal change points quickly with adaptive interventions.
problem Detecting changes in causal models with interventions.
method Centralization technique, Kullback-Leibler divergence for intervention selection, adaptive intervention policy.
result Theoretical first-order optimality and validation through simulations and real-world studies.
New method detects and locates changes in spatio-temporal point processes.
problem Detecting and localizing changes in spatio-temporal data.
method Score-based, likelihood-free approach estimating change time and region.
result The method provides theoretical guarantees on detection and localization accuracy.
Study on signal detection in sparse additive models with nonasymptotic minimax rates.
problem Signal detection in sparse additive models.
method Nonasymptotic minimax analysis of signal detection in sparse additive models.
result Established minimax separation rate for signal detection.
Study on signal detection in heteroscedastic Gaussian sequences with sparse alternatives.
problem Signal detection in heterogeneous Gaussian sequences with unknown means and known covariance.
method Characterization of minimax separation radius and derivation of matching upper and lower bounds.
result Matching minimax upper and lower bounds for signal detection in heteroscedastic Gaussian sequences.
This paper surveys some recent developments in fundamental limits and optimal algorithms for network analysis. We focus on minimax optimal rates in three fundamental problems of network analysis: graphon estimation, community detection, and hypothesis testing. For each problem, we review state-of-the-art results in the…
Deep learning detects novel changes in time series data.
problem Detecting novel changes in time series with unknown probability structures.
method Causally extracts an innovations sequence for novelty detection.
result Minimax optimality established for the novelty detection method.
MOSAIC detects change points in dynamic networks with low-rank and sparse changes.
problem Detecting change points in dynamic networks with specific structural properties.
method Eigen-decomposition-based test with screened signals and residual-based adjustment.
result MOSAIC achieves minimax-optimal detection and testing rates.
Community detection is a central problem of network data analysis. Given a network, the goal of community detection is to partition the network nodes into a small number of clusters, which could often help reveal interesting structures. The present paper studies community detection in Degree-Corrected Block Models (DCB…
Detecting a planted submatrix in random matrices with non-asymptotic methods.
problem Detecting a planted submatrix in random matrices with non-zero entries.
method Established minimax lower bounds and derived optimal tests for distinguishing the null and alternative hypotheses.
result Non-asymptotic upper and lower bounds match for any configuration of matrix dimensions.
Novel graph-spanning algorithm detects changes in high-dimensional data.
problem Detecting changes in high-dimensional data across various distributions.
method Graph-spanning algorithm designed for offline and online data.
result Achieves high detection power with minimal separation rate.
We consider the sequential anomaly detection problem in the one-class setting when only the anomalous sequences are available and propose an adversarial sequential detector by solving a minimax problem to find an optimal detector against the worst-case sequences from a generator. The generator captures the dependence i…
The paper provides theoretical guarantees for neural network-based anomaly detection.
problem Theoretical guarantees for unsupervised neural network-based anomaly detection.
method Casting anomaly detection as a binary classification problem, establishing non-asymptotic upper bounds and convergence rates.
result The convergence rate on the excess risk matches the minimax optimal rate.
Several problems such as network intrusion, community detection, and disease outbreak can be described by observations attributed to nodes or edges of a graph. In these applications presence of intrusion, community or disease outbreak is characterized by novel observations on some unknown connected subgraph. These prob…
We investigate the use of Minimax distances to extract in a nonparametric way the features that capture the unknown underlying patterns and structures in the data. We develop a general-purpose and computationally efficient framework to employ Minimax distances with many machine learning methods that perform on numerica…
New estimator for overlapping community detection in graphs.
problem Reconstructing community relations in graphs with overlapping memberships.
method Proposes a new estimator for Mixed-Membership Stochastic Block Model (MMSB) under diverging spiked eigenvalues condition.
result New estimator matches theoretical minimax lower bound on estimation error.
Efficient algorithm detects communities in noisy graphs with robustness.
problem Community detection in stochastic block models with adversarial corruptions.
method Efficient algorithm using semidefinite programming for robust clustering.
result Achieves error O(ε)+e−2C(1±o(1)) for ε-fraction of corruptions. Study detects boundaries in unlabeled noisy images without labels.
problem Detecting boundaries in unlabeled noisy images without labels.
method Proposed a continuous hinge-type surrogate loss for boundary detection, combined with deep neural networks.
result Deep neural network achieves minimax-optimal boundary recovery rate under piecewise smooth boundary model.
Paper introduces a statistical framework for watermarking LLM-generated text.
problem Detecting LLM-generated text from human-written text with statistical signals.
method Hypothesis testing formulation, pivotal statistic selection, secret key, closed-form expression of false negative rate, minimax optimization.
result Derives optimal detection rules for LLM-generated text, demonstrating higher power than existing methods.
Paper proposes DMGD for integrating outlier and community detection in graph embedding.
problem Outlier nodes affect graph embedding of regular nodes, especially in networks with multiple communities.
method DMGD integrates outlier and community detection with node embedding using multiclass graph description.
result DMGD detects outliers relative to their communities and achieves better node embedding compared to state-of-the-arts.
The study reveals fundamental limits of fraud detection in card payment networks.
problem Fraud detection in card payment networks is challenging due to structural information impairments.
method Formalized card authorization as a sequential decision problem with delayed feedback, derived minimax regret lower bound.
result Improving issuer reporting quality or reducing censorship can yield larger reductions in the regret floor than increasing model complexity.
We perform a finite sample analysis of the detection levels for sparse principal components of a high-dimensional covariance matrix. Our minimax optimal test is based on a sparse eigenvalue statistic. Alas, computing this test is known to be NP-complete in general, and we describe a computationally efficient alternativ…
Randomization is minimax-optimal for variance in experimental design, even with structure.
problem Designing optimal randomized experiments for variance minimization.
method Analyzing permutation symmetric and non-symmetric sets of outcomes, proposing inference-constrained MSOD.
result Randomization is minimax-optimal for variance, even with structure, and requires uniformity constraints for Fisher's exact test.
New algorithm detects communities near KS threshold with optimal rate, even in noisy conditions.
problem Community detection in symmetric stochastic block models with noisy data.
method Polynomial-time algorithm using Sum-of-Squares framework and robust majority voting.
result Achieves minimax-optimal misclassification rate near Kesten-Stigum threshold, even with node corruption.
New tests detect communities in dense bipartite graphs with high accuracy.
problem Detecting communities in dense bipartite graphs with high accuracy.
method Non-asymptotic upper and lower bounds, novel minimax-optimal tests, hard-thresholded nonlinear statistics.
result Non-asymptotic upper and lower bounds match for any configuration of graph sizes.
Estimating signals with linear recurrence relations under Gaussian noise is nearly as hard as sparse signals.
problem Estimating discrete-time signals with unknown linear recurrence relations in Gaussian noise.
method Analyzing shift-invariant subspaces and their Fourier coefficients as reproducing filters.
result The statistical complexity is nearly the same as for s-sparse signals, and the estimator is tractable. DARLING tackles non-stationary RL with guarantees, improving dynamic regret.
problem Non-stationary reinforcement learning in unknown change points.
method Detection Augmented Reinforcement Learning (DARLING) for tabular and linear MDPs.
result DARLING matches minimax lower bounds in tabular and linear MDPs.
Study minimax estimation of stratified structure from i.i.d. samples.
problem Estimating stratified structure from i.i.d. samples of stratified mixtures of immersed manifolds.
method Ascending hierarchical co-detection of points belonging to different layers, identifying number of layers and their dimensions, assigning points to layers accurately, estimating tangent spaces optimally.
result Achieves optimal estimation of mixture components at their optimal dimension-specific rates adaptively.
Optimistic search speeds up change point detection in large datasets.
problem Efficiently detecting change points in large-scale data with high computational demands.
method Adaptive logarithmic queries to reduce evaluation complexity.
result Asymptotic minimax optimality and fast localization rates for change point detection.
Study tests uniformity of categorical data against missing-ball alternatives, finding chi-squared test outperforms.
problem Testing uniformity of categorical data against missing-ball alternatives.
method Characterizes minimax risk, uses collisions and chi-squared test, reduces to structured subset of alternatives.
result Minimax test outperforms chi-squared test under least favorable alternative.
The paper studies inference in hypergraph β-models with multiple layers.
problem Estimating and testing in hypergraph β-models with degree heterogeneity.
method Maximum likelihood estimation and likelihood ratio test for hypergraph β-models with multiple layers.
result The ML estimate and LR test are optimally powerful under the null hypothesis.
Study online conformal prediction for non-stationary data with optimal training-conditional regret.
problem Online prediction for non-stationary data streams with unknown distribution drift.
method Proposes split-conformal and full-conformal algorithms that adapt to drift detection and incorporate stability for online learning.
result Proves minimax-optimal regret for online full conformal algorithm under appropriate restrictions.
The paper improves prediction and testing for signals from a linear combination of translated features with Gaussian noise.
problem Predicting and testing signals from a linear combination of translated features with varying scale parameter and Gaussian noise.
method Extends previous off-the-grid prediction results, improves minimal distance between features, proposes a goodness-of-fit test with upper bounds.
result Upper bounds on the minimax separation rate match those for the high-dimensional linear model, matching the lower bound.
New findings suggest minimax optimality doesn't guarantee distribution learning for GANs.
problem Understanding when GANs can truly learn the underlying distribution.
method Using cryptographic assumptions and ReLU network generators, the paper shows that achieving minimax optimality is insufficient for distribution learning.
result Achieving minimax optimality is insufficient for distribution learning in the usual statistical sense.