Timezone: »
We consider worker skill estimation for the single coin Dawid-Skene crowdsourcing model. In practice skill-estimation is challenging because worker assignments are sparse and irregular due to the arbitrary, and uncontrolled availability of workers. We formulate skill estimation as a rank-one correlation-matrix completion problem, where the observed components correspond to observed label correlation between workers. We show that the correlation matrix can be successfully recovered and skills identifiable if and only if the sampling matrix (observed components) is irreducible and aperiodic. We then propose an efficient gradient descent scheme and show that skill estimates converges to the desired global optima for such sampling matrices. Our proof is original and the results are surprising in light of the fact that even the weighted rank-one matrix factorization problem is NP hard in general. Next we derive sample complexity bounds for the noisy case in terms of spectral properties of the signless Laplacian of the sampling matrix. Our proposed scheme achieves state-of-art performance on a number of real-world datasets.
Author Information
Yao Ma (Boston University)
Alex Olshevsky (Boston University)
Csaba Szepesvari (Deepmind)
Venkatesh Saligrama (Boston University)
Related Events (a corresponding poster, oral, or spotlight)
-
2018 Poster: Gradient Descent for Sparse Rank-One Matrix Completion for Crowd-Sourced Aggregation of Sparsely Interacting Workers »
Fri. Jul 13th 04:15 -- 07:00 PM Room Hall B #77
More from the Same Authors
-
2022 : Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk »
Tianrui Chen · Aditya Gangrade · Venkatesh Saligrama -
2022 : ActiveHedge: Hedge meets Active Learning »
Bhuvesh Kumar · Jacob Abernethy · Venkatesh Saligrama -
2022 : Acting Optimistically in Choosing Safe Actions »
Tianrui Chen · Aditya Gangrade · Venkatesh Saligrama -
2022 : ActiveHedge: Hedge meets Active Learning »
Bhuvesh Kumar · Jacob Abernethy · Venkatesh Saligrama -
2022 : Achieving High TinyML Accuracy through Selective Cloud Interactions »
Anil Kag · Igor Fedorov · Aditya Gangrade · Paul Whatmough · Venkatesh Saligrama -
2022 : FedHeN: Federated Learning in Heterogeneous Networks »
Durmus Alp Emre Acar · Venkatesh Saligrama -
2022 Poster: Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk »
Tianrui Chen · Aditya Gangrade · Venkatesh Saligrama -
2022 Spotlight: Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk »
Tianrui Chen · Aditya Gangrade · Venkatesh Saligrama -
2022 Poster: Faster Algorithms for Learning Convex Functions »
Ali Siahkamari · Durmus Alp Emre Acar · Christopher Liao · Kelly Geyer · Venkatesh Saligrama · Brian Kulis -
2022 Poster: ActiveHedge: Hedge meets Active Learning »
Bhuvesh Kumar · Jacob Abernethy · Venkatesh Saligrama -
2022 Spotlight: ActiveHedge: Hedge meets Active Learning »
Bhuvesh Kumar · Jacob Abernethy · Venkatesh Saligrama -
2022 Spotlight: Faster Algorithms for Learning Convex Functions »
Ali Siahkamari · Durmus Alp Emre Acar · Christopher Liao · Kelly Geyer · Venkatesh Saligrama · Brian Kulis -
2021 : RL Foundation Panel »
Matthew Botvinick · Thomas Dietterich · Leslie Kaelbling · John Langford · Warrren B Powell · Csaba Szepesvari · Lihong Li · Yuxi Li -
2021 Workshop: Reinforcement Learning for Real Life »
Yuxi Li · Minmin Chen · Omer Gottesman · Lihong Li · Zongqing Lu · Rupam Mahmood · Niranjani Prasad · Zhiwei (Tony) Qin · Csaba Szepesvari · Matthew Taylor -
2021 Poster: Debiasing Model Updates for Improving Personalized Federated Training »
Durmus Alp Emre Acar · Yue Zhao · Ruizhao Zhu · Ramon Matas · Matthew Mattina · Paul Whatmough · Venkatesh Saligrama -
2021 Spotlight: Debiasing Model Updates for Improving Personalized Federated Training »
Durmus Alp Emre Acar · Yue Zhao · Ruizhao Zhu · Ramon Matas · Matthew Mattina · Paul Whatmough · Venkatesh Saligrama -
2021 Poster: Memory Efficient Online Meta Learning »
Durmus Alp Emre Acar · Ruizhao Zhu · Venkatesh Saligrama -
2021 Poster: Temporal Difference Learning as Gradient Splitting »
Rui Liu · Alex Olshevsky -
2021 Oral: Temporal Difference Learning as Gradient Splitting »
Rui Liu · Alex Olshevsky -
2021 Spotlight: Memory Efficient Online Meta Learning »
Durmus Alp Emre Acar · Ruizhao Zhu · Venkatesh Saligrama -
2021 Poster: Training Recurrent Neural Networks via Forward Propagation Through Time »
Anil Kag · Venkatesh Saligrama -
2021 Spotlight: Training Recurrent Neural Networks via Forward Propagation Through Time »
Anil Kag · Venkatesh Saligrama -
2021 Town Hall: Town Hall »
John Langford · Marina Meila · Tong Zhang · Le Song · Stefanie Jegelka · Csaba Szepesvari -
2020 : Efficient Planning in Large MDPs with Weak Linear Function Approximation - Csaba Szepesvari »
Csaba Szepesvari -
2020 : Speaker Panel »
Csaba Szepesvari · Martha White · Sham Kakade · Gergely Neu · Shipra Agrawal · Akshay Krishnamurthy -
2020 Poster: Piecewise Linear Regression via a Difference of Convex Functions »
Ali Siahkamari · Aditya Gangrade · Brian Kulis · Venkatesh Saligrama -
2020 Poster: Minimax Rate for Learning From Pairwise Comparisons in the BTL Model »
Julien Hendrickx · Alex Olshevsky · Venkatesh Saligrama -
2019 Workshop: Reinforcement Learning for Real Life »
Yuxi Li · Alborz Geramifard · Lihong Li · Csaba Szepesvari · Tao Wang -
2019 Poster: Graph Resistance and Learning from Pairwise Comparisons »
Julien Hendrickx · Alex Olshevsky · Venkatesh Saligrama -
2019 Oral: Graph Resistance and Learning from Pairwise Comparisons »
Julien Hendrickx · Alex Olshevsky · Venkatesh Saligrama -
2019 Poster: Learning Classifiers for Target Domain with Limited or No Labels »
Pengkai Zhu · Hanxiao Wang · Venkatesh Saligrama -
2019 Oral: Learning Classifiers for Target Domain with Limited or No Labels »
Pengkai Zhu · Hanxiao Wang · Venkatesh Saligrama -
2017 Workshop: ML on a budget: IoT, Mobile and other tiny-ML applications »
Manik Varma · Venkatesh Saligrama · Prateek Jain -
2017 Poster: Adaptive Neural Networks for Efficient Inference »
Tolga Bolukbasi · Joseph Wang · Ofer Dekel · Venkatesh Saligrama -
2017 Talk: Adaptive Neural Networks for Efficient Inference »
Tolga Bolukbasi · Joseph Wang · Ofer Dekel · Venkatesh Saligrama -
2017 Poster: Connected Subgraph Detection with Mirror Descent on SDPs »
Cem Aksoylar · Orecchia Lorenzo · Venkatesh Saligrama -
2017 Talk: Connected Subgraph Detection with Mirror Descent on SDPs »
Cem Aksoylar · Orecchia Lorenzo · Venkatesh Saligrama