Proximal Projection for Doubly Sparse Regularized Models

기술 요약: 이중 희소 정규화 모델을 위한 근사 투영

문제 제기
예측 변수의 수 ($p$) 가 표본 크기 ($n$) 를 초과하는 고차원 회귀 설정에서는 특이성과 다중공선성으로 인해 표준 최소제곱법 (OLS) 이 실패합니다. LASSO($l_1$ 페널티) 와 릿지 ($l_2$ 페널티) 와 같은 정규화 방법은 희소성과 안정성을 다루지만, 종종 예측 변수 간의 근본적인 구조적 관계를 무시합니다. 예측 변수를 가우시안 그래픽 모델로 표현할 수 있는 경우, 이러한 구조를 활용하면 추정이 개선됩니다.

기존 접근법인 그래픽 구조를 반영한 희소 회귀 (SRIG) 와 그 이중 희소 확장 버전 (DSRIG) 은 계수 벡터 $\beta$를 노드 기여도에 해당하는 잠재 변수로 분해하고 이러한 잠재 변수에 정규화를 적용합니다. 그러나 "이중 희소성"(그룹 간 및 그룹 내 희소성) 을 달성하는 DSRIG 모델은 중첩된 그룹을 처리하기 위해 예측 변수 중복에 의존합니다. 이 접근법은 최적화 문제의 차원을 크게 증가시켜 고차원 데이터나 밀집된 그래프의 경우 계산적으로 불가능해집니다. 또한 DSRIG 는 그룹 간 및 그룹 내 희소성을 균형 있게 조정하기 위해 두 개의 매개변수 ($\lambda$ 및 $\xi$) 를 조정해야 하므로 최적 해를 찾는 과정이 복잡해집니다.

방법론
저자들은 그래픽 구조를 반영한 희소 중첩 그룹 LASSO (SGLIG) 모델을 제안합니다. 이 모델은 계산 복잡성과 조정 매개변수의 수를 줄이면서 이중 희소성을 유지하도록 DSRIG 프레임워크를 재매개변수화합니다.

1. 모델 공식화:
   SGLIG 모델은 다음 목적 함수를 최소화합니다:
   $$\min_{\beta, V^{(1)}, \dots, V^{(p)}} \frac{1}{2n}\|Y - X\beta\|_2^2 + \lambda^* \sum_{i=1}^p \left( \alpha \tau_i \|V^{(i)}\|_2 + (1-\alpha) \frac{1}{\sqrt{d_i}} \|V^{(i)}\|_1 \right)$$
   여기서 $\beta = \sum V^{(i)}$, $V^{(i)}$는 예측 변수 $i$의 기여도를 나타내고, $d_i$는 이웃의 차수이며, $\alpha \in [0, 1]$은 $l_2$(그룹) 와 $l_1$(그룹 내) 페널티 간의 균형을 조절합니다. DSRIG 와 달리 SGLIG 는 단일 조정 매개변수 $\alpha$를 사용하며 ($\lambda^*$는 $\lambda_{max}$에 기반한 상수로 고정됨), 최적화 그리드 탐색을 단순화합니다.

2. 이중 투영 근사 알고리즘:
   SGLIG 목적 함수를 최적화하기 위해 저자들은 FISTA(고속 반복적 축소 - 임계값 알고리즘) 기반의 이중 투영 근사 알고리즘을 개발했습니다.

   • 활성 그룹 전략: 알고리즘은 현재 기울기 단계에 기반하여 활성 그룹 집합 $\hat{G}_m$을 식별합니다.
   • 교집합에 대한 투영: 예측 변수를 중복하는 대신, 알고리즘은 $l_2$ 및 $l_\infty$ 노름 공으로 정의된 볼록 집합의 교집합에 투영하여 근사 연산자를 계산합니다.
   • 2 단계 투영: 투영은 순차적으로 계산됩니다. 먼저 그룹 내 희소성 ($l_1$/$l_\infty$) 을 위한 소프트 쉐이킹을 적용한 후, 그룹 간 희소성 ($l_2$) 을 위한 그룹 소프트 쉐이킹을 적용합니다. 이는 저자들이 활성 집합 전략에 대해 더 효율적이라고 주장하는 병렬 디크스트라와 유사한 알고리즘 대신, 일련의 합성 (POCS) 을 사용하여 구현됩니다.

3. 이론적 특성:
   이 논문은 최적 분해, 제한된 강한 볼록성 (RSC), 그리고 가중치 $\tau_i$와 노드 차수에 대한 특정 상한에 대한 가정 하에 SGLIG 추정량의 유한 표본 오차 한계를 유도합니다. 또한, 고정된 $p$ 상태에서 $n \to \infty$일 때 추정량의 점근적 정규성을 증명하여 추가된 $l_1$ 페널티에도 불구하고 SRIG 모델과 일관됨을 보여줍니다.

주요 기여

• 알고리즘적 혁신: 예측 변수 중복을 피하는 새로운 이중 투영 근사 알고리즘 개발. 이 방법은 볼록 집합의 교집합에 대한 투영을 반복적으로 계산하여 고차원 및 밀집된 그래프 구조에 대한 계산 자원을 절약합니다.
• 모델 효율성: SGLIG 모델은 단일 조정 매개변수($\alpha$) 로 이중 희소성을 달성하여, 두 개의 매개변수를 사용하는 DSRIG 에 비해 하이퍼파라미터 선택의 계산 부담을 줄입니다.
• 이론적 보장: SGLIG 추정량에 대한 유한 표본 오차 한계 유도 및 점근적 정규성 증명으로 표준 가정 하에서 통계적 타당성을 확립합니다.
• 실증적 검증: 다섯 가지 서로 다른 그래프 구조 (이중 클래스, 이분, 무작위, 블록, 밴드) 와 두 가지 실제 데이터셋 (혈액 - 뇌 장벽 및 알츠하이머병 신경영상 이니셔티브) 에 대한 포괄적인 평가.

결과

• 시뮬레이션 연구:

  • 정확도: DSRIG 모델은 일반적으로 가장 낮은 평균 제곱 오차 (MSE) 와 $l_2$ 거리를 달성했습니다. 그러나 SGLIG 모델은 경쟁력 있는 성능을 보였으며, 종종 DSRIG 의 정확도와 거의 일치하면서 단일 희소성 모델인 SRIG 보다 훨씬 우수한 성능을 발휘했습니다.
  • 효율성: SGLIG 모델은 DSRIG 에 비해 계산 시간이 크게 단축되었습니다. 고차원 시나리오 (예: 800 개의 예측 변수) 에서 DSRIG 는 2,900 초 이상이 소요된 반면, SGLIG 는 약 60 초, SRIG 는 40 초가 소요되었습니다. SGLIG 는 SRIG 의 속도와 DSRIG 의 정확도 사이의 간극을 효과적으로 메꿉니다.
  • 그래프 민감도: SGLIG 는 "밴드"그래프를 제외하고 다양한 그래프 토폴로지에서 견고하게 작동했습니다. 밴드 그래프의 경우 선형 연결 구조로 인해 그룹 내 희소성이 덜 유익했습니다.

• 실제 데이터:

  • 혈액 - 뇌 장벽 데이터셋에서 SGLIG 는 세 모델 중 가장 낮은 MSE 를 달성하면서도 SRIG 와 유사한 계산 시간을 유지하고 DSRIG 보다 현저히 낮은 시간을 보였습니다.
  • 변수 선택 분석 결과, SGLIG 와 DSRIG(모두 이중 희소성) 는 입자 전하와 관련된 변수를 선택한 반면, SRIG 는 표면적 측정에 더 집중하여 이중 희소성이 다른 구조적 뉘앙스를 포착함을 시사했습니다.

의의 및 주장
이 논문은 SGLIG 모델이 그래픽 구조를 가진 고차원 회귀를 위한 실용적인 절충안을 제공한다고 주장합니다. 예측 변수 중복을 새로운 근사 투영 기법으로 대체함으로써 저자들은 이중 희소성의 이점을 희생하지 않으면서 계산 자원을 절약한다고 주장합니다. 결과는 SGLIG 가 다른 단일 또는 이중 희소성 그래픽 회귀 모델에 비해 안정적인 성능을 보이며, DSRIG 가 계산적으로 불가능한 시나리오에서 실현 가능한 대안이 될 수 있음을 시사합니다. 저자들은 그들의 구현이 밀집된 예측 변수 그래프를 가진 고차원 데이터에 특히 유리하다고 강조합니다.