Continual Learning With Participation Privacy: An Auditable Buffering-Aggregation Recipe

기술 요약: 참여 프라이버시를 고려한 지속적 학습 (Continual Learning With Participation Privacy)

문제 정의
현대의 연합 학습(Federated Learning) 및 스트리밍 학습 시스템은 훈련 중에 중간 모델 스냅샷을 빈번하게 공개하며, 이는 공격자에게 최종 모델뿐만 아니라 업데이트의 전체 궤적 $(w(t))_{t \ge 0}$을 노출하는 결과를 초래한다. 지속적인 공개(continual release)에 대한 고전적인 차분 프라이버시(Differential Privacy, DP) 분석은 대개 해밍 이웃(Hamming-neighbor) 스트림(두 스트림이 정확히 한 번의 시간 인덱스에서 서로 다른 경우)을 가정하지만, 실제 배포 환경에서는 **참여 프라이버시(Participation Privacy)**가 요구되는 경우가 많다. 이 설정에서 사용자는 자신이 참여했는지 여부에 대해 그럴듯한 부인 가능성(plausible deniability)을 확보하고자 한다. 이는 단일 편집(Single-edit, 편집 거리) 이웃 스트림에 대한 동기 부여가 된다. 여기서 두 스트림은 하나의 사용자 이벤트가 삽입되거나 삭제됨으로써 서로를 얻을 수 있는 관계를 가진다.

핵심적인 어려움은 단일 삽입 또는 삭제가 이후 스트림의 모든 위치 정렬(alignment)을 변화시킨다는 점이다. 결과적으로, 편집 이웃 쌍은 해밍 이웃 관계로부터 임의로 멀어질 수 있다. 또한, 지속적 학습은 본질적으로 **상호작용적(Interactive)**이다. 즉, 공개된 모델이 미래의 사용자 업데이트에 영향을 미치는 적응형 피드백 루프를 생성한다. 표준적인 지속적 DP 프리미티브(예: 트리 기반 접두사 합, tree-based prefix sums)는 원래 비적응형(non-adaptive) 해밍 가정을 기반으로 분석되었으며, 이러한 보장 사항들은 편집 이웃 스트림과 적응형 상호작용이 결합된 상황으로 직접 전이되지 않는다.

방법론: 감사 가능한 버퍼링-집계 레시피 (An Auditable Buffering-Aggregation Recipe)
저자들은 **무작위 버퍼링 래퍼(Randomized Buffering Wrapper)**와 **인증된 지속적 공개 DP 프리미티브(Certified Continual-Release DP Primitive)**라는 두 가지 주요 구성 요소로 이루어진 모듈형 파이프라인을 제안한다.

1. 무작위 버퍼링 (RandBin):

   • 이 구성 요소는 단일 편집 이웃 이벤트 스트림을 희소한(sparse) 해밍 스타일의 빈(bin) 단위 업데이트 스트림으로 변환하는 인터페이스 역할을 한다.
   • 이 방식은 무작위 지연을 도입하여, 사용자 업데이트를 제어된 크기 $[U, 2U]$의 "빈(bin)" 단위로 공개한다. 여기서 $U$는 프라이버시 예산 $(\varepsilon, \delta)$에 의해 조정되는 파라미터이다.
   • 빈의 경계를 무작위화함으로써, 입력 스트림에서의 단일 삽입 또는 삭제는 방출되는 빈 스트림에 제한적인 해밍 스타일의 섭동(perturbation)만을 유도한다(구체적으로, 최대 두 개의 인접한 빈에만 영향을 미친다).
   • 이 메커니즘은 명시적인 백로그(backlog) 및 지연 보장을 제공하여, 대기 중인 이벤트의 수가 높은 확률로 유계(bounded)임을 보장한다.

2. 적응형 안전성 인증 (Certification of Adaptive Safety):

   • 저자들은 표준 비적응형 DP 증명이 적응형 상호작용(피드백) 하에서도 지속적 프리미티브에 대해 유효하게 유지되기 위한 **인증 정리(Certification Theorem)**를 도입한다.
   • 이 인증은 다운스트림 프리미티브에 대해 두 가지 구조적 조건을 요구한다:
     • 매 라운드 독립적인 무작위성 (Fresh Per-Round Randomness): 메커니즘은 각 공개 단계에서 독립적인 무작위성을 사용해야 한다.
     • 안정적인 컨텍스트 (Stable Context, 정량적 분해 가능성): 적응형 업데이트가 통계량을 변경할 수는 있지만, 이웃하는 스트림 간의 고유한 해밍 불일치(Hamming discrepancy)에 대한 프라이버시 비용을 변경해서는 안 된다.
   • 이러한 조건을 만족하는 프리미티브(예: 트리 기반 접두사 합, 하삼각 행렬 메커니즘)는 "피드백 안전(feedback-safe)"한 것으로 간주되어, 비적응형 프라이버시 분석을 적응형 설정으로 직접 확장할 수 있다.

3. 모듈형 결합 (Modular Composition):

   • 이 파이프라인은 무작위 버퍼링(편집 인접성을 해밍 인접성으로 감소시킴)과 인증된 DP 집계기를 결합한다.
   • 엔드 투 엔드(end-to-end) 프라이버시 보장은 래퍼의 이웃 보존(neighbor-preserving, NPDP) 특성과 적응형 DP의 특성을 결합하는 모듈형 합성 정리를 통해 도출된다.

주요 기여

• 편집 이웃 지속적 학습의 공식화: 본 논문은 중간 공개 및 적응형 피드백이 존재하는 지속적 학습 환경에서, 단일 편집 이웃 사용자 업데이트 스트림을 통한 참여 프라이버시를 공식화하였다.
• 명시적인 프라이버시-지연 연결: 저자들은 타겟 프라이버시 파라미터 $(\varepsilon, \delta)$가 버퍼링 수준 $U$를 명시적으로 결정하여, 학습 과정에 정량화 가능한 지연/신선도 저하(staleness)를 유도하는 모듈형 파이프라인을 제공한다.
• 적응형 안전성을 위한 인증 정리: 표준 비적-적응형 해밍 이웃 DP 증명이 적응형 상호작용 하에서도 유효하게 유지될 수 있는 재사용 가능하고 검증 가능한 조건을 확립하였다. 이 조건은 신선한 무작위성과 안정적 컨텍스트 요구사항을 결합한다.
• 엔드 투 엔드 보장: 본 논문은 구성된 파이프라인이 피드백 하의 단일 편집 이웃 스트림에 대해 궤적 수준의 $(\varepsilon, \delta)$-DP를 달성함을 증명한다.

결과 및 구현

• 이론적 보장: 주요 정리(Theorem 3.1)에 따르면, 버퍼링 수준을 $U = \Theta(\frac{1}{\varepsilon_b} \log \frac{1}{\delta_b})$로 설정함으로써 시스템은 단일 편집 스트림에 대해 $(\varepsilon, \delta)$-DP를 달성한다. 백로그는 $O(\frac{1}{\varepsilon_b} \log t (\log t + \log \frac{1}{\delta_b}))$로 제한된다.
• SGD 구현: 이 레시피는 스트리밍 SGD(Stochastic Gradient Descent)로 구현된다. 집계기는 표준 트리 기반 또는 하삼각 행렬 접두사 합 메커니즘을 사용한다.
• 실험적 맥락: 본 논문은 정확도 대비 $(\varepsilon, \delta)$ 및 경험적 지연 분포를 보고하는 동반 연구 [CSZZ26]를 참조한다. DP-SGD 변형의 이론적 수렴은 이미 기존 문헌에서 광범하게 분석되었음을 언급한다.

의의 및 주장
본 논문은 참여 프라이버시(편집 인접성)와 적응형 지속적 공개(adaptive continual release) 사이의 근본적인 간극을 메운다고 주장한다. 저자들은 정렬 변화(alignment shifts)로 인해 단순한 지속적 공개 분석이 편집 이웃 스트림에는 적용될 수 없음을 보여준다. "차폐(shielding)" 인터페이스(무작위 버퍼링)와 적응형 안전성을 위한 구조적 인증을 도입함으로써, 저자들은 기존의 지속적 DP 프리미티브(예: 트리 접두사 합)를 상호작용적이고 참여에 민감한 환경에서 안전하게 재사용할 수 있게 한다.

본 연구는 **모듈성(modularity)과 감사 가능성(auditability)**을 강조한다: 파이프라인은 편집 인접성을 처리하는 문제(업스트림)와 적응형 피드백을 처리하는 문제(다운스트림)를 분리한다. 이를 통해 시스템 설계자는 프라이버시, 지연 시간, 유용성 사이의 명시적인 트레이드오프를 유지하면서 다양한 인증된 프리미티브를 플러그인 방식으로 사용할 수 있다. 저자들은 자신들의 인증 조건이 충분조건이지만 필요조건은 아니며, 버퍼링에 의해 발생하는 지연은 지속적 환경에서 편집 프라이버시를 달성하기 위한 내재적인 비용이라고 언급한다.