Timezone: »
The Neural Tangent Kernel (NTK) characterizes the behavior of infinitely-wide neural networks trained under least squares loss by gradient descent. Recent works also report that NTK regression can outperform finitely-wide neural networks trained on small-scale datasets. However, the computational complexity of kernel methods has limited its use in large-scale learning tasks. To accelerate learning with NTK, we design a near input-sparsity time approximation algorithm for NTK, by sketching the polynomial expansions of arc-cosine kernels: our sketch for the convolutional counterpart of NTK (CNTK) can transform any image using a linear runtime in the number of pixels. Furthermore, we prove a spectral approximation guarantee for the NTK matrix, by combining random features (based on leverage score sampling) of the arc-cosine kernels with a sketching algorithm. We benchmark our methods on various large-scale regression and classification tasks and show that a linear regressor trained on our CNTK features matches the accuracy of exact CNTK on CIFAR-10 dataset while achieving 150x speedup.
Author Information
Amir Zandieh (Max-Planck-Institut für Informatik)
Insu Han (Yale University)
Haim Avron (Tel Aviv University)
Neta Shoham (Edgify)
Chaewon Kim (KAIST)
Jinwoo Shin (KAIST)
More from the Same Authors
-
2021 : SURF: Semi-supervised Reward Learning with Data Augmentation for Feedback-efficient Preference-based Reinforcement Learning »
Jongjin Park · Younggyo Seo · Jinwoo Shin · Honglak Lee · Pieter Abbeel · Kimin Lee -
2022 : STUNT: Few-shot Tabular Learning with Self-generated Tasks from Unlabeled Tables »
Jaehyun Nam · Jihoon Tack · Kyungmin Lee · Hankook Lee · Jinwoo Shin -
2022 : Dynamics-Augmented Decision Transformer for Offline Dynamics Generalization »
Changyeon Kim · Junsu Kim · Younggyo Seo · Kimin Lee · Honglak Lee · Jinwoo Shin -
2022 : Unsupervised Meta-learning via Few-shot Pseudo-supervised Contrastive Learning »
Huiwon Jang · Hankook Lee · Jinwoo Shin -
2023 Poster: Multi-scale Diffusion Denoised Smoothing »
Jongheon Jeong · Jinwoo Shin -
2023 Poster: Slimmed Asymmetrical Contrastive Learning and Cross Distillation for Lightweight Model Training »
Jian Meng · Li Yang · Kyungmin Lee · Jinwoo Shin · Deliang Fan · Jae-sun Seo -
2023 Poster: Modality-Agnostic Self-Supervised Learning with Meta-Learned Masked Auto-Encoder »
Huiwon Jang · Jihoon Tack · Daewon Choi · Jongheon Jeong · Jinwoo Shin -
2023 Poster: Learning Large-scale Neural Fields via Context Pruned Meta-Learning »
Jihoon Tack · Subin Kim · Sihyun Yu · Jaeho Lee · Jinwoo Shin · Jonathan Richard Schwarz -
2023 Poster: S-CLIP: Semi-supervised Vision-Language Pre-training using Few Specialist Captions »
Sangwoo Mo · Minkyu Kim · Kyungmin Lee · Jinwoo Shin -
2023 Poster: Guide Your Agent with Adaptive Multimodal Rewards »
Changyeon Kim · Younggyo Seo · Hao Liu · Lisa Lee · Jinwoo Shin · Honglak Lee · Kimin Lee -
2023 Poster: Accelerating Reinforcement Learning with Value-Conditional State Entropy Exploration »
Dongyoung Kim · Jinwoo Shin · Pieter Abbeel · Younggyo Seo -
2023 Poster: Collaborative Score Distillation for Consistent Visual Synthesis »
Subin Kim · Kyungmin Lee · June Suk Choi · Jongheon Jeong · Kihyuk Sohn · Jinwoo Shin -
2022 Poster: NOTE: Robust Continual Test-time Adaptation Against Temporal Correlation »
Taesik Gong · Jongheon Jeong · Taewon Kim · Yewon Kim · Jinwoo Shin · Sung-Ju Lee -
2022 Poster: RényiCL: Contrastive Representation Learning with Skew Rényi Divergence »
Kyungmin Lee · Jinwoo Shin -
2022 Poster: Meta-Learning with Self-Improving Momentum Target »
Jihoon Tack · Jongjin Park · Hankook Lee · Jaeho Lee · Jinwoo Shin -
2022 Poster: Scalable Neural Video Representations with Learnable Positional Features »
Subin Kim · Sihyun Yu · Jaeho Lee · Jinwoo Shin -
2021 Poster: Improving Transferability of Representations via Augmentation-Aware Self-Supervision »
Hankook Lee · Kibok Lee · Kimin Lee · Honglak Lee · Jinwoo Shin -
2021 Poster: Landmark-Guided Subgoal Generation in Hierarchical Reinforcement Learning »
Junsu Kim · Younggyo Seo · Jinwoo Shin -
2021 Poster: RoMA: Robust Model Adaptation for Offline Model-based Optimization »
Sihyun Yu · Sungsoo Ahn · Le Song · Jinwoo Shin -
2021 Poster: Meta-Learning Sparse Implicit Neural Representations »
Jaeho Lee · Jihoon Tack · Namhoon Lee · Jinwoo Shin -
2021 Poster: Object-Aware Regularization for Addressing Causal Confusion in Imitation Learning »
Jongjin Park · Younggyo Seo · Chang Liu · Li Zhao · Tao Qin · Jinwoo Shin · Tie-Yan Liu -
2021 Poster: Object-aware Contrastive Learning for Debiased Scene Representation »
Sangwoo Mo · Hyunwoo Kang · Kihyuk Sohn · Chun-Liang Li · Jinwoo Shin -
2021 Poster: SmoothMix: Training Confidence-calibrated Smoothed Classifiers for Certified Robustness »
Jongheon Jeong · Sejun Park · Minkyu Kim · Heung-Chang Lee · Do-Guk Kim · Jinwoo Shin -
2020 Poster: Faster Randomized Infeasible Interior Point Methods for Tall/Wide Linear Programs »
Agniva Chowdhury · Palma London · Haim Avron · Petros Drineas -
2020 Poster: Distribution Aligning Refinery of Pseudo-label for Imbalanced Semi-supervised Learning »
Jaehyung Kim · Youngbum Hur · Sejun Park · Eunho Yang · Sung Ju Hwang · Jinwoo Shin -
2020 Poster: Time-Reversal Symmetric ODE Network »
In Huh · Eunho Yang · Sung Ju Hwang · Jinwoo Shin -
2020 Poster: Learning from Failure: De-biasing Classifier from Biased Classifier »
Junhyun Nam · Hyuntak Cha · Sungsoo Ahn · Jaeho Lee · Jinwoo Shin -
2020 Poster: CSI: Novelty Detection via Contrastive Learning on Distributionally Shifted Instances »
Jihoon Tack · Sangwoo Mo · Jongheon Jeong · Jinwoo Shin -
2020 Poster: Guiding Deep Molecular Optimization with Genetic Exploration »
Sungsoo Ahn · Junsu Kim · Hankook Lee · Jinwoo Shin -
2020 Poster: Consistency Regularization for Certified Robustness of Smoothed Classifiers »
Jongheon Jeong · Jinwoo Shin -
2020 Poster: Trajectory-wise Multiple Choice Learning for Dynamics Generalization in Reinforcement Learning »
Younggyo Seo · Kimin Lee · Ignasi Clavera Gilaberte · Thanard Kurutach · Jinwoo Shin · Pieter Abbeel -
2020 Poster: Learning Bounds for Risk-sensitive Learning »
Jaeho Lee · Sejun Park · Jinwoo Shin -
2020 Poster: Few-shot Visual Reasoning with Meta-Analogical Contrastive Learning »
Youngsung Kim · Jinwoo Shin · Eunho Yang · Sung Ju Hwang -
2019 Poster: Efficiently Learning Fourier Sparse Set Functions »
Andisheh Amrollahi · Amir Zandieh · Michael Kapralov · Andreas Krause -
2019 Spotlight: Efficiently Learning Fourier Sparse Set Functions »
Andisheh Amrollahi · Amir Zandieh · Michael Kapralov · Andreas Krause -
2019 Poster: Mining GOLD Samples for Conditional GANs »
Sangwoo Mo · Chiheon Kim · Sungwoong Kim · Minsu Cho · Jinwoo Shin -
2018 Poster: A Simple Unified Framework for Detecting Out-of-Distribution Samples and Adversarial Attacks »
Kimin Lee · Kibok Lee · Honglak Lee · Jinwoo Shin -
2018 Poster: Stochastic Chebyshev Gradient Descent for Spectral Optimization »
Insu Han · Haim Avron · Jinwoo Shin -
2018 Spotlight: A Simple Unified Framework for Detecting Out-of-Distribution Samples and Adversarial Attacks »
Kimin Lee · Kibok Lee · Honglak Lee · Jinwoo Shin -
2018 Spotlight: Stochastic Chebyshev Gradient Descent for Spectral Optimization »
Insu Han · Haim Avron · Jinwoo Shin -
2018 Poster: Learning to Specialize with Knowledge Distillation for Visual Question Answering »
Jonghwan Mun · Kimin Lee · Jinwoo Shin · Bohyung Han -
2017 Poster: Gauging Variational Inference »
Sungsoo Ahn · Michael Chertkov · Jinwoo Shin -
2016 Poster: Synthesis of MCMC and Belief Propagation »
Sungsoo Ahn · Michael Chertkov · Jinwoo Shin -
2016 Oral: Synthesis of MCMC and Belief Propagation »
Sungsoo Ahn · Michael Chertkov · Jinwoo Shin -
2015 Poster: Minimum Weight Perfect Matching via Blossom Belief Propagation »
Sungsoo Ahn · Sejun Park · Michael Chertkov · Jinwoo Shin -
2015 Spotlight: Minimum Weight Perfect Matching via Blossom Belief Propagation »
Sungsoo Ahn · Sejun Park · Michael Chertkov · Jinwoo Shin -
2013 Poster: A Graphical Transformation for Belief Propagation: Maximum Weight Matchings and Odd-Sized Cycles »
Jinwoo Shin · Andrew E Gelfand · Misha Chertkov