Timezone: »
When a probabilistic model and its prior are given, Bayesian learning offers inference with automatic parameter tuning. However, Bayesian learning is often obstructed by computational difficulty: the rigorous Bayesian learning is intractable in many models, and its variational Bayesian (VB) approximation is prone to suffer from local minima. In this paper, we overcome this difficulty for low-rank subspace clustering (LRSC) by providing an exact global solver and its efficient approximation. LRSC extracts a low-dimensional structure of data by embedding samples into the union of low-dimensional subspaces, and its variational Bayesian variant has shown good performance. We first prove a key property that the VB-LRSC model is highly redundant. Thanks to this property, the optimization problem of VB-LRSC can be separated into small subproblems, each of which has only a small number of unknown variables. Our exact global solver relies on another key property that the stationary condition of each subproblem is written as a set of polynomial equations, which is solvable with the homotopy method. For further computational efficiency, we also propose an efficient approximate variant, of which the stationary condition can be written as a polynomial equation with a single variable. Experimental results show the usefulness of our approach.
Author Information
Shinichi Nakajima (TU Berlin)
Akiko Takeda (The University of Tokyo / RIKEN)
S. Derin Babacan (Google Research)
Masashi Sugiyama (RIKEN / University of Tokyo)
Ichiro Takeuchi (Nagoya Institute of Technology)
More from the Same Authors
-
2021 : On the Role of Pre-training for Meta Few-Shot Learning »
Chia-You Chen · Hsuan-Tien Lin · Masashi Sugiyama · Gang Niu -
2021 : Mixture-of-experts VAEs can disregard unimodal variation in surjective multimodal data »
Jannik Wolff · Tassilo Klein · Moin Nabi · Rahul G Krishnan · Shinichi Nakajima -
2021 Workshop: Second Workshop on Quantum Tensor Networks in Machine Learning »
Xiao-Yang Liu · Qibin Zhao · Ivan Oseledets · Yufei Ding · Guillaume Rabusseau · Jean Kossaifi · Khadijeh Najafi · Anwar Walid · Andrzej Cichocki · Masashi Sugiyama -
2021 : Discussion: Chelsea Finn, Masashi Sugiyama »
Chelsea Finn · Masashi Sugiyama -
2021 : Importance Weighting for Transfer Learning »
Masashi Sugiyama -
2021 Poster: A Gradient Method for Multilevel Optimization »
Ryo Sato · Mirai Tanaka · Akiko Takeda -
2021 Poster: Loss function based second-order Jensen inequality and its application to particle variational inference »
Futoshi Futami · Tomoharu Iwata · naonori ueda · Issei Sato · Masashi Sugiyama -
2021 Poster: Probabilistic Margins for Instance Reweighting in Adversarial Training »
qizhou wang · Feng Liu · Bo Han · Tongliang Liu · Chen Gong · Gang Niu · Mingyuan Zhou · Masashi Sugiyama -
2020 Poster: Dual T: Reducing Estimation Error for Transition Matrix in Label-noise Learning »
Yu Yao · Tongliang Liu · Bo Han · Mingming Gong · Jiankang Deng · Gang Niu · Masashi Sugiyama -
2020 Poster: Part-dependent Label Noise: Towards Instance-dependent Label Noise »
Xiaobo Xia · Tongliang Liu · Bo Han · Nannan Wang · Mingming Gong · Haifeng Liu · Gang Niu · Dacheng Tao · Masashi Sugiyama -
2020 Poster: Computing Valid p-value for Optimal Changepoint by Selective Inference using Dynamic Programming »
Vo Nguyen Le Duy · Hiroki Toda · Ryota Sugiyama · Ichiro Takeuchi -
2020 Spotlight: Part-dependent Label Noise: Towards Instance-dependent Label Noise »
Xiaobo Xia · Tongliang Liu · Bo Han · Nannan Wang · Mingming Gong · Haifeng Liu · Gang Niu · Dacheng Tao · Masashi Sugiyama -
2020 Spotlight: Computing Valid p-value for Optimal Changepoint by Selective Inference using Dynamic Programming »
Vo Nguyen Le Duy · Hiroki Toda · Ryota Sugiyama · Ichiro Takeuchi -
2020 Poster: Rethinking Importance Weighting for Deep Learning under Distribution Shift »
Tongtong Fang · Nan Lu · Gang Niu · Masashi Sugiyama -
2020 Poster: Learning from Aggregate Observations »
Yivan Zhang · Nontawat Charoenphakdee · Zhenguo Wu · Masashi Sugiyama -
2020 Poster: Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring »
Taira Tsuchiya · Junya Honda · Masashi Sugiyama -
2020 Spotlight: Rethinking Importance Weighting for Deep Learning under Distribution Shift »
Tongtong Fang · Nan Lu · Gang Niu · Masashi Sugiyama -
2020 Poster: Provably Consistent Partial-Label Learning »
Lei Feng · Jiaqi Lv · Bo Han · Miao Xu · Gang Niu · Xin Geng · Bo An · Masashi Sugiyama -
2020 Poster: Coupling-based Invertible Neural Networks Are Universal Diffeomorphism Approximators »
Takeshi Teshima · Isao Ishikawa · Koichi Tojo · Kenta Oono · Masahiro Ikeda · Masashi Sugiyama -
2020 Oral: Coupling-based Invertible Neural Networks Are Universal Diffeomorphism Approximators »
Takeshi Teshima · Isao Ishikawa · Koichi Tojo · Kenta Oono · Masahiro Ikeda · Masashi Sugiyama -
2019 : Poster Presentations »
Rahul Mehta · Andrew Lampinen · Binghong Chen · Sergio Pascual-Diaz · Jordi Grau-Moya · Aldo Faisal · Jonathan Tompson · Yiren Lu · Khimya Khetarpal · Martin Klissarov · Pierre-Luc Bacon · Doina Precup · Thanard Kurutach · Aviv Tamar · Pieter Abbeel · Jinke He · Maximilian Igl · Shimon Whiteson · Wendelin Boehmer · RaphaĆ«l Marinier · Olivier Pietquin · Karol Hausman · Sergey Levine · Chelsea Finn · Tianhe Yu · Lisa Lee · Benjamin Eysenbach · Emilio Parisotto · Eric Xing · Ruslan Salakhutdinov · Hongyu Ren · Anima Anandkumar · Deepak Pathak · Christopher Lu · Trevor Darrell · Alexei Efros · Phillip Isola · Feng Liu · Bo Han · Gang Niu · Masashi Sugiyama · Saurabh Kumar · Janith Petangoda · Johan Ferret · James McClelland · Kara Liu · Animesh Garg · Robert Lange -
2019 Poster: Computing Full Conformal Prediction Set with Approximate Homotopy »
Eugene Ndiaye · Ichiro Takeuchi -
2019 Poster: Uncoupled Regression from Pairwise Comparison Data »
Liyuan Xu · Junya Honda · Gang Niu · Masashi Sugiyama -
2019 Poster: Are Anchor Points Really Indispensable in Label-Noise Learning? »
Xiaobo Xia · Tongliang Liu · Nannan Wang · Bo Han · Chen Gong · Gang Niu · Masashi Sugiyama -
2019 Poster: On the Calibration of Multiclass Classification with Rejection »
Chenri Ni · Nontawat Charoenphakdee · Junya Honda · Masashi Sugiyama -
2018 Poster: Binary Classification from Positive-Confidence Data »
Takashi Ishida · Gang Niu · Masashi Sugiyama -
2018 Spotlight: Binary Classification from Positive-Confidence Data »
Takashi Ishida · Gang Niu · Masashi Sugiyama -
2018 Poster: Uplift Modeling from Separate Labels »
Ikko Yamane · Florian Yger · Jamal Atif · Masashi Sugiyama -
2018 Poster: Continuous-time Value Function Approximation in Reproducing Kernel Hilbert Spaces »
Motoya Ohnishi · Masahiro Yukawa · Mikael Johansson · Masashi Sugiyama -
2018 Poster: Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks »
Yusuke Tsuzuku · Issei Sato · Masashi Sugiyama -
2018 Poster: Masking: A New Perspective of Noisy Supervision »
Bo Han · Jiangchao Yao · Gang Niu · Mingyuan Zhou · Ivor Tsang · Ya Zhang · Masashi Sugiyama -
2018 Poster: Co-teaching: Robust training of deep neural networks with extremely noisy labels »
Bo Han · Quanming Yao · Xingrui Yu · Gang Niu · Miao Xu · Weihua Hu · Ivor Tsang · Masashi Sugiyama -
2017 : Poster Session (encompasses coffee break) »
Beidi Chen · Borja Balle · Daniel Lee · iuri frosio · Jitendra Malik · Jan Kautz · Ke Li · Masashi Sugiyama · Miguel A. Carreira-Perpinan · Ramin Raziperchikolaei · Theja Tulabandhula · Yung-Kyun Noh · Adams Wei Yu -
2017 Poster: Positive-Unlabeled Learning with Non-Negative Risk Estimator »
Ryuichi Kiryo · Gang Niu · Marthinus C du Plessis · Masashi Sugiyama -
2017 Poster: Learning from Complementary Labels »
Takashi Ishida · Gang Niu · Weihua Hu · Masashi Sugiyama -
2017 Oral: Positive-Unlabeled Learning with Non-Negative Risk Estimator »
Ryuichi Kiryo · Gang Niu · Marthinus C du Plessis · Masashi Sugiyama -
2017 Poster: Expectation Propagation for t-Exponential Family Using q-Algebra »
Futoshi Futami · Issei Sato · Masashi Sugiyama -
2017 Poster: Generative Local Metric Learning for Kernel Regression »
Yung-Kyun Noh · Masashi Sugiyama · Kee-Eung Kim · Frank Park · Daniel Lee -
2016 Poster: Theoretical Comparisons of Positive-Unlabeled Learning against Positive-Negative Learning »
Gang Niu · Marthinus Christoffel du Plessis · Tomoya Sakai · Yao Ma · Masashi Sugiyama -
2015 Poster: Regularization Path of Cross-Validation Error Lower Bounds »
Atsushi Shibagaki · Yoshiki Suzuki · Masayuki Karasuyama · Ichiro Takeuchi -
2014 Poster: Analysis of Variational Bayesian Latent Dirichlet Allocation: Weaker Sparsity Than MAP »
Shinichi Nakajima · Issei Sato · Masashi Sugiyama · Kazuho Watanabe · Hiroko Kobayashi -
2014 Poster: Multitask learning meets tensor factorization: task imputation via convex optimization »
Kishan Wimalawarne · Masashi Sugiyama · Ryota Tomioka -
2014 Poster: Analysis of Learning from Positive and Unlabeled Data »
Marthinus C du Plessis · Gang Niu · Masashi Sugiyama -
2013 Poster: Parametric Task Learning »
Ichiro Takeuchi · Tatsuya Hongo · Masashi Sugiyama · Shinichi Nakajima -
2012 Poster: Probabilistic Low-Rank Subspace Clustering »
S. Derin Babacan · Shinichi Nakajima · Minh Do -
2012 Poster: Perfect Dimensionality Recovery by Variational Bayesian PCA »
Shinichi Nakajima · Ryota Tomioka · Masashi Sugiyama · S. Derin Babacan -
2012 Poster: Density-Difference Estimation »
Masashi Sugiyama · Takafumi Kanamori · Taiji Suzuki · Marthinus C du Plessis · Song Liu · Ichiro Takeuchi -
2011 Poster: Relative Density-Ratio Estimation for Robust Distribution Comparison »
Makoto Yamada · Taiji Suzuki · Takafumi Kanamori · Hirotaka Hachiya · Masashi Sugiyama -
2011 Poster: Target Neighbor Consistent Feature Weighting for Nearest Neighbor Classification »
Ichiro Takeuchi · Masashi Sugiyama -
2011 Poster: Analysis and Improvement of Policy Gradient Estimation »
Tingting Zhao · Hirotaka Hachiya · Gang Niu · Masashi Sugiyama -
2011 Poster: Global Solution of Fully-Observed Variational Bayesian Matrix Factorization is Column-Wise Independent »
Shinichi Nakajima · Masashi Sugiyama · S. Derin Babacan -
2010 Spotlight: Global Analytic Solution for Variational Bayesian Matrix Factorization »
Shinichi Nakajima · Masashi Sugiyama · Ryota Tomioka -
2010 Poster: Global Analytic Solution for Variational Bayesian Matrix Factorization »
Shinichi Nakajima · Masashi Sugiyama · Ryota Tomioka -
2009 Poster: Multiple Incremental Decremental Learning of Support Vector Machines »
Masayuki Karasuyama · Ichiro Takeuchi -
2008 Poster: Efficient Direct Density Ratio Estimation for Non-stationarity Adaptation and Outlier Detection »
Takafumi Kanamori · Shohei Hido · Masashi Sugiyama -
2007 Poster: Direct Importance Estimation with Model Selection and Its Application to Covariate Shift Adaptation »
Masashi Sugiyama · Shinichi Nakajima · Hisashi Kashima · Paul von Buenau · Motoaki Kawanabe -
2007 Poster: Multi-Task Learning via Conic Programming »
Tsuyoshi Kato · Hisashi Kashima · Masashi Sugiyama · Kiyoshi Asai -
2006 Workshop: Learning when test and training inputs have different distributions »
Joaquin QuiƱonero Candela · Masashi Sugiyama · Anton Schwaighofer · Neil D Lawrence -
2006 Poster: Mixture Regression for Covariate Shift »
Amos Storkey · Masashi Sugiyama