Microsoft at NeurIPS 2021

A Universal Law of Robustness via Isoperimetry

Sébastien Bubeck, Mark Sellke

An Exponential Lower Bound for Linearly Realizable MDP with Constant Suboptimality Gap

Yuanhao Wang, Ruosong Wang, Sham Kakade

A Universal Law of Robustness via Isoperimetry

Sébastien Bubeck, Mark Sellke

Aligning Pretraining for Detection via Object-Level Contrastive Learning

Fangyun Wei, Yue Gao, Zhirong Wu, Han Hu, Stephen Lin

Bandits with Knapsacks beyond the Worst Case

Karthik Abinav Sankararaman, Aleksandrs Slivkins (slivkins)

Bayesian decision-making under misspecified priors with applications to meta-learning

Max Simchowitz, Christopher Tosh, Akshay Krishnamurthy, Daniel Hsu, Thodoris Lykouris, Miro Dudík, Robert E. Schapire

BayesIMP: Uncertainty Quantification for Causal Data Fusion

Siu Lun Chau, Jean-Francois Ton, Javier González, Yee The, Dino Sejdinovic

Bootstrap Your Object Detector via Mixed Training

Mengde Xu, Zheng Zhang, Fangyun Wei, Yutong Lin, Yue Cao, Stephen Lin, Han Hu, Xiang Bai

Dueling Bandits with Adversarial Sleeping

Aadirupa Saha, Pierre Gaillard

Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination

Dylan Foster, Akshay Krishnamurthy

Grounding Spatio-Temporal Language with Transformers

Tristan Karch, Laetitia Teodorescu, Katja Hofmann, Clément Moulin-Frier, Pierre-Yves Oudeyer

Identifiable Generative Models for Missing Not at Random Data Imputation

Chao Ma, Cheng Zhang

Memory Efficient Meta-Learning with Large Images

John Bronskill, Daniela Massiceti, Massimiliano Patacchiola, Katja Hofmann, Richard Turner

Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness

Ankit Garg, Robin Kothari, Praneeth Netrapalli, , Suhail Sherif

Neural Pseudo-Label Optimism for the Bank Loan Problem

Aldo Pacchiano, Shaun Singh, Alex Berg, Jakob Foerster

Optimal Algorithms for Stochastic Contextual Preference Bandits

Aadirupa Saha

Optimality of Zeroth Order Gradient Ascent for Nonlinear Bandit Optimization

Baihe Huang, Kaixuan Huang, Sham Kakade, Jason Lee, Qi Lei, Runzhe Wang, Jiaqi Yang

Piper: Multidimensional Planner for DNN Parallelization

Jakub Tarnawski, Deepak Narayanan, Amar Phanishayee

Probing Inter-modality: Visual Parsing with Self-Attention for Vision-and-Language Pre-training

Hongwei Xue, Yupan Huang, Bei Liu, Houwen Peng, Jianlong Fu, Houqiang Li, Jiebo Luo

R-Drop: Regularized Dropout for Neural Networks

xiaobo liang, Lijun Wu, Juntao Li, Yue Wang, Qi Meng, Tao Qin, Wei Chen, Min Zhang, Tie-Yan Liu

Recovering Latent Causal Factor for Generalization to Distributional Shifts

Xinwei Sun, Botong Wu, Xiangyu Zheng, Chang Liu, Wei Chen, Tao Qin, Tie-Yan Liu

Reinforcement Learning in Reward-Mixing MDPs

Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, Shie Mannor

Searching the Search Space of Vision Transformer

Minghao Chen, Kan Wu, Bolin Ni, Houwen Peng, Bei Liu, Jianlong Fu, Hongyang Chao, Haibin Ling

Semi-Supervised Semantic Segmentation via Adaptive Equalization Learning

Hanzhe Hu, Fangyun Wei, Han Hu, Qiwei Ye, Jinshi Cui, Liwei Wang

Do Transformers Really Perform Badly for Graph Representation?

Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, Tie-Yan Liu

Few-Shot Data-Driven Algorithms for Low Rank Approximation

Piotr Indyk, Tal Wagner, David Woodruff

Improving Visual Quality of Image Synthesis by A Token-based Generator with Transformers

Yanhong Zeng, Huan Yang, Hongyang Chao, Jianbo Wang, Jianlong Fu

Learning and Generalization in RNNs

Abhishek Panigrahi, Navin Goyal

List-Decodable Mean Estimation in Nearly-PCA Time

Ilias Diakonikolas, Daniel Kane, Daniel Kongsgaard, Jerry Li, Kevin Tian

Robust Regression Revisited: Acceleration and Improved Estimation Rates

Arun Jambulapati, Jerry Li, Kevin Tian

The Elastic Lottery Ticket Hypothesis

Xiaohan Chen, Yu Cheng, Shuohang Wang, Zhe Gan, Jingjing Liu, Zhangyang Wang

The Emergence of Objectness: Learning Zero-shot Segmentation from Videos

Runtao Liu, Zhirong Wu, Stella Yu, Stephen Lin

Tensor Programs V: Tuning Large Neural Networks via Zero-Shot Hyperparameter Transfer

Greg Yang, Edward J. Hu, Igor Babuschkin, Szymon Sidor, David Farhi, Jakub Pachocki, Xiaodong Liu, Weizhu Chen, Jianfeng Gao

Unadversarial Examples: Designing Objects for Robust Vision

Hadi Salman*, Andrew Ilyas*, Logan Engstrom*, Sai Vemprala, Aleksander Madry, Ashish Kapoor

Adversarial Examples in Multi-Layer Random ReLU Networks

Peter Bartlett, Sébastien Bubeck, Yeshwanth Cherapanamjeri

A single gradient step finds adversarial examples on random two-layers neural networks

Sébastien Bubeck, Yeshwanth Cherapanamjeri, Gauthier Gidel, Remi Tachet des Combes

COCO-LM: Correcting and Contrasting Text Sequences for Language Model Pretraining

Yu Meng, Chenyan Xiong, Payal Bajaj, Saurabh Tiwary, Paul Bennett, Jiawei Han, Xia Song

Disentangling the Roles of Curation, Data-Augmentation and the Prior in the Cold Posterior Effect

Lorenzo Noci, Kevin Roth, Gregor Bachmann, Sebastian Nowozin, Thomas Hofmann

Do Input Gradients Highlight Discriminative Features?

Harshay Shah, Prateek Jain, Praneeth Netrapalli

FastCorrect: Fast Error Correction with Edit Alignment for Automatic Speech Recognition

Yichong Leng, Xu Tan, Linchen Zhu, Jin Xu, Renqian Luo, Linquan Liu, Tao Qin, Xiangyang Li, Edward Lin, Tie-Yan Liu

FlexMatch: Boosting Semi-Supervised Learning with Curriculum Pseudo Labeling

Bowen Zhang, Yidong Wang, Wenxin Hou, Hao Wu, Jindong Wang, Manabu Okumura

GraphFormers: GNN-nested Transformers for Representation Learning on Textual Graph

Junhan Yang, Zheng Liu, Shitao Xiao, Chaozhuo Li, Defu Lian, Sanjay Agrawal, Amit Singh, Guangzhong Sun, Xing Xie

Implicit Deep Adaptive Design: Policy-Based Experimental Design without Likelihoods

Desislava Ivanova, Adam Foster, Steven Kleinegesse, Michael Gutmann, Thomas Rainforth

Learning from Inside: Self-driven Siamese Sampling and Reasoning for Video Question Answering

Weijiang Yu, Haoteng Zheng, Mengfei Li, Lei Ji, Lijun Wu, Nong Xiao, Nan Duan

Learning Causal Semantic Representation for Out-of-Distribution Prediction

Chang Liu, Xinwei Sun, Jindong Wang, Haoyue Tang, Tao Li, Tao Qin, Wei Chen, Tie-Yan Liu

Neural Additive Models: Interpretable Machine Learning with Neural Nets

Rishabh Agarwal, Levi Melnick, Xuezhou Zhang, Ben Lengerich, Rich Caruana, Geoffrey Hinton

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

On Riemannian Optimization over Positive Definite Matrices with the Bures-Wasserstein Geometry

Andi Han, Bamdev Mishra, Pratik Kumar Jawanpuria (prjawanp), Junbin Gao

Only Train Once: A One-Shot Neural Network Training And Pruning Framework

Tianyi Chen, Bo Ji, Tianyu Ding, Biyi Fang, Guanyi Wang, Zhihui Zhu, Luming Liang, Yixin Shi, Sheng Yi, , Xiao Tu

Recognizing Vector Graphics without Rasterization

Xinyang Jiang, Lu Liu, Caihua Shan, Yifei Shen, Xuanyi Dong, Dongsheng Li

Searching Parameterized AP Loss for Object Detection

Tao Chenxin, Zizhang Li, Xizhou Zhu, Gao Huang, Yong Liu, Jifeng Dai

SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search

Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, Jingdong Wang, Mao Yang, Jingdong Wang

Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding

Shengjie Luo, Shanda Li, Tianle Cai, Di He, Dinglan Peng, Shuxin Zheng, Guolin Ke, Liwei Wang, Tie-Yan Liu

The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle

Fang Kong, Yueran Yang, Wei Chen, Shuai Li

Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination

Dylan Foster, Akshay Krishnamurthy

Bellman-consistent Pessimism for Offline Reinforcement Learning

Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, Alekh Agarwal

A Surrogate Objective Framework for Prediction+Programming with Soft Constraints

Kai Yan, …, Qingwei Lin 林庆维, …

Chasing Sparsity in Vision Transformers: An End-to-End Exploration

Tianlong Chen, Yu Cheng, Zhe Gan, Lu Yuan, Lei Zhang, Zhangyang Wang

Data-Efficient GAN Training Beyond (Just) Augmentations: A Lottery Ticket Perspective

Tianlong Chen, Yu Cheng, Zhe Gan, Jingjing Liu, Zhangyang Wang

Focal Attention for Long-Range Interactions in Vision Transformers

Jianwei Yang, Chunyuan Li, Pengchuan Zhang, Xiyang Dai, Bin Xiao, Lu Yuan, Jianfeng Gao

Gone Fishing: Neural Active Learning with Fisher Embeddings

Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, Sham Kakade

HRFormer: High-Resolution Vision Transformer for Dense Predict

Yuhui Yuan, Rao Fu, Lang Huang, Weihong Lin, Chao Zhang, Xilin Chen, Jingdong Wang

Pretraining Representations for Data-Efficient Reinforcement Learning

Max Schwarzer, Nitarshan Rajkumar, Michael Noukhovitch, Ankesh Anand, Laurent Charlin, Devon Hjelm, Philip Bachman, Aaron Courville

Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selection

Matteo Papini, Andrea Tirinzoni, Aldo Pacchiano, Marcello Restelli, Alessandro Lazaric, Matteo Pirotta

Co-evolution Transformer for Protein Contact Prediction

He Zhang, Fusong Ju, Jianwei Zhu, Liang He, Bin Shao, Nanning Zheng, Tie-Yan Liu

Combinatorial Pure Exploration with Bottleneck Reward Function

Yihan Du, Yuko Kuroki, Wei Chen

Deep Contextual Video Compression

Jiahao Li, Bin Li, Yan Lu

Distributional Reinforcement Learning for Multi-Dimensional Reward Functions

Pushi Zhang, Xiaoyu Chen, Li Zhao, Wei Xiong, Tao Qin, Tie-Yan Liu

Going Beyond Linear RL: Sample Efficient Neural Function Approximation

Baihe Huang, Kaixuan Huang, Sham Kakade, Jason D. Lee, Qi Lei, Runzhe Wang, Jiaqi Yang

Latent Matters: Learning Deep State-Space Models

Alexej Klushyn, Richard Kurle, Maximilian Soelch, Botond Cseke, Patrick van der Smagt

Information Directed Reward Learning for Reinforcement Learning

David Lindner, Matteo Turchetta, Sebastian Tschiatschek, Kamil Ciosek, Andreas Krause

LLC: Accurate, Multi-purpose Learnt Low-dimensional Binary Codes.

Aditya Kusupati, Matthew Wallingford, Vivek Ramanujan, Raghav Somani, Jae Sung Park, Krishna Pillutla, Prateek Jain, Sham Kakade, Ali Farhadi

Neural Rule-Execution Tracking Machine For Transformer-Based Text Generation

Yufei Wang, Can Xu, Huang Hu, Chongyang Tao, Stephen Wan, Mark Dras, Mark Johnson, Daxin Jiang (姜大昕)

Numerical Composition of Differential Privacy

Sivakanth Gopi, Yin Tat Lee, Lukas Wutschitz

Optimizing Information-theoretical Generalization Bound via Anisotropic Noise of SGLD

Bohan Wang, Huishuai Zhang, Jieyu Zhang, Qi Meng, Wei Chen, Tie-Yan Liu

PlayVirtual: Augmenting Cycle-Consistent Virtual Trajectories for Reinforcement Learning

Tao Yu, Cuiling Lan, Wenjun Zeng, Mingxiao Feng, Zhizheng Zhang, Zhibo Chen

Precise characterization of the prior predictive distribution of deep ReLU networks

Lorenzo Noci, Gregor Bachmann, Kevin Roth, Sebastian Nowozin, Thomas Hofmann

Stylized Dialogue Generation with Multi-Pass Dual Learning

Jinpeng Li, Yingce Xia, Rui Yan, Hongda Sun, Dongyan Zhao, Tie-Yan Liu

Tactical Optimism and Pessimism for Deep Reinforcement Learning

Ted Moskovitz, Jack Parker-Holder, Aldo Pacchiano, Michael Arbel, Michael Jordan

ToAlign: Task-Oriented Alignment for Unsupervised Domain Adaptation

Guoqiang Wei, Cuiling Lan, Wenjun Zeng, Zhizheng Zhang, Zhibo Chen

Asymptotics of the Bootstrap via Stability with Applications to Inference with Model Selection

Morgane Austern, Vasilis Syrgkanis

Curriculum Offline Imitating Learning

Minghuan Liu, Hanye Zhao, Zhengyu Yang, Jian Shen, Weinan Zhang, Li Zhao, Tie-Yan Liu

Detecting Individual Decision-Making Style: Exploring Behavioral Stylometry in Chess

Reid McIlroy-Young, Russell Wang, Jon Kleinberg, Siddhartha Sen, Ashton Anderson

Differentially private n-gram extraction

Kunho Kim, Sivakanth Gopi, Janardhan (Jana) Kulkarni, Sergey Yekhanin

Double/Debiased Machine Learning for Dynamic Treatment Effects via g-Estimation

Greg Lewis, Vasilis Syrgkanis

Dr Jekyll & Mr Hyde: the strange case of off-policy policy updates

Romain Laroche, Remi Tachet des Combes

Estimating the Long-Term Effects of Novel Treatments

Keith Battocchi, Eleanor Dillon, Maggie Hei, Greg Lewis, Miruna Oprescu, Vasilis Syrgkanis

Fast and Memory Efficient Differentially Private-SGD via JL Projections

Zhiqi Bu, Sivakanth Gopi, Janardhan (Jana) Kulkarni, Yin Tat Lee, Judy Hanwen Shen, Uthaipon Tantipongpipat

Multiclass Boosting and the Cost of Weak Learning

Nataly Brukhim, Elad Hazan, Shay Moran, Robert E. Schapire

Neural-PIL: Neural Pre-Integrated Lighting for Reflectance Decomposition

Mark Boss, Varun Jampani, Raphael Braun, Ce Liu, Jonathan Barron, Hendrik PA Lensch

NxMTransformer: Semi-Structured Sparsification for Natural Language Understanding via ADMM

Connor Holmes, Minjia Zhang, Yuxiong He, Bo Wu

On the Theory of Reinforcement Learning with Once-per-Episode Feedback

Niladri Chatterji, Aldo Pacchiano, Peter Bartlett, Michael Jordan

Parameter Inference with Bifurcation Diagrams

Gregory Szep, Neil Dalchau, Attila Csikász-Nagy

Reinforcement Learning Enhanced Explainer for Graph Neural Networks

Caihua Shan, Yifei Shen, Yao Zhang, Xiang Li, Dongsheng Li

Representation Learning for Event-based Visuomotor Policies

Sai Vemprala, Sami Mian, Ashish Kapoor

RL for Latent MDPs: Regret Guarantees and a Lower Bound

Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, Shie Mannor

Speech-T: Transducer for Text to Speech and Beyond

Jiawei Chen, Xu Tan, Yichong Leng, Jin Xu, Guihua Wen, Tao Qin, Tie-Yan Liu

Towards optimally abstaining from prediction with OOD test examples

Adam Tauman Kalai, Varun Kanade

ViSER: Video-Specific Surface Embeddings for Articulated 3D Shape Reconstruction

Gengshan Yang, Deqing Sun, Varun Jampani, Daniel Vlasic, Forrester Cole, Ce Liu, Deva Ramanan

An Exponential Lower Bound for Linearly Realizable MDP with Constant Suboptimality Gap

Yuanhao Wang, Ruosong Wang, Sham Kakade

Adaptive Diffusion in Graph Neural Networks

Jialin Zhao, Yuxiao Dong, Ming Ding, Evgeny Kharlamov, Jie Tang

Fairness via Representation Neutralization

Mengnan Du, Subhabrata (Subho) Mukherjee, Guanchu Wang, Ruixiang Tang, Ahmed Awadallah, Xia Hu

Heuristic-Guided Reinforcement Learning

Ching-An Cheng, Andrey Kolobov, Adith Swaminathan

On the Generative Utility of Cyclic Conditionals

Chang Liu, Haoyue Tang, Tao Qin, Jintao Wang, Tie-Yan Liu

Robust and Differentially Private Mean Estimation

Xiyang Liu, Weihao Kong, Sham Kakade, Sewoong Oh

SimiGrad: Fine-Grained Adaptive Batching for Large Scale Training using Gradient Similarity Measurement

Heyang Qin, Samyam Rajbhandari, Olatunji Ruwase, Feng Yan, Lei Yang, Yuxiong He

Stronger NAS with Weaker Predictors

Junru Wu, Xiyang Dai, Dongdong Chen, Yinpeng Chen, Mengchen Liu, Ye Yu, Zhangyang Wang, Zicheng Liu, Mei Chen, Lu Yuan

The Benefits of Implicit Regularization from SGD in Least Squares Problems

Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, Dean P. Foster, Sham Kakade

An Information-theoretic Approach to Distribution Shifts

Marco Federici, Ryota Tomioka, Patrick Forré

Bellman-consistent Pessimism for Offline Reinforcement Learning

Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, Alekh Agarwal

Contrastive Learning of Global-Local Video Representations

Shuang Ma, Zhaoyang Zeng, Daniel McDuff, Yale Song

Minimax Regret for Stochastic Shortest Path

Alon Cohen, Yonathan Efroni, Yishay Mansour, Aviv Rosenberg

Multi-Objective SPIBB: Seldonian Offline Policy Improvement with Safety Constraints in Finite MDPs

Harsh Satija, Philip S. Thomas, Joelle Pineau, Romain Laroche

Near Optimal Policy Optimization via REPS

Aldo Pacchiano, Jonathan N. Lee, Peter L. Bartlett, Ofir Nachum

On Contrastive Representations of Stochastic Processes

Emile Mathieu, Adam Foster, Yee Whye Teh

Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps

Janardhan (Jana) Kulkarni, Yin Tat Lee, Daogao Liu

Self-Supervised Bug Detection and Repair

Miltos Allamanis, Henry Jackson-Flux, Marc Brockschmidt

Sparse Uncertainty Representation in Deep Learning with Inducing Weights

Hippolyt Ritter, Martin Kukla, Cheng Zhang, Yingzhen Li

Structured Denoising Diffusion Models in Discrete State-Spaces

Jacob Austin, Daniel D. Johnson, Jonathan Ho, Daniel Tarlow, Rianne van den Berg