Paper tackles graph estimation with approximate recovery criteria, matching exact recovery bounds in many cases.
problem Estimating the graph of an Ising model with approximate recovery criteria.
method Adopting approximate recovery criterion, using Fano's inequality and graph ensembles to derive lower bounds.
result Lower bounds on sample complexity match exact recovery bounds in many cases, indicating similar difficulty.
Guarantees recovery of compressible signals from adversarial noise.
problem Recovering compressible signals from noise and adversarial attacks.
method Extends adversarial defense framework to ℓ0, ℓ2, and ℓ∞ norms. result Recovery guarantees for various signal recovery methods under different noise types.
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-ℓ1 regularization. While the current theory provides promis…
Global optimization for low-rank matrix recovery from noisy measurements.
problem Low-rank matrix recovery from noisy measurements.
method Factorized parametrization, curvature bound, stochastic gradient descent.
result Global convergence guarantee for stochastic gradient descent from random initialization.
Study on limits of recovering sparse variables from phaseless measurements.
problem Support recovery in phase retrieval model with noisy phaseless measurements.
method Information-theoretic analysis, considering discrete and Gaussian models, Gaussian measurement matrices.
result Sharp thresholds with near-matching constant factors for sparsity and signal-to-noise ratio in various scaling regimes.
WPCA improves subspace recovery robustness to outliers.
problem Improving subspace recovery in the presence of outliers.
method Winsorized PCA (WPCA) with theoretical analysis of accuracy and robustness.
result WPCA provides consistent subspace recovery from contaminated data.
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 …
This paper tackles tensor recovery from noisy and multi-level quantized measurements.
problem Tensors from multi-level quantized measurements.
method Nonconvex optimization problem with alternating proximal gradient descent.
result The recovery error diminishes to zero with increasing tensor dimensions.
Improves sparse recovery with non-linear Fourier features.
problem Sparse recovery challenges with non-linear Fourier features.
method Characterizes sufficient data points for perfect recovery.
result Sufficient data points depend on kernel matrix.
New method explains computational barriers in high-dimensional statistical models.
problem Understanding detection-recovery gaps in high-dimensional inference.
method Combining algorithmic contiguity and cross-validation reduction to obtain conditional computational lower bounds.
result Mild control of low-degree advantage is sufficient to explain computational barriers for recovery.
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.
We study the problem of corrupted sensing, a generalization of compressed sensing in which one aims to recover a signal from a collection of corrupted or unreliable measurements. While an arbitrary signal cannot be recovered in the face of arbitrary corruption, tractable recovery is possible when both signal and corrup…
Lower bounds on sample complexity for recovering diffusion network structures.
problem Determining the minimum number of samples needed to accurately recover network structures.
method Information-theoretic analysis of discrete and continuous-time diffusion models.
result Lower bounds of order Ω(klogp) for correct recovery of network structures. Study shows DNNs can recover functions with fewer samples than model parameters at overparameterization.
problem Determining reliable function recovery in overparameterized deep neural networks.
method Introducing 'local linear recovery' (LLR) and proving upper bounds on sample sizes for recovery.
result Upper bounds on optimistic sample sizes for function recovery in overparameterized DNNs are achieved.
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 ℓ1 recovery," (b) block-sparsity with possibly overlapping blo…
Optimal sparse recovery with decision stumps achieves strong feature selection guarantees.
problem Sparse recovery of active features from high-dimensional data.
method Analysis of single-depth decision trees (decision stumps) for feature selection in linear regression.
result Tight sample performance guarantees for O(slogp), improving upon previous bounds. Study generalizes matrix completion with side info in low noise settings.
problem Matrix completion with side information in low noise conditions.
method Inductive matrix completion with i.i.d. subgaussian noise, uniform sampling, and side information.
result Generalization bounds with noise scaling, convergence to zero, and logarithmic dependence on matrix size.
New method uses extreme eigenvalue deviations for sparse recovery guarantees.
problem Sparse recovery from extreme eigenvalue deviations.
method State-of-the-art small deviation estimates on extreme eigenvalues for Gaussian and Rademacher matrices.
result Derives upper bounds on RICs and lower bounds on SRSR.
The paper sets information-theoretic lower bounds for neural networks' parameter recovery and excess risk.
problem Establishing sample complexity lower bounds for neural network parameters and excess risk.
method Using information-theoretic tools, the paper proves lower bounds by constructing a generative network.
result Proves information-theoretic lower bounds for exact parameter recovery and positive excess risk.
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.
Paper proves conditions for nonconvex matrix recovery to avoid spurious local minima.
problem Ensuring no spurious local minima in nonconvex matrix recovery.
method Sharp restricted isometry bounds proof technique.
result RIP constant of δ < 1/2 is necessary and sufficient for exact recovery.
Paper tackles sparse recovery with shuffled labels, establishing statistical and computational limits.
problem Sparse recovery with shuffled labels, focusing on permutation matrix and sparse signal reconstruction.
method Statistical and computational analysis, including minimax lower bounds and exhaustive-search based estimator.
result Established statistical and computational limits for correct recovery of permutation matrix and support set.
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.
Paper improves group sparse recovery bounds using ℓ1-norm minimization.
problem Recovering group sparse vectors from few measurements.
method Introduces GRNSP and GRIP, and uses convex relaxations.
result New bounds for group sparse recovery, including equal and unequal group sizes.
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 k-support norm regularizer. result Achieves sparse recovery with explicit constants and standard linear rate.
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 Lq-norms. result NLA minimax rates continuously depend on noise level and match optimal recovery rates as noise decreases.
This paper optimizes how many samples are needed to estimate a population's binary responses.
problem Estimating a distribution from incomplete or corrupted samples.
method The approach involves computing the empirical mean of a certain function, pre-solving a linear program, and using complex-analytic methods.
result Optimal sample complexity for population recovery is determined, showing phase transitions and sensitivity to dimension.
OLS recovers sparse signals from noisy measurements with high probability.
problem Recovering sparse signals from noisy linear measurements.
method Orthogonal Least-Squares (OLS) algorithm under noisy conditions.
result OLS recovers true support in k iterations with high probability under certain conditions. PopArt efficiently solves sparse linear bandits with tighter recovery guarantees.
problem Sparse linear bandits where rewards depend on a few covariates.
method PopArt: a simple, computationally efficient sparse linear estimation method.
result Improved regret bounds compared to state-of-the-art algorithms.
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 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.
The paper analyzes error bounds and KL properties for noisy matrix recovery problems.
problem Noisy low-rank matrix recovery problems.
method Squared F-norm regularization, accelerated alternating minimization method.
result Established error bounds and KL properties for critical points and global minimizers.
We study the problem of recovering a hidden community of cardinality K from an n×n symmetric data matrix A, where for distinct indices i,j, Aij∼P if i,j both belong to the community and Aij∼Q otherwise, for two known probability distributions P and Q depending on n. If $P={\r…
This work proves exact low tubal rank tensor recovery from Gaussian measurements.
problem Low rank tensor recovery from Gaussian measurements.
method Careful choice of atomic set and computation of Gaussian width for atomic norm.
result Exact recovery of tensors with tubal rank r from O(r(n1+n2−r)n3) Gaussian measurements. 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.
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.
Researchers prove it's impossible to partially recover graph alignments in certain conditions.
problem Recovering vertex correspondence between two random graphs with correlated edges.
method Used the probabilistic method to build automorphisms between tree components of a subcritical Erdös-Rényi graph.
result Proved an impossibility result for partial recovery in the sparse regime with constant average degree and correlation.
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 ℓ2,∞ 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.
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…
New bounds for convex clustering under graph connectivity.
problem Understanding clustering performance under different graph connectivity structures.
method Random walks and concentration inequalities for random graph models.
result Improved rates of convergence for centroid recovery.
Greedy method improves low rank matrix estimation with new approximation guarantees.
problem Low rank matrix estimation under restricted strong convexity and smoothness.
method Novel greedy algorithm analysis linking to combinatorial optimization.
result Improved approximation guarantees and statistical recovery.
New nonconvex regularizers improve low-rank matrix recovery efficiency and accuracy.
problem Efficiently recover low-rank matrices from incomplete data.
method Factor group-sparse regularization, related to Schatten-p norms.
result Improved generalization error bounds for Schatten-p norms as p decreases.
Sharp threshold for exact recovery in non-uniform hypergraph stochastic block model.
problem Community detection in random hypergraphs with non-uniform hyperedge probabilities.
method Sharp threshold established; two efficient algorithms for exact recovery.
result Sharp threshold for exact recovery; information-theoretic lower bound on misclassification.
New methods for robust subspace recovery in noisy data with adversarial outliers.
problem Robust subspace recovery in the presence of adversarial outliers.
method Proposed two tractable estimators: a variant of RANSAC and a simple relaxation of the theoretical estimator.
result Achieve state-of-the-art theoretical performance in a noiseless RSR setting with adversarial outliers.
Study on sparse recovery with mixed-quality data, establishing sample-size conditions.
problem Sparse recovery with heterogeneous noise from high- and low-quality sources.
method Establishes linear trade-off for sufficient conditions, analyzes LASSO algorithm.
result Linear trade-off for sufficient conditions, robustness of LASSO to data heterogeneity.
The paper analyzes prediction and recovery bounds for noisy ordinal embedding.
problem Predicting and recovering embeddings from noisy distance comparisons.
method Derives prediction error bounds, investigates Maximum Likelihood estimator, proposes new algorithms.
result Relates prediction errors to embedding accuracy through a nonlinear map.
The paper explores recovery thresholds in heterogeneous SBM with varying community sizes and densities.
problem Understanding the limits of community recovery in heterogeneous SBM.
method Generalized Stochastic Block Model with varying community sizes and densities.
result Exact recovery of very small communities is possible under certain conditions.
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.