New Insight of Variance reduce in Zero-Order Hard-Thresholding: Mitigating Gradient Error and Expansivity Contradictions

기술적 요약: 영차수 하드-역치화에서의 분산 감소에 대한 새로운 통찰

문제 정의
본 논문은 고차원 기계 학습 작업에서 희소 학습을 달성하는 데 필수적인 $\ell_0$-제약 최적화 문제를 해결하는 과제를 다룹니다. 구체적인 문제는 $\|\theta\|_0 \leq k$를 조건으로 정규화된 경험적 위험 $F(\theta) = \frac{1}{n}\sum_{i=1}^n f_i(\theta)$를 최소화하는 것으로 공식화됩니다. 하드-역치화 반복 알고리즘은 $\ell_0$ 제약에 효과적이지만, 전통적으로 참된 기울기에 대한 접근이 필요했습니다. 밴딧 문제, 블랙박스 적대적 공격, 강화 학습과 같은 많은 현대적 시나리오에서는 기울기에 접근할 수 없으므로, 함수 평가를 기반으로 하는 영차수 (ZO) 최적화 방법을 사용해야 합니다.

이 설정에 대한 기존 최첨단 알고리즘인 확률적 영차수 하드-역치화 (SZOHT) 는 치명적인 한계를 겪고 있습니다. 저자들은 영차수 기울기 추정기의 편차 (오차) 와 하드-역치화 연산자의 확장성 (비비약성) 사이에 내재된 충돌을 확인했습니다. SZOHT 는 수렴을 보장하기 위해 기울기 추정에 사용되는 무작위 방향의 수 ($q$) 와 희소성 수준 ($k$) 에 대해 엄격한 조건을 부과합니다. 이러한 조건은 실제 응용 분야에 대해 종종 지나치게 제한적이어서 알고리즘의 유용성을 제한합니다.

방법론
본 논문은 분산 감소에 초점을 맞춤으로써 영차수 기울기와 하드-역치화 사이의 충돌을 해결하는 새로운 관점을 제시합니다. 저자들은 이 충돌이 본질적으로 기울기 추정 오차 자체가 아니라, 하드-역치화 연산자와 기울기 추정의 분산 사이에 존재한다고 주장합니다.

이를 해결하기 위해 논문은 pM-SZHT(p-기억 확률적 영차수 하드-역치화) 라는 일반화된 프레임워크를 도입합니다. 이 프레임워크는 SAGA 및 SVRG 와 같은 1 차 분산 감소 기법과 유사하게 역사적 기울기를 활용하여 분산을 감소시키지만, 영차수 설정에 맞게 조정되었습니다. 핵심 구성 요소는 다음과 같습니다:

1. 일반화된 반복식: 알고리즘은 $\theta^{(r+1)} = H_k(\theta^{(r)} - \eta \hat{g}^{(r)}(\theta^{(r)}))$라는 업데이트 규칙을 따르며, 여기서 $\hat{g}^{(r)}$은 분산 감소를 통합한 일반화된 기울기 추정치입니다.
2. p-기억: 이 프레임워크는 각 반복에서 기울기 추정치의 무작위 부분집합을 업데이트하는 메모리 메커니즘을 사용하여, 알고리즘이 역사적 정보를 활용하여 영차수 추정을 안정화할 수 있게 합니다.
3. 구체적 알고리즘: 이 프레임워크 내에서 저자들은 VR-SZHT(SVRG 의 영차수 적응형) 와 SARAH-SZHT(SARAH 의 영차수 적응형) 를 포함한 구체적인 알고리즘들을 구현합니다.

이론적 분석
본 논문은 제한적 강볼록성 (RSC) 과 제한적 강부드러움 (RSS) 과 같은 표준 희소 학습 가정 하에 포괄적인 수렴 분석을 제공합니다.

• 충돌 완화: 분석은 분산 감소를 사용함으로써 알고리즘이 수렴에 필요한 무작위 방향의 수 ($q$) 에 대한 엄격한 의존성을 제거할 수 있음을 보여줍니다. SZOHT 에서는 $q$가 $k$에 대한 특정 경계를 만족할 만큼 충분히 커야 하지만, 제안된 방법들에서는 다른 매개변수 (예: 학습률) 가 올바르게 선택되는 한 $q > 0$인 모든 경우에 대해 수렴이 보장됩니다.
• 수렴 속도: 이론적 결과는 제안된 알고리즘이 SZOHT 보다 향상된 수렴 속도를 달성함을 보여줍니다. 구체적으로, VR-SZHT 의 쿼리 복잡도는 $O([n + \frac{\kappa^3}{\kappa^2+1}] \log(1/\epsilon))$로 유도되며, 이는 특히 조건수 $\kappa$가 클 때 SZOHT 의 $O((k + d/s^2)\kappa^2 \log(1/\epsilon))$ 복잡도보다 상당한 개선을 나타냅니다.
• $q$에 대한 독립성: 주요 이론적 발견은 분산 감소가 수렴 조건을 무작위 방향의 수와 분리시켜 더 유연한 매개변수 선택을 가능하게 한다는 점입니다.

실험 결과
저자들은 두 가지 주요 작업에서 그들의 방법을 검증했습니다:

1. 릿지 회귀: 합성 데이터를 사용하여 제안된 분산 감소 알고리즘 (VR-SZHT, SAGA-SZHT, SARAH-SZHT) 은 일관되게 원형 SZOHT 및 전체 기울기 영차수 하드-역치화 (FGZOHT) 보다 우수한 성능을 발휘했습니다. 이들은 더 적은 하드-역치화 연산 (NHT) 으로 더 낮은 함수 값을 달성하고 경쟁력 있는 영차수 오라클 호출 (IZO) 을 보였습니다.
2. 블랙박스 적대적 공격: 이 방법들은 블랙박스 분류기에 대한 CIFAR-10 데이터셋에서 희소 보편적 적대적 섭동을 생성하는 데 적용되었습니다. 결과는 SZOHT 에 비해 분산 감소 방법, 특히 SARAH-SZHT 와 SAGA-SZHT 가 더 높은 공격 성공률과 더 낮은 손실 값을 달성함을 나타냅니다. 예를 들어, SARAH-SZHT 는 "비행기" 클래스의 10 장 이미지 중 7 장을 성공적으로 공격하여 SZOHT 를 능가했습니다.

의의 및 주장
본 논문은 분산 감소를 단순히 속도 향상 메커니즘이 아닌, 영차수 추정기와 하드-역치화 연산자 사이의 고유한 모순을 완화하는 필수 도구로 규정함으로써 분산 감소에 대한 "새로운 통찰"을 제공한다고 주장합니다. 이 연구의 의의는 다음과 같습니다:

• 제약 완화: SZOHT 에서 발견된 무작위 방향의 수 ($q$) 에 대한 금지적인 제한을 제거하여, 영차수 하드-역치화를 더 넓은 범위의 실제 문제에 적용 가능하게 합니다.
• 일반 프레임워크: 다양한 분산 감소 영차수 방법을 포괄하는 일반 분석 프레임워크 (pM-SZHT) 를 정립하여 통합된 이론적 이해를 제공합니다.
• 실용적 유용성: 적대적 공격 및 회귀에 대한 실험 결과는 이러한 방법들이 희소성 제약을 유지하면서 최첨단 영차수 알고리즘과 비교하여 경쟁력 있거나 우수한 성능을 달성할 수 있음을 보여줍니다.

저자들은 그들의 접근 방식이 희소 영차수 최적화를 위한 기존 알고리즘을 효과적으로 강화하여, 기울기에 접근할 수 없는 시나리오에서 더 유연하고 견고한 솔루션을 제공한다고 결론지었습니다.