In this paper, we propose a provably correct algorithm for convolutive nonnegative matrix factorization (CNMF) under separability assumptions. CNMF is a convolutive variant of nonnegative matrix factorization (NMF), which functions as an NMF with additional sequential structure. This model is useful in a number of appl…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,786 papers · 148 categories
Trend · papers per month
48 results for “provably correct”
Proposes a method for obtaining interval bounds in off-policy evaluation.
problem Provides provably correct upper and lower bounds for off-policy evaluation.
method Searches for the maximum and minimum values of the expected reward among Lipschitz Q-functions.
result Introduces a Lipschitz value iteration method to monotonically tighten interval bounds.
ART trains neural nets to be both accurate and safe.
problem Ensuring neural nets are both accurate and safe during training.
method Integrates an optimization-based abstraction refinement loop into the learning process.
result Enables training provably correct networks with respect to safety properties.
Non-negative matrix factorization (NMF) is a natural model of admixture and is widely used in science and engineering. A plethora of algorithms have been developed to tackle NMF, but due to the non-convex nature of the problem, there is little guarantee on how well these methods work. Recently a surge of research have …
New neural methods for stable control with provable guarantees.
problem Designing stable control policies for nonlinear systems.
method Neural network Lyapunov functions and a falsifier to guide learning.
result Provable stability of controlled nonlinear systems.
PAC-Wrap provides provable guarantees for semi-supervised anomaly detection.
problem Ensuring reliable anomaly detection in safety-critical applications.
method PAC-Wrap wraps around existing anomaly detection methods to provide PAC guarantees.
result PAC-Wrap effectively provides rigorous guarantees for various anomaly detectors.
The Cheap Gradient Principle (Griewank 2008) --- the computational cost of computing the gradient of a scalar-valued function is nearly the same (often within a factor of ) as that of simply computing the function itself --- is of central importance in optimization; it allows us to quickly obtain (high dimensional) …
New AI error correctors improve classifier performance with provable guarantees.
problem Improving AI classifier performance with scarce training data.
method Weakly supervised AI error correctors with performance guarantees.
result Provable performance guarantees for AI error correction.
Learning Self-Correctable Policies and Value Functions from Demonstrations with Negative Samplingcs.LG
Algorithm corrects mistakes in imitation learning tasks.
problem Covariate shift problem in learning from demonstrations.
method Value Iteration with Negative Sampling (VINS) for conservative extrapolation.
result VINS corrects mistakes of the behavioral cloning policy.
New partial models correct for confounding effects in reinforcement learning.
problem Confounding effects in partial models lead to incorrect planning.
method Introduces causally correct partial models for reinforcement learning.
result Causally correct partial models avoid confounding effects and improve planning accuracy.
This research improves online learning by correcting for target shift in machine learning.
problem Online learning struggles with distributional shift, especially in target values.
method Derives closed-form expressions for online and offline learning, and target correction.
result Online kernel-based learning can learn the same predictor as offline learning with target correction.
This work explores test-time scaling strategies for LLMs, improving sample efficiency and expressiveness.
problem Understanding the sample efficiency and expressiveness of test-time scaling strategies for LLMs.
method Established separation and expressiveness results for self-consistency, best-of-, and self-correction strategies.
result Self-correction enables Transformers to simulate online learning over multiple tasks without prior knowledge.
A new convex model tackles noisy separable NMF with provable correctness.
problem Noisy separable NMF with multiple data points near basis vectors.
method Smooth separability assumption, convex model, fast gradient method.
result The convex model provably recovers factors in the presence of noise.
We study the problem of subspace tracking in the presence of missing data (ST-miss). In recent work, we studied a related problem called robust ST. In this work, we show that a simple modification of our robust ST solution also provably solves ST-miss and robust ST-miss. To our knowledge, our result is the first `compl…
PatchGuard defends against localized adversarial patches with provable robustness.
problem Localized adversarial patches induce misclassification in machine learning models.
method PatchGuard uses CNNs with small receptive fields and robust masking to detect and mask corrupted features.
result PatchGuard achieves state-of-the-art provable robust accuracy and clean accuracy.
We consider the problem of matrix column subset selection, which selects a subset of columns from an input matrix such that the input can be well approximated by the span of the selected columns. Column subset selection has been applied to numerous real-world data applications such as population genetics summarization,…
Develops a new tensor model for clustering with degree correction.
problem Clustering with unknown degree heterogeneity in multiway data.
method Degree-corrected tensor block model with estimation guarantees.
result Demonstrates an intrinsic statistical-to-computational gap for tensors of order three or greater.
dtControl uses decision trees to represent controllers efficiently and explainably.
problem Representing controllers concisely and explainably.
method dtControl uses decision tree learning algorithms to represent controllers. Novel techniques for determinizing controllers are introduced.
result Novel techniques for determinizing controllers during decision tree construction are extremely efficient, yielding small decision trees.
Most existing algorithms for dictionary learning assume that all entries of the (high-dimensional) input data are fully observed. However, in several practical applications (such as hyper-spectral imaging or blood glucose monitoring), only an incomplete fraction of the data entries may be available. For incomplete sett…
Parallel Mappercs.CV
The construction of Mapper has emerged in the last decade as a powerful and effective topological data analysis tool that approximates and generalizes other topological summaries, such as the Reeb graph, the contour tree, split, and joint trees. In this paper, we study the parallel analysis of the construction of Mappe…
Modern neural networks are typically trained in an over-parameterized regime where the parameters of the model far exceed the size of the training data. Such neural networks in principle have the capacity to (over)fit any set of labels including pure noise. Despite this, somewhat paradoxically, neural network models tr…
A fast spectral algorithm detects community structure in evolving graphs.
problem Detecting community structure in time-evolving sparse graphs.
method Extension of the Bethe-Hessian matrix for spectral community detection.
result The algorithm reaches the optimal detectability threshold and outperforms other methods.
Comparing the Value of Labeled and Unlabeled Data in Method-of-Moments Latent Variable Estimationcs.LG
New framework assesses value of labeled vs unlabeled data in latent variable models.
problem Determining the optimal use of labeled and unlabeled data in latent variable models.
method Developed a bias-variance decomposition of the generalization error for method-of-moments latent variable estimation, and introduced a correction for misspecification.
result Labeled data is more valuable than unlabeled data when models are misspecified, but this value can be reduced with correction.
BEMA reduces bias in EMA, leading to faster convergence and better performance.
problem Stochasticity in language model fine-tuning destabilizes training.
method Bias-Corrected Exponential Moving Average (BEMA) augmentation of EMA.
result BEMA leads to significantly improved convergence rates and final performance.
Develops a comprehensive theory of corruption in supervised learning.
problem Widespread corruption in data collection affects supervised learning problems.
method Introduces a general theory of corruption using Markov kernels, distinguishing and comparing corruption types.
result Establishes a unified framework for corruption types and develops mitigation strategies.
This paper describes a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image of the matrix, called a sketch. These methods can preserve structural properties of the input matrix, such as positive-semidefiniteness, and they can produce approximations with a user-speci…
Principal Components Analysis (PCA) is one of the most widely used dimension reduction techniques. Robust PCA (RPCA) refers to the problem of PCA when the data may be corrupted by outliers. Recent work by Cand{è}s, Wright, Li, and Ma defined RPCA as a problem of decomposing a given data matrix into the sum of a low-ran…
One-step Bellman alignment improves online RL by reducing task mismatch.
problem Online RL struggles with task similarity defined by rewards or transitions.
method One-step Bellman alignment and re-weighted targeting (RWT) to correct task mismatch.
result Regret bounds show task shift complexity, not target MDP, affects performance.
The goal of imitation learning is for an apprentice to learn how to behave in a stochastic environment by observing a mentor demonstrating the correct behavior. Accurate prior knowledge about the correct behavior can reduce the need for demonstrations from the mentor. We present a novel approach to encoding prior knowl…
The separability assumption (Donoho & Stodden, 2003; Arora et al., 2012) turns non-negative matrix factorization (NMF) into a tractable problem. Recently, a new class of provably-correct NMF algorithms have emerged under this assumption. In this paper, we reformulate the separable NMF problem as that of finding the ext…
Paper proves noise-tolerant SSC using greedy methods under coherence conditions.
problem Proving noise-tolerant SSC using greedy methods under coherence conditions.
method Derives coherence-based sufficient conditions for correct neighbor identification using MP/OMP in the presence of bounded noise.
result MP/OMP succeed in identifying correct neighbors under certain noise levels, leading to higher clustering accuracy.
FedSplit improves federated learning by ensuring correct convergence to optimal solutions.
problem Federated learning's fixed points do not always correspond to optimal solutions in simple convex settings.
method FedSplit uses operator splitting procedures to solve distributed convex minimization problems with additive structure.
result FedSplit ensures that the fixed points correspond to optima of the original optimization problem.
Given a binary prediction problem, which performance metric should the classifier optimize? We address this question by formalizing the problem of Metric Elicitation. The goal of metric elicitation is to discover the performance metric of a practitioner, which reflects her innate rewards (costs) for correct (incorrect)…
System uses neural networks to prove program equivalence via rewrite rules.
problem Proving equivalence between two dataflow graphs.
method Developed a graph-to-sequence neural network trained on example generation to find semantics-preserving rewrite rules.
result System correctly outputs a rewrite sequence for 96% of program pairs, proving equivalence.
Prediction suffix trees (PST) provide an effective tool for sequence modelling and prediction. Current prediction techniques for PSTs rely on exact matching between the suffix of the current sequence and the previously observed sequence. We present a provably correct algorithm for learning a PST with approximate suffix…
Deployment of deep neural networks (DNNs) in safety- or security-critical systems requires provable guarantees on their correct behaviour. A common requirement is robustness to adversarial perturbations in a neighbourhood around an input. In this paper we focus on the norm and aim to compute, for a trained DNN an…
New method improves dictionary recovery from over-realized models.
problem Theoretical guarantees for model recovery in dictionary learning are limited.
method Search over larger over-realized models to facilitate dictionary recovery.
result Model recovery can be upper-bounded by empirical risk and generalization gap.
New tiling algorithm for hyperbolic 3-manifolds, characterizing cusp areas.
problem Characterizing and computing maximal cusp areas in hyperbolic 3-manifolds.
method Developed a new tiling algorithm and provided simpler expressions for distances.
result Completely characterized the space of cusp neighborhoods and found the Epstein-Penner decomposition.
Two kernel Stein tests control decision errors in non-parametric model comparison.
problem Non-parametric multiple model comparison.
method Two statistical tests controlling false positive and false discovery rates.
result The first test has a higher true positive rate than the second under appropriate conditions.
The paper establishes principles for initializing and designing GNNs with ReLU activations to avoid oversmoothing and correlation collapse.
problem Oversmoothing and correlation collapse in deep ReLU GNNs.
method The paper derives and validates three principles for initialization and architecture selection in finite width graph neural networks with ReLU activations.
result Correct initialization, residual aggregation operators, and residual connections significantly improve early training dynamics in deep ReLU GNNs.
In this paper, we present multi-task structure learning for Gaussian graphical models. We analyze the sufficient number of samples for the correct recovery of the support union and edge signs. We also analyze the necessary number of samples for any conceivable method by providing information-theoretic lowe…
We analyze the complexity of Gibbs samplers for inference in crossed random effect models used in modern analysis of variance. We demonstrate that for certain designs the plain vanilla Gibbs sampler is not scalable, in the sense that its complexity is worse than proportional to the number of parameters and data. We thu…
Many computer vision tasks involve processing large amounts of data contaminated by outliers, which need to be detected and rejected. While outlier detection methods based on robust statistics have existed for decades, only recently have methods based on sparse and low-rank representation been developed along with guar…
The problem of change-point estimation is considered under a general framework where the data are generated by unknown stationary ergodic process distributions. In this context, the consistent estimation of the number of change-points is provably impossible. However, it is shown that a consistent clustering method may …
Improved elimination strategies for adaptive bandit identification reduce sample complexity and computational burden.
problem Inefficient elimination strategies in bandit identification.
method Adaptive elimination methods that update sampling rules frequently and reduce problem size.
result Adaptive elimination methods achieve better sample complexity and computational efficiency.
Bayesian learning is built on an assumption that the model space contains a true reflection of the data generating mechanism. This assumption is problematic, particularly in complex data environments. Here we present a Bayesian nonparametric approach to learning that makes use of statistical models, but does not assume…
Supervised topic models simultaneously model the latent topic structure of large collections of documents and a response variable associated with each document. Existing inference methods are based on variational approximation or Monte Carlo sampling, which often suffers from the local minimum defect. Spectral methods …
We study the Low Rank Phase Retrieval (LRPR) problem defined as follows: recover an matrix of rank from a different and independent set of phaseless (magnitude-only) linear projections of each of its columns. To be precise, we need to recover from …