Timezone: »
Given a graphical model (GM), computing its partition function is the most essential inference task, but it is computationally intractable in general. To address the issue, iterative approximation algorithms exploring certain local structure/consistency of GM have been investigated as popular choices in practice. However, due to their local/iterative nature, they often output poor approximations or even do not converge, e.g., in low-temperature regimes (hard instances of large parameters). To overcome the limitation, we propose a novel approach utilizing the global spectral feature of GM. Our contribution is two-fold: (a) we first propose a fully polynomial-time approximation scheme (FPTAS) for approximating the partition function of GM associating with a low-rank coupling matrix; (b) for general high-rank GMs, we design a spectral mean-field scheme utilizing (a) as a subroutine, where it approximates a high-rank GM into a product of rank-1 GMs for an efficient approximation of the partition function. The proposed algorithm is more robust in its running time and accuracy than prior methods, i.e., neither suffers from the convergence issue nor depends on hard local structures, as demonstrated in our experiments.
Author Information
Sejun Park (KAIST)
Eunho Yang (KAIST,AITRICS)
Se-Young Yun (KAIST)
Jinwoo Shin (KAIST, AITRICS)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Oral: Spectral Approximate Inference »
Thu. Jun 13th 07:00 -- 07:05 PM Room Room 101
More from the Same Authors
-
2021 : SmoothMix: Training Confidence-calibrated Smoothed Classifiers for Certified Adversarial Robustness »
Jongheon Jeong · Sejun Park · Minkyu Kim · Heung-Chang Lee · Doguk Kim · Jinwoo Shin -
2021 : Entropy Weighted Adversarial Training »
Minseon Kim · Jihoon Tack · Jinwoo Shin · Sung Ju Hwang -
2021 : Consistency Regularization for Adversarial Robustness »
Jihoon Tack · Sihyun Yu · Jongheon Jeong · Minseon Kim · Sung Ju Hwang · Jinwoo Shin -
2022 : ALASCA: Rethinking Label Smoothing for Deep Learning Under Label Noise »
Jongwoo Ko · Bongsoo Yi · Se-Young Yun -
2023 Poster: Prefer to Classify: Improving Text Classifiers via Auxiliary Preference Learning »
Jaehyung Kim · Jinwoo Shin · Dongyeop Kang -
2023 Poster: RGE: A Repulsive Graph Rectification for Node Classification via Influence »
Jaeyun Song · Sungyub Kim · Eunho Yang -
2023 Poster: Fighting Fire with Fire: Contrastive Debiasing without Bias-free Data via Generative Bias-transformation »
Yeonsung Jung · Hajin Shim · June Yong Yang · Eunho Yang -
2023 Poster: Modality-Agnostic Variational Compression of Implicit Neural Representations »
Jonathan Richard Schwarz · Jihoon Tack · Yee-Whye Teh · Jaeho Lee · Jinwoo Shin -
2023 Poster: Multi-View Masked World Models for Visual Robotic Manipulation »
Younggyo Seo · Junsu Kim · Stephen James · Kimin Lee · Jinwoo Shin · Pieter Abbeel -
2022 : Revisiting Architecture-aware Knowledge Distillation: Smaller Models and Faster Search »
Taehyeon Kim · Heesoo Myeong · Se-Young Yun -
2022 : Supernet Training for Federated Image Classification »
Taehyeon Kim · Se-Young Yun -
2022 Poster: TSPipe: Learn from Teacher Faster with Pipelines »
Hwijoon Lim · Yechan Kim · Sukmin Yun · Jinwoo Shin · Dongsu Han -
2022 Spotlight: TSPipe: Learn from Teacher Faster with Pipelines »
Hwijoon Lim · Yechan Kim · Sukmin Yun · Jinwoo Shin · Dongsu Han -
2022 Poster: Disentangling Sources of Risk for Distributional Multi-Agent Reinforcement Learning »
Kyunghwan Son · Junsu Kim · Sungsoo Ahn · Roben Delos Reyes · Yung Yi · Jinwoo Shin -
2022 Poster: Rotting Infinitely Many-Armed Bandits »
Jung-hun Kim · Milan Vojnovic · Se-Young Yun -
2022 Poster: TAM: Topology-Aware Margin Loss for Class-Imbalanced Node Classification »
Jaeyun Song · Joonhyung Park · Eunho Yang -
2022 Poster: Time Is MattEr: Temporal Self-supervision for Video Transformers »
Sukmin Yun · Jaehyung Kim · Dongyoon Han · Hwanjun Song · Jung-Woo Ha · Jinwoo Shin -
2022 Spotlight: Disentangling Sources of Risk for Distributional Multi-Agent Reinforcement Learning »
Kyunghwan Son · Junsu Kim · Sungsoo Ahn · Roben Delos Reyes · Yung Yi · Jinwoo Shin -
2022 Spotlight: Time Is MattEr: Temporal Self-supervision for Video Transformers »
Sukmin Yun · Jaehyung Kim · Dongyoon Han · Hwanjun Song · Jung-Woo Ha · Jinwoo Shin -
2022 Spotlight: TAM: Topology-Aware Margin Loss for Class-Imbalanced Node Classification »
Jaeyun Song · Joonhyung Park · Eunho Yang -
2022 Spotlight: Rotting Infinitely Many-Armed Bandits »
Jung-hun Kim · Milan Vojnovic · Se-Young Yun -
2021 : Contrastive Learning for Novelty Detection »
Jinwoo Shin -
2021 Poster: Self-Improved Retrosynthetic Planning »
Junsu Kim · Sungsoo Ahn · Hankook Lee · Jinwoo Shin -
2021 Spotlight: Self-Improved Retrosynthetic Planning »
Junsu Kim · Sungsoo Ahn · Hankook Lee · Jinwoo Shin -
2021 Poster: Learning to Generate Noise for Multi-Attack Robustness »
Divyam Madaan · Jinwoo Shin · Sung Ju Hwang -
2021 Spotlight: Learning to Generate Noise for Multi-Attack Robustness »
Divyam Madaan · Jinwoo Shin · Sung Ju Hwang -
2021 Poster: Improved Regret Bounds of Bilinear Bandits using Action Space Analysis »
Kyoungseok Jang · Kwang-Sung Jun · Se-Young Yun · Wanmo Kang -
2021 Spotlight: Improved Regret Bounds of Bilinear Bandits using Action Space Analysis »
Kyoungseok Jang · Kwang-Sung Jun · Se-Young Yun · Wanmo Kang -
2021 Poster: Meta-StyleSpeech : Multi-Speaker Adaptive Text-to-Speech Generation »
Dongchan Min · Dong Bok Lee · Eunho Yang · Sung Ju Hwang -
2021 Spotlight: Meta-StyleSpeech : Multi-Speaker Adaptive Text-to-Speech Generation »
Dongchan Min · Dong Bok Lee · Eunho Yang · Sung Ju Hwang -
2021 Poster: Federated Continual Learning with Weighted Inter-client Transfer »
Jaehong Yoon · Wonyong Jeong · GiWoong Lee · Eunho Yang · Sung Ju Hwang -
2021 Poster: State Entropy Maximization with Random Encoders for Efficient Exploration »
Younggyo Seo · Lili Chen · Jinwoo Shin · Honglak Lee · Pieter Abbeel · Kimin Lee -
2021 Spotlight: Federated Continual Learning with Weighted Inter-client Transfer »
Jaehong Yoon · Wonyong Jeong · GiWoong Lee · Eunho Yang · Sung Ju Hwang -
2021 Spotlight: State Entropy Maximization with Random Encoders for Efficient Exploration »
Younggyo Seo · Lili Chen · Jinwoo Shin · Honglak Lee · Pieter Abbeel · Kimin Lee -
2020 Poster: Cost-Effective Interactive Attention Learning with Neural Attention Processes »
Jay Heo · Junhyeon Park · Hyewon Jeong · Kwang Joon Kim · Juho Lee · Eunho Yang · Sung Ju Hwang -
2020 Poster: Self-supervised Label Augmentation via Input Transformations »
Hankook Lee · Sung Ju Hwang · Jinwoo Shin -
2020 Poster: Context-aware Dynamics Model for Generalization in Model-Based Reinforcement Learning »
Kimin Lee · Younggyo Seo · Seunghyun Lee · Honglak Lee · Jinwoo Shin -
2020 Poster: Polynomial Tensor Sketch for Element-wise Function of Low-Rank Matrix »
Insu Han · Haim Avron · Jinwoo Shin -
2020 Poster: Learning What to Defer for Maximum Independent Sets »
Sungsoo Ahn · Younggyo Seo · Jinwoo Shin -
2020 Poster: Adversarial Neural Pruning with Latent Vulnerability Suppression »
Divyam Madaan · Jinwoo Shin · Sung Ju Hwang -
2019 Poster: Robust Inference via Generative Classifiers for Handling Noisy Labels »
Kimin Lee · Sukmin Yun · Kibok Lee · Honglak Lee · Bo Li · Jinwoo Shin -
2019 Poster: Learning What and Where to Transfer »
Yunhun Jang · Hankook Lee · Sung Ju Hwang · Jinwoo Shin -
2019 Oral: Robust Inference via Generative Classifiers for Handling Noisy Labels »
Kimin Lee · Sukmin Yun · Kibok Lee · Honglak Lee · Bo Li · Jinwoo Shin -
2019 Oral: Learning What and Where to Transfer »
Yunhun Jang · Hankook Lee · Sung Ju Hwang · Jinwoo Shin -
2019 Poster: Training CNNs with Selective Allocation of Channels »
Jongheon Jeong · Jinwoo Shin -
2019 Poster: Trimming the $\ell_1$ Regularizer: Statistical Analysis, Optimization, and Applications to Deep Learning »
Jihun Yun · Peng Zheng · Eunho Yang · Aurelie Lozano · Aleksandr Aravkin -
2019 Oral: Training CNNs with Selective Allocation of Channels »
Jongheon Jeong · Jinwoo Shin -
2019 Oral: Trimming the $\ell_1$ Regularizer: Statistical Analysis, Optimization, and Applications to Deep Learning »
Jihun Yun · Peng Zheng · Eunho Yang · Aurelie Lozano · Aleksandr Aravkin -
2018 Poster: Deep Asymmetric Multi-task Feature Learning »
Hae Beom Lee · Eunho Yang · Sung Ju Hwang -
2018 Poster: Bucket Renormalization for Approximate Inference »
Sungsoo Ahn · Michael Chertkov · Adrian Weller · Jinwoo Shin -
2018 Oral: Deep Asymmetric Multi-task Feature Learning »
Hae Beom Lee · Eunho Yang · Sung Ju Hwang -
2018 Oral: Bucket Renormalization for Approximate Inference »
Sungsoo Ahn · Michael Chertkov · Adrian Weller · Jinwoo Shin -
2017 Poster: Faster Greedy MAP Inference for Determinantal Point Processes »
Insu Han · Prabhanjan Kambadur · Kyoungsoo Park · Jinwoo Shin -
2017 Poster: Sparse + Group-Sparse Dirty Models: Statistical Guarantees without Unreasonable Conditions and a Case for Non-Convexity »
Eunho Yang · Aurelie Lozano -
2017 Poster: Confident Multiple Choice Learning »
Kimin Lee · Changho Hwang · KyoungSoo Park · Jinwoo Shin -
2017 Talk: Confident Multiple Choice Learning »
Kimin Lee · Changho Hwang · KyoungSoo Park · Jinwoo Shin -
2017 Talk: Sparse + Group-Sparse Dirty Models: Statistical Guarantees without Unreasonable Conditions and a Case for Non-Convexity »
Eunho Yang · Aurelie Lozano -
2017 Talk: Faster Greedy MAP Inference for Determinantal Point Processes »
Insu Han · Prabhanjan Kambadur · Kyoungsoo Park · Jinwoo Shin -
2017 Poster: Ordinal Graphical Models: A Tale of Two Approaches »
ARUN SAI SUGGALA · Eunho Yang · Pradeep Ravikumar -
2017 Talk: Ordinal Graphical Models: A Tale of Two Approaches »
ARUN SAI SUGGALA · Eunho Yang · Pradeep Ravikumar