PAC-Bayes

• Learning sample $\mathcal{S} := \{z_1, z_2, \dots, z_n\} \sim \mathcal{D}^n$
• Hypothesis $h : \mathcal{X} \to \mathcal{Y}$, $h \in \mathcal{H}$
• Prior $P$, Posterior $Q$
• Loss function $\ell : \mathcal{H} \times \mathcal{Z} \to \mathbb{R}$

일반적으로 PAC-Bayes Bound는 아래와 같이 주어진다.
With probability at least $1-\delta$,

Online PAC-Bayes

한편 데이터가 누적됨에 따라 Prior $P$와 Posterior $Q$가 시간에 따라 변화하는 상황을 고려해보자.

• Sequence of Priors $(P_i)_{1 \le i \le m}$, $P_1 = P$는 Data-free prior이고, $P_i$는 $\mathcal{F}_{t-1}$에 의존할 수 있다.
• Sequence of Posteriors $(Q_i)_{1 \le i \le m}$

논문의 Main Result인 Online PAC-Bayes Bound는 아래와 같다.

또한, Upper Bound를 최소화하는 $Q_{i}$는 Gibbs Posterior로 주어짐이 알려져있다. 일반적으로, Gibbs Posterior를 구하는 과정은 비용이 매우 비싸다. Gibbs Posterior를 Variational Approximation하는 방법으로 풀 수도 있겠지만 (e.g. Cherief-Abdellatif, 2019), 이 논문에서는 다른 방법을 제시한다.

Disintegrated Bounds

위에서 Upper Bound를 최소화하는 문제를 풀어서 Posterior를 구한다고 하였다. 한편 앞서 언급한 Upper Bound를 최소화하여 문제를 푸는 것은 계산을 하는 것은 비용적인 문제가 있다. 그 이유는 아래의 적분 계산을 수행하는 것이 어렵기 때문이다.

뿐만 아니라 Gibbs Posterior의 Normalizing Term과 관련하여 아래의 계산을 수행해야한다.

그래서 전체 Hypothesis에 대해서 평가된 loss를 최소화하는 것이 아니라, sampling된 hypothesis에 대해서 평가된 loss를 최소하는 문제로 바꾸고자 한다.

그래서 논문에서는 sampled된 hypothesis sequence $(h_1, \dots, h_m)$에 대해서 아래와 같은 Bound를 증명했다.

$\Psi$와 $\Phi$는 Bound를 어떤 disintegrated PAC-Bayes inequality를 사용하느냐에 따라 달라지며, 논문에서는 두 가지를 제안한다. 하나는 (Rivasplata, 2020)의 KL 기반이고, 다른 하나는 (Viallard, 2021)의 Renyi 기반이다.

위 Upper Bound를 매 Step마다 최소화하는 방향으로 문제를 풀어나가면 될것이다.

Key contribution?

다 이해하지는 못했지만,
기존의 PAC-Bayesian Bound를 Online 세팅에 맞게 변형한 것 (Thm 2.3)이 key contribution인 것으로 이해하고 있다. 구체적으로는 과거 정보에 의존하는 Prior와 시간에 따라 변화하는 Posterior를 허용한 세팅에서 Bound를 보인 것이 중요한 기여인 것 같다.

Haddouche, Maxime, and Benjamin Guedj. "Online pac-bayes learning." Advances in Neural Information Processing Systems 35 (2022): 25725-25738.