Timezone: »
This paper considers the Pointer Value Retrieval (PVR) benchmark introduced in [ZRKB21], where a `reasoning' function acts on a string of digits to produce the label. More generally, the paper considers the learning of logical functions with gradient descent (GD) on neural networks. It is first shown that in order to learn logical functions with gradient descent on symmetric neural networks, the generalization error can be lower-bounded in terms of the noise-stability of the target function, supporting a conjecture made in [ZRKB21]. It is then shown that in the distribution shift setting, when the data withholding corresponds to freezing a single feature (referred to as canonical holdout), the generalization error of gradient descent admits a tight characterization in terms of the Boolean influence for several relevant architectures. This is shown on linear models and supported experimentally on other models such as MLPs and Transformers. In particular, this puts forward the hypothesis that for such architectures and for learning logical functions such as PVR functions, GD tends to have an implicit bias towards low-degree representations, which in turn gives the Boolean influence for the generalization error under quadratic loss.
Author Information
Emmanuel Abbe (Swiss Federal Institute of Technology Lausanne)
Samy Bengio (Apple)
Elisabetta Cornacchia (EPFL - EPF Lausanne)
Jon Kleinberg (Cornell University)
Aryo Lotfi (EPFL - EPF Lausanne)
Maithra Raghu (Google Brain)
Chiyuan Zhang (Google Research)
More from the Same Authors
-
2021 Spotlight: On the Power of Differentiable Learning versus PAC and SQ Learning »
Emmanuel Abbe · Pritish Kamath · Eran Malach · Colin Sandon · Nathan Srebro -
2021 : Understanding and Improving Robustness of VisionTransformers through patch-based NegativeAugmentation »
Yao Qin · Chiyuan Zhang · Ting Chen · Balaji Lakshminarayanan · Alex Beutel · Xuezhi Wang -
2021 : Models of fairness in federated learning »
Kate Donahue · Jon Kleinberg -
2021 : Models of fairness in federated learning »
Kate Donahue · Jon Kleinberg -
2022 : Continuous Soft Pseudo-Labeling in ASR »
Tatiana Likhomanenko · Ronan Collobert · Navdeep Jaitly · Samy Bengio -
2023 Poster: Sparsity-Preserving Differentially Private Training »
Badih Ghazi · Yangsibo Huang · Pritish Kamath · Ravi Kumar · Pasin Manurangsi · Amer Sinha · Chiyuan Zhang -
2023 Poster: Transformers learn through gradual rank increase »
Emmanuel Abbe · Samy Bengio · Enric Boix-Adsera · Etai Littwin · Joshua Susskind -
2023 Poster: Optimal Unbiased Randomizers for Regression with Label Differential Privacy »
Ashwinkumar Badanidiyuru Varadaraja · Badih Ghazi · Pritish Kamath · Ravi Kumar · Ethan Leeman · Pasin Manurangsi · Avinash V Varadarajan · Chiyuan Zhang -
2023 Poster: User-Level Differential Privacy With Few Examples Per User »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi · Raghu Meka · Chiyuan Zhang -
2023 Poster: On the Relationship Between Relevance and Conflict in Online Social Link Recommendations »
Yanbang Wang · Jon Kleinberg -
2023 Poster: Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputs »
Emmanuel Abbe · Elisabetta Cornacchia · Aryo Lotfi -
2023 Poster: Counterfactual Memorization in Neural Language Models »
Chiyuan Zhang · Daphne Ippolito · Katherine Lee · Matthew Jagielski · Florian Tramer · Nicholas Carlini -
2023 Oral: User-Level Differential Privacy With Few Examples Per User »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi · Raghu Meka · Chiyuan Zhang -
2022 : Panel »
Meena Jagadeesan · Avrim Blum · Jon Kleinberg · Celestine Mendler-Dünner · Jennifer Wortman Vaughan · Chara Podimata -
2022 Poster: On the non-universality of deep learning: quantifying the cost of symmetry »
Emmanuel Abbe · Enric Boix-Adsera -
2022 Poster: Understanding and Improving Robustness of Vision Transformers through Patch-based Negative Augmentation »
Yao Qin · Chiyuan Zhang · Ting Chen · Balaji Lakshminarayanan · Alex Beutel · Xuezhi Wang -
2022 Poster: The Privacy Onion Effect: Memorization is Relative »
Nicholas Carlini · Matthew Jagielski · Chiyuan Zhang · Nicolas Papernot · Andreas Terzis · Florian Tramer -
2021 : Algorithmic Monoculture and Social Welfare »
Jon Kleinberg -
2021 : Panel II: Machine decisions »
Anca Dragan · Karen Levy · Himabindu Lakkaraju · Ariel Rosenfeld · Maithra Raghu · Irene Y Chen -
2021 : Spotlight 2: Models of fairness in federated learning »
Kate Donahue · Jon Kleinberg -
2021 Poster: On the Power of Differentiable Learning versus PAC and SQ Learning »
Emmanuel Abbe · Pritish Kamath · Eran Malach · Colin Sandon · Nathan Srebro -
2021 Poster: Learnable Fourier Features for Multi-dimensional Spatial Positional Encoding »
Yang Li · Si Si · Gang Li · Cho-Jui Hsieh · Samy Bengio -
2021 Poster: Deep Learning with Label Differential Privacy »
Badih Ghazi · Noah Golowich · Ravi Kumar · Pasin Manurangsi · Chiyuan Zhang -
2021 Poster: Improving Anytime Prediction with Parallel Cascaded Networks and a Temporal-Difference Loss »
Michael Iuzzolino · Michael Mozer · Samy Bengio -
2021 Poster: Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components »
Nate Veldt · Austin Benson · Jon Kleinberg -
2021 Poster: Optimality and Stability in Federated Learning: A Game-theoretic Approach »
Kate Donahue · Jon Kleinberg -
2021 Poster: Detecting Individual Decision-Making Style: Exploring Behavioral Stylometry in Chess »
Reid McIlroy-Young · Russell Wang · Siddhartha Sen · Jon Kleinberg · Ashton Anderson -
2021 Poster: The staircase property: How hierarchical structure can guide deep learning »
Emmanuel Abbe · Enric Boix-Adsera · Matthew S Brennan · Guy Bresler · Dheeraj Nagaraj -
2021 Poster: Do Vision Transformers See Like Convolutional Neural Networks? »
Maithra Raghu · Thomas Unterthiner · Simon Kornblith · Chiyuan Zhang · Alexey Dosovitskiy -
2020 Poster: What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation »
Vitaly Feldman · Chiyuan Zhang -
2020 Spotlight: What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation »
Vitaly Feldman · Chiyuan Zhang -
2020 Poster: Memory Based Trajectory-conditioned Policies for Learning from Sparse Rewards »
Yijie Guo · Jongwook Choi · Marcin Moczulski · Shengyu Feng · Samy Bengio · Mohammad Norouzi · Honglak Lee -
2020 Poster: What is being transferred in transfer learning? »
Behnam Neyshabur · Hanie Sedghi · Chiyuan Zhang -
2020 : Dr. Samy Bengio (Google Brain) »
Samy Bengio -
2019 : Contributed Session - Spotlight Talks »
Jonathan Frankle · David Schwab · Ari Morcos · Qianli Ma · Yao-Hung Hubert Tsai · Ruslan Salakhutdinov · YiDing Jiang · Dilip Krishnan · Hossein Mobahi · Samy Bengio · Sho Yaida · Muqiao Yang -
2019 : Lunch Break and Posters »
Xingyou Song · Elad Hoffer · Wei-Cheng Chang · Jeremy Cohen · Jyoti Islam · Yaniv Blumenfeld · Andreas Madsen · Jonathan Frankle · Sebastian Goldt · Satrajit Chatterjee · Abhishek Panigrahi · Alex Renda · Brian Bartoldson · Israel Birhane · Aristide Baratin · Niladri Chatterji · Roman Novak · Jessica Forde · YiDing Jiang · Yilun Du · Linara Adilova · Michael Kamp · Berry Weinstein · Itay Hubara · Tal Ben-Nun · Torsten Hoefler · Daniel Soudry · Hsiang-Fu Yu · Kai Zhong · Yiming Yang · Inderjit Dhillon · Jaime Carbonell · Yanqing Zhang · Dar Gilboa · Johannes Brandstetter · Alexander R Johansen · Gintare Karolina Dziugaite · Raghav Somani · Ari Morcos · Freddie Kalaitzis · Hanie Sedghi · Lechao Xiao · John Zech · Muqiao Yang · Simran Kaur · Qianli Ma · Yao-Hung Hubert Tsai · Ruslan Salakhutdinov · Sho Yaida · Zachary Lipton · Daniel Roy · Michael Carbin · Florent Krzakala · Lenka Zdeborová · Guy Gur-Ari · Ethan Dyer · Dilip Krishnan · Hossein Mobahi · Samy Bengio · Behnam Neyshabur · Praneeth Netrapalli · Kris Sankaran · Julien Cornebise · Yoshua Bengio · Vincent Michalski · Samira Ebrahimi Kahou · Md Rifat Arefin · Jiri Hron · Jaehoon Lee · Jascha Sohl-Dickstein · Samuel Schoenholz · David Schwab · Dongyu Li · Sang Choe · Henning Petzka · Ashish Verma · Zhichao Lin · Cristian Sminchisescu -
2019 : Poster Session I »
Shuangjia Zheng · Arnav Kapur · Umar Asif · Eyal Rozenberg · Cyprien Gilet · Oleksii Sidorov · Yogesh Kumar · Tom Van Steenkiste · William Boag · David Ouyang · Paul Jaeger · Sheng Liu · Aparna Balagopalan · Deepta Rajan · Marta Skreta · Nikhil Pattisapu · Jann Goschenhofer · Viraj Prabhu · Di Jin · Laura-Jayne Gardiner · Irene Li · sriram kumar · Qiyuan Hu · Mehul Motani · Justin Lovelace · Usman Roshan · Lucy Lu Wang · Ilya Valmianski · Hyeonwoo Lee · Sunil Mallya · Elias Chaibub Neto · Jonas Kemp · Marie Charpignon · Amber Nigam · Wei-Hung Weng · Sabri Boughorbel · Alexis Bellot · Lovedeep Gondara · Haoran Zhang · Taha Bahadori · John Zech · Rulin Shao · Edward Choi · Laleh Seyyed-Kalantari · Emily Aiken · Ioana Bica · Yiqiu Shen · Kieran Chin-Cheong · Subhrajit Roy · Ioana Baldini · So Yeon Min · Dirk Deschrijver · Pekka Marttinen · Damian Pascual Ortiz · Supriya Nagesh · Niklas Rindtorff · Andriy Mulyar · Katharina Hoebel · Martha Shaka · Pierre Machart · Leon Gatys · Nathan Ng · Matthias Hüser · Devin Taylor · Dennis Barbour · Natalia Martinez · Clara McCreery · Benjamin Eyre · Vivek Natarajan · Ren Yi · Ruibin Ma · Chirag Nagpal · Nan Du · Chufan Gao · Anup Tuladhar · Sam Shleifer · Jason Ren · Pouria Mashouri · Ming Yang Lu · Farideh Bagherzadeh-Khiabani · Olivia Choudhury · Maithra Raghu · Scott Fleming · Mika Jain · GUO YANG · Alena Harley · Stephen Pfohl · Elisabeth Rumetshofer · Alex Fedorov · Saloni Dash · Jacob Pfau · Sabina Tomkins · Colin Targonski · Michael Brudno · Xinyu Li · Yiyang Yu · Nisarg Patel -
2019 : Spotlight Paper Talks »
Arnav Kapur · Maithra Raghu · Xinyu Li -
2019 Poster: Transfusion: Understanding Transfer Learning for Medical Imaging »
Maithra Raghu · Chiyuan Zhang · Jon Kleinberg · Samy Bengio -
2018 : Panel Discussion »
Rich Caruana · Mike Schuster · Ralf Schlüter · Hynek Hermansky · Renato De Mori · Samy Bengio · Michiel Bacchiani · Jason Eisner -
2018 : Poster Session I »
Aniruddh Raghu · Daniel Jarrett · Kathleen Lewis · Elias Chaibub Neto · Nicholas Mastronarde · Shazia Akbar · Chun-Hung Chao · Henghui Zhu · Seth Stafford · Luna Zhang · Jen-Tang Lu · Changhee Lee · Adityanarayanan Radhakrishnan · Fabian Falck · Liyue Shen · Daniel Neil · Yusuf Roohani · Aparna Balagopalan · Brett Marinelli · Hagai Rossman · Sven Giesselbach · Jose Javier Gonzalez Ortiz · Edward De Brouwer · Byung-Hoon Kim · Rafid Mahmood · Tzu Ming Hsu · Antonio Ribeiro · Rumi Chunara · Agni Orfanoudaki · Kristen Severson · Mingjie Mai · Sonali Parbhoo · Albert Haque · Viraj Prabhu · Di Jin · Alena Harley · Geoffroy Dubourg-Felonneau · Xiaodan Hu · Maithra Raghu · Jonathan Warrell · Nelson Johansen · Wenyuan Li · Marko Järvenpää · Satya Narayan Shukla · Sarah Tan · Vincent Fortuin · Beau Norgeot · Yi-Te Hsu · Joel H Saltz · Veronica Tozzo · Andrew Miller · Guillaume Ausset · Azin Asgarian · Francesco Paolo Casale · Antoine Neuraz · Bhanu Pratap Singh Rawat · Turgay Ayer · Xinyu Li · Mehul Motani · Nathaniel Braman · Laetitia M Shao · Adrian Dalca · Hyunkwang Lee · Emma Pierson · Sandesh Ghimire · Yuji Kawai · Owen Lahav · Anna Goldenberg · Denny Wu · Pavitra Krishnaswamy · Colin Pawlowski · Arijit Ukil · Yuhui Zhang -
2018 Poster: Large Margin Deep Networks for Classification »
Gamaleldin Elsayed · Dilip Krishnan · Hossein Mobahi · Kevin Regan · Samy Bengio -
2018 Poster: Insights on representational similarity in neural networks with canonical correlation »
Ari Morcos · Maithra Raghu · Samy Bengio -
2018 Poster: Content preserving text generation with attribute controls »
Lajanugen Logeswaran · Honglak Lee · Samy Bengio -
2017 Workshop: Deep Learning: Bridging Theory and Practice »
Sanjeev Arora · Maithra Raghu · Russ Salakhutdinov · Ludwig Schmidt · Oriol Vinyals -
2017 : Competition I: Adversarial Attacks and Defenses »
Alexey Kurakin · Ian Goodfellow · Samy Bengio · Yao Zhao · Yinpeng Dong · Tianyu Pang · Fangzhou Liao · Cihang Xie · Adithya Ganesh · Oguz Elibol -
2017 Poster: SVCCA: Singular Vector Canonical Correlation Analysis for Deep Learning Dynamics and Interpretability »
Maithra Raghu · Justin Gilmer · Jason Yosinski · Jascha Sohl-Dickstein -
2016 Workshop: Extreme Classification: Multi-class and Multi-label Learning in Extremely Large Label Spaces »
Moustapha Cisse · Manik Varma · Samy Bengio -
2016 Poster: Can Active Memory Replace Attention? »
Łukasz Kaiser · Samy Bengio -
2016 Poster: An Online Sequence-to-Sequence Model Using Partial Conditioning »
Navdeep Jaitly · Quoc V Le · Oriol Vinyals · Ilya Sutskever · David Sussillo · Samy Bengio -
2016 Poster: Exponential expressivity in deep neural networks through transient chaos »
Ben Poole · Subhaneil Lahiri · Maithra Raghu · Jascha Sohl-Dickstein · Surya Ganguli -
2016 Poster: Reward Augmented Maximum Likelihood for Neural Structured Prediction »
Mohammad Norouzi · Samy Bengio · zhifeng Chen · Navdeep Jaitly · Mike Schuster · Yonghui Wu · Dale Schuurmans -
2015 Poster: Scheduled Sampling for Sequence Prediction with Recurrent Neural Networks »
Samy Bengio · Oriol Vinyals · Navdeep Jaitly · Noam Shazeer -
2013 Workshop: Output Representation Learning »
Yuhong Guo · Dale Schuurmans · Richard Zemel · Samy Bengio · Yoshua Bengio · Li Deng · Dan Roth · Kilian Q Weinberger · Jason Weston · Kihyuk Sohn · Florent Perronnin · Gabriel Synnaeve · Pablo R Strasser · julien audiffren · Carlo Ciliberto · Dan Goldwasser -
2013 Poster: DeViSE: A Deep Visual-Semantic Embedding Model »
Andrea Frome · Greg Corrado · Jonathon Shlens · Samy Bengio · Jeff Dean · Marc'Aurelio Ranzato · Tomas Mikolov -
2012 Workshop: Big Data Meets Computer Vision: First International Workshop on Large Scale Visual Recognition and Retrieval »
Jia Deng · Samy Bengio · Yuanqing Lin · Li Fei-Fei -
2010 Poster: Label Embedding Trees for Large Multi-Class Tasks »
Samy Bengio · Jason E Weston · David Grangier -
2009 Poster: Group Sparse Coding »
Samy Bengio · Fernando Pereira · Yoram Singer · Dennis Strelow -
2009 Poster: An Online Algorithm for Large Scale Image Similarity Learning »
Gal Chechik · Uri Shalit · Varun Sharma · Samy Bengio -
2007 Workshop: Efficient Machine Learning - Overcoming Computational Bottlenecks in Machine Learning (Part 2) »
Samy Bengio · Corinna Cortes · Dennis DeCoste · Francois Fleuret · Ramesh Natarajan · Edwin Pednault · Dan Pelleg · Elad Yom-Tov -
2007 Workshop: Efficient Machine Learning - Overcoming Computational Bottlenecks in Machine Learning (Part 1) »
Samy Bengio · Corinna Cortes · Dennis DeCoste · Francois Fleuret · Ramesh Natarajan · Edwin Pednault · Dan Pelleg · Elad Yom-Tov -
2006 Workshop: Learning to Compare Examples »
David Grangier · Samy Bengio