Timezone: »
Poster
Statistical Performance of Convex Tensor Decomposition
Ryota Tomioka · Taiji Suzuki · Kohei Hayashi · Hisashi Kashima
We analyze the statistical performance of a recently proposed convex tensor decomposition algorithm. Conventionally tensor decomposition has been formulated as non-convex optimization problems, which hindered the analysis of their performance. We show under some conditions that the mean squared error of the convex method scales linearly with the quantity we call the normalized rank of the true tensor. The current analysis naturally extends the analysis of convex low-rank matrix estimation to tensors. Furthermore, we show through numerical experiments that our theory can precisely predict the scaling behaviour in practice.
Author Information
Ryota Tomioka (Microsoft Research AI4Science)
Taiji Suzuki (The University of Tokyo/RIKEN-AIP)
Kohei Hayashi (Preferred Networks)
Hisashi Kashima
More from the Same Authors
-
2021 Spotlight: Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space »
Taiji Suzuki · Atsushi Nitanda -
2022 Poster: Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning »
Tomoya Murata · Taiji Suzuki -
2022 : Reducing Communication in Nonconvex Federated Learning with a Novel Single-Loop Variance Reduction Method »
Kazusato Oko · Shunta Akiyama · Tomoya Murata · Taiji Suzuki -
2022 Spotlight: Lightning Talks 4A-2 »
Barakeel Fanseu Kamhoua · Hualin Zhang · Taiki Miyagawa · Tomoya Murata · Xin Lyu · Yan Dai · Elena Grigorescu · Zhipeng Tu · Lijun Zhang · Taiji Suzuki · Wei Jiang · Haipeng Luo · Lin Zhang · Xi Wang · Young-San Lin · Huan Xiong · Liyu Chen · Bin Gu · Jinfeng Yi · Yongqiang Chen · Sandeep Silwal · Yiguang Hong · Maoyuan Song · Lei Wang · Tianbao Yang · Han Yang · MA Kaili · Samson Zhou · Deming Yuan · Bo Han · Guodong Shi · Bo Li · James Cheng -
2022 Spotlight: Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning »
Tomoya Murata · Taiji Suzuki -
2022 Poster: High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation »
Jimmy Ba · Murat Erdogdu · Taiji Suzuki · Zhichao Wang · Denny Wu · Greg Yang -
2022 Poster: Two-layer neural network on infinite dimensional data: global optimization guarantee in the mean-field regime »
Naoki Nishikawa · Taiji Suzuki · Atsushi Nitanda · Denny Wu -
2022 Poster: Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization »
Yuri Kinoshita · Taiji Suzuki -
2021 Poster: An Information-theoretic Approach to Distribution Shifts »
Marco Federici · Ryota Tomioka · Patrick Forré -
2021 Poster: Differentiable Multiple Shooting Layers »
Stefano Massaroli · Michael Poli · Sho Sonoda · Taiji Suzuki · Jinkyoo Park · Atsushi Yamashita · Hajime Asama -
2021 Poster: Particle Dual Averaging: Optimization of Mean Field Neural Network with Global Convergence Rate Analysis »
Atsushi Nitanda · Denny Wu · Taiji Suzuki -
2021 Poster: Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space »
Taiji Suzuki · Atsushi Nitanda -
2020 Poster: Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks »
Kenta Oono · Taiji Suzuki -
2020 Poster: Generalization bound of globally optimal non-convex neural network training: Transportation map estimation by infinite dimensional Langevin dynamics »
Taiji Suzuki -
2020 Spotlight: Generalization bound of globally optimal non-convex neural network training: Transportation map estimation by infinite dimensional Langevin dynamics »
Taiji Suzuki -
2020 Poster: On the Loss Landscape of Adversarial Training: Identifying Challenges and How to Overcome Them »
Chen Liu · Mathieu Salzmann · Tao Lin · Ryota Tomioka · Sabine Süsstrunk -
2019 Poster: Einconv: Exploring Unexplored Tensor Network Decompositions for Convolutional Neural Networks »
Kohei Hayashi · Taiki Yamaguchi · Yohei Sugawara · Shin-ichi Maeda -
2019 Poster: Continuous Hierarchical Representations with Poincaré Variational Auto-Encoders »
Emile Mathieu · Charline Le Lan · Chris Maddison · Ryota Tomioka · Yee Whye Teh -
2018 Poster: Sample Efficient Stochastic Gradient Iterative Hard Thresholding Method for Stochastic Sparse Linear Regression with Limited Attribute Observation »
Tomoya Murata · Taiji Suzuki -
2017 Poster: Fitting Low-Rank Tensors in Constant Time »
Kohei Hayashi · Yuichi Yoshida -
2017 Spotlight: Fitting Low-Rank Tensors in Constant Time »
Kohei Hayashi · Yuichi Yoshida -
2017 Poster: Doubly Accelerated Stochastic Variance Reduced Dual Averaging Method for Regularized Empirical Risk Minimization »
Tomoya Murata · Taiji Suzuki -
2017 Poster: QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding »
Dan Alistarh · Demjan Grubic · Jerry Li · Ryota Tomioka · Milan Vojnovic -
2017 Poster: On Tensor Train Rank Minimization : Statistical Efficiency and Scalable Algorithm »
Masaaki Imaizumi · Takanori Maehara · Kohei Hayashi -
2017 Spotlight: Communication-Efficient Stochastic Gradient Descent, with Applications to Neural Networks »
Dan Alistarh · Demjan Grubic · Jerry Li · Ryota Tomioka · Milan Vojnovic -
2017 Poster: Trimmed Density Ratio Estimation »
Song Liu · Akiko Takeda · Taiji Suzuki · Kenji Fukumizu -
2016 Poster: Minimax Optimal Alternating Minimization for Kernel Nonparametric Tensor Learning »
Taiji Suzuki · Heishiro Kanagawa · Hayato Kobayashi · Nobuyuki Shimizu · Yukihiro Tagami -
2016 Poster: f-GAN: Training Generative Neural Samplers using Variational Divergence Minimization »
Sebastian Nowozin · Botond Cseke · Ryota Tomioka -
2016 Poster: Minimizing Quadratic Functions in Constant Time »
Kohei Hayashi · Yuichi Yoshida -
2015 Poster: Interpolating Convex and Non-Convex Tensor Decompositions via the Subspace Norm »
Qinqing Zheng · Ryota Tomioka -
2014 Poster: Multitask learning meets tensor factorization: task imputation via convex optimization »
Kishan Wimalawarne · Masashi Sugiyama · Ryota Tomioka -
2013 Poster: Factorized Asymptotic Bayesian Inference for Latent Feature Models »
Kohei Hayashi · Ryohei Fujimaki -
2013 Poster: Convex Tensor Decomposition via Structured Schatten Norm Regularization »
Ryota Tomioka · Taiji Suzuki -
2012 Poster: Weighted Likelihood Policy Search with Model Selection »
Tsuyoshi Ueno · Yoshinobu Kawahara · Kohei Hayashi · Takashi Washio -
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: Unifying Framework for Fast Learning Rate of Non-Sparse Multiple Kernel Learning »
Taiji Suzuki -
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 -
2007 Spotlight: Invariant Common Spatial Patterns: Alleviating Nonstationarities in Brain-Computer Interfacing »
Benjamin Blankertz · Motoaki Kawanabe · Ryota Tomioka · Friederike Hohlefeld · Vadim Nikulin · Klaus-Robert Müller -
2007 Poster: Invariant Common Spatial Patterns: Alleviating Nonstationarities in Brain-Computer Interfacing »
Benjamin Blankertz · Motoaki Kawanabe · Ryota Tomioka · Friederike Hohlefeld · Vadim Nikulin · Klaus-Robert Müller -
2006 Poster: Logistic Regression for Single Trial EEG Classification »
Ryota Tomioka · Kazuyuki Aihara · Klaus-Robert Müller -
2006 Spotlight: Logistic Regression for Single Trial EEG Classification »
Ryota Tomioka · Kazuyuki Aihara · Klaus-Robert Müller