Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLearning Communities in the Presence of Errors
89
0
0.0
(
0
)
Added by
Aravindan Vijayaraghavan
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the problem of learning communities in the presence of modeling errors and give robust recovery algorithms for the Stochastic Block Model (SBM). This model, which is also known as the Planted Partition Model, is widely used for community detection and graph partitioning in various fields, including machine learning, statistics, and social sciences. Many algorithms exist for learning communities in the Stochastic Block Model, but they do not work well in the presence of errors. In this paper, we initiate the study of robust algorithms for partial recovery in SBM with modeling errors or noise. We consider graphs generated according to the Stochastic Block Model and then modified by an adversary. We allow two types of adversarial errors, Feige---Kilian or monotone errors, and edge outlier errors. Mossel, Neeman and Sly (STOC 2015) posed an open question about whether an almost exact recovery is possible when the adversary is allowed to add $o(n)$ edges. Our work answers this question affirmatively even in the case of $k>2$ communities. We then show that our algorithms work not only when the instances come from SBM, but also work when the instances come from any distribution of graphs that is $epsilon m$ close to SBM in the Kullback---Leibler divergence. This result also works in the presence of adversarial errors. Finally, we present almost tight lower bounds for two communities.
rate research
Read More
We resolve one of the major outstanding problems in robust statistics. In particular, if $X$ is an evenly weighted mixture of two arbitrary $d$-dimensional Gaussians, we devise a polynomial time algorithm that given access to samples from $X$ an $eps$-fraction of which have been adversarially corrupted, learns $X$ to error $poly(eps)$ in total variation distance.
Strong turbulence conditions create amplitude aberrations through the effects of near-field diffraction. When integrated over long optical path lengths, amplitude aberrations (seen as scintillation) can nullify local areas in the recorded image of a coherent beam, complicating the wavefront reconstruction process. To estimate phase aberrations experienced by a telescope beam control system in the presence of strong turbulence, the wavefront sensor (WFS) of an adaptive optics must be robust to scintillation. We have designed and built a WFS, which we refer to as a Fresnel sensor, that uses near-field diffraction to measure phase errors under moderate to strong turbulent conditions. Systematic studies of its sensitivity were performed with laboratory experiments using a point source beacon. The results were then compared to a Shack-Hartmann WFS (SHWFS). When the SHWFS experiences irradiance fade in the presence of moderate turbulence, the Fresnel WFS continues to routinely extract phase information. For a scintillation index of $S = 0.55$, we show that the Fresnel WFS offers a factor of $9times$ gain in sensitivity over the SHWFS. We find that the Fresnel WFS is capable of operating with extremely low light levels, corresponding to a signal-to-noise ratio of only $mbox{SNR}approx 2-3$ per pixel. Such a device is well-suited for coherent beam propagation, laser communications, remote sensing, and applications involving long optical path-lengths, site-lines along the horizon, and faint signals.
Low-rank tensor decomposition generalizes low-rank matrix approximation and is a powerful technique for discovering low-dimensional structure in high-dimensional data. In this paper, we study Tucker decompositions and use tools from randomized numerical linear algebra called ridge leverage scores to accelerate the core tensor update step in the widely-used alternating least squares (ALS) algorithm. Updating the core tensor, a severe bottleneck in ALS, is a highly-structured ridge regression problem where the design matrix is a Kronecker product of the factor matrices. We show how to use approximate ridge leverage scores to construct a sketched instance for any ridge regression problem such that the solution vector for the sketched problem is a $(1+varepsilon)$-approximation to the original instance. Moreover, we show that classical leverage scores suffice as an approximation, which then allows us to exploit the Kronecker structure and update the core tensor in time that depends predominantly on the rank and the sketching parameters (i.e., sublinear in the size of the input tensor). We also give upper bounds for ridge leverage scores as rows are removed from the design matrix (e.g., if the tensor has missing entries), and we demonstrate the effectiveness of our approximate ridge regressioni algorithm for large, low-rank Tucker decompositions on both synthetic and real-world data.
We study the problem of robustly estimating the mean of a $d$-dimensional distribution given $N$ examples, where most coordinates of every example may be missing and $varepsilon N$ examples may be arbitrarily corrupted. Assuming each coordinate appears in a constant factor more than $varepsilon N$ examples, we show algorithms that estimate the mean of the distribution with information-theoretically optimal dimension-independent error guarantees in nearly-linear time $widetilde O(Nd)$. Our results extend recent work on computationally-efficient robust estimation to a more widely applicable incomplete-data setting.
We study the query complexity of exactly reconstructing a string from adaptive queries, such as substring, subsequence, and jumbled-index queries. Such problems have applications, e.g., in computational biology. We provide a number of new and improved bounds for exact string reconstruction for settings where either the string or the queries are mixed-up. For example, we show that a periodic (i.e., mixed-up) string, $S=p^kp$, of smallest period $p$, where $|p|<|p|$, can be reconstructed using $O(sigma|p|+lg n)$ substring queries, where $sigma$ is the alphabet size, if $n=|S|$ is unknown. We also show that we can reconstruct $S$ after having been corrupted by a small number of errors $d$, measured by Hamming distance. In this case, we give an algorithm that uses $O(dsigma|p| + d|p|lg frac{n}{d+1})$ queries. In addition, we show that a periodic string can be reconstructed using $2sigmalceillg nrceil + 2|p|lceillg sigmarceil$ subsequence queries, and that general strings can be reconstructed using $2sigmalceillg nrceil + nlceillg sigmarceil$ subsequence queries, without knowledge of $n$ in advance. This latter result improves the previous best, decades-old result, by Skiena and Sundaram. Finally, we believe we are the first to study the exact-learning query complexity for string reconstruction using jumbled-index queries, which are a mixed-up typeA of query that have received much attention of late.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
