2 citations · 8 across the 17 of their papers we have counts for
14 papers · 1 filter
Active Learning on Adversarially Corrupted Graphs
Marco Bressan, Nicolò Cesa-Bianchi, Tommaso d`Orsi +2
Motivated by real-world scenarios where malicious entities tamper with existing networks, we define a model where an adversary seeks to hide a set of \emph{corrupted vertices} insi…
Tight Differentially Private PCA via Matrix Coherence
Tommaso d'Orsi, Gleb Novikov
We revisit the task of computing the span of the top singular vectors of a matrix under differential privacy. We show that a simple and efficient algorithm -…
On Purely Private Covariance Estimation
Tommaso d'Orsi, Gleb Novikov
We present a simple perturbation mechanism for the release of -dimensional covariance matrices under pure differential privacy. For large datasets with at least $n\geq d^2/\…
Multi-View Stochastic Block Models
Vincent Cohen-Addad, Tommaso d'Orsi, Silvio Lattanzi +1
Graph clustering is a central topic in unsupervised learning with a multitude of practical applications. In recent years, multi-view graph clustering has gained a lot of attention…
Perturb-and-Project: Differentially Private Similarities and Marginals
Vincent Cohen-Addad, Tommaso d'Orsi, Alessandro Epasto +2
We revisit the input perturbations framework for differential privacy where noise is added to the input and the result is then projected back to the space of adm…
Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions
Jingqiu Ding, Tommaso d'Orsi, Yiding Hua +1
We study robust community detection in the context of node-corrupted stochastic block model, where an adversary can arbitrarily modify all the edges incident to a fraction of the $…
Higher degree sum-of-squares relaxations robust against oblivious outliers
Tommaso d'Orsi, Rajai Nasser, Gleb Novikov +1
We consider estimation models of the form , where is some -dimensional signal we wish to recover, and is symmetrically distributed noise that may be unbounded…
On the well-spread property and its relation to linear regression
Hongjie Chen, Tommaso d'Orsi
We consider the robust linear regression model , where an adversary oblivious to the design may choose $\bolds…
Fast algorithm for overcomplete order-3 tensor decomposition
Jingqiu Ding, Tommaso d'Orsi, Chih-Hung Liu +2
We develop the first fast spectral algorithm to decompose a random third-order tensor over of rank up to . Our algorithm only involves…
Robust recovery for stochastic block models
Jingqiu Ding, Tommaso d'Orsi, Rajai Nasser +1
We develop an efficient algorithm for weak recovery in a robust version of the stochastic block model. The algorithm matches the statistical guarantees of the best known algorithms…
Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers
Tommaso d'Orsi, Chih-Hung Liu, Rajai Nasser +3
We develop machinery to design efficiently computable and consistent estimators, achieving estimation error approaching zero as the number of observations grows, when facing an obl…
The Complexity of Sparse Tensor PCA
Davin Choo, Tommaso d'Orsi
We study the problem of sparse tensor principal component analysis: given a tensor with having i.i.d. Gaussian…
Sparse PCA: Algorithms, Adversarial Perturbations and Certificates
Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov +1
We study efficient algorithms for Sparse PCA in standard statistical models (spiked covariance in its Wishart form). Our goal is to achieve optimal recovery guarantees while being…
Consistent regression when oblivious outliers overwhelm
Tommaso d'Orsi, Gleb Novikov, David Steurer
We consider a robust linear regression model , where an adversary oblivious to the design may choose to corrupt all but an fractio…