Timezone: »
Poster
Fine-grained Generalization Analysis of Inductive Matrix Completion
Antoine Ledent · Rodrigo Alves · Yunwen Lei · Marius Kloft
In this paper, we bridge the gap between the state-of-the-art theoretical results for matrix completion with the nuclear norm and their equivalent in \textit{inductive matrix completion}: (1) In the distribution-free setting, we prove bounds improving the previously best scaling of $O(rd^2)$ to $\widetilde{O}(d^{3/2}\sqrt{r})$, where $d$ is the dimension of the side information and $r$ is the rank. (2) We introduce the (smoothed) \textit{adjusted trace-norm minimization} strategy, an inductive analogue of the weighted trace norm, for which we show guarantees of the order $\widetilde{O}(dr)$ under arbitrary sampling. In the inductive case, a similar rate was previously achieved only under uniform sampling and for exact recovery. Both our results align with the state of the art in the particular case of standard (non-inductive) matrix completion, where they are known to be tight up to log terms. Experiments further confirm that our strategy outperforms standard inductive matrix completion on various synthetic datasets and real problems, justifying its place as an important tool in the arsenal of methods for matrix completion using side information.
Author Information
Antoine Ledent (TU Kaiserslautern)
I obtained a PhD in stochastic analysis at the University of Luxembourg, and am now working in statistical learning theory as a postdoc.
Rodrigo Alves (TU Kaiserslautern)
Yunwen Lei (University of Birmingham)
I am currently a Lecturer at School of Computer Science, University of Birmingham. Previously, I was a Humboldt Research Fellow at University of Kaiserslautern, a Research Assistant Professor at Southern University of Science and Technology, and a Postdoctoral Research Fellow at City University of Hong Kong. I obtained my PhD degree in Computer Science at Wuhan University in 2014.
Marius Kloft (TU Kaiserslautern)
More from the Same Authors
-
2021 : Hierarchical Topic Evaluation: Statistical vs. Neural Models »
Mayank Kumar Nagda · Charu Karakkaparambil James · Sophie Burkhardt · Marius Kloft -
2023 Poster: Labeling Neural Representations with Inverse Recognition »
Kirill Bykov · Laura Kopf · Shinichi Nakajima · Marius Kloft · Marina Höhne -
2023 Poster: Zero-Shot Batch-Level Anomaly Detection »
Aodong Li · Chen Qiu · Marius Kloft · Padhraic Smyth · Maja Rudolph · Stephan Mandt -
2023 Poster: Toward Better PAC-Bayes Bounds for Uniformly Stable Algorithms »
Sijia Zhou · Yunwen Lei · Ata Kaban -
2022 Spotlight: A Communication-Efficient Distributed Gradient Clipping Algorithm for Training Deep Neural Networks »
Mingrui Liu · Zhenxun Zhuang · Yunwen Lei · Chunyang Liao -
2022 : Unsupervised Anomaly Detection for Auditing Data and Impact of Categorical Encodings. »
Ajay Chawda · Marius Kloft · Stefanie Grimm -
2022 Poster: A Communication-Efficient Distributed Gradient Clipping Algorithm for Training Deep Neural Networks »
Mingrui Liu · Zhenxun Zhuang · Yunwen Lei · Chunyang Liao -
2022 Poster: Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks »
Yunwen Lei · Rong Jin · Yiming Ying -
2022 Poster: Stability and Generalization for Markov Chain Stochastic Gradient Methods »
Puyu Wang · Yunwen Lei · Yiming Ying · Ding-Xuan Zhou -
2021 Poster: Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learning »
ZHENHUAN YANG · Yunwen Lei · Puyu Wang · Tianbao Yang · Yiming Ying -
2021 Poster: Beyond Smoothness: Incorporating Low-Rank Analysis into Nonparametric Density Estimation »
Robert Vandermeulen · Antoine Ledent -
2021 Poster: Generalization Guarantee of SGD for Pairwise Learning »
Yunwen Lei · Mingrui Liu · Yiming Ying -
2020 Poster: Sharper Generalization Bounds for Pairwise Learning »
Yunwen Lei · Antoine Ledent · Marius Kloft -
2019 : Poster and Coffee Break 2 »
Karol Hausman · Kefan Dong · Ken Goldberg · Lihong Li · Lin Yang · Lingxiao Wang · Lior Shani · Liwei Wang · Loren Amdahl-Culleton · Lucas Cassano · Marc Dymetman · Marc Bellemare · Marcin Tomczak · Margarita Castro · Marius Kloft · Marius-Constantin Dinu · Markus Holzleitner · Martha White · Mengdi Wang · Michael Jordan · Mihailo Jovanovic · Ming Yu · Minshuo Chen · Moonkyung Ryu · Muhammad Zaheer · Naman Agarwal · Nan Jiang · Niao He · Nikolaus Yasui · Nikos Karampatziakis · Nino Vieillard · Ofir Nachum · Olivier Pietquin · Ozan Sener · Pan Xu · Parameswaran Kamalaruban · Paul Mineiro · Paul Rolland · Philip Amortila · Pierre-Luc Bacon · Prakash Panangaden · Qi Cai · Qiang Liu · Quanquan Gu · Raihan Seraj · Richard Sutton · Rick Valenzano · Robert Dadashi · Rodrigo Toro Icarte · Roshan Shariff · Roy Fox · Ruosong Wang · Saeed Ghadimi · Samuel Sokota · Sean Sinclair · Sepp Hochreiter · Sergey Levine · Sergio Valcarcel Macua · Sham Kakade · Shangtong Zhang · Sheila McIlraith · Shie Mannor · Shimon Whiteson · Shuai Li · Shuang Qiu · Wai Lok Li · Siddhartha Banerjee · Sitao Luan · Tamer Basar · Thinh Doan · Tianhe Yu · Tianyi Liu · Tom Zahavy · Toryn Klassen · Tuo Zhao · Vicenç Gómez · Vincent Liu · Volkan Cevher · Wesley Suttle · Xiao-Wen Chang · Xiaohan Wei · Xiaotong Liu · Xingguo Li · Xinyi Chen · Xingyou Song · Yao Liu · YiDing Jiang · Yihao Feng · Yilun Du · Yinlam Chow · Yinyu Ye · Yishay Mansour · · Yonathan Efroni · Yongxin Chen · Yuanhao Wang · Bo Dai · Chen-Yu Wei · Harsh Shrivastava · Hongyang Zhang · Qinqing Zheng · SIDDHARTHA SATPATHI · Xueqing Liu · Andreu Vall -
2019 : Break / Poster Session 1 »
Antonia Marcu · Yao-Yuan Yang · Pascale Gourdeau · Chen Zhu · Thodoris Lykouris · Jianfeng Chi · Mark Kozdoba · Arjun Nitin Bhagoji · Xiaoxia Wu · Jay Nandy · Michael T Smith · Bingyang Wen · Yuege Xie · Konstantinos Pitas · Suprosanna Shit · Maksym Andriushchenko · Dingli Yu · Gaël Letarte · Misha Khodak · Hussein Mozannar · Chara Podimata · James Foulds · Yizhen Wang · Huishuai Zhang · Ondrej Kuzelka · Alexander Levine · Nan Lu · Zakaria Mhammedi · Paul Viallard · Diana Cai · Lovedeep Gondara · James Lucas · Yasaman Mahdaviyeh · Aristide Baratin · Rishi Bommasani · Alessandro Barp · Andrew Ilyas · Kaiwen Wu · Jens Behrmann · Omar Rivasplata · Amir Nazemi · Aditi Raghunathan · Will Stephenson · Sahil Singla · Akhil Gupta · YooJung Choi · Yannic Kilcher · Clare Lyle · Edoardo Manino · Andrew Bennett · Zhi Xu · Niladri Chatterji · Emre Barut · Flavien Prost · Rodrigo Toro Icarte · Arno Blaas · Chulhee Yun · Sahin Lale · YiDing Jiang · Tharun Kumar Reddy Medini · Ashkan Rezaei · Alexander Meinke · Stephen Mell · Gary Kazantsev · Shivam Garg · Aradhana Sinha · Vishnu Lokhande · Geovani Rizk · Han Zhao · Aditya Kumar Akash · Jikai Hou · Ali Ghodsi · Matthias Hein · Tyler Sypherd · Yichen Yang · Anastasia Pentina · Pierre Gillot · Antoine Ledent · Guy Gur-Ari · Noah MacAulay · Tianzong Zhang -
2019 Poster: Optimal Stochastic and Online Learning with Individual Iterates »
Yunwen Lei · Peng Yang · Ke Tang · Ding-Xuan Zhou -
2019 Spotlight: Optimal Stochastic and Online Learning with Individual Iterates »
Yunwen Lei · Peng Yang · Ke Tang · Ding-Xuan Zhou -
2019 Poster: Effective End-to-end Unsupervised Outlier Detection via Inlier Priority of Discriminative Network »
Siqi Wang · Yijie Zeng · Xinwang Liu · En Zhu · Jianping Yin · Chuanfu Xu · Marius Kloft -
2018 Poster: Stochastic Composite Mirror Descent: Optimal Bounds with High Probabilities »
Yunwen Lei · Ke Tang -
2017 : Marius Kloft (Kaiserslautern) on Generalization Error Bounds for Extreme Multi-class Classification »
Marius Kloft -
2017 Workshop: Extreme Classification: Multi-class & Multi-label Learning in Extremely Large Label Spaces »
Manik Varma · Marius Kloft · Krzysztof Dembczynski -
2015 Poster: Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithms »
Yunwen Lei · Urun Dogan · Alexander Binder · Marius Kloft -
2014 Workshop: Second Workshop on Transfer and Multi-Task Learning: Theory meets Practice »
Urun Dogan · Tatiana Tommasi · Yoshua Bengio · Francesco Orabona · Marius Kloft · Andres Munoz · Gunnar Rätsch · Hal Daumé III · Mehryar Mohri · Xuezhi Wang · Daniel Hernández-lobato · Song Liu · Thomas Unterthiner · Pascal Germain · Vinay P Namboodiri · Michael Goetz · Christopher Berlind · Sigurd Spieckermann · Marta Soare · Yujia Li · Vitaly Kuznetsov · Wenzhao Lian · Daniele Calandriello · Emilie Morvant -
2013 Workshop: New Directions in Transfer and Multi-Task: Learning Across Domains and Tasks »
Urun Dogan · Marius Kloft · Tatiana Tommasi · Francesco Orabona · Massimiliano Pontil · Sinno Jialin Pan · Shai Ben-David · Arthur Gretton · Fei Sha · Marco Signoretto · Rajhans Samdani · Yun-Qian Miao · Mohammad Gheshlaghi azar · Ruth Urner · Christoph Lampert · Jonathan How -
2013 Workshop: MLINI-13: Machine Learning and Interpretation in Neuroimaging (Day 2) »
Georg Langs · Brian Murphy · Kai-min K Chang · Paolo Avesani · James Haxby · Nikolaus Kriegeskorte · Susan Whitfield-Gabrieli · Irina Rish · Guillermo Cecchi · Raif Rustamov · Marius Kloft · Jonathan Young · Sina Ghiassian · Michael Coen -
2013 Workshop: MLINI-13: Machine Learning and Interpretation in Neuroimaging (Day 1) »
Georg Langs · Brian Murphy · Kai-min K Chang · Paolo Avesani · James Haxby · Nikolaus Kriegeskorte · Susan Whitfield-Gabrieli · Irina Rish · Guillermo Cecchi · Raif Rustamov · Marius Kloft · Jonathan Young · Sina Ghiassian · Michael Coen -
2013 Poster: Learning Kernels Using Local Rademacher Complexity »
Corinna Cortes · Marius Kloft · Mehryar Mohri -
2013 Spotlight: Learning Kernels Using Local Rademacher Complexity »
Corinna Cortes · Marius Kloft · Mehryar Mohri -
2011 Poster: The Local Rademacher Complexity of Lp-Norm Multiple Kernel Learning »
Marius Kloft · Gilles Blanchard -
2010 Workshop: New Directions in Multiple Kernel Learning »
Marius Kloft · Ulrich Rueckert · Cheng Soon Ong · Alain Rakotomamonjy · Soeren Sonnenburg · Francis Bach -
2009 Poster: Efficient and Accurate Lp-Norm Multiple Kernel Learning »
Marius Kloft · Ulf Brefeld · Soeren Sonnenburg · Pavel Laskov · Klaus-Robert Müller · Alexander Zien