Descend or Rewind? Stochastic Gradient Descent Unlearning

이 논문은 확률적 경사 하강법을 기반으로 한 'Descent-to-Delete'와 'Rewind-to-Delete' 알고리즘에 대해 강볼록, 볼록, 비볼록 손실 함수 모두에서 $(\varepsilon, \delta)$ 인증된 기계 망각 (unlearning) 보증을 이론적으로 증명하고, 두 알고리즘의 성능을 비교 분석하여 각각의 적합한 적용 영역을 제시합니다.

핵심

이 논문은 **"기계가 잊는 법"**에 대한 흥미로운 연구입니다.

우리가 사진을 찍거나 글을 쓸 때, 나중에 "이건 지워줘"라고 요청하면 어떻게 될까요? 보통은 그 데이터를 다시 처음부터 다시 학습시켜야 합니다. 하지만 데이터가 수백만 개라면, 처음부터 다시 학습하는 데는 엄청난 시간과 돈이 듭니다. 마치 거대한 도서관에서 한 권의 책을 빼고 싶다고 해서, 도서관 전체를 해체하고 다시 지어야 하는 것과 비슷하죠.

이 논문은 **"처음부터 다시 짓지 않고, 어떻게 하면 효율적으로 그 책만 지울 수 있을까?"**에 대한 두 가지 방법을 비교하고, 그중 어떤 방법이 더 좋은지 수학적으로 증명했습니다.

두 가지 방법을 **'내리막길 걷기 (Descent)'**와 **'되감기 (Rewind)'**라고 부르겠습니다.

---

1. 두 가지 방법의 비유

📉 방법 A: "내리막길 걷기" (Descent-to-Delete, D2D)

이 방법은 **"이미 도착한 곳에서부터 다시 시작"**하는 방식입니다.

• 상황: 기차가 목적지 (최종 학습 모델) 에 도착했습니다.
• 작동: 기차가 목적지에 도착한 후, "아, 저기 한 승객 (삭제할 데이터) 을 내리게 하려면 어떡하지?"라고 생각하며, 지금 있는 위치에서부터 다시 조금씩 뒤로 밀어내듯 (내리막길로) 이동합니다.
• 문제점: 만약 기차가 이미 목적지 (최적의 상태) 에 아주 가깝게 도착해 있었다면, 뒤로 밀어내는 과정에서 기차가 다시 다른 곳으로 치우치거나, 아예 제자리에서 빙빙 돌게 될 수 있습니다. 특히 복잡한 지형 (비볼록 함수, 즉 현대 AI 가 다루는 복잡한 문제) 에서는 길 잃을 확률이 높습니다.

⏪ 방법 B: "되감기" (Rewind-to-Delete, R2D)

이 방법은 **"과거로 돌아가서 다시 시작"**하는 방식입니다.

• 상황: 기차가 목적지에 도착하기 직전, 예를 들어 10 분 전에 멈췄던 지점 (체크포인트) 을 기억해 둡니다.
• 작동: "저 승객을 지우려면?"이라고 생각하자마자, 기차를 10 분 전 위치로 되감아 (Rewind) 가져옵니다. 그리고 그 시점부터 새로운 승객들 (나머지 데이터) 만 태우고 다시 목적지로 향합니다.
• 장점: 이미 최적의 길에 가까웠던 시점으로 돌아가서 다시 출발하므로, 길을 잃을 확률이 훨씬 적고 훨씬 빠릅니다.

---

2. 이 논문이 발견한 핵심 사실

저자들은 이 두 방법을 수학적으로 분석하고 실험해 보았습니다. 결과는 다음과 같습니다.

• 단순하고 규칙적인 문제 (볼록 함수):
  • 두 방법 모두 잘 작동하지만, **'내리막길 걷기 (D2D)'**가 약간 더 정밀하게 작동할 수 있습니다. (비유하자면, 평탄한 도로에서는 뒤로 밀어내는 게 나을 수도 있음)
• 복잡하고 험난한 문제 (비볼록 함수, 현대 AI 의 대부분):
  • **'되감기 (R2D)'**가 압도적으로 좋습니다.
  • **'내리막길 걷기 (D2D)'**는 복잡한 지형에서 길을 잃거나, 아예 멈춰서 버리는 (국소 최적점에 갇히는) 경우가 많습니다. 마치 미로에서 출구를 찾으려다 벽에 부딪혀서 더 이상 움직이지 못하는 상황과 같습니다.
  • 반면, **'되감기 (R2D)'**는 과거의 안전한 지점으로 돌아가서 다시 길을 찾으므로, 항상 재학습 (처음부터 다시 시작) 하는 것보다 빠르고 안전합니다.

3. 왜 이것이 중요한가요? (실생활 예시)

• GDPR(유럽 개인정보 보호법) 과 같은 법: 사람들은 "내 데이터를 지워달라"고 요청할 권리가 있습니다.
• 현재의 문제: 이 요청을 받으면 AI 는 보통 "다시 처음부터 학습해"라고 대답합니다. 이는 엄청난 에너지와 시간을 낭비합니다.
• 이 논문의 해결책: "되감기 (R2D)" 방식을 사용하면, AI 는 과거의 기록을 찾아서 그 부분만 지우고 다시 빠르게 학습할 수 있습니다. 마치 비디오 테이프를 되감아서 특정 장면을 잘라내고 다시 녹화하는 것처럼, 전체를 다시 녹화할 필요가 없습니다.

4. 결론: 무엇을 선택해야 할까?

이 논문은 **"복잡한 현대 AI(딥러닝) 를 다룰 때는 무조건 '되감기 (Rewind)' 방식을 써야 한다"**고 강력히 주장합니다.

• 내리막길 걷기 (D2D): 이론적으로는 좋지만, 실제로 복잡한 AI 에 적용하면 성능이 떨어지거나 멈춰버릴 위험이 큽니다.
• 되감기 (R2D): 조금 더 많은 계산이 필요할 수 있지만, 안정적이고 빠르며, AI 가 잊어버린 데이터를 진짜로 잊게 만들어줍니다.

한 줄 요약:

"기계가 잊으라고 할 때, 지금 위치에서 뒤로 밀어내려 하지 말고, 과거의 안전한 지점으로 되감아서 다시 출발하는 것이 가장 빠르고 안전한 방법입니다."

기술 요약

1. 문제 제기 (Problem)

• 배경: GDPR, CCPA 등 데이터 보호 규제로 인해 사용자는 자신의 데이터가 모델에서 삭제될 '잊힐 권리 (Right to be Forgotten)'를 요구합니다.
• 현황: 데이터를 삭제하기 위해 처음부터 모델을 다시 학습 (Retraining) 하는 것은 계산 비용이 너무 큽니다. 따라서 기존 모델을 수정하여 특정 데이터의 영향을 제거하는 '망각 알고리즘'이 필요합니다.
• 한계:
  • 기존 인증된 망각 (Certified Unlearning) 알고리즘들은 대부분 2 차 미분 정보 (Hessian) 를 필요로 하거나 전체 경사 (Full-batch Gradient) 를 계산해야 하여 대규모 모델에 적용하기 어렵습니다.
  • 현재 널리 쓰이는 '파인튜닝 (Finetuning)' 방식은 SGD 를 사용하지만, 비볼록 (Nonconvex) 함수에 대한 이론적 보장 (Certified Guarantee) 이 부족합니다.
  • 기존 SGD 기반 망각 연구들은 볼록 함수에만 적용되거나, 약한 정의의 망각을 증명하는 데 그쳤습니다.

2. 방법론 (Methodology)

저자들은 두 가지 기존 알고리즘인 **D2D (Descent-to-Delete)**와 **R2D (Rewind-to-Delete)**를 SGD 환경으로 확장하고, 이를 통해 $(\epsilon, \delta)$ 인증 망각을 증명합니다.

• 알고리즘 정의:

  • SGD-D2D: 학습이 끝난 최종 모델 파라미터 ($\theta_T$) 에서 시작하여, 유지된 데이터 ($D'$) 로만 SGD 를 수행하며 '내려가는 (Descend)' 방식입니다.
  • SGD-R2D: 학습 과정 중 $T-K$ 시점의 체크포인트로 '되감기 (Rewind)'한 후, 유지된 데이터 ($D'$) 로 $K$ 단계의 SGD 를 수행하는 방식입니다.
  • 두 방법 모두 학습 종료 후 및 망각 수행 후 가우시안 노이즈를 추가하여 $(\epsilon, \delta)$-구분 불가능성 (Indistinguishability) 을 달성합니다.

• 핵심 분석 기법:

  1. 결합 (Coupling) 기법: 학습 경로와 재학습 (Retraining) 경로의 무작위성 (미니배치 샘플링) 을 최적화하여 결합합니다. 이를 통해 두 경로의 거리를 기대값 (Expectation) 에서 최소화하고 민감도 (Sensitivity) 상한을 유도합니다.
  2. 경사 시스템의 수축/확산 성질 분석:
     • 강볼록 (Strongly Convex): 경사 시스템이 수축 (Contracting) 성질을 가짐.
     • 볼록 (Convex): 준수축 (Semi-contracting) 성질.
     • 비볼록 (Nonconvex): 확산 (Expansive) 성질.
  3. 편향된 SGD 해석: 망각 과정을 유지된 데이터에 대한 '편향된 (Biased)' SGD 로 해석합니다.
     • R2D: 비볼록 함수에서도 되감기를 통해 초기화된 시점의 편향을 제거하여 재학습 경로와 망각 경로의 거리를 줄입니다.
     • D2D: 강볼록 함수의 경우, 편향을 '접어넣어 (Folded)' 기존 SGD 수렴 분석에 포함시킴으로써 더tight한 2 차 모멘트 바운드를 유도합니다.

3. 주요 기여 (Key Contributions)

1. SGD-R2D 및 SGD-D2D의 $(\epsilon, \delta)$ 인증 망각 증명:
   • SGD-R2D: 투영 (Projection) 유무와 상관없이 강볼록, 볼록, 비볼록 손실 함수 모두에 대해 인증된 망각을 증명했습니다. 특히 비볼록 함수에 대한 SGD 기반 망각의 이론적 보장을 최초로 제공했습니다.
   • SGD-D2D: 강볼록 함수에 대해 기존 연구의 제한적인 가정 (Lipschitz 연속성 등) 을 우회하는 새로운 증명 기법을 통해 인증된 망각을 증명했습니다.
2. 새로운 결합 (Coupling) 및 민감도 분석: 결정론적 민감도 바운드가 필요한 기존 가우시안 메커니즘과 달리, 결합된 확률 분포에 대한 기대값 기반 민감도 바운드를 유도하여 SGD 알고리즘 분석의 유연성을 높였습니다.
3. D2D 와 R2D 의 비교 분석:
   • 강볼록 함수: D2D 가 더tight한 확률적 바운드를 제공하지만, 초기점이 최적점에 가까울 경우 재학습보다 효율적이지 않을 수 있습니다.
   • 볼록/비볼록 함수: R2D 가 항상 재학습보다 계산 효율이 높으며, 비볼록 함수에서는 D2D 가 국소 최적점 (Stationary Point) 에 갇히는 문제를 우회하여 더 안정적인 망각을 수행합니다.

4. 실험 결과 (Results)

• 데이터셋: eICU (의료 데이터, MLP 사용) 와 Lacuna-100 (얼굴 데이터, ResNet-18 사용) 에서 실험 수행.
• 성능 지표:
  • 파라미터 공간 거리 (L2 Distance): R2D 는 망각 후 모델이 재학습 모델에 더 가깝게 이동하는 경향을 보였습니다. 반면 D2D 는 비볼록 환경에서 오히려 원래 모델이나 재학습 모델 모두에서 멀어지거나 성능이 개선되는 현상 (망각 실패 신호) 을 보였습니다.
  • 멤버십 추론 공격 (MIA): R2D 는 D2D 보다 공격 성공률을 더 효과적으로 낮추어 (AUC 감소) 망각 효과를 입증했습니다.
  • 계산 효율성: R2D 는 재학습보다 적은 계산량 ($T-K$) 으로 동일한 수준의 망각 보장을 제공하며, 특히 강볼록 함수에서는 $K$가 상수에 수렴하여 무한한 계산 이점을 가질 수 있음을 이론적으로 보였습니다.

5. 의의 및 결론 (Significance)

• 실용성: 이 연구는 대규모 딥러닝 모델 (비볼록 함수) 에 적용 가능한 블랙박스 (Black-box) 형태의 망각 알고리즘을 제공합니다. 학습 중 특수한 절차 없이, 학습 후 노이즈만 주입하면 되므로 기존 모델에 쉽게 적용 가능합니다.
• 이론적 기여: SGD 기반의 비볼록 최적화 환경에서도 '되감기 (Rewinding)' 전략이 '내려가기 (Descending)' 전략보다 이론적으로 더 강력하고 실용적임을 증명했습니다.
• 규제 준수: GDPR 등 데이터 삭제 요구에 대응할 수 있는 계산 효율적이고 이론적으로 검증된 솔루션을 제시하여, 프라이버시 보호와 모델 성능 유지 사이의 균형을 찾는 데 기여합니다.

요약하자면, 이 논문은 SGD-R2D가 비볼록 딥러닝 모델에서 가장 신뢰할 수 있고 효율적인 망각 방법임을 이론적으로 증명하고 실험적으로 입증한 중요한 연구입니다.