Riemannian Dueling Optimization

이 논문은 추천 시스템 및 로봇 공학 등 기존 유클리드 공간 기반 알고리즘으로 해결하기 어려운 리만 다양체 상의 듀얼링 최적화 문제를 해결하기 위해, 지경적 L-스무스 및 (강) 볼록 함수에 대한 리만 듀얼링 정규화 경사 하강법 (RDNGD) 과 투영이 불가능한 상황을 위한 리만 듀얼링 프랭크-울프 (RDFW) 알고리즘을 제안하고 그 수렴성을 분석합니다.

핵심

🌍 핵심 개념: "눈가리개 하고 산을 오르는 법"

일반적인 최적화 (Optimization) 는 산꼭대기 (또는 골짜기) 를 찾을 때 **높이계 (Function Value)**나 **나침반 (Gradient/기울기)**을 봅니다. "여기가 100m 고도, 저기는 90m 고도"라고 숫자를 보고 "아, 아래로 내려가야겠다"라고 판단합니다.

하지만 이 논문이 다루는 상황은 다릅니다.

1. 눈가리개 상태 (Dueling Optimization): 숫자 (높이) 를 알 수 없습니다. 오직 **"A 지점과 B 지점 중 어디가 더 낮나요?"**라고 물어보면 "A 가 더 낮아요"라고만 알려주는 비교만 가능한 상황입니다.
2. 구불구불한 지형 (Riemannian Manifold): 우리가 사는 세상은 평평한 종이 (유클리드 공간) 가 아니라, 지구처럼 둥글거나 구부러진 지형 (리만니안 다양체) 일 수 있습니다. 예를 들어, 로봇 팔의 회전, 3D 이미지 왜곡, 추천 시스템의 복잡한 관계 등은 평평한 지도로 설명하기 어렵습니다.

결론: 이 논문은 **"숫자도 모르고, 지형도 구부러진 곳에서, 오직 'A 와 B 중 뭐가 더 좋아?'라는 비교 정보만 받아서 최선의 답을 찾는 새로운 방법"**을 제안합니다.

---

🛠️ 제안된 두 가지 새로운 도구

저자들은 이 어려운 문제를 해결하기 위해 두 가지 알고리즘을 개발했습니다.

1. RDNGD: "나침반 없이 방향을 잡는 등산가"

• 비유: 눈가리개를 하고 산을 오르는 등산가가 있다고 상상해 보세요. 그는 "얼마나 높은지"는 모릅니다. 대신, "왼쪽으로 한 걸음 옮기면 더 가깝나요, 오른쪽으로 한 걸음 옮기면 더 가깝나요?"라고 두 번 물어봅니다.
• 작동 원리:
  • 현재 위치에서 아주 작은 두 방향 (왼쪽, 오른쪽) 을 무작위로 선택합니다.
  • "어느 쪽이 더 좋아?"라고 비교합니다.
  • 더 좋은 쪽으로 한 걸음 내딛습니다.
  • 특이점: 평평한 땅 (일반적인 컴퓨터 공간) 이 아니라, 구부러진 지구 표면 (리만니안 다양체) 을 걷는 것이므로, 걸을 때마다 발을 어떻게 디뎌야 하는지 (기하학적 계산) 를 매우 정교하게 처리합니다.
• 효과: 이 방법은 비교 정보만으로도 매우 빠르게 최적의 지점을 찾아냅니다.

2. RDFW: "벽에 부딪히지 않는 유체 (Projection-Free)"

• 비유: 어떤 산은 울타리 (제약 조건) 가 있어서, 그 울타리 밖으로 나가지 못하게 됩니다. 보통의 방법은 "울타리에 부딪히면 다시 안으로 밀어 넣는 (Projection)" 작업을 해야 하는데, 이 작업이 너무 비싸고 복잡할 때가 있습니다.
• 작동 원리:
  • RDFW 는 "울타리에 부딪히지 않고, 울타리 안쪽에서 가장 좋은 방향을 찾아서 자연스럽게 이동하는" 방법을 씁니다.
  • 마치 물이 그릇의 모양에 맞춰 흐르듯, 제약 조건을 깨뜨리지 않으면서 최적의 해를 찾습니다.
• 효과: 계산이 너무 무거운 문제 (예: 복잡한 로봇 제어나 3D 모델링) 에서 효율적으로 작동합니다.

---

🚀 실제 어디에 쓰일까요? (생생한 예시)

이론만 있는 게 아니라, 실제 현실 문제에 적용됩니다.

1. 악성 해킹 (DNN Attack):

   • 상황: 해커가 AI 모델의 작동 원리 (수식) 를 모를 때, "이 이미지를 약간 변형하면 AI 가 틀릴까요?"라고 물어보며 AI 를 속이는 이미지를 만듭니다.
   • 적용: 해커는 정확한 점수를 알 수 없지만, "A 변형이 B 변형보다 AI 를 더 잘 속였나요?"라고 비교만 할 수 있습니다. 이 논문 알고리즘으로 AI 를 속이는 가장 효과적인 이미지를 찾아냅니다.

2. 사진의 수평 맞추기 (Horizon Leveling):

   • 상황: 찍힌 사진이 기울어져 있을 때, "어느 각도로 회전시키면 수평이 될까요?"를 찾아야 합니다.
   • 적용: "이 각도로 돌린 사진이 저 각도로 돌린 사진보다 더 수평으로 보이나요?"라고 사람이나 AI 가 비교해 주면, 알고리즘이 자동으로 정확한 회전 각도를 찾아냅니다.

3. 추천 시스템:

   • 상황: "이 영화 A 와 영화 B 중 사용자가 더 좋아할까요?"라는 비교 데이터만 있을 때, 사용자의 취향을 가장 잘 반영하는 복잡한 추천 모델을 만듭니다.

---

💡 왜 이 논문이 중요한가요?

기존의 방법들은 대부분 "평평한 땅 (유클리드 공간)"에서 작동하거나, "높이 (숫자)"를 알아야 했습니다. 하지만 현실 세계의 많은 문제 (로봇, AI, 3D 그래픽) 는 구부러진 공간에서 발생하며, 정확한 숫자 대신 비교 데이터만 주어지는 경우가 많습니다.

이 논문은 **"비교만 가능하고, 지형이 구부러진 세상에서도 최적의 답을 찾을 수 있다"**는 것을 수학적으로 증명하고, 실제로 작동하는 알고리즘을 제시했습니다. 이는 AI 와 로봇 공학 분야에서 더 정교하고 효율적인 시스템을 만드는 데 큰 발걸음이 될 것입니다.

한 줄 요약:

"숫자도 모르고, 땅도 구부러진 곳에서, 'A 와 B 중 뭐가 더 좋아?'라는 비교 말만 듣고도 최고의 답을 찾아내는 똑똑한 등산법을 개발했다!"

기술 요약

1. 문제 정의 (Problem Definition)

• 배경: 많은 현대 학습 작업 (추천 시스템, 로봇 제어, 표현 학습 등) 에서 목적 함수의 값이나 기울기 (Gradient) 에 직접 접근할 수 없으며, 오직 두 지점 간의 상대적 비교 (Pairwise Comparison) 정보만 얻을 수 있습니다. 이를 '듀얼링 피드백'이라고 합니다.
• 제약 조건: 이러한 문제들의 결정 공간 (Decision Space) 은 종종 유클리드 공간이 아닙니다. 예를 들어, 추천 시스템의 임베딩은 쌍곡 공간 (Hyperbolic space), 로봇의 궤적 최적화는 특수 직교 군 $SO(3)$, 표현 학습의 투영 행렬은 스테ifel 다양체 (Stiefel manifold) 등 리만 다양체 (Riemannian Manifold) 위에 존재합니다.
• 수식적 정의:
  $$\min_{x \in X \subseteq \mathcal{M}} f(x)$$
  여기서 $\mathcal{M}$은 $d$차원 리만 다양체이며, $f$는 매끄러운 함수입니다. 우리는 $f(x)$의 값 대신 두 점 $x, y$에 대한 비교 오라클 $Q_f(x, y)$만 접근 가능합니다.
  $$Q_f(x, y) = 2 \cdot \mathbb{1}(f(x) > f(y)) - 1$$
  (즉, $f(x)$가 $f(y)$보다 크면 1, 작으면 -1 을 반환).

2. 제안된 방법론 (Methodology)

저자는 리만 다양체의 기하학적 구조 (곡률, 지오데식 등) 를 고려하여 두 가지 주요 알고리즘을 제안했습니다.

A. 리만 듀얼링 정규화 기울기 하강법 (RDNGD)

• 개요: 유클리드 공간의 듀얼링 정규화 기울기 하강법을 리만 다양체로 확장한 알고리즘입니다.
• 기울기 추정기: 비교 오라클을 사용하여 기울기 방향을 추정합니다.
  • 현재 점 $x_k$에서 무작위 방향 $u$를 선택하고, 지오데식 (Geodesic) 을 따라 $\nu u$와 $-\nu u$만큼 이동한 두 점 $Expx(\nu u)$와 $Expx(-\nu u)$를 비교합니다.
  • 추정치: $h_\nu(x) = Q_f(Expx(\nu u), Expx(-\nu u)) \cdot u$.
  • 이 추정치는 정규화된 기울기 방향과 높은 확률로 일치하며, 편향 (Bias) 을 이론적으로 분석했습니다.
• 업데이트: 추정된 기울기 방향으로 지오데식을 따라 이동한 후, 제약 집합 $X$에 사영 (Projection) 합니다.
  $$x_{k+1} = P_X(Expx_k(-\eta_k h_\nu(x_k)))$$
• 수렴성:
  • 비볼록 (Geodesically L-smooth): $\epsilon$-정류점 (stationary point) 도달을 위한 반복 복잡도 $O(d\epsilon^{-2})$.
  • 볼록 (Geodesically convex): $\epsilon$-최적 해 도달을 위한 반복 복잡도 $O(d\epsilon^{-1})$.
  • 강한 볼록 (Strongly convex): 선형 수렴 속도를 달성하는 RRDNGD 알고리즘을 제안하여 반복 복잡도 $O(d \log(1/\epsilon))$를 달성했습니다.

B. 리만 듀얼링 프랭크 - 울프 방법 (RDFW)

• 동기: RDNGD 는 매 반복마다 사영 (Projection) 연산이 필요하며, 이는 일부 다양체 (예: SPD 행렬 공간) 에서 계산 비용이 매우 높을 수 있습니다.
• 접근: 사영이 금지되거나 비효율적인 경우를 위해 사영 없는 (Projection-free) 알고리즘을 제안합니다.
• 메커니즘:
  • 유클리드 프랭크 - 울프 방법의 선형 최소화 오라클 (LMO) 을 리만 다양체로 확장합니다.
  • 추정된 기울기 방향 $\bar{h}_k$를 사용하여 다음 문제를 풉니다:
    $$z_k = \arg \min_{z \in X} \langle \bar{h}_k, \text{Log}_{x_k}(z) \rangle$$
  • $x_k$에서 $z_k$로 가는 지오데식을 따라 이동하여 다음 점을 업데이트합니다.
• 수렴성: 볼록 설정에서 반복 복잡도 $O(\epsilon^{-1})$ 및 오라클 복잡도 $O(d\epsilon^{-2})$를 보장합니다. 이는 다양체 상의 사영 없는 듀얼링 최적화에 대한 첫 번째 수렴 결과입니다.

3. 주요 기여 (Key Contributions)

1. 새로운 프레임워크: 비교 오라클만 사용 가능한 리만 다양체 상의 최적화 문제를 공식화하고, 이를 해결하는 첫 번째 이론적 틀을 제시했습니다.
2. 알고리즘 제안:
   • RDNGD: 사영이 가능한 경우를 위한 정규화 기울기 하강법.
   • RRDNGD: 강한 볼록성 하에서 선형 수렴을 보장하는 반복적 알고리즘.
   • RDFW: 사영이 불가능하거나 비효율적인 경우를 위한 프랭크 - 울프 기반 알고리즘.
3. 이론적 개선:
   • 유클리드 공간의 기존 결과 (Saha et al., 2021) 를 리만 다양체로 일반화하는 과정에서 곡률 (Curvature) 로 인한 기하학적 장벽을 극복했습니다.
   • 기울기 추정기의 편향 (Bias) 분석을 정교화하여 기존 연구보다 더 엄밀한 상한 (Upper bound) 을 증명했습니다.
   • 차원 의존성 (Dimension dependence) 을 개선하여 기존 방법보다 더 나은 복잡도 보장을 제공했습니다.
4. 실험적 검증:
   • 합성 데이터: Rayleigh 몫 최대화, Karcher 평균 (SPD 행렬) 문제 등에서 RDNGD 와 RDFW 의 성능을 입증했습니다.
   • 실제 응용:
     • 딥러닝 공격 (Adversarial Attack): 블랙박스 환경에서 VGG 네트워크에 대한 공격을 수행하여, 기울기 정보 없이 비교 정보만으로 ZO-RGD(Zeroth-order Riemannian Gradient Descent) 보다 효율적인 공격을 성공시켰습니다.
     • 지평선 수평화 (Horizon Leveling): 이미지 지평선 보정 문제를 $SO(2)$ 다양체 상의 듀얼링 최적화 문제로 모델링하여 해결했습니다.

4. 결과 및 의의 (Results & Significance)

• 성능: 제안된 알고리즘들은 비교 오라클만 사용함에도 불구하고, 함수 값이나 기울기를 사용하는 기존 0 차 (Zeroth-order) 방법들과 유사하거나 더 나은 수렴 성능을 보였습니다. 특히 고차원 실제 문제 (이미지 공격) 에서는 쿼리 효율성 (Query Efficiency) 면에서 우위를 보였습니다.
• 적용 가능성: 추천 시스템 (쌍곡 공간), 로봇 공학 ($SO(3)$), 표현 학습 (Stiefel 다양체) 등 기존 듀얼링 최적화 알고리즘으로는 해결할 수 없었던 중요한 문제들을 해결할 수 있는 길을 열었습니다.
• 미래 전망: 이 연구는 선호 기반 최적화 (Preference-based optimization) 와 리만 최적화 (Riemannian optimization) 라는 두 개의 활발한 연구 분야를 연결했습니다. 향후 가속화 알고리즘, 헤시안 기반 국소 최소점 탐색, 안장점 (Saddle point) 탈출 메커니즘 등으로 확장 가능한 방향을 제시합니다.

결론적으로, 이 논문은 제한된 정보 (비교만 가능) 와 복잡한 기하학적 구조 (리만 다양체) 가 공존하는 현실 세계의 최적화 문제를 해결하기 위한 강력한 이론적 도구와 알고리즘을 제공했습니다.