We consider the mixed regression problem with two components, under adversarial and stochastic noise. We give a convex optimization formulation that provably recovers the true solution, and provide upper bounds on the recovery errors for both arbitrary noise and stochastic noise settings. We also give matching minimax …
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,695 papers · 148 categories
Trend · papers per month
48 results for “recovery error bounds”
We introduce a general framework to handle structured models (sparse and block-sparse with possibly overlapping blocks). We discuss new methods for their recovery from incomplete observation, corrupted with deterministic and stochastic noise, using block- regularization. While the current theory provides promis…
Study exact partition recovery with same-cluster oracle, bounded error.
problem Exact recovery of partitions with same-cluster oracle in adversarial error.
method Novel connection to correlation clustering, Rényi-Ulam framework, upper and lower bounds, randomized algorithm analysis, adaptivity-query complexity study.
result Upper and lower bounds on worst-case query complexity, expected performance bounds of randomized algorithm.
Higher-order tensors can represent scores in a rating system, frames in a video, and images of the same subject. In practice, the measurements are often highly quantized due to the sampling strategies or the quality of devices. Existing works on tensor recovery have focused on data losses and random noises. Only a few …
In this paper, we develop a relative error bound for nuclear norm regularized matrix completion, with the focus on the completion of full-rank matrices. Under the assumption that the top eigenspaces of the target matrix are incoherent, we derive a relative upper bound for recovering the best low-rank approximation of t…
In this paper we consider the cluster estimation problem under the Stochastic Block Model. We show that the semidefinite programming (SDP) formulation for this problem achieves an error rate that decays exponentially in the signal-to-noise ratio. The error bound implies weak recovery in the sparse graph regime with bou…
Study recovers community structure from coarse graph measurements.
problem Community recovery from low-resolution graph measurements.
method Formalized coarsening process of graph measurements, developed conditions for perfect recovery.
result Simple and closed-form asymptotic conditions for perfect recovery of coarse graph communities.
The paper provides entrywise bounds for Sparse PCA, improving upon previous results.
problem Sparse Principal Component Analysis (PCA) recovery error characterization in spectral or Frobenius norms.
method Entrywise bounds for Sparse PCA under general high-dimensional subgaussian design, using sparsistent algorithms.
result Improved entrywise bounds for Sparse PCA, finer characterization of estimation error.
We discuss a general notion of "sparsity structure" and associated recoveries of a sparse signal from its linear image of reduced dimension possibly corrupted with noise. Our approach allows for unified treatment of (a) the "usual sparsity" and "usual recovery," (b) block-sparsity with possibly overlapping blo…
New insights into variable selection with different model assumptions.
problem Sparse recovery with error guarantees in variable selection.
method Separation between oblivious and adaptive models of sparse recovery.
result Proves a surprising contrast between oblivious and adaptive models in sparse recovery.
Paper reconciles minimax rates and optimal recovery rates for noisy observations.
problem Estimating a function from noisy observations.
method Develops NLA minimax rates for Besov classes in -norms.
result NLA minimax rates continuously depend on noise level and match optimal recovery rates as noise decreases.
Sign information is the key to overcoming the inevitable saturation error in compressive sensing systems, which causes information loss and results in bias. For sparse signal recovery from saturation, we propose to use a linear loss to improve the effectiveness from existing methods that utilize hard constraints/hinge …
This paper improves support recovery in universal one-bit compressed sensing.
problem Support recovery in one-bit compressed sensing for sparse signals.
method Proposes approximate support recovery and superset recovery algorithms with polynomial-time complexity.
result Achieves improved support recovery with fewer measurements compared to existing methods.
Paper develops a new algorithm for sparse signal recovery.
problem Sparse signal recovery from noisy observations.
method Iterative Stochastic Optimization using Stochastic Mirror Descent.
result Linear convergence during preliminary phase of the routine.
The support recovery problem consists of determining a sparse subset of a set of variables that is relevant in generating a set of observations, and arises in a diverse range of settings such as compressive sensing, and subset selection in regression, and group testing. In this paper, we take a unified approach to supp…
Paper quantizes heavy-tailed data for near optimal estimation rates.
problem Estimating parameters from heavy-tailed data with quantization.
method Truncate and dither data, then uniformly quantize; achieves near minimax rates.
result Near optimal estimation rates achievable with quantized data.
Model-based neural networks generalize better than ReLU networks for sparse recovery.
problem Understanding and quantifying the superior generalization of model-based neural networks.
method Using complexity measures like global and local Rademacher complexities, the paper provides theoretical bounds on generalization and estimation errors.
result Model-based neural networks exhibit higher generalization capabilities for sparse recovery problems compared to ReLU networks.
For the problems of low-rank matrix completion, the efficiency of the widely-used nuclear norm technique may be challenged under many circumstances, especially when certain basis coefficients are fixed, for example, the low-rank correlation matrix completion in various fields such as the financial market and the low-ra…
A hierarchical model shows how scaling laws emerge from sequential feature recovery.
problem Emergence of scaling laws from feature learning in multi-layer networks.
method Layer-wise spectral algorithm adapted to compositional structure, sequential feature detection.
result Sequential detection of latent features, leading to explicit power-law decay of prediction error.
Small initialization improves tensor recovery from noisy data.
problem Recovering low-tubal-rank tensors from noisy measurements.
method Factorized gradient descent with small initialization.
result Achieves nearly minimax optimal recovery error.
Estimates shared linear subspace from noisy data with multiple users.
problem Recovering shared linear subspace from noisy data with non-isotropic noise.
method Estimates shared subspace using at least two data points per user, avoiding restrictive assumptions.
result Upper and lower bounds for estimation error match, showing no additional error due to noise irregularity.
IRKSN algorithm achieves sparse recovery with wider applicability conditions.
problem Sparse recovery challenges due to NP-hard nature and restrictive conditions.
method IRKSN algorithm based on -support norm regularizer.
result Achieves sparse recovery with explicit constants and standard linear rate.
Proposes a new sparse recovery method using generalized error function.
problem Sparse recovery in signal processing and imaging.
method Introduces a penalty function with shape and scale parameters for sparse recovery.
result The method improves MRI reconstruction and is theoretically sound.
Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutationsmath.ST
We tackle tensor denoising with unknown permutations, achieving optimal recovery with polynomial estimators.
problem Structured tensor denoising with unknown permutations in recommendation systems, neuroimaging, etc.
method Developed a constrained least-squares estimator in a block-wise polynomial family.
result Achieved the minimax error bound with polynomial estimators of degree up to .
Unified analysis of neural networks for sparse signal recovery.
problem Sparse signal recovery from few linear measurements.
method Introduces a general class of neural networks with weight-sharing, analyzes their Rademacher complexity, and derives generalization bounds.
result Derives generalization bounds that depend linearly on the number of parameters and depth, applicable to various neural network types.
We are motivated by problems that arise in a number of applications such as Online Marketing and Explosives detection, where the observations are usually modeled using Poisson statistics. We model each observation as a Poisson random variable whose mean is a sparse linear superposition of known patterns. Unlike many co…
We extend the theory of low-rank matrix recovery and completion to the case when Poisson observations for a linear combination or a subset of the entries of a matrix are available, which arises in various applications with count data. We consider the usual matrix recovery formulation through maximum likelihood with pro…
This paper considers the recovery of a low-rank matrix from an observed version that simultaneously contains both (a) erasures: most entries are not observed, and (b) errors: values at a constant fraction of (unknown) locations are arbitrarily corrupted. We provide a new unified performance guarantee on when the natura…
Optimal recovery framework for non-IID data in Hilbert spaces.
problem Generalization in non-IID data scenarios.
method Optimal recovery perspective, semidefinite programming, kernel ridgeless regression.
result Optimal recovery formula coincides with kernel ridgeless regression in some cases.
We provide a unified treatment of a broad class of noisy structure recovery problems, known as structured normal means problems. In this setting, the goal is to identify, from a finite collection of Gaussian distributions with different means, the distribution that produced some observed data. Recent work has studied s…
New findings on computational limits for estimating hidden structures.
problem Estimating hidden structures in noisy data.
method Use of low-degree polynomials as a restricted model of computation.
result Established low-degree hardness of recovery problems for easy detection problems.
In this paper, we study the problem of recovering a group sparse vector from a small number of linear measurements. In the past the common approach has been to use various "group sparsity-inducing" norms such as the Group LASSO norm for this purpose. By using the theory of convex relaxations, we show that it is also po…
We study the problem of recovering a hidden community of cardinality from an symmetric data matrix , where for distinct indices , if both belong to the community and otherwise, for two known probability distributions and depending on . If $P={\r…
Global optimization for low-dimensional switching linear regression and bounded-error estimationcs.LG
The paper provides global optimization algorithms for two particularly difficult nonconvex problems raised by hybrid system identification: switching linear regression and bounded-error estimation. While most works focus on local optimization heuristics without global optimality guarantees or with guarantees valid only…
Recovering edge activities from node activity data in temporal networks.
problem Recovering lost edge activity data from aggregated node activity data in temporal networks.
method Analyzing the relationship between edge activity and node activity data, using both theoretical and empirical methods to show recovery is possible and under what conditions.
result Recovery of edge activities from node activities is possible with surprising accuracy, even when network density increases.
New bounds for adaptive control in high dimensions without fixed state space.
problem Adaptive control of linear systems in high or infinite dimensions.
method Novel perturbation bound for certainty equivalence, scaling with prediction error.
result First regret bounds for LQR in infinite dimensional systems, independent of ambient dimension.
The paper infers multiple graphs from stationary signals on them.
problem Inferring multiple graphs from signals observed on their nodes.
method Convex optimization method leveraging matrix polynomial commutation.
result High-probability bounds on recovery error provided.
Hidden Integrality and Semi-random Robustness of SDP Relaxation for Sub-Gaussian Mixture Modelstat.ML
We consider the problem of estimating the discrete clustering structures under the Sub-Gaussian Mixture Model. Our main results establish a hidden integrality property of a semidefinite programming (SDP) relaxation for this problem: while the optimal solution to the SDP is not integer-valued in general, its estimation …
We demonstrate that the primal-dual witness proof method may be used to establish variable selection consistency and -bounds for sparse regression problems, even when the loss function and/or regularizer are nonconvex. Using this method, we derive two theorems concerning support recovery and -…
Analysis of non-asymptotic estimation error and structured statistical recovery based on norm regularized regression, such as Lasso, needs to consider four aspects: the norm, the loss function, the design matrix, and the noise model. This paper presents generalizations of such estimation error analysis on all four aspe…
This paper sets thresholds for recovering vertex correspondences in partially correlated graphs.
problem Recovering hidden vertex correspondences in partially correlated graphs.
method Proposed partially correlated Erdős-Rényi graphs model; information-theoretic thresholds; correlated functional digraphs.
result Optimal rates for partial and exact recovery of vertex correspondences.
SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samplesstat.ML
Improved algorithm for partial recovery of tree-structured graphs with noisy data.
problem Learning Ising tree models with noisy observations.
method Symmetrized Geometric Averaging (SGA) algorithm with improved sample complexity.
result Significantly better sample complexity for partial tree recovery.
The completion of tensors, or high-order arrays, attracts significant attention in recent research. Current literature on tensor completion primarily focuses on recovery from a set of uniformly randomly measured entries, and the required number of measurements to achieve recovery is not guaranteed to be optimal. In add…
Poisson Matrix Completionstat.ML
We extend the theory of matrix completion to the case where we make Poisson observations for a subset of entries of a low-rank matrix. We consider the (now) usual matrix recovery formulation through maximum likelihood with proper constraints on the matrix , and establish theoretical upper and lower bounds on the rec…
Paper bounds tensor decomposition's RLCT, aiding Bayesian inference.
problem Unclear mathematical property of tensor decomposition.
method Algebraic geometrical method for upper bound derivation.
result Upper bound of real log canonical threshold (RLCT) derived.
New algorithm recovers matrices with unknown correspondences.
problem Recovering matrices from observations with unknown correspondences.
method Solves a nuclear norm minimization problem via proximal gradient with a Max-Oracle.
result Achieves state-of-the-art performance and high accuracy in recovering ground-truth correspondences.
New method for tensor completion using nonconvex dual total variation.
problem Tensor completion from partial measurements with exponential-family noise.
method Proposed dual-TV (DTV) regularizers for tensor completion under exponential-family noise.
result Theoretical upper bounds on recovery error for tensor completion.
A new line search rule improves support recovery in high-dimensional data.
problem Support recovery in high-dimensional data analysis with penalty.
method Data-driven line search rule for adaptive step size determination.
result Proves error bound without restrictions on cost functional.