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…
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 “bounded recovery”
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 …
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.
In this paper, we consider the problem of estimating the underlying graph associated with an Ising model given a number of independent and identically distributed samples. We adopt an \emph{approximate recovery} criterion that allows for a number of missed edges or incorrectly-included edges, in contrast with the widel…
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 …
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.
We provide recovery guarantees for compressible signals that have been corrupted with noise and extend the framework introduced in \cite{bafna2018thwarting} to defend neural networks against -norm, -norm, and -norm attacks. Our results are general as they can be applied to most unitary tr…
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…
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 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 , 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.
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.
The support recovery problem consists of determining a sparse subset of variables that is relevant in generating a set of observations. In this paper, we study the support recovery problem in the phase retrieval model consisting of noisy phaseless measurements, which arises in a diverse range of settings such as optica…
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.
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.
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.
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.
PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Banditsstat.ML
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.
The problem of population recovery refers to estimating a distribution based on incomplete or corrupted samples. Consider a random poll of sample size conducted on a population of individuals, where each pollee is asked to answer binary questions. We consider one of the two polling impediments: (a) in lossy pop…
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…
Nonconvex matrix recovery is known to contain no spurious local minima under a restricted isometry property (RIP) with a sufficiently small RIP constant . If is too large, however, then counterexamples containing spurious local minima are known to exist. In this paper, we introduce a proof technique that is capa…
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…
We study the information-theoretic lower bound of the sample complexity of the correct recovery of diffusion network structures. We introduce a discrete-time diffusion model based on the Independent Cascade model for which we obtain a lower bound of order , for directed graphs of nodes, and at most …
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.
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.
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 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 show that there are no spurious local minima in the non-convex factorized parametrization of low-rank matrix recovery from incoherent linear measurements. With noisy measurements we show all local minima are very close to a global optimum. Together with a curvature bound at saddle points, this yields a polynomial ti…
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 consider the Orthogonal Least-Squares (OLS) algorithm for the recovery of a -dimensional -sparse signal from a low number of noisy linear measurements. The Exact Recovery Condition (ERC) in bounded noisy scenario is established for OLS under certain condition on nonzero elements of the signal. The new result a…
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.
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.
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 recent proposed Tensor Nuclear Norm (TNN) [Lu et al., 2016; 2018a] is an interesting convex penalty induced by the tensor SVD [Kilmer and Martin, 2011]. It plays a similar role as the matrix nuclear norm which is the convex surrogate of the matrix rank. Considering that the TNN based Tensor Robust PCA [Lu et al., 2…
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.
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.
GNMR controls runtime stability in low-precision language model training.
problem Efficient low-precision training faces numerical risks at specific operators.
method GNMR compares gradient norms to historical means, applying bounded recovery actions.
result GNMR preserves high-fidelity quality with sparse, budgeted recovery.
In this work we compute lower Lipschitz bounds of pooling operators for as well as pooling operators preceded by half-rectification layers. These give sufficient conditions for the design of invertible neural network layers. Numerical experiments on MNIST and image patches confirm tha…
Researchers prove inner product recovery is impossible in latent space models.
problem Recovering inner products in latent space models with random geometric graphs.
method Rate-distortion theory applied to Gaussian or spherical latent locations.
result Impossible to recover inner products if dimensionality exceeds , matching positive results' conditions.
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…
Spectral methods achieve near-optimal performance in orthogonal and permutation group synchronization.
problem Recovering group elements from pairwise measurements in computer vision.
method Spectral methods applied with the leave-one-out technique.
result Near-optimal performance bounds for orthogonal and permutation group synchronization established.
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…