랜덤 행렬 불일치 -- CLuP 알고리즘과 매개변수적 RDT 접근법
Random matrix discrepancy -- CLuP algorithm and parametric RDT approach
한국어 초록
우리는 비례 영역에서 랜덤 행렬 불일치(discrepancy)의 정보 이론적 측면과 알고리즘적 측면을 연구한다. 이 문제는 $\kappa=\min_{\x\in\mB^n}\|\sum_{i=1}^{n}\bar{A}_i\x_i\|_2$를 구하는 것에 해당하며, 여기서 $\bar{A}_i\in\mR^{d\times d}$는 n개의 독립동일분포 GOE 행렬의 모음이고, $\mB^n$은 $\mR^n$에서 단위 정육면체의 꼭짓점들이며, $\alpha=\lim_{n\rightarrow \infty}\frac{n}{d^2}$는 비례 상수이다. 여러 방향에서 상당한 진전을 이루었다. (i) 랜덤 쌍대성 이론(RDT) 프레임워크를 개발하고 그 lifted 변형을 활용하여 $\kappa$의 하한을 도출하였으며, 이는 [81]에서 1차 모멘트를 통해 얻은 하한과 정확히 일치한다. (ii) 분석상의 어려움을 해결하기 위해, 완전한 lifted RDT를 구현하기 위한 프록시로 음의 Hopfield 모델을 제안한다. 2차 lifting 수준에서 이 모델은 [81]의 정보 이론적 하한과 [38]의 알고리즘적 상한 사이에 매우 잘 들어맞는다. (iii) 3차 및 4차 lifting 수준에서, 매개변수적 RDT 개념은 프록시 모델에서 낮은 $\kappa$ 값에 대해 상당한 계산적 간극을 예측한다. 프록시의 정보 이론적 적합을 알고리즘적 적합으로 확장하면, [73]과 부합하게 낮은 $\kappa$ 영역의 행렬 불일치에도 유사한 계산적 간극이 있음을 시사한다. (iv) 행렬 불일치를 위한 Controlled Loosening Up(CLuP) 알고리즘을 설계한다. 이 알고리즘의 성능은 우리의 분석 결과와 강하게 일치한다. 낮은 $\alpha$ 범위에서는 정보 이론적 예측에 근접하고(계산적 간극이 작거나 존재하지 않음을 시사), 높은 $\alpha$ 범위에서는 프록시 모델의 알고리즘적 예측을 따른다(상당한 계산적 간극을 시사). 정보 이론적 예측과 알고리즘적 예측 모두 전체 $\alpha\in(0,\infty)$ 범위에서 벡터 유사체인 대칭 이진 퍼셉트론(SBP)의 해당 현상과 일치한다 [1,2,14,31,51,92,111].
원문 초록
We study information-theoretic and algorithmic aspects of random matrix discrepancy in proportional regime. The problem amounts to finding $\kappa=\min_{\x\in\mB^n}\|\sum_{i=1}^{n}\bar{A}_i\x_i\|_2$, where $\bar{A}_i\in\mR^{d\times d}$ is a collection of $n$ iid GOE matrices, $\mB^n$ are vertices of the unit cube in $\mR^n$, and $\alpha=\lim_{n\rightarrow \infty}\frac{n}{d^2}$ is a proportionality constant. Strong progress is made in several directions: (i) We develop a Random duality theory (RDT) framework and utilize its a lifted variant to establish lower bounds on $\kappa$, which precisely match the bounds obtained via the first moment in [81]. (ii) To address analytical challenges, we propose a negative Hopfield model as a proxy for implementation of a fully lifted RDT. On the 2nd lifting level, this model fits remarkably well between the information-theoretic lower bounds from [81] and the algorithmic upper bounds from [38]. (iii) On the 3rd and 4th lifting levels, parametric RDT concepts predict a sizeable computational gap for lower $\kappa$ values in the proxy model. Extending proxy information-theoretic fitting to algorithmic suggests a similar computational gap for matrix discrepancy in low $\kappa$ regime, aligning with [73]. (iv) We design a Controlled Loosening Up (CLuP) algorithm for matrix discrepancy. Its performance strongly matches our analytical results -- closely approaching information-theoretic predictions in lower $\alpha$ ranges (indicating a small or nonexistent computational gap) and following the proxy model's algorithmic predictions in higher $\alpha$ ranges (indicating a sizeable computational gap). Both the information-theoretic and algorithmic predictions match the corresponding phenomenologies of the symmetric binary perceptron (SBP) vector analogue in the entire $\alpha\in(0,\infty)$ range [1,2,14,31,51,92,111].
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2611.18650v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.