Timezone: »

 
Spotlight
Stability Based Generalization Bounds for Exponential Family Langevin Dynamics
Arindam Banerjee · Tiancong Chen · Xinyan Li · Yingxue Zhou

Wed Jul 20 07:50 AM -- 07:55 AM (PDT) @ Ballroom 1 & 2
in Deep Learning »

Recent years have seen advances in generalization bounds for noisy stochastic algorithms, especially stochastic gradient Langevin dynamics (SGLD) based on stability (Mou et al., 2018; Li et al., 2020) and information theoretic approaches (Xu & Raginsky, 2017; Negrea et al., 2019; Steinke & Zakynthinou, 2020). In this paper, we unify and substantially generalize stability based generalization bounds and make three technical contributions. First, we bound the generalization error in terms of expected (not uniform) stability which arguably leads to quantitatively sharper bounds. Second, as our main contribution, we introduce Exponential Family Langevin Dynamics (EFLD), a substantial generalization of SGLD, which includes noisy versions of Sign-SGD and quantized SGD as special cases. We establish data dependent expected stability based generalization bounds for any EFLD algorithm with a O(1/n) sample dependence and dependence on gradient discrepancy rather than the norm of gradients, yielding significantly sharper bounds. Third, we establish optimization guarantees for special cases of EFLD. Further, empirical results on benchmarks illustrate that our bounds are non-vacuous, quantitatively sharper than existing bounds, and behave correctly under noisy labels.

Keywords: DL: Algorithms · DL: Theory · OPT: Non-Convex · T: Deep Learning · T: Optimization

Author Information

Arindam Banerjee (UIUC)
Arindam Banerjee

Arindam Banerjee is a Founder Professor at the Department of Computer Science, University of Illinois Urbana-Champaign. His research interests are in machine learning. His current research focuses on computational and statistical aspects of over-parameterized models including deep learning, spatial and temporal data analysis, generative models, and sequential decision making problems. His work also focuses on applications of machine learning in complex real-world and scientific domains including problems in climate science and ecology. He has won several awards, including the NSF CAREER award, the IBM Faculty Award, and six best paper awards in top-tier venues.

Tiancong Chen (University of Minnesota)
Xinyan Li (University of Minnesota, Twin Cities)
Yingxue Zhou (University of Minnesota)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors