Timezone: »
Poster
Fine-Grained Analysis of Stability and Generalization for Modern Meta Learning Algorithms
Jiechao Guan · Yong Liu · Zhiwu Lu
@
The support/query episodic training strategy has been widely applied in modern meta learning algorithms. Supposing the $n$ training episodes and the test episodes are sampled independently from the same environment, previous work has derived a generalization bound of $O(1/\sqrt{n})$ for smooth non-convex functions via algorithmic stability analysis. In this paper, we provide fine-grained analysis of stability and generalization for modern meta learning algorithms by considering more general situations. Firstly, we develop matching lower and upper stability bounds for meta learning algorithms with two types of loss functions: (1) nonsmooth convex functions with $\alpha$-H{\"o}lder continuous subgradients $(\alpha \in [0,1))$; (2) smooth (including convex and non-convex) functions. Our tight stability bounds show that, in the nonsmooth convex case, meta learning algorithms can be inherently less stable than in the smooth convex case. For the smooth non-convex functions, our stability bound is sharper than the existing one, especially in the setting where the number of iterations is larger than the number $n$ of training episodes. Secondly, we derive improved generalization bounds for meta learning algorithms that hold with high probability. Specifically, we first demonstrate that, under the independent episode environment assumption, the generalization bound of $O(1/\sqrt{n})$ via algorithmic stability analysis is near optimal. To attain faster convergence rate, we show how to yield a deformed generalization bound of $O(\ln{n}/n)$ with the curvature condition of loss functions. Finally, we obtain a generalization bound for meta learning with dependent episodes whose dependency relation is characterized by a graph. Experiments on regression problems are conducted to verify our theoretical results.
Author Information
Jiechao Guan (Renmin University of China)
Yong Liu (Renmin University of China)
Zhiwu Lu (Renmin University of China)
More from the Same Authors
-
2021 Spotlight: Improved Learning Rates of a Functional Lasso-type SVM with Sparse Multi-Kernel Representation »
shaogao lv · Junhui Wang · Jiankun Liu · Yong Liu -
2021 Spotlight: Refined Learning Bounds for Kernel and Approximate $k$-Means »
Yong Liu -
2022 Poster: BMU-MoCo: Bidirectional Momentum Update for Continual Video-Language Modeling »
Yizhao Gao · Nanyi Fei · Haoyu Lu · Zhiwu Lu · Hao Jiang · Yijie Li · Zhao Cao -
2022 Poster: LGDN: Language-Guided Denoising Network for Video-Language Modeling »
Haoyu Lu · Mingyu Ding · Nanyi Fei · Yuqi Huo · Zhiwu Lu -
2022 Spotlight: Lightning Talks 6A-2 »
Yichuan Mo · Botao Yu · Gang Li · Zezhong Xu · Haoran Wei · Arsene Fansi Tchango · Raef Bassily · Haoyu Lu · Qi Zhang · Songming Liu · Mingyu Ding · Peiling Lu · Yifei Wang · Xiang Li · Dongxian Wu · Ping Guo · Wen Zhang · Hao Zhongkai · Mehryar Mohri · Rishab Goel · Yisen Wang · Yifei Wang · Yangguang Zhu · Zhi Wen · Ananda Theertha Suresh · Chengyang Ying · Yujie Wang · Peng Ye · Rui Wang · Nanyi Fei · Hui Chen · Yiwen Guo · Wei Hu · Chenglong Liu · Julien Martel · Yuqi Huo · Wu Yichao · Hang Su · Yisen Wang · Peng Wang · Huajun Chen · Xu Tan · Jun Zhu · Ding Liang · Zhiwu Lu · Joumana Ghosn · Shanshan Zhang · Wei Ye · Ze Cheng · Shikun Zhang · Tao Qin · Tie-Yan Liu -
2022 Spotlight: BMU-MoCo: Bidirectional Momentum Update for Continual Video-Language Modeling »
Yizhao Gao · Nanyi Fei · Haoyu Lu · Zhiwu Lu · Hao Jiang · Yijie Li · Zhao Cao -
2022 Spotlight: LGDN: Language-Guided Denoising Network for Video-Language Modeling »
Haoyu Lu · Mingyu Ding · Nanyi Fei · Yuqi Huo · Zhiwu Lu -
2022 Spotlight: Lightning Talks 6A-1 »
Ziyi Wang · Nian Liu · Yaming Yang · Qilong Wang · Yuanxin Liu · Zongxin Yang · Yizhao Gao · Yanchen Deng · Dongze Lian · Nanyi Fei · Ziyu Guan · Xiao Wang · Shufeng Kong · Xumin Yu · Daquan Zhou · Yi Yang · Fandong Meng · Mingze Gao · Caihua Liu · Yongming Rao · Zheng Lin · Haoyu Lu · Zhe Wang · Jiashi Feng · Zhaolin Zhang · Deyu Bo · Xinchao Wang · Chuan Shi · Jiangnan Li · Jiangtao Xie · Jie Zhou · Zhiwu Lu · Wei Zhao · Bo An · Jiwen Lu · Peihua Li · Jian Pei · Hao Jiang · Cai Xu · Peng Fu · Qinghua Hu · Yijie Li · Weigang Lu · Yanan Cao · Jianbin Huang · Weiping Wang · Zhao Cao · Jie Zhou -
2022 Spotlight: Fine-Grained Analysis of Stability and Generalization for Modern Meta Learning Algorithms »
Jiechao Guan · Yong Liu · Zhiwu Lu -
2022 Spotlight: Lightning Talks 4A-1 »
Jiawei Huang · Su Jia · Abdurakhmon Sadiev · Ruomin Huang · Yuanyu Wan · Denizalp Goktas · Jiechao Guan · Andrew Li · Wei-Wei Tu · Li Zhao · Amy Greenwald · Jiawei Huang · Dmitry Kovalev · Yong Liu · Wenjie Liu · Peter Richtarik · Lijun Zhang · Zhiwu Lu · R Ravi · Tao Qin · Wei Chen · Hu Ding · Nan Jiang · Tie-Yan Liu -
2022 Spotlight: Stability and Generalization of Kernel Clustering: from Single Kernel to Multiple Kernel »
Weixuan Liang · Xinwang Liu · Yong Liu · sihang zhou · Jun-Jie Huang · Siwei Wang · Jiyuan Liu · Yi Zhang · En Zhu -
2022 Poster: Randomized Sketches for Clustering: Fast and Optimal Kernel $k$-Means »
Rong Yin · Yong Liu · Weiping Wang · Dan Meng -
2022 Poster: Stability and Generalization of Kernel Clustering: from Single Kernel to Multiple Kernel »
Weixuan Liang · Xinwang Liu · Yong Liu · sihang zhou · Jun-Jie Huang · Siwei Wang · Jiyuan Liu · Yi Zhang · En Zhu -
2021 Poster: Towards Sharper Generalization Bounds for Structured Prediction »
Shaojie Li · Yong Liu -
2021 Poster: Refined Learning Bounds for Kernel and Approximate $k$-Means »
Yong Liu -
2021 Poster: Improved Learning Rates of a Functional Lasso-type SVM with Sparse Multi-Kernel Representation »
shaogao lv · Junhui Wang · Jiankun Liu · Yong Liu -
2021 Poster: Compressed Video Contrastive Learning »
Yuqi Huo · Mingyu Ding · Haoyu Lu · Nanyi Fei · Zhiwu Lu · Ji-Rong Wen · Ping Luo -
2019 Poster: Two Generator Game: Learning to Sample via Linear Goodness-of-Fit Test »
Lizhong Ding · Mengyang Yu · Li Liu · Fan Zhu · Yong Liu · Yu Li · Ling Shao -
2018 Poster: Domain-Invariant Projection Learning for Zero-Shot Recognition »
An Zhao · Mingyu Ding · Jiechao Guan · Zhiwu Lu · Tao Xiang · Ji-Rong Wen -
2018 Poster: Multi-Class Learning: From Theory to Algorithm »
Jian Li · Yong Liu · Rong Yin · Hua Zhang · Lizhong Ding · Weiping Wang