🤖 machine learning

Privacy Amplification in Differentially Private Zeroth-Order Optimization with Hidden States

본 논문은 비등방성 업데이트로 인한 표준 이동 발산 프레임워크의 한계를 극복하는 하이브리드 잡음 메커니즘과 새로운 결합 분석을 도입함으로써 0 차 최적화에 대한 최초의 수렴하는 미분 프라이버시 경계를 제시한다.

원저자: Eli Chien, Wei-Ning Chen, Pan Li

게시일 2026-05-04

📖 5 분 읽기🧠 심층 분석

원저자: Eli Chien, Wei-Ning Chen, Pan Li

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

이 글은 해당 논문을 쉬운 언어와 창의적인 비유를 사용하여 설명한 것입니다.

큰 그림: 거대한 퍼즐을 풀면서 흔적을 숨기기

상상해 보세요. 거대하고 복잡한 퍼즐 (엄청난 규모의 AI 모델) 을 풀어야 합니다. 이를 제로오더 최적화 (Zeroth-Order Optimization) 라는 특정 방법으로 해결하고 싶습니다.

문제:
보통 퍼즐을 풀 때는 조각들을 살펴보고 정확히 어느 방향으로 움직여야 할지 (기울기, gradients) 파악합니다. 하지만 '제로오더' 방식에서는 조각을 직접 볼 수 없습니다. 대신, 한 번 움직여 보고 그림이 어떻게 보이는지 확인한 뒤, 다른 방향으로 움직여 보고 그 모습을 확인하며, 이러한 추측들을 평균내어 가장 좋은 방향을 찾아야 합니다. 이는 지도를 보는 대신 어두운 미로에서 벽에 부딪히고 메아리를 들어 출구를 찾는 것과 같습니다.

개인정보 보호의 도전:
많은 사람의 데이터를 이용해 이 퍼즐을 풀고 싶지만, 그들의 개인정보를 보호해야 합니다 (차등 개인정보 보호, Differential Privacy). 이를 위해 보통 추측에 '노이즈 (잡음)'를 추가하여 특정 사람의 데이터가 사용되었는지 알 수 없게 만듭니다.

기존 방식 (Composition 의 함정):
이전 방법들은 퍼즐을 푸는 과정의 각 단계를 별도의 사건으로 취급했습니다. 그들은 "1 단계에 노이즈를 추가하고, 2 단계, 3 단계에 추가하면... 총 개인정보 보호 비용이 청구서처럼 누적된다"고 생각했습니다. 1,000 단계를 거치면 개인정보 보호 비용이 엄청나게 커져, 결국 '개인정보 예산'을 모두 소진했기 때문에 멈추게 됩니다. 이는 운전할 때마다 톨게이트 통행료를 내는 것과 같아, 결국 여행을 끝낼 수 없게 되는 상황입니다.

이 논문의 혁신:
이 논문은 말합니다. "잠깐만요! 중간 단계를 숨긴다면 매 단계마다 통행료를 낼 필요가 없습니다."

그들은 반복에 의한 개인정보 증폭 (Privacy Amplification by Iteration, PABI) 이라는 개념을 도입했습니다. 다음과 같이 생각할 수 있습니다.

기존 방식: 10 피트마다 모두에게 당신의 위치를 알립니다. 그들은 당신의 정확한 경로를 추적할 수 있습니다.
새로운 방식: 시작 위치와 도착 위치만 모두에게 알립니다. 그 사이의 경로는 비밀로 합니다. 경로가 숨겨져 있기 때문에, 처음에 추가한 '노이즈'가 실제로 도착할 때 당신의 신원을 보호하는 효과가 훨씬 더 커집니다. 개인정보 보호 비용은 더 이상 증가하지 않고 실제로 일정 수준에 머무릅니다.

그들이 극복한 구체적인 장애물

저자들은 이 '숨겨진 경로' 아이디어를 제로오더 방식에 적용하려 할 때 두 가지 주요 문제에 직면했습니다.

1. '이방성 (Anisotropic)' 노이즈 문제 (한 방향의 잡음)
표준 방법에서는 모든 방향으로 노이즈를 추가합니다 (TV 화면 전체에 잡음이 생기는 것처럼). 하지만 제로오더 방식에서는 추측한 특정 방향을 따라만 노이즈를 추가합니다 (오직 한 줄기에서만 잡음이 생기는 것처럼).

문제: '모든 방향' 노이즈에 대한 개인정보 보호를 증명하는 수학 도구는 '한 방향' 노이즈에는 작동하지 않습니다. 이는 둥근 구멍에 네모난 못을 박으려는 것과 같습니다. 표준 수학은 "노이즈가 균일하지 않으므로 이는 작동하지 않는다"고 말합니다.

2. '리프시츠 (Lipschitz)' 장벽 (미끄러운 경사)
개인정보 보호를 증명하기 위해 수학자들은 보통 시스템이 '안정적'임을 증명해야 합니다. 즉, 입력의 작은 변화가 출력의 작고 예측 가능한 변화로 이어져야 합니다.

문제: 제로오더 방식에서는 방향이 무작위이기 때문에 시스템이 항상 완벽하게 안정적이지는 않습니다. 대부분 안정적일 뿐입니다. 기존 수학 도구는 항상 안정적이어야 한다고 요구하므로 실패했습니다.

해결책: 하이브리드 엔진과 '유령' 프로세스

저자들은 이러한 문제들을 해결하기 위해 새로운 엔진을 구축했습니다.

1. 하이브리드 노이즈 메커니즘
'모든 방향의 노이즈'와 '한 방향의 노이즈' 중 하나를 선택하는 대신, 그들은 혼합 방식을 만들었습니다.

추측하는 특정 방향을 따라 노이즈를 추가합니다 (퍼즐 풀기 효율성을 유지하기 위해).
또한, 수학적 요구 사항을 충족시키기 위해 다른 모든 방향으로도 아주 작은 양의 노이즈를 추가합니다.
결과: 이는 양쪽의 장점을 모두 제공합니다. 훌륭한 퍼즐 풀기 성능과 개인정보 보호 증명을 가능하게 하는 수학 구조를 동시에 확보한 것입니다.

2. '유령' 프로세스 (결합 트릭)
기존 수학 도구를 사용할 수 없었기 때문에, 저자들은 새로운 트릭을 고안했습니다.

약간 다른 데이터로 퍼즐을 풀려고 하는 두 사람, 앨리스와 밥을 상상해 보세요.
저자들은 앨리스와 밥의 정중앙에 위치하는 프로세스의 '유령' 버전을 만들었습니다.
그들은 앨리스와 유령이 매우 가깝고, 밥과 유령도 매우 가깝다는 것을 증명했습니다.
이 '유령'을 다리로 사용하여, 기존 수학 도구 없이도 앨리스와 밥이 충분히 가까워 개인정보 보호가 된 것으로 간주될 수 있음을 증명했습니다.

놀라운 발견: 더 많은 방향 = 더 나은 개인정보 보호

이 논문에서 가장 흥미로운 발견 중 하나는 한 번에 추측하는 방향의 수인 $K$ 에 관한 것입니다.

기존 신념: 더 많은 방향 ( $K > 1$ ) 을 사용하면 퍼즐을 더 쉽게 풀 수 있지만 (더 나은 유용성), 개인정보 보호 비용이 더 많이 듭니다.
새로운 발견: 이 새로운 '숨겨진 경로' 분석 하에서는, 더 많은 방향을 사용할수록 퍼즐 풀기 품질을 유지하면서 개인정보 보호가 실제로 향상됩니다.
비유: 건초더미에서 바늘을 찾는 상황을 상상해 보세요. 한 곳만 본다면 무엇을 하고 있는지 숨기기 위해 많은 '덮개 (노이즈)'가 필요합니다. 하지만 한 번에 10 곳을 본다면, 그 '덮개'가 더 효과적으로 퍼져 관찰자가 당신이 정확히 어느 곳을 보고 있었는지 파악하기가 더 어려워집니다.

그들이 주장하는 바의 요약

제로오더 최적화가 수렴하는 개인정보 보호 비용을 가질 수 있음을 수학적으로 증명한 최초의 사례를 만들었습니다. 이는 개인정보 보호 비용이 영원히 증가하는 것이 아니라 일정 단계 이후 증가를 멈춘다는 것을 의미합니다.
최적화의 중간 단계를 숨김으로써 이전에 가능하다고 생각했던 것보다 훨씬 강력한 개인정보 보호 보장을 얻을 수 있음을 증명했습니다.
여러 무작위 방향 (직교 정규 방향) 을 한 번에 사용하는 것이 속도뿐만 아니라 개인정보 보호를 위한 비밀 병기임을 보여주었습니다.
이를 가능하게 하는 새로운 '하이브리드 노이즈' 레시피를 제시했습니다.

그들이 주장하지 않는 바:

이 방법이 즉시 모든 유형의 AI 모델이나 데이터 세트에 적용된다고 주장하지 않습니다. 그들의 수학은 손실 함수가 '매끄럽고 (smooth)' '볼록 (convex)'하다는 것과 같은 특정 가정에 의존합니다.
이것이 AI 의 모든 개인정보 보호 문제를 해결한다고 주장하지 않으며, 단지 이 특정 유형의 최적화 방법에 대해 더 나은 이론적 경계를 제공한다고 주장합니다.
아직 대중을 위한 준비된 소프트웨어 도구를 제공하지는 않습니다. 이는 향후 도구를 위한 길을 닦는 이론적 프레임워크입니다.

"Hidden States 를 가진 차분 프라이버시 영차수 최적화에서의 프라이버시 증폭"에 대한 상세한 기술 요약입니다.

1. 문제 정의

이 논문은 대규모 모델 (예: LLM) 을 차분 프라이버시 (DP) 제약 하에서 훈련하는 동시에 엄격한 메모리 제한을 관리하는 과제를 다룹니다.

배경: 표준 1 차수 DP 방법 (예: DP-SGD) 은 역전파 중 샘플별 그래디언트를 저장해야 하므로, 모델 크기에 따라 비효율적으로 증가하는 막대한 메모리 오버헤드를 초래합니다.
해결 추세: 영차수 최적화 (ZO) 방법은 명시적인 그래디언트 계산 없이 순전파 (손실 평가) 만으로 작동하므로 메모리 효율적인 대안으로 등장했습니다.
격차: 기존 ZO 방법 (예: DPZero) 은 경험적으로 잘 작동하지만, 이들의 이론적 프라이버시 분석은 표준 합성 정리에 의존합니다. 이로 인해 프라이버시 비용이 훈련 단계 수 ( $T$ ) 에 비례하여 선형적으로 증가하여 유용성과 프라이버시 간의 트레이드오프를 강요합니다.
핵심 과제: 1 차수 방법에서 수렴하는 (상수) 프라이버시 경계를 제공하는 반복에 의한 프라이버시 증폭 (PABI) 기법을 영차수 방법으로 확장하는 것입니다.
- 어려운 이유: 1 차수 PABI 는 그래디언트에 등방성 (방향 무관) 가우스 노이즈를 추가하여 "이동된 레니 발산 (shifted Rényi divergence)" 보조정리를 사용할 수 있게 합니다. 반면, 효율적인 ZO 방법은 무작위 업데이트 방향을 따라 비등방성 (방향 의존) 스칼라 노이즈를 추가합니다. 이 비등방성은 표준 이동 발산 프레임워크에 필요한 전역 리프시츠 (Lipschitz) 성질을 깨뜨려 기존 PABI 도구를 적용 불가능하게 만듭니다.

2. 방법론

저자들은 표준 분석의 한계를 우회하기 위해 하이브리드 노이즈 메커니즘과 커플링 분석을 결합한 새로운 프레임워크를 제안합니다.

A. 하이브리드 노이즈 메커니즘 (Noisy-ZOGD)

순수한 방향성 노이즈 (효율적이지만 분석이 어려움) 나 순수한 등방성 노이즈 (분석은 쉬우나 유용성 저하) 중 하나를 선택하는 대신, 저자들은 통합된 업데이트 규칙을 제안합니다:
$w_{t+1} = \Pi_{\mathcal{B}_R} \left[ w_t - \frac{\eta}{K} \sum_{k=1}^K \hat{g}_t(w_t; u_{t,k}) + \frac{\eta}{\sqrt{K}} \sum_{k=1}^K G^{(1)}_{t,k} u_{t,k} + \eta \sqrt{d} G^{(2)}_t \right]$

$K$ 차원 업데이트: 각 단계에서 $K$ 개의 무작위 방향을 사용하여 그래디언트 추정 분산을 줄입니다.
하이브리드 노이즈:
1. 방향성 노이즈 ( $G^{(1)}$ ): 업데이트 방향 $u_{t,k}$ 를 따라 추가되는 스칼라 가우스 노이즈입니다. 민감도가 존재하는 곳에 노이즈를 집중시켜 유용성을 보존합니다.
2. 등방성 노이즈 ( $G^{(2)}$ ): 모든 차원에 걸쳐 추가되는 작은 등방성 가우스 노이즈입니다. 이는 커플링 과정에서의 "이동 (shift)"을 처리하기 위한 이론적 분석에 필수적입니다.
직교 정규 방향: 업데이트 방향 $\{u_{t,k}\}$ 는 i.i.d. 무작위 벡터가 아닌 스테이펠 다양체 (Stiefel manifold) 에서 직교 정규 집합으로 샘플링되어 프라이버시 경계를 강화합니다.

B. 새로운 커플링 분석 (이동 발산 우회)

표준 PABI 증명은 이동된 레니 발산 (Shifted Rényi Divergence) 보조정리에 의존하며, 이는 전역 리프시츠 조건을 요구합니다. ZO 업데이트 매핑이 전역 리프시츠가 아니기 때문에 (높은 확률로만 점별 리프시츠 성질을 가짐), 저자들은 커플링된 보조 과정 $\tilde{W}_t$ 를 구성합니다:

구성: 인접한 두 훈련 과정 (데이터셋 $D$ 에서의 $W_t$ 와 데이터셋 $D'$ 에서의 $W'_t$ ) 의 "중간"에 위치하는 보조 궤적 $\tilde{W}_t$ 를 정의합니다.
분해: 프라이버시 분석은 두 부분으로 나뉩니다:
- 총변동 (TV) 경계: 커플링이 실패할 확률 (즉, $W_t$ 와 $\tilde{W}_t$ 가 발산하는 경우) 을 측정합니다. 이는 ZO 업데이트의 점별 리프시츠 성질 (높은 확률로 성립) 을 사용하여 경계화됩니다.
- 레니 발산 경계: 보조 과정 $\tilde{W}_t$ 와 인접 과정 $W'_t$ 사이의 발산을 측정합니다. $\tilde{W}_t$ 가 노이즈 구조와 정렬되도록 구성되었으므로, 이 부분은 표준 이동 가우스 메커니즘을 사용하여 분석할 수 있습니다.
결과: 이 접근법은 전역 리프시츠 상수가 필요하지 않으므로, 비등방성 노이즈가 있더라도 수렴하는 프라이버시 경계를 가능하게 합니다.

3. 주요 기여

최초의 수렴하는 영차수 PABI: 이 논문은 숨겨진 상태 (hidden states) 를 가진 영차수 최적화가 $T$ 에 비례하여 증가하는 것이 아니라, 고정된 단계 수 이후 프라이버시 비용이 포화되는 수렴하는 프라이버시 경계를 달성한다는 최초의 이론적 증명을 제공합니다.
하이브리드 노이즈 메커니즘: 유용성 (방향성 노이즈를 통해) 과 분석적 처리 가능성 (소량의 등방성 성분을 통해) 을 균형 있게 조절하는 노이즈 주입 방식을 도입합니다.
업데이트 차원 ( $K$ ) 의 역할:
- 숨겨진 상태 분석 하에서는 업데이트 방향 수 $K$ 를 증가시키는 것이 프라이버시 손실을 감소시킨다는 것을 밝힙니다 (표준 합성 분석에서는 $K$ 가 비용을 증가시키는 것과 반대).
- i.i.d. 무작위 방향에 비해 직교 정규 업데이트 방향을 사용하면 프라이버시 경계가 크게 개선됨을 입증합니다.
새로운 커플링 기법: 전역 리프시츠 장벽을 우회하는 특정 보조 과정 구성을 개발했으며, 이 기법은 다른 비매끄럽거나 비리프시츠 최적화 설정에도 적용 가능할 수 있습니다.

4. 주요 결과

프라이버시 경계: 매끄럽고 강한 볼록 손실에 대해 제안된 Noisy-ZOGD 알고리즘은 다음을 만족하는 $(\epsilon, \delta)$ $(ϵ, δ)$ -DP 를 충족합니다:
$\epsilon = O\left( \sqrt{\frac{\Delta^2 \log(1/\delta)}{n^2 \sigma^2} \min\left(T, \frac{R n \sqrt{d}}{K \Delta}\right)} \right)$
- 경계는 $T \approx \frac{R n \sqrt{d}}{K \Delta}$ 에서 포화되므로, 추가 반복은 프라이버시 비용을 증가시키지 않습니다.
- 경계는 $K$ 에 반비례하므로, 더 많은 방향을 사용할수록 프라이버시가 개선됨을 보여줍니다.
비교:
- 표준 합성 대비: 표준 분석은 $\epsilon \propto \sqrt{T}$ 를 산출하여 무한히 증가합니다. 제안된 방법은 수렴합니다.
- 출력 교란 대비: 출력 교란 (마지막 단계에서만 노이즈 추가) 은 $T$ 와 무관하지만, 일반적인 실용적 $T$ 에서는 더 약합니다. 제안된 방법은 중간 $T$ 에 대해 더 엄격한 경계를 제공합니다.
유용성: 하이브리드 노이즈 메커니즘은 총 노이즈 분산을 보존하므로 순수한 방향성 노이즈 (DPZero) 와 동일한 유용성 보장을 유지합니다.

5. 의의

확장성: 이 연구는 현재 LLM 파인튜닝의 주요 병목 현상인 제한된 메모리와 DP 하에서 막대한 모델 (수십억 개의 파라미터) 을 훈련하는 이론적 근거를 제공합니다.
알고리즘 설계: 여러 영차수 방향 ( $K > 1$ ) 을 사용하는 것이 순수한 유용성 트레이드오프라는 신념을 뒤집습니다. 이 논문은 이것이 프라이버시 이점이기도 하다고 증명하여, DP-ZO 알고리즘에서 고차원 업데이트 사용을 장려합니다.
이론적 발전: PABI 에서의 "비등방성 노이즈" 문제를 해결함으로써, 1 차수와 영차수 프라이버시 이론 간의 중요한 격차를 메우고, 프라이버시 제약 하의 복잡하고 비리프시츠 최적화 동역학을 분석하기 위한 새로운 도구 (보조 과정과 함께하는 커플링) 를 제공합니다.
실무적 영향: 실무자에게 구체적인 지침을 제공합니다: 직교 정규 방향을 사용하고, 하이브리드 노이즈 매개변수 $\beta_t$ 를 조정하며, 메모리 비용 증가 없이 더 나은 프라이버시 - 유용성 트레이드오프를 달성하기 위해 더 큰 $K$ 를 활용합니다.