💻 computer science

Riemannian Optimization for Hadamard Products of Low-Rank Matrices

본 논문은 아다마르 곱(Hadamard product) 하에서의 고유한 스케일링 대칭성을 해결함으로써 저계수 행렬을 효율적으로 학습하기 위해, 새로운 블록 대각 메트릭과 튜닝이 필요 없는 가우스-뉴턴 알고리즘을 갖춘 리만 최적화 프레임워크를 제안한다.

원저자: Pratik Jawanpuria, Ankish Chandresh, Bamdev Mishra

게시일 2026-06-02

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Pratik Jawanpuria, Ankish Chandresh, Bamdev Mishra

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

개요: 두 사람의 춤

당신이 단 두 개의 단순하고 저해상도인 스케치만을 사용하여 복잡한 그림(거대한 데이터 행렬)을 재현하려고 한다고 상상해 보세요.

스케치 A는 넓고 일반적인 형태를 포착합니다.
스케치 B는 미세하고 세밀한 질감을 포착합니다.

이 논문은 이 그림을 재현하는 가장 좋은 방법은 이 스케치들을 단순히 위로 쌓아 올리는 것이 아니라고 주장합니다. 대신, 당신은 이들을 픽셀 단위로 서로 곱해야 합니다 (이를 "아다마르 곱(Hadamard product)"이라고 부릅니다). 이를 통해 모델은 표준적인 방법보다 훨씬 적은 "붓터치"(파라미터)를 사용하여 매우 효율적으로 작업할 수 있습니다.

하지만 문제가 하나 있습니다. 두 개의 스케치를 곱하기 때문에, 스케치 A의 밝기를 조절하거나 스케치 B의 대비를 조절하여 결과적으로 완전히 동일한 최종 그림을 만드는 방법이 무수히 많습니다. 마치 "스케치 A의 불을 밝게 해서 그림을 더 밝게 만들 수도 있고", 혹은 "스케치 B의 불을 낮춰서 그림을 더 밝게 만들 수도 있다"라고 말하는 것과 같습니다. 이러한 조정의 조합은 결과적으로 동일한 그림을 만들어내는 무한한 경우의 수를 가집니다.

이는 컴퓨터가 모델을 학습시키는 데 혼란을 줍니다. 표준적인 컴퓨터 방식들은 이러한 "무한 루프" 속에서 길을 잃고 시간과 에너지를 낭비하게 됩니다.

문제점: 안개 속에서 길을 잃다

저자들은 기존 방식들(교대 경사 하강법 또는 블록 좌표 하강법 등)이 이 특정 유형의 문제에서 어려움을 겪는다는 점을 지적합니다.

표준 방식들은 문제를 평평하고 곧은 길 위를 걷는 것처럼 취급합니다. 하지만 실제 지형은 곡선형이고 울퉁불퉁합니다. 이들은 지형의 모양을 이해하지 못하기 때문에 너무 작은 발걸음을 떼거나 잘못된 방향으로 움직입니다.
특화된 방식들은 단순히 오차를 최소화하는 것(예: "제곱 오차")이 목표일 때는 아주 잘 작동하지만, 더 복합적인 목표(예: 사용자 평점 예측 또는 지저분한 데이터 처리)를 사용하려 하면 완전히 무너집니다. 이들은 마치 경주용 트랙에서만 달릴 수 있고 비포장도로에서는 멈춰버리는 자동차와 같습니다.

해결책: 스마트한 지도 (리만 최적화)

저자들은 **리만 최적화(Riemannian Optimization)**를 사용하여 이 문제를 헤쳐 나가는 새로운 방법을 제안합니다.

문제 공간을 평평한 종이가 아니라, 굽어 있고 접힌 표면(매니폴드)이라고 생각하십시오.

"접힌" 특성: 앞서 언급한 "무한 루프"(대칭성) 때문에, 지도상의 많은 서로 다른 지점들이 사실은 정확히 같은 그림을 나타냅니다.
몫 매니폴드(Quotient Manifold): 저자들은 이 "몫 매니폴드"를 만듭니다. 그 접힌 표면을 가져와서 같은 그림을 나타내는 모든 지점들을 하나로 붙여버린다고 상상해 보세요. 이제 당신은 모든 지점이 고유한 값을 갖는 깨끗하고 단순화된 지도를 갖게 됩니다. 루프들이 모두 붙어버렸기 때문에 더 이상 루프 속에서 길을 잃을 일이 없습니다.

비밀 병기: 맞춤형 나침반 (메트릭)

이 굽은 표면 위를 효율적으로 걷기 위해서는 특별한 나침반이 필요합니다. 수학에서는 이를 **리만 메트릭(Riemannian Metric)**이라고 부릅 합니다.

저자들은 새로운 맞춤형 나침반을 발명했습니다.

기존의 나침반: 표준 방식들은 지면이 평평하다고 가정하는 일반적인 나침반을 사용합니다. 그래서 곡선에 부딪히면 혼란에 빠집니다.
새로운 나침반: 저자들의 나침반은 "블록 대각(block-diagonal)" 구조입니다. 스케치의 모든 행과 열마다 독립적인 센서가 달려 있는 나침반을 상상해 보세요. 이 나침반은 스케치의 한 부분이 다른 부분의 형태에 어떻게 영향을 미치는지 정확히 알고 있습니다.
마법 같은 점: 이 나침반은 **스케일 불변(scale-invariant)**입니다. 만약 당신이 스케치 A를 두 배 밝게 하고 스케치 B를 절반으로 어둡게 만든다 해도, 나침반은 상관하지 않습니다. 당신이 그림 자체를 바꾼 것이 아님을 알기 때문에 혼란스러워하지 않습니다. 임의적인 스케일링의 "노이즈"를 무시하고 실제 데이터의 형태에만 집중합니다.

알고리즘: 튜닝이 필요 없는 등산가

이 새로운 지도와 나침반을 사용하여, 저자들은 **RGD(리만 경사 하강법)**라는 등산 알고리즘을 구축했습니다.

조절 다이얼이 필요 없음: 대부분의 등산 알고리즘은 "단계 크기(step size)" 다이얼을 수동으로 조절해야 합니다. 너무 많이 돌리면 목표를 지나치고, 너무 적게 돌리면 너무 느리게 움직입니다. 이 새로운 알고리즘은 "가우스-뉴턴(Gauss-Newton)" 기법을 사용하여 완벽한 단계 크기를 자동으로 계산합니다. 이는 마치 언덕의 경사도를 보고 본능적으로 발걸음의 크기를 결정하는 등산가와 같아서, 수동 조절이 전혀 필요 없습니다.
속도: 믿을 수 없을 정도로 빠릅니다. 데이터의 양에 따라 선형적으로 확장되므로, 그림의 크기가 두 배가 된다고 해서 시간이 네 배나 열 배로 늘어나는 것이 아니라 딱 두 배만큼만 더 걸립니다.

결과: 경주에서의 승리

저자들은 실제 데이터(MovieLens의 영화 평점 및 네트워크 맵 등)를 사용하여 기존 방식들과 이 등산가를 대결시켰습니다.

정확도: MovieLens 데이터셋(영화 평점 예측)에서, 이들의 방식은 테스트된 모든 구성 중에서 가장 낮은 오차율(최고의 정확도)을 달eric했습니다. 이들은 "경주용 트랙 전용" 특화 방식들보다 더 나은 해답을 찾아냈습니다.
강건성(Robustness): 실험을 위해 시작 조건을 인위적으로 망가뜨렸을 때(한쪽 스케치는 매우 밝게, 다른 쪽은 매우 어둡게 설정), 이 방식은 그 혼란을 무시하고 매번 정답을 찾아냈습니다. 기존 방식들은 혼란에 빠져 성능이 떨어졌습니다.
다재다능함: 단순한 수학 문제에서만 작동하는 특화된 방식들과 달리, 이 새로운 방식은 어떤 매끄러운 목표 함수에도 작동하므로 이 유형의 데이터를 위한 보편적인 도구가 됩니다.

요약

이 논문은 "곱셈적" 구조를 가진 데이터로부터 컴퓨터가 학습하는 더 똑똑한 방법을 소개합니다. 문제가 굽어 있고 접힌 표면에 존재한다는 점을 깨닫고, 무의미한 스케일링 기법을 무시하는 맞춤형 나침반을 만듦으로써, 이전 방식들보다 더 빠르고, 더 정확하며, 인간의 튜닝이 적게 필요한 알고리즘을 만들어냈습니다. 이는 눈을 가린 채 걷는 사람에서, 완벽하고 자동 조절되는 GPS를 가진 등산가로 업그레이드한 것과 같습니다.

기술 요약: 하다마르 곱을 갖는 저계수 행렬을 위한 리만 최적화

문제 정식화
본 논문은 두 저계수 행렬의 원소별(하다마르) 곱을 사용하여 데이터의 곱셈 구조를 모델링하는 과제를 다룹니다. 대상 행렬 $W \in \mathbb{R}^{m \times n}$ 은 다음과 같이 모델링됩니다:
$W = (GH^\top) \circ (UV^\top)$
여기서 $G, U \in \mathbb{R}^{m \times r_1, r_2}$ 이고 $H, V \in \mathbb{R}^{n \times r_1, r_2}$ 입니다. 이 공식은 표준 rank- $r_1r_2$ 인수 분해(파라미터 $(m+n)r_1r_2$ 필요)에 비해 파라미터 효율성을 제공하지만( $G, U, H, V$ 에 대해 $(m+n)(r_1+r_2)$ 파라미터 필요), 복잡한 최적화 지형을 유발합니다. 구체적으로, 이 모델은 표준 일반 선형(GL) 재매개변수화 불변성을 넘어선 대칭성을 보입니다. 곱 $W$ 는 두 인자 쌍 $(G, H)$ 와 $(U, V)$ 사이의 결합된 행 및 열 스케일링에 대해 불변성을 유지합니다. 이러한 추가적인 자유도는 표준 유클리드 경사 하강법이 효율적으로 탐색하기 어려운 도전적인 기하학적 구조를 생성합니다.

기존 솔버들은 한계에 직면해 있습니다: 교대 경사 하강법(AGD)은 특정 기하학 및 스케일링 대칭성을 무시하며, 블록 좌표 하강법(BCD)은 최소 제곱 손실에는 매우 효과적이지만 비이차적 손실(예: 로지스틱 링크 예측 또는 크로스 엔트로피)에 대한 폐쇄형 해(closed-form solution)가 부족하여 강건한 통계 및 기타 영역으로의 적용이 제한됩니다.

방법론
저자들은 학습 문제를 리만 몫 다양체(Riemannian quotient manifold) 상의 최적화 작업으로 정식화할 것을 제안합니다. 이 접근 방식은 하다마르 곱의 자연스러운 불변성을 명시적으로 고려합니다.

다양체 기하학: 저자들은 전체 행렬 대칭 그룹 $\mathcal{G}$ 를 인수로 하는 몫 다양체 $\mathcal{M}$ 을 정의합니다. $\mathcal{G}$ 는 다음을 포함합니다:
- 각 인자 쌍에 대한 표준 GL 재매개변수화 불변성.
- 두 인자 쌍 사이에서 행과 열을 역으로 스케일링하는 새로운 교차-하다마르 스케일링 대칭성(invertible diagonal matrices).
  다양체는 풀 컬럼 랭크(full-column-rank) 행렬들의 공간을 이 그룹 작용에 의해 나누어 구성됩니다.
새로운 리만 메트릭: 본 논문의 핵심 기여는 프로베니우스 내적의 풀백(pullback)에서 유도된 블록 대각 리만 메트릭( $g_x$ )의 유도입니다.
- 전체 풀백 메트릭은 네 개의 인자 블록을 모두 결합하여 밀집되고 계산 비용이 많이 드는 선형 시스템을 생성합니다.
- 제안된 메트릭은 풀백의 대각 블록만을 유지하고 교차 항을 버립니다.
- 메트릭은 각 행/열에 대한 가중치 행렬( $S$ -블록)을 통해 정의됩니다. 예를 들어, $G$ 의 $i$ 번째 행에 대한 가중치는 $S^G_i = H^\top \text{Diag}(Y^2_{i,:}) H$ 입니다 (여기서 $Y = UV^\top$ ).
- 불변성: 이 메트릭은 GL 재매개변수화 및 교차-하다마르 스케일링 대칭성 모두에 대해 불변임이 증명되었습니다. 이는 최적화 도구가 인자 간의 임의적인 크기 분할에 영향을 받지 않음을 보장합니다.
- BCD와의 연결: 제안된 메트릭의 가중치 행렬은 BCD 업데이트에서 사용되는 정규 방정식 행렬과 정확히 일치합니다. 따라서 리만 경사는 임의의 매끄러운 손실 함수에 대해 모든 행에 대해 동시에 수행되는 "연성(soft)" BCD 단계를 수행하는 것으로 해석될 수 있습니다.
최적화 알고리즘 (RGD): 저자들은 리만 경사 하강법(RGD) 알고리즘을 개발했습니다:
- 경사 계산: $S$ -블록을 사용하여 독립적인 $r \times r$ 선형 시스템(행/열당 하나씩)을 풀어 리만 경사를 계산합니다.
- 단계 크기: 튜닝이 필요 없는 **가우스-뉴턴 코시 단계 크기(Gauss–Newton Cauchy step size)**가 유도되었습니다. 이 단계 크기는 대칭 그룹에 대해 불변이며 하이퍼파라미터 튜닝을 요구하지 않습니다.
- Retraction: 업데이트를 다양체로 다시 매핑하기 위해 가산 리트랙션(additive retraction)이 사용됩니다.
- 복잡도: 반복당 비용은 관측된 항목의 수 $N$ 에 대해 선형적으로($O(Nr) $), 랭크에 대해 다항식적으로($ O((m+n)r^4)$) 확장되어 대규모 데이터셋에 효율적입니다.

주요 기여

기하학적 특성화: 하다마르 곱의 몫 다양체 구조를 기술하고, GL 및 교차-하다마르 스케일링 대칭성을 식별했습니다.
스케일 불변 메트릭: 전체 대칭 그룹을 존중하고 최적화를 독립적인 행/열 하위 문제로 분리하는 새로운 블록 대각 리만 메트릭을 제안했습니다.
알고리즘 개발: BCD가 이차 손실에 국한되는 것과 달리, 임의의 매끄러운 손실 함수를 지원하는 튜닝 프리 가우스-뉴턴 단계 크기를 갖는 RGD 알고리즘을 유도했습니다.
실증적 검증: 최소 제곱 문제에서 BCD의 효율성과 매끄러운 손실 함수의 유연성 사이의 간극을 메우는 성능을 입증했습니다.

실험 결과
저자들은 합성 및 실제 데이터셋에 대해 RGD를 평가했습니다:

합성 스트레스 테스트: $2,000 \times 1,000$ $2, 000 \times 1, 000$ 합성 타겟에 대해 RGD는 다음을 보여주었습니다:
- 스케일 불변성: 다양한 대각 스케일 분리( $\kappa_{scale}$ )에 대해 복구 오차가 일정하게 유지되어, 메트릭의 불변성을 경험적으로 검증했습니다. 반면 AGD는 스케일링에 민감함을 보였습니다.
- 조건수(Conditioning): RGD는 다양한 인자 조건수 변화에 대해 BCD와 유사한 성능을 보였으며, AGD를 크게 앞질렀습니다.
- 노이즈 강건성: RGD는 BCD와 동일한 속도로 노이즈 플로어(noise floor)로 수렴한 반면, AGD는 뒤처졌습니다.
실제 데이터셋:
- 전체 행렬 근사: Camera, Football, Les Misérables 데이터셋에서 RGD는 상대 오차 측면에서 BCD를 밀접하게 추적하여, 메트릭이 이차 손실에 대해 BCD와 동등한 프리컨디셔닝을 제공함을 확인했습니다.
- MovieLens-1M: 고정된 파라미터 예산( $r_1+r_2=6$ )을 가진 행렬 완결 작업에서, RGD는 테스트된 모든 하다마르 랭크 구성 중 가장 낮은 Held-out RMSE를 달 기록했습니다. 특히, 균형 잡힌 구성 $(3,3)$ 이 거의 베니라(vanilla) 형태인 $(1,5)$ 보다 우수한 성능을 보였는데, 이는 하다마르 상호작作用 용량( $r_1r_2$ )이 정확도에 기여함을 시사합니다. RGD는 일관되게 AGD를 능가했으며, 진정한 하다마르 구성에서는 BCD보다 낮은 RMSE를 달성했습니다.

의의 및 주장
본 논문은 최소 제곱 문제에 대한 BCD의 효율성과 일반적인 매끄러운 손실에 대한 경사 기반 방법의 유연성 사이의 간극을 메운다고 주장합니다. 문제를 리만 몫 다양체로 격상함으로써, 저자들은 복잡한 대칭성을 처리하는 원칙적인 프레임워크를 제공합니다. 제안된 RGD 알고리즘은 데이터 크기에 선형적으로 확장되는 튜닝 프리(tuning-free), 스케일 불변(scale-invariant) 최적화 방법을 제공합니다. 저자들은 이 프레임워크가 $k$ 개의 저계수 행렬 곱으로 자연스럽게 확장될 수 있으며, 다른 리만 솔버(예: 공액 경사법, 신뢰 영역 방법)와 호환 가능하다는 점을 강조하며, 곱셈적 저계수 모델링을 위한 강력한 대안을 제시합니다.