Locally Private Online Quantile Regression: Estimation and Inference

기술 요약: 국소적 프라이버시가 보장된 온라인 분위수 회귀

문제 정의
본 논문은 1회 보고(one-report), 사용자 수준의 $\varepsilon$-국소 차분 프라이버시($\varepsilon$-LDP) 프로토콜 하에서 온라인 분위수 회귀(QR)를 수행하는 과제를 다룹다. 표준 온라인 QR에서 서버는 추정식 기여분인 $g_\beta(X, Y) = X \{ \mathbb{1}(Y \le X^\top \beta) - \tau \}$를 사용하여 추정치를 업데이트한다. 이 벡터는 공변량 $X$를 잔차 비교(지시 함수)와 결합시킨다. 사용자 수준 LDP 하에서, 서버는 각 사용자로부터 프라이버시가 보호된 단일 보고만을 받는다. 핵심적인 어려움은, 표준적인 벡터 프라이버시 처리는 프라이버시 제약을 위반하거나 확률적 근사(stochastic approximation)에 필요한 조건부 평균 구조를 파괴하지 않고서는 불가능하다는 점이다. 즉, 서버가 $X$와 지시 함수를 직접 관찰할 수 없다면, 수렴에 필요한 불편(unbiased) 업데이트 벡터를 형성할 수 없다. 기존의 스칼라 프라이빗 분위수 또는 중앙 집중형/프라이빗 분산 QR 방식은, 단일 LDP 보고가 어떻게 불편한 공변량 의존적 업데이트로 변환되어야 하는지에 대한 이 "디코딩된 추정 방정식(decoded estimating-equation)" 문제를 해결하지 못한다.

방법론
저자들은 서버가 가공되지 않은 그래디언트를 받는 대신, 추정 방정식의 조건부 평균을 보존하는 디코딩된 입력을 받는 프레임워크를 제안한다.

1. 지지 구조를 고려한 기하학(Support-Aware Geometry): 정확한 QR 추정 방정식 기여분 $g_\beta(O)$는 특정 2면(two-face) 지지 기하 구조 $G_\tau$ 위에 존재한다. 절편(intercept) 좌표는 활성 면($\mathbb{1}(Y \le X^\top \beta) = 0$ 또는 $1$)을 식별하며, 기울기(slope) 좌표는 해당 면과 유계 공변량에 의해 결정되는 대칭 구간 내로 제한된다.
2. CQX($q, s$) 채널: 저자들은 $q$를 기울기 양자화의 그리드 크기, $s$를 선택된 좌표 블록의 크기로 하는 CQX($q, s$)라는 유한 알파벳 채널을 구축한다.
   • 로컬 처리: 각 사용자는 로컬에서 $g_\beta(X, Y)$를 계산한다. 사용자들은 선택된 기울기 좌표를 (공용 그리드를 사용하여) 유한 범주로 확률적으로 양자화한다. 만약 절편이 선택되면 이는 면(face) 라벨 역할을 하며, 그렇지 않으면 기울기들은 무조건적 그리드 상에서 양자화된다.
   • 무작위 응답(Randomized Response): 사용자는 결과물인 "선택된 블록 범주"에 무작위 응답을 적용하여 단일 LDP 보고를 생성한다.
   • 서버 측 디코딩: 서버는 왜곡을 교정하기 위해 아핀 무작위 응답 디코더(affine randomized-response decoder)를 적용하고, 호프비츠-톰슨(Horvitz-Thompson) 재구성을 사용하여 전체 벡터를 복원한다.
   • 핵심 속성: 디코딩된 입력 $\tilde{g}_\beta$는 조건부 불편성 $E[\tilde{g}_\beta(X, Y) \mid X, Y, \beta] = g_\beta(X, Y)$를 만족한다. 이를 통해 서버는 타겟 파라미터에 편향을 주지 않고 투영된 폴리악-루퍼트 평균화(projected Polyak-Ruppert averaging) 스킴($\beta_i = \Pi_B \{ \beta_{i-1} - \eta_i \tilde{g}_i(\beta_{i-1}) \}$)을 사용할 수 있다.
3. 추론(Inference): 본 논문은 QR 헤시안(Hessian)을 추정하는 것이 어려운(LDP 하에서) 상황을 고려하여, 헤시안을 필요로 하지 않는 추론 절차를 개발한다. 여기에는 다음이 포함된다:
   • 자기 정규화(Self-Normalization, SN): 단일 궤적 내에서의 폴리악 평균의 시간적 변동성을 사용한다.
   • 분할 정복(Divide-and-Conquer, DC): 스트림을 서로 소인 그룹들로 분할하여 그룹 평균을 계산하고 호텔링(Hotelling) 유형의 신뢰 집합을 형성한다.
   • HiGrad: 공용 트리 구조를 사용하여 알려진 공분산 템플릿을 가진 상관된 그룹 중심들을 생성한다.

주요 기여

1. 정식화: 본 논문은 순차적 1회 보고 사용자 수준 LDP 하에서의 스트리밍 선형 QR을 디코딩된 추정 방정식 문제로 정식화하여, 보고의 프라이버시 보장과 평균 보존 요구 사항을 분리하였다.
2. 메커니즘 구축: 공용 좌표 선택, 지지 구조를 고려한 확률적 양자화, 무작위 응답, 그리고 아핀 디코딩을 결합한 CQX($q, s$) 채널을 도입한다. 이 메커니즘은 QR 기여분의 2면 지지 기하 구조를 활용하여 디코딩된 서버 입력이 조건부로 불편함을 보장한다.
3. 이론적 보장: 고정된 유한 채널 설계에 대해 저자들은 다음을 증명한다:
   • 1회 기록 기여분에 대한 국소 프라이버시($\varepsilon$-L로컬 차분 프라이버시).
   • 조건부 디코더 불편성.
   • 투영된 폴리악-루퍼트 평균 추정량의 일치성 및 점근적 정규성.
   • 미리 지정된 스칼라 대조(scalar contrasts) 및 벡터 타원체에 대한 유효한 자기 정규화 추론의 타당성.
4. 실증적 검증: 시뮬레이션과 뉴욕시 택시 운행 데이터 예시를 통해, 프라이버시 예산($\varepsilon$)이 증가함에 따라 프라이빗 궤적이 비프라이빗 온라인 참조 모델에 접근함을 보여준다. 제안된 채널은 직접 라플라스(Laplace) 방출(지지를 무시함) 및 면-지수(face-exponential) 방출(평균을 이동시킴)보다 추정 오차 및 불확실성 정량화 측면에서 우수한 성능을 보인다.

결과

• 추정 정확도: 시뮬레이션에서 CQX($q, s$) 메커니즘은 기하학적 베이스라인(직접 라플라스 및 면-지수)에 비해 더 낮은 평균 유클리드 추정 오차를 달성한다. 면-지수 메커니즘은 평균장 불일치로 인한 투영 경계 포화 현상 때문에 높은 분위수($\tau=0.75$)에서 종종 실패한다.
• 높은 예산에서의 복구: $\varepsilon \to \infty$이고 그리드 해상도 $q$가 증가함에 따라, 프라이빗 추정량의 공분산은 비프라이빗 ASGD 오라클의 공분산으로 수렴한다.
• 추론 교정: 자기 정규화(SN), 분할 정복(DC), HiGrad 절차는 특히 스칼라 대조 및 조밀한 대조에 대해 명목 95% 수준에 가까운 커버리지 비율을 제공하는 신뢰 구간을 제공한다. 전체 벡터 타원체는 유한한 유효 정보 및 조건 설정에 더 민감하지만, 명시된 랭크 조건 하에서 유효하다.
• 실제 데이터 적용: NYC 택시 데이터셋에 적용했을 때, 프라이빗 추정치는 비프라이빗 참조 모델의 홀드아웃 교정(hit rates) 및 예측 체크 손실을 보존하며, $\varepsilon$이 증가함에 따라 성능이 향 Improves 된다.

의의 및 주장
본 논문은 평균을 보존하는 디코딩된 추정 방정식 입력을 기반으로 한 온라인 QR 추정 및 추론을 위한 최초의 1회 보고 LDP 프레임워크를 제시한다고 주장한다. 저자들은 표준적인 가법 노이즈(additive-noise) SGD 접근 방식이 QR의 특정한 지지 구조를 무시하기 때문에 QR에 부적합하다고 주장한다. 디코딩 단계를 통해 프라이버시 메커니즘을 추정 업데이트로부터 분리함으로써, 저자들은 1회 보고 국소 프라이버시가 온라인 QR과 호환 가능함을 보여준다. 본 연구의 의의는 신뢰할 수 있는 큐레이터나 사용자당 여러 개의 보고 없이도 스트리밍 및 프라이버시가 제한된 환경에서 유효한 통계적 추론(일치성, 정규성, 신뢰 구간)을 가능하게 한다는 점에 있다. 저자들은 본 이론이 의도적으로 고정된 차원을 다루며 유계 공변량에 의존한다는 점을 언급하였으며, 고차원 설정이나 적응형 채널 설계로의 확장은 향후 과제로 남겨두었다.