Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion

• URL: http://arxiv.org/abs/2010.12181v1
• Date: Fri, 23 Oct 2020 06:23:20 GMT
• Title: Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion
• Authors: Qianqian Ma and Alex Olshevsky
• Abstract summary: It is not known which revealed entries are corrupted. We show that our proposed algorithm is optimal when the set of revealed entries is given by an ErdHos-R'enyi random graph. In particular, we show that our proposed algorithm is optimal when the set of revealed entries is given by an ErdHos-R'enyi random graph.
• Score: 17.615174152419133
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of reconstructing a rank-one matrix from a revealed subset of its entries when some of the revealed entries are corrupted with perturbations that are unknown and can be arbitrarily large. It is not known which revealed entries are corrupted. We propose a new algorithm combining alternating minimization with extreme-value filtering and provide sufficient and necessary conditions to recover the original rank-one matrix. In particular, we show that our proposed algorithm is optimal when the set of revealed entries is given by an Erd\H{o}s-R\'enyi random graph. These results are then applied to the problem of classification from crowdsourced data under the assumption that while the majority of the workers are governed by the standard single-coin David-Skene model (i.e., they output the correct answer with a certain probability), some of the workers can deviate arbitrarily from this model. In particular, the "adversarial" workers could even make decisions designed to make the algorithm output an incorrect answer. Extensive experimental results show our algorithm for this problem, based on rank-one matrix completion with perturbations, outperforms all other state-of-the-art methods in such an adversarial scenario.

Related papers

• Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
  Motivated by crowdsourcing, we consider a problem where we partially observe the correctness of the answers of $n$ experts on $d$ questions. In this paper, we assume that the matrix $M$ containing the probability that expert $i$ answers correctly to question $j$ is bi-isotonic up to a permutation of it rows and columns. We construct an efficient-time algorithm that turns out to be minimax optimal for this classification problem.
  arXiv  Detail & Related papers  (2024-08-27T18:28:31Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  We study matrix estimation problems arising in reinforcement learning (RL) with low-rank structure. In low-rank bandits, the matrix to be recovered specifies the expected arm rewards, and for low-rank Markov Decision Processes (MDPs), it may for example characterize the transition kernel of the MDP. We show that simple spectral-based matrix estimation approaches efficiently recover the singular subspaces of the matrix and exhibit nearly-minimal entry-wise error.
  arXiv  Detail & Related papers  (2023-10-10T17:06:41Z)
• Learning the Positions in CountSketch [49.57951567374372]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries.
  arXiv  Detail & Related papers  (2023-06-11T07:28:35Z)
• Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and Eigenvector Disjunctions [6.537257913467247]
  Low-rank matrix completion consists of a matrix of minimal complexity that recovers a given set of observations as accurately as possible. New convex relaxations decrease the optimal by magnitude compared to existing methods.
  arXiv  Detail & Related papers  (2023-05-20T22:04:34Z)
• A Non-monotonic Self-terminating Language Model [62.93465126911921]
  In this paper, we focus on the problem of non-terminating sequences resulting from an incomplete decoding algorithm. We first define an incomplete probable decoding algorithm which includes greedy search, top-$k$ sampling, and nucleus sampling. We then propose a non-monotonic self-terminating language model, which relaxes the constraint of monotonically increasing termination probability.
  arXiv  Detail & Related papers  (2022-10-03T00:28:44Z)
• Partial Matrix Completion [29.68420094716923]
  This work establishes a new framework of partial matrix completion. The goal is to identify a large subset of the entries that can be completed with high confidence. We propose an efficient algorithm with the following provable guarantees.
  arXiv  Detail & Related papers  (2022-08-25T12:47:20Z)
• Matrix Completion with Sparse Noisy Rows [3.42658286826597]
  We study exact low-rank completion under non-degenerate noise model. In this paper, we assume that each row can receive random noise instead of columns.
  arXiv  Detail & Related papers  (2022-04-01T05:45:43Z)
• Causal Matrix Completion [15.599296461516984]
  Matrix completion is the study of recovering an underlying matrix from a sparse subset of noisy observations. Traditionally, it is assumed that the entries of the matrix are "missing completely at random"
  arXiv  Detail & Related papers  (2021-09-30T14:17:56Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• Adversarial Robust Low Rank Matrix Estimation: Compressed Sensing and Matrix Completion [2.0257616108612373]
  We deal with matrix compressed sensing, including lasso as a partial problem, and matrix completion. We propose a simple unified approach based on a combination of the Huber loss function and the nuclear norm penalization.
  arXiv  Detail & Related papers  (2020-10-25T02:32:07Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.