ICML 2023 Workshop

PAC-Bayes Meets Interactive Learning

Hawaii Convention Center, Honolulu, Hawaii
Meeting Room 314
28th July, 2023


Interactive learning encompasses online learning, continual learning, active learning, bandits, reinforcement learning, and other settings where an algorithm must learn while interacting with a continual stream of data. Such problems often involve exploration-exploitation dilemmas, which can be elegantly handled with probabilistic and Bayesian methods. Deep interactive learning methods leveraging neural networks are typically used when the setting involves rich observations, such as images. As a result, both probabilistic and deep interactive learning methods are growing in popularity. However, acquiring observations in an interactive fashion with the environment can be costly. There is therefore great interest in understanding when sample-efficient learning with probabilistic and deep interactive learning can be expected or guaranteed. Within statistical learning theory, PAC-Bayesian theory is designed for the analysis of probabilistic learning methods. It has recently been shown to be well-suited for the analysis of deep learning methods. This workshop aims to bring together researchers from the broad Bayesian and interactive learning communities in order to foster the emergence of new ideas that could contribute to both theoretical and empirical advancement of PAC-Bayesian theory in interactive learning settings.

Call For Papers

Important dates:
  • Submission deadline: June 5th, 2023 at 23:59 GMT
  • Reviewer registration link: https://docs.google.com/forms/d/1B4iX6dl1QgxPfRUmhqrriAWNllN-rFlRPR9WAjUwQNw/edit
  • Submission link: https://openreview.net/group?id=ICML.cc/2023/Workshop/PAC-Bayes_Meets_Interactive_Learning
  • Notification of acceptance: June 15th, 2023 (end of the day)
  • Posters and camera ready: July 21st, 2023
All accepted papers will have a poster presentation, and we will select a few papers for contributed talks of approximately 15 minutes each. Please note that at least one author of each accepted paper must be available for the poster/oral presentation.

Topics: We are interested in (but not limited to) the following topics:
  • Explaining the success of existing interactive learning algorithms with PAC-Bayesian theory
  • PAC-Bayesian analysis of exploration-exploitation trade-offs
  • PAC-Bayes bounds under distribution shift
  • PAC-Bayes bounds under adversarial corruptions
  • Development of practically useful interactive learning algorithms using PAC-Bayesian theory.
Submission instructions: The page limit is 4 pages (exluding references). Submissions may include supplementary material, but reviewers are only required to read the first 4 pages. Submissions should use the template in this LaTeX style file. The reviewing process is double-blind, so the submissions should be anonymized and should not contain information that could identify the authors. Parallel submission (to a journal, conference, workshop, or preprint repository) is allowed. Authors planning to submit already accepted articles are allowed to submit the full article, but are asked to make it clear that the work already went through a peer-review process.

Speakers and Panelists

Karolina Dziugaite

Senior Research Scientist, Google Brain
Adjunct Professor, McGill University

Pascal Germain

Assistant Professor, Université Laval
Canada CIFAR AI Chair

Anirudha Majumdar

Assistant Professor
Princeton University, USA

Aaditya Ramdas

Assistant Professor
Carnegie Mellon University, Amazon

Jonas Rothfuss

PhD Student
ETH Zürich, Switzerland

Preliminary Workshop Schedule

Time Title Speaker
09:00-09:15 Welcome Organisers
PAC-Bayes Tutorial

Since the first "PAC [Probably Approximately Correct] guarantees for 'Bayesian' algorithms" of McAllester (1999) - quickly followed by key additions of Catoni, Langford, Seeger and Shawe-Taylor - the PAC-Bayesian theory continuously expands to embrace the vast diversity of machine learning views and practices.

This tutorial recaps some of the key historical contributions to the field, with an emphasis on numerical aspects, such as bound-driven learning algorithms (aka self-certified learning). It also discusses a few connections recently drawn between PAC-Bayes and other theories (as mutual information) and practices (as generative adversarial methods).

Pascal Germain
10:00-10:30 Posters + break 1
Invited Talk 1: Lessons Learned from Studying PAC-Bayes and Generalization

Abstract will appear here.

Gintare Karolina Dziugaite
Invited Talk 2: A unified recipe for deriving (time-uniform) PAC-Bayes bound

We present a unified framework for deriving PAC-Bayesian generalization bounds. Unlike most previous literature on this topic, our bounds are anytime-valid (i.e., time-uniform), meaning that they hold at all stopping times, not only for a fixed sample size. Our approach combines four tools in the following order: (a) nonnegative supermartingales or reverse submartingales, (b) the method of mixtures, (c) the Donsker-Varadhan formula (or other convex duality principles), and (d) Ville's inequality. Our main result is a PAC-Bayes theorem which holds for a wide class of discrete stochastic processes. We show how this result implies time-uniform versions of well-known classical PAC-Bayes bounds, such as those of Seeger, McAllester, Maurer, and Catoni, in addition to many recent bounds. We also present several novel bounds.

Aaditya Ramdas
12:00-13:00 Lunch break
Contributed Talk: Improved Time-Uniform PAC-Bayes Bounds using Coin Betting

Link to the paper

Kyoungseok Jang
Contributed Talk: PAC-Bayesian Offline Contextual Bandits with Guarantees

Link to the paper

Otmane Sakhi
Contributed Talk: PAC-Bayes bounds’ parameter optimization via events’ space discretization: new bounds for losses with general tail behaviors

Link to the paper

Borja Rodríguez Gálvez
Invited Talk 3: Meta-Learning Reliable Priors for Interactive Learning

To navigate the exploration-exploitation trade-off in interactive learning we often rely on the uncertainty estimates of a probabilistic or Bayesian model. A key challenge is to correctly specify the prior of our model so that its epistemic uncertainty estimates are reliable. In this talk, we explore how we can harness related datasets or previous experience to meta-learn priors in a data-driven way. We study this problem through the lens of PAC-Bayesian theory and derive practical and scalable meta-learning algorithms. In particular, we discuss how to make sure that the meta-learned priors yield confidence intervals that are not overconfident so that our interactive learners explore sufficiently. Overall, the proposed meta-learning framework allows us significantly speed up interactive learning through transfer from previous tasks/runs.

Jonas Rothfuss
Invited Talk 4: Generalization Theory for Robot Learning

The ability of machine learning techniques to process rich sensory inputs such as vision makes them highly appealing for use in robotic systems (e.g., micro aerial vehicles and robotic manipulators). However, the increasing adoption of learning-based components in the robotics perception and control pipeline poses an important challenge: how can we guarantee the safety and performance of such systems? As an example, consider a micro aerial vehicle that learns to navigate using a thousand different obstacle environments or a robotic manipulator that learns to grasp using a million objects in a dataset. How likely are these systems to remain safe and perform well on a novel (i.e., previously unseen) environment or object? How can we learn control policies for robotic systems that provably generalize to environments that our robot has not previously encountered? Unfortunately, existing approaches either do not provide such guarantees or do so only under very restrictive assumptions.

In this talk, I will present our group’s work on developing a principled theoretical and algorithmic framework for learning control policies for robotic systems with formal guarantees on generalization to novel environments. The key technical insight is to leverage and extend powerful techniques from PAC-Bayes theory. We apply our techniques on problems including vision-based navigation and manipulation in order to demonstrate the ability to provide strong generalization guarantees on robotic systems with nonlinear or hybrid dynamics, rich sensory inputs, and neural network-based control policies.

Anirudha Majumdar
15:00-15:30 Posters + break 2
Contributed Talk: Anytime Model Selection in Linear Bandits

Link to the paper

Parnian Kassraie
Contributed Talk: PAC-Bayesian Error Bound, via Rényi Divergence, for a Class of Linear Time-Invariant State-Space Models

Link to the paper

Deividas Eringis
Contributed Talk: Experiment Planning with Function Approximation

Link to the paper

Aldo Pacchiano
16:00-16:45 Panel discussion

Accepted Papers

Contributed talks

  1. Improved Time-Uniform PAC-Bayes Bounds using Coin Betting
    Kyoungseok Jang, Kwang-Sung Jun, Ilja Kuzborskij and Francesco Orabona
  2. PAC-Bayesian Offline Contextual Bandits with Guarantees
    Otmane Sakhi, Pierre Alquier, Nicolas Chopin
  3. PAC-Bayes Bounds’ Parameter Optimization via Events’ Space Discretization: New Bounds for Losses with General Tail Behaviors
    Borja Rodríguez Gálvez, Ragnar Thobaben, Mikael Skoglund
  4. Anytime Model Selection in Linear Bandits
    Parnian Kassraie, Aldo Pacchiano, Nicolas Emmenegger, Andreas Krause
  5. PAC-Bayesian Error Bound, via Rényi Divergence, for a Class of Linear Time-Invariant State-Space Models
    Deividas Eringis, John Leth, Rafal Wisniewski, Zheng-Hua Tan, Mihaly Petreczky
  6. Experiment Planning with Function Approximation
    Aldo Pacchiano, Jonathan Lee, Emma Brunskill


  1. Flat Minima Can Fail to Transfer to Downstream Tasks
    Deepansha Singh, Ekansh Sharma, Daniel Roy, Gintare Karolina Dziugaite
  2. Tighter Fast and Mixed Rate PAC-Bayes Bounds
    Borja Rodríguez Gálvez, Ragnar Thobaben, Mikael Skoglund
  3. Computing Non-vacuous PAC-Bayes Generalization Bounds for Models under Adversarial Corruptionss
    Waleed Mustafa, Philipp Liznerski, Dennis Wagner, Puyu Wang, Marius Kloft
  4. Bayesian Risk-Averse Q-Learning with Streaming Data
    Yuhao Wang, Enlu Zhou
  5. PAC-Bayesian Domain Adaptation Bounds for Multi-view Learning
    Mehdi Hennequin, Khalid Benabdeslem, Haytham Elghazel
  6. Information-Theoretic Generalization Bounds for the Subtask Problem
    Firas Laakom, Yuheng Bu, Moncef Gabbouj
  7. XLDA: Linear Discriminant Analysis for Scaling Continual Learning to Extreme Classification Settings at the Edge
    Karan Shah, Vishruth Veerendranath, Anushka Hebbar, Raghavendra Bhat
  8. Bayesian Feasibility Determination with Multiple Constraints
    Tingnan Gong, Di Liu, Yao Xie, Seong-Hee Kim


Audrey Durand

Canada CIFAR AI Chair
Assistant Professor, Université Laval

Hamish Flynn

PhD Student, TU Darmstadt, Bosch Center for Artificial Intelligence

Benjamin Guedj

Associate Professor, University College London
Tenured Research Scientist, Inria
Turing Fellow, The Alan Turing Institute

Maxime Heuillet

PhD Student, Université Laval, Thales Group

Melih Kandemir

Associate Professor, University of Southern Denmark


Funding from CIFAR is available to support Canadian students who might not otherwise be able to attend the event, with a focus on students who identify as members of underrepresented groups.


Please contact the organisers at: pacbayes.interactivelearning@gmail.com