August 10, 2026

여섯 편의 프리프린트로 구성된 편이다. 앞의 두 양자 항목(P1, P2)은 순수 표본복잡도 이론과 실험 하드웨어에 바로 적용 가능한 측정 스케줄링이라는 서로 다른 층위에 있지만, 모두 이 사이트가 앞서 다룬 양자 오류정정 스레드(QEC, 2026-08-07 편)의 연장선에 있다. P3은 위상학적 애니온을 냉원자 등 공학적 플랫폼에서 직접 제어하려는 제안으로, 앞서 다룬 chiral topological order 항목과 주제를 공유하되 이번에는 시뮬레이션 플랫폼 쪽에 초점을 둔다. 다체 항목은 이 사이트가 처음 다루는 strange-metal 문제이며, Discussion에서 같은 거시적 현상(선형 저항)을 서로 다른 미시적 메커니즘으로 설명하는 최근 별개 연구와 대조한다. 마지막 두 ML/AI 항목은 지금까지의 응용·해석가능성 위주 항목들과 달리 학습이론·최적화이론의 순수 결과다.

Quantum Information & Computing

P1. Dimension-Free Polylogarithmic Quantum Shadow Tomography from Sequential Pretty-Good Measurements

Authors	Fernando Granha Jeronimo, Qizhao Huang, Lenny Liu
Venue	arXiv:2608.06345
Tags	Quantum state tomography

More details

Background

• Shadow tomography는 미지의 $d$차원 양자 상태 $\rho$의 사본을 여러 개 소비해, 미리 정해진 $m$개의 관측량 $E_1,\dots ,E_m$에 대한 기댓값 $\mathrm{Tr}(\rho E_i)$ 전부를 정확도 $\epsilon$·신뢰도 $1-\delta$로 동시에 추정하는 문제다. Aaronson의 STOC 2018 결과 [1]는 필요한 사본 수가 $m$에 대해 다항로그(${\log }^{4}m$)로만 늘어난다는 것을 보여 이 문제를 사실상 연 논문이지만, 그 사본 수는 여전히 차원 $d$에 의존했다($\log d$ 인자) — Aaronson은 차원에 무관하면서도 다항로그 스케일링을 유지할 수 있는지를 공개 질문으로 남겼다.
• Sinha(2024) [2]는 차원 무관(dimension-independent) 사본 수 $O(\sqrt{m}\log m/{\epsilon }^2)$를 처음 달성했지만, 이는 $m$에 대해 다항로그가 아니라 다항식(제곱근) 스케일링이다 — Aaronson의 질문에 완전히 답하지는 못한 결과였다.

Summary

• 핵심 정리(Theorem 1.2): 사본 수 $T\le \frac{C}{{\epsilon }^2}\frac{L^4}{(\log L{)}^3},L=\log \frac{16m}{\delta }$ 만으로 shadow tomography가 가능함을 증명한다 — 차원 $d$에 전혀 의존하지 않으면서 $m$에 대해서는 다항로그로만 스케일링한다. Sinha의 결과 대비 지수적 개선이며, Aaronson이 남긴 질문에 긍정으로 답한다.
• 증명은 두 층으로 이루어진다. 1층: 유한한 사전분포(prior)를 가진 상태들의 앙상블에 대해, 매 라운드 $n$개의 사본을 소비하며 사후분포를 갱신하는 순차적(sequential) pretty-good measurement(PGM) 프로토콜을 구성해 베이즈 실패확률을 억제한다. 2층: Sion의 minimax 정리로 사전분포 의존성을 제거해 유한 앙상블에 대한 균일한 보장으로 바꾸고, 상태공간 위의 trace-distance net을 이용해 이 보장을 모든 상태로 확장한다.
• 순차 PGM 자체는 관측량에 무관하게 구성되므로, 하나의 프로토콜을 $m$개 좌표 전체에 재사용할 수 있다는 점이 다항로그 스케일링의 핵심 축이다.

Discussion

• 이 결과는 정보이론적(information-theoretic) 사본-수 상한이며, 계산적으로 효율적인 측정 프로토콜을 제시한다고 주장하지 않는다 — 즉 몇 개의 사본이 “원리적으로” 필요한지를 답할 뿐, 그 측정을 실제 양자 회로로 얼마나 효율적으로 구현할 수 있는지는 이 논문의 범위 밖이다. 계산적으로 효율적인 것으로 잘 알려진 classical shadows 기법과는 이 지점에서 목표가 다르다.
• 이 논문이 발표되기 약 일주일 전, 별도의 연구진(Chen, O’Donnell, Pelecanos, Wright)이 “Online Shadow Tomography Matching the Classical Bounds” [3]에서 차원-무관 사본 수 $O(\sqrt{m}/{\epsilon }^2)$를 제시하며 이를 “차원-무관 상한 중 최적”이라고 명시했다 — 언뜻 이 논문의 다항로그 결과와 충돌하는 것처럼 보이지만, 두 논문은 서로 다른 문제를 다룬다. Chen 등의 결과는 관측량이 매 단계 적대적(adversarial)으로, 이전 측정 결과를 본 뒤 적응적으로 주어지는 online(적응형) 세팅에 대한 것이고, 이 논문은 $m$개의 관측량이 처음부터 고정되어 주어지는 offline(비적응형) 세팅을 다룬다. 적응형 세팅이 원리적으로 더 어려운 문제이므로, 그쪽에서 성립하는 $\sqrt{m}$ 하한이 이 논문이 다루는 비적응형 세팅의 다항로그 상한과 모순되지 않는다 — 두 논문은 발표 시점이 일주일 남짓밖에 차이 나지 않아 서로를 인용하지 않는다.
• 이 논문 자체는 다항로그 상한이 비적응형 세팅에서 최적(즉 이에 맞는 하한)이라는 것까지 증명하지는 않는다 — $m$에 대한 다항로그 스케일링이 더 개선될 수 있는지는 이 논문 자체가 열어 둔 질문이다.

References

• [1] Aaronson, “Shadow Tomography of Quantum States”, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), 325–338.
• [2] Sinha, “Dimension Independent and Computationally Efficient Shadow Tomography”, Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025).
• [3] Chen, O’Donnell, Pelecanos, and Wright, “Online Shadow Tomography Matching the Classical Bounds”, arXiv:2607.29686 (2026).

P2. Exponential logical-error reduction in quantum memories via optimal syndrome-measurement timing

Authors	Tobias Haug, Kishor Bharti, Leandro Aolita
Venue	arXiv:2608.06242
Tags	QEC

More details

Background

• 양자 오류 정정 코드는 syndrome을 반복적으로 측정해 오류를 검출·정정한다. 측정 주기는 보통 고정된 클럭을 따르지만, 이 논문은 그 간격 $\Delta t$ 자체를 최적화 대상으로 삼는다 — 너무 뜸하게 측정하면 그 사이 대기 중 오류가 쌓이고, 너무 자주 측정하면 측정 자체가 만드는 오류(게이트·readout 오류)가 늘어나는 트레이드오프가 있다.
• 저자들은 라운드마다 두 오류원을 갖는 현상론적 모델을 쓴다: 대기 중 오류 $p_{\text{idle}}\sim p\lambda \Delta t$와 측정 자체의 오류 $p_{\text{stab}}=p$(데이터 큐비트), $p_{\text{read}}=b_{\text{read}}\cdot p$(readout). 합쳐진 데이터 큐비트 오류율은 $p_{\text{data}}=1-(1-p_{\text{stab}})(1-p_{\text{idle}})\sim p(1+\lambda \Delta t)$다.

Summary

• 최적 측정 간격은 코드 거리 $d$에 반비례하게 스케일링한다: $\Delta t^{\ast }\propto 1/d$. 간격을 최적값에서 벗어나게 고정하면 손해가 ${\Gamma }_{\text{opt}}\sim \frac{1}{e}\frac{\Delta t^{\ast }}{\Delta t}\exp \left(\frac{\Delta t}{\Delta t^{\ast }}\right)$로 지수적으로 커진다 — 뒤집어 말하면, 간격을 코드 거리에 맞게 최적으로 잡을 때 고정-간격 방식 대비 논리오류율이 지수적으로 줄어든다.
• 순간적인 노이즈 활동도(burst)에 실시간으로 반응해 $\Delta t(t)$를 조절하는 적응형(adaptive) 전략도 제시한다 — burst 비율 $r={\lambda }_{\text{high}}/{\lambda }_{\text{low}}$에 대해 이득 ${\Gamma }_{\text{adapt}}\sim \frac{r}{e\log r}$을 얻으며, 짧고 강한 burst일수록, 그리고 burst 진폭이 클수록 거의 선형적으로 이득이 커진다.
• Rotated surface code · phenomenological bit-flip 노이즈 · MWPM(pymatching) 디코더로 시뮬레이션했고, burst 탐지는 syndrome 활동도에 대한 log-likelihood-ratio 검정과 이동평균으로 수행한다. Google의 실험 보정 파라미터를 대입하면 단위시간당 논리오류율이 최대 약 40% 감소한다고 예측하며, $d=15$·현실적 burst 파라미터 조건에서는 논리오류가 거의 절반으로 준다.

Discussion

• 저자들이 직접 밝힌 제약: $\Delta t^{\ast }\propto 1/d$가 요구하는 간격은 결국 실험 플랫폼의 물리적 속도 한계($\Delta t_{\min }$)에 부딪힌다 — 코드 거리를 계속 키우면 어느 지점부터는 이론이 요구하는 최적 간격을 실제로 구현할 수 없다. 즉 이 이득은 무한정 스케일되지 않고 하드웨어의 게이트·측정 속도로 상한이 걸린다.
• 측정을 더 빠르게 하면(작은 $\Delta t$) 일반적으로 readout 오류가 늘어나는 트레이드오프가 있는데, 이 모델은 그 트레이드오프를 파라미터($b_{\text{read}}$)로 반영할 뿐 왜 그런 트레이드오프가 생기는지의 하드웨어 물리는 다루지 않는다 — 실제 적용에는 플랫폼별 실측 보정이 계속 필요하다.
• 적응형 프로토콜의 이론적 이득 ${\Gamma }_{\text{adapt}}$은 순간 노이즈율 $\lambda (t)$를 정확히 안다고 가정한 이상적인 경우다. 저자들은 실제로는 노이즈가 섞인 syndrome 신호에서 burst를 탐지해야 하므로 오탐·누락률이 $O(1/(W{d}^2))$로 스케일된다고 스스로 명시한다 — 이론적 상한과 실전 구현 사이의 간극을 인정한 것이다.
• 이 결과는 시간 의존적 정보를 활용할 수 있는 디코더를 가정하며, soft-information 디코더를 쓰면 성능이 더 오를 수 있다고 저자들이 언급한다 — 즉 보고된 약 40%라는 수치는 이 특정 디코더·노이즈 모델 조합에서의 하한에 가깝다.
• 앞서 이 사이트가 다룬 Approximate quantum error correction at chiral topological edges(2026-08-07 편, P1)이 코드 구조 자체를 바꿔 오류 정정을 개선하는 접근이라면, 이 논문은 코드나 하드웨어를 바꾸지 않고 순수하게 측정 스케줄만 바꾼다 — 기존 장치에 소프트웨어 수준의 변경만으로 적용해 볼 수 있다는 점에서 문턱이 낮은 개선이다.

P3. Anyon-Impurity Bound States in Quantum-Engineered Fractional Chern Insulators

Authors	Botao Wang, Amit Vashisht, Felix A. Palm, Fabian Grusdt, Laurens Vanderstraeten, Nathan Goldman
Venue	arXiv:2608.06233
Tags	Fractional Chern insulator Quantum simulation

More details

Background

• Fractional Chern insulator(FCI)는 격자 위에 인공 자기선속을 걸어 만드는 fractional quantum Hall 상태의 격자 유사체다. 저자들은 최근 고체 물질에서 애니온-불순물 복합체가 실제로 관측된 사례와, 광격자 등 공학적 격자 시스템에서 Laughlin류 상태가 실현된 최근 사례 둘 다에서 동기를 얻었다고 밝힌다.
• 이동 가능한 불순물 입자를 매질에 담그면, 그 불순물이 주변 매질에 “감싸이는(dressing)” 방식 자체가 매질의 상관관계·위상학적 성질을 알려주는 탐침이 된다는 폴라론 물리학의 일반적 아이디어를, 애니온(quasihole)에 적용한다.

Summary

• Interacting Harper–Hofstadter 모델 $H=H_{\text{host}}+H_{\text{imp}}+H_U$을 다룬다: 인공 자기선속이 걸린 2차원 격자 위에서 host 입자(hard-core boson)들이 FCI 바닥상태를 이루고, 별도 종류의 이동 가능한 불순물 입자가 host와 반발 상호작용(contact interaction)하며, 프로그램 가능한 국소 pinning 퍼텐셜이 quasihole을 만든다.
• 단일입자 해석적 분석(Bessel 함수 경계값 문제)으로, 2차원에서는 어떤 인력 퍼텐셜도 최소 하나의 속박 상태를 지원함을 보이고, 속박 에너지가 유효 confinement 세기에 선형적으로 비례함을 유도한다.
• 핵심 결과: 서로 다른 분수 전하 $Q^{\prime }$에 대한 속박 에너지의 비 $E_B(Q^{\prime })/E_B(Q=1)$가 약한 상호작용 극한에서 전하값 $|Q^{\prime }|$ 자체로 수렴한다 — 속박 에너지의 비율을 재는 것만으로 quasihole의 분수 전하를 직접 읽어낼 수 있다는 뜻이다.
• $10\times 10$ 격자·hard-core boson 10개 규모의 MPS(DMRG) 계산으로 $Q=-1/2$ 등 분수 전하 생성을 확인했고, 약한 결합($U/J<0.5$)에서는 평균장 예측과 잘 맞으며 집단여기로 인한 되먹임이 거의 사라진다. 무한 실린더(VUMPS, window MPS, Tao–Thouless 상태) 계산으로 $-1/2$, $-1/3$ 분수 전하를 재현했고, 창(window) 크기가 충분히 크면 속박 에너지 비율이 예상 전하비로 수렴함을 확인했다.
• 시간 의존 변분원리(TDVP) 실시간 전개로, pinning 퍼텐셜을 외부에서 끌고 가면 불순물이 quasihole을 따라 결맞게(coherently) 이동하며, 결합이 강할수록 수송 효율이 좋아짐을 보였다. 단열적으로 따라가는 것이 깨지는 시점이 속박 에너지의 역수 시간 스케일 근처에서 일어나, 이 자체가 속박 에너지를 재는 별도의 동적 프로토콜이 될 수 있다.

Discussion

• 저자들이 직접 밝힌 한계: 결합이 강해지면($U/J>0.5$) magnetoroton 모드와의 결합이 중요해져 전하 추출이 복잡해진다 — “속박 에너지 비율이 곧 분수 전하”라는 이 논문의 핵심 결과는 약한 결합 극한이라는 조건이 붙은 결과이며, 강한 결합까지 그대로 성립한다고 주장하지 않는다. 충전율 $\nu =1/3$의 quasihole은 공간적으로 더 퍼져 있어 유한 크기·실린더 둘레 방향의 인공적 효과가 더 두드러진다고도 인정한다 — 분수 전하가 작을수록(1/3 < 1/2) 신호 추출이 어려워진다는 뜻이다.
• 이 논문은 이론과 수치 시뮬레이션이며, 저자들도 애니온-불순물 복합체를 공학적 세팅에서 실제로 만들고 조작할 수 있는지가 여전히 미해결 과제(“outstanding challenge”)라고 표현한다 — 다만 이 논문 자체의 목적이 그 과제에 대한 구체적 프로토콜(냉원자 양자가스현미경의 프로그램 가능한 광학 퍼텐셜로 pinning을, Feshbach 공명으로 조절 가능한 별도 초미세구조 상태로 불순물을 구현하는 방안)을 제시하는 데 있다.
• 결맞은 수송 결과를 저자들은 braiding(애니온을 서로 교환시켜 그 통계를 직접 검증하는 실험)으로 가는 디딤돌로 명시적으로 제시하지만, 이 논문 자체가 실제 braiding 신호(통계적 위상)를 계산하거나 관측하지는 않는다 — 단일 애니온-불순물 복합체를 원하는 대로 끌고 갈 수 있음을 보인 단계이며, 둘 이상의 애니온을 서로 교환시키는 다음 단계는 이 논문의 범위 밖이다.

Many-body / materials physics

P1. Resilient strange metal at an unconventional quantum critical point in d=2

Authors	Jérôme Leblanc, A.-M. S. Tremblay
Venue	arXiv:2608.05988
Tags	Quantum criticality

More details

Background

• 2차원 정사각격자 Hubbard 모델(최근접-이웃 홉핑)은 콜드아톰 실험과 diagrammatic quantum Monte Carlo로 광범위하게 연구되는 모델이다. 이 논문은 Fermi liquid와 비정합(incommensurate) spin-density-wave(SDW) 질서 사이의 quantum critical point(QCP)를 다룬다.
• 이 QCP에서는 SDW 파수벡터 $\mathbf{Q}$가 Fermi 표면 위의 두 점을 거의 반대 방향(antiparallel)의 Fermi 속도로 연결하는 특별한 기하학적 상황(Kohn point)이 생기며, 이것이 Kohn anomaly를 만든다.
• 방법은 “Improved two-particle self-consistent approach(TPSC+)“라는 비섭동적 방법으로, spin·charge susceptibility에 대한 RPA류 합규칙(sum rule)을 만족시키고 Mermin–Wagner 정리를 준수하며, 약한~중간 상호작용 세기의 물리를 담아낸다.

Summary

• QCP의 임계 지수가 표준 Hertz–Millis 이론의 예측과 다른 값($\gamma \approx 0.92$, $\nu \approx 0.98$, $z\approx 1.28$)으로 나온다 — Kohn anomaly와 Fermi 표면의 거의 완전한 네스팅이 결합해 만드는 비표준적 지수다.
• 저항이 $T=0.003t$부터 $T\sim 0.3t$까지 상당히 넓은 온도 구간에서 선형(strange-metal 거동)으로 유지된다.
• Fermi 표면을 따라 본 self-energy의 온도 의존성이 균일하지 않고 운동량에 강하게 의존해, Landau quasiparticle의 뚜렷한 증거가 없다 — 그럼에도 저항은 선형적이다. 즉 이 논문의 핵심 주장은, 저항의 선형성이 “self-energy가 Fermi 표면 전체에서 균일하게 선형-T”라는 통상적인 marginal-Fermi-liquid 가정 없이도 나타날 수 있다는 것이다.

Discussion

• 저자들이 직접 밝힌 한계: vertex correction, disorder, 그리고 점근적으로 낮은 온도($T\ll 0.003t$)에서의 “resilient Fermi liquid” 효과는 이 논문이 다루지 않는다고 명시한다. 거듭제곱 법칙들을 해석적으로 유도하는 것은 상당히 어렵다고 인정하며, 이 전이가 (이들이 가정한 연속 전이가 아니라) 1차 전이일 가능성도 배제하지 않는다고 스스로 밝힌다.
• 같은 질문 — 2D Hubbard류 모델에서 strange-metal 저항이 왜 나타나는가 — 을 다른 방법으로 다룬 최근 연구와 대조할 만하다. Tanaka(2026) [1]는 ladder dual-fermion 근사로 cuprate에 가까운 조건에서 strange-metal 상태를 얻는데, 그 결과는 marginal-Fermi-liquid 그림에 가깝다 — 산란율의 운동량 의존성이 작다고 보고해, Landau quasiparticle이 (온도에 선형인 산란율을 갖더라도) 여전히 상당히 잘 정의된 개념으로 남는다는 그림을 제시한다. 이는 이 논문(Leblanc–Tremblay)이 강조하는 “quasiparticle의 뚜렷한 증거가 없다”는 결론과 정면으로 대비된다.
• 두 연구는 방법(TPSC+ vs. ladder dual-fermion)도 다르고 겨냥하는 상호작용 세기·도핑 영역도 정확히 같지는 않으므로 직접적인 반박 관계는 아니다. 다만 “저항이 선형-T”라는 같은 거시적 관측 뒤에 서로 다른 미시적 메커니즘(quasiparticle 소멸 vs. marginal Fermi liquid로서 잔존)을 제시한다는 점에서, 선형 저항이라는 현상 하나만으로는 그 원인이 되는 미시적 메커니즘을 유일하게 특정할 수 없다는 것을 보여주는 사례로 읽을 수 있다.
• 이 논문은 특정 실험 물질의 성질을 정량적으로 재현하려는 시도가 아니라 모델(2D Hubbard) 자체의 성질을 규명하는 이론 계산이다 — 콜드아톰 실험이 이 모델을 상당히 직접적으로 구현할 수 있다는 점에서 원리적으로 검증 가능하지만, 이 논문 자체는 그 실험적 검증을 수행하지 않는다.

References

• [1] Tanaka, “Pseudogap and strange metal states in the square-lattice Hubbard model: A comprehensive study”, Phys. Rev. B (2026).

ML/AI

P1. An Optimal Agnostic PAC Algorithm

Authors	Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy
Venue	arXiv:2608.06363
Tags	PAC learning

More details

Background

• 다루는 문제: PAC 학습 이론의 기초 질문 중 하나는 “정답이 완벽하게 분류 가능하지 않은(agnostic) 상황에서, 학습기가 최적 오류율에 얼마나 빨리, 얼마나 가깝게 수렴할 수 있는가”이다. VC 차원 $d$인 가설 클래스, 표본 $n$개, 클래스 내 최소 달성 가능 오류 $L^{\ast }$가 주어졌을 때, 1996년 Devroye–Györfi–Lugosi의 교과서가 제시한 하한은 어떤 학습기에 대해서도 나쁜 경우 확률 $\ge \delta$로 $L(\hat{h})\ge L^{\ast }+c\left(\sqrt{\frac{L^{\ast }(d+\log (1/\delta ))}{n}}+\frac{d+\log (1/\delta )}{n}\right)$ 가 성립한다는 것이었다. 이 하한과 정확히 맞아떨어지는 상한(구체적 알고리즘과 그 보장)을 찾는 것이 오랫동안 공백으로 남아 있었다.
• Hanneke, Larsen, Zhivotovskiy(FOCS 2024) [1]가 $L^{\ast }$ 앞의 계수를 1로 유지하는 최적의 첫 항(느린 항)을 얻는 학습기를 제시했지만, 둘째 항(빠른 항)에는 ${\log }^5(n/d)$ 같은 여분의 다항로그 인자가 남아 하한과 정확히 일치하지는 않았다. 최근 Asilis, Høgsgaard, Velegkas [2]는 $\tau \approx d/n$(오류가 작은 영역)이라는 좁은 구간에 한해 계수 2.1로 하한과 맞아떨어지는 학습기를 제시하며 HLZ가 남긴 공백의 일부를 메웠다.

Summary

• 기여: 이 논문은 결정론적(deterministic)이고 improper(가설 클래스 밖의 분류기를 낼 수 있는) 학습기를 구성해, 모든 분포·모든 $n\ge 1$·모든 $0<\delta \le 1/2$에 대해 확률 $1-\delta$ 이상으로 $L(\hat{h})\le L^{\ast }+7\times 10^8\left(\sqrt{\frac{L^{\ast }(d+\log (1/\delta ))}{n}}+\frac{d+\log (1/\delta )}{n}\right)$ 을 만족함을 증명한다(Theorem 1) — 앞선 Asilis 등의 결과가 좁은 오류 구간에서만 상수를 조였던 것과 달리, 이 결과는 모든 고정된 $L^{\ast }$ 수준에서 동시에 (전역 상수 배 이내로) agnostic PAC 학습의 표본복잡도를 완전히 해결한다.
• 알고리즘 구성은 세 단계다: (1) 불리언 하이퍼큐브 위에서 클래스에 의존하는 edge-isoperimetry 부등식(Lemma 2.1)으로, 경험적 최적해에 계수 1을 유지하는 leave-one-out 상한을 주는 결정론적 orientation을 만든다. (2) 이를 순열-불변 예측으로 대칭화한 뒤, 연속된 접두사(prefix)로 각각 학습한 점수를 평균 내는 randomized predictor로 바꾼다(Aden-Ali 등의 분산-통제 martingale 기법을 agnostic 세팅에 맞춘 것). (3) 별도의 검증 표본으로 점수를 문턱값화(thresholding)해 최종 이진 분류기를 만드는 empirical-risk-minimization 단계를 거친다.

Discussion

• 왜 중요한가: 이 결과는 응용보다는 “학습이 이론적으로 얼마나 빨리, 얼마나 잘 될 수 있는가”라는 근본 한계를 확정짓는 기초 결과다. Asilis 등이 $\tau \approx d/n$이라는 좁은 구간만 계수 2.1로 닫았던 것과 비교하면, 이 논문은 적용 범위를 모든 $L^{\ast }$ 수준으로 훨씬 넓히는 대신 상수를 크게 희생한다($7\times 10^8$ vs. $2.1$) — “얼마나 넓은 영역에서 성립하는가”와 “상수가 실용적으로 의미 있는 크기인가”는 서로 다른 축의 진전이며, 이 논문은 전자를 택했다.
• 저자들은 상수를 더 줄일 여지가 있다고 언급하지만 본문에서 구체적 방법을 제시하지는 않는다 — 이 결과는 점근적 표본복잡도 질문을 (상수를 제외하고) 완전히 닫았을 뿐, 실용적으로 바로 쓸 수 있는 유한-표본 알고리즘을 제공한다고 주장하지는 않는다.
• 학습기가 improper라는 점은, 이 결과가 이론적으로 최적인 표본복잡도를 달성하는 대가로 학습기가 반환하는 분류기가 원래 가설 클래스에 속한다는 보장이나 그 해석 가능성을 포기한다는 뜻이다 — 가설 클래스 자체의 구조(예: 선형 분류기)를 유지해야 하는 실무 상황에는 이 결과가 직접 적용되지 않는다.

References

• [1] Hanneke, Larsen, and Zhivotovskiy, “Revisiting Agnostic PAC Learning”, Proceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2024).
• [2] Asilis, Høgsgaard, and Velegkas, “On Agnostic PAC Learning in the Small Error Regime”, arXiv:2502.09496 (2026).

P2. Muon on the Stiefel Manifold Admits an Exact Closed-Form Update

Authors	Mikhail Solonko, Molozhavenko Alexander, Maxim Rakhuba
Venue	arXiv:2608.06218
Tags	Muon optimizer

More details

Background

• 다루는 문제: Muon은 스펙트럴 노름 기준 최속강하로 이해되는 행렬-인식(matrix-aware) 최적화기로 [1] [2], 최근 대형 언어모델 프리트레이닝에서 학습 속도를 눈에 띄게 높인다고 보고되며 빠르게 채택되고 있다. 신경망의 일부 파라미터(저랭크 어댑터, 직교성 제약이 있는 층 등)는 열이 서로 정규직교하는 행렬들의 공간인 Stiefel manifold 위에 놓여야 하는데, Muon을 여기로 확장하려는 기존 시도들은 tangent-space 위의 최적화 부분문제를 근사적·반복적으로만 풀거나(스텝마다 계산 비용이 크게 늘어남), 문제 자체를 완화(relax)해 정확한 tangent-space 문제를 피해갔다 — 정확한 닫힌 형태 해는 알려져 있지 않았다.

Summary

• 기여: Stiefel Muon 문제를 스큐-대칭(skew-symmetric) 행렬에 대한 동치 문제(“Skewon 문제”)로 재정식화하면, 원래 문제가 사실은 정확한 닫힌 형태 해를 갖는다는 것을 보인다. **핵심 정리(Theorem 2)**는 Skewon 문제가 원래 문제의 완화가 아니라 진짜 동치임을 증명한다 — 스큐-대칭 행렬 $N$이 비특이(nonsingular)일 때 해는 $Y_{\text{opt}}=-\mathrm{msign}(N)=-U{V}^{\top }$(행렬 부호함수, $N$의 극분해에서 나오는 $U,V$)로 명시적으로 주어진다.
• 이를 구현한 Skewon 알고리즘 두 버전을 제시한다: 일반적인 경우는 Newton–Schulz 반복으로 행렬 부호함수를 계산하고(복잡도 $O(n^3)$), $p\ll n$인 경우(열의 수가 행보다 훨씬 적은 상황)는 QR 분해를 이용해 복잡도를 $O(n{p}^2)$로 낮춘다 — Muon 자체의 점근적 복잡도와 같아진다.
• 매끄러운 비볼록(non-convex) 목적함수에 대한 1차 수렴 보장을 증명한다: ${\min }_{t\in \{0,\dots ,T-1\}}\Vert \mathrm{grad}f(X_t){\Vert }_F\le \sqrt{8p\Delta L/T}$ ($\Delta$는 초기 함수값과 최적값의 차, $L$은 립시츠 상수).
• Bernstein, Cesista, Su의 방법, Riemannian 방법, iMuon 등 5개 경쟁 방법과 여러 행렬 크기에서 비교한 수치실험으로, Skewon이 Muon과 같은 점근적 계산복잡도를 유지하면서 더 정확한 해를 낸다는 것을 확인했다.

Discussion

• 왜 중요한가: Muon이 이미 실제 대형 모델 프리트레이닝에 쓰이기 시작했다는 점에서, 이 논문처럼 그 확장판의 “근사”를 “정확한 닫힌 형태”로 바꾸는 결과는 이론적 정제에 그치지 않고 직접적인 실무 효율(정확도 손실 없이 Muon과 같은 계산 비용으로 직교성 제약을 다룰 수 있음)로 이어질 잠재력이 있다.
• 다만 저자들 스스로 밝히듯, 일반적인 경우(Algorithm 1)에 필요한 SVD 기반 극분해 계산은 Newton–Schulz 반복 자체보다 “일반적으로 GPU 친화적이지 않다” — 이 논문이 제공하는 것은 정확도-복잡도 트레이드오프에서 우월한 알고리즘 두 개(일반적인 경우, $p\ll n$인 경우)이지, 모든 경우에 걸쳐 Newton–Schulz 반복만큼 하드웨어 친화적인 단일 해법은 아니다. GPU 상에서 실제 벽시계 시간(wall-clock) 이득이 얼마나 되는지는 이 논문의 수렴 보장이나 수치실험 자체와는 별개의 질문으로 남는다.
• 수렴 보장은 매끄러운 비볼록 설정에 국한되며, 실제 LLM 프리트레이닝 손실함수가 이 가정을 얼마나 잘 만족하는지, Stiefel 제약이 걸린 파라미터에 이 최적화기를 실제로 적용했을 때 최종 모델 품질(downstream 성능)에 어떤 차이를 만드는지는 이 논문이 다루는 범위(최적화 부분문제 자체의 정확성과 수렴) 밖이다 — 이 결과는 “이 특정 부분문제를 정확하고 효율적으로 푼다”는 주장이지, “Stiefel-제약 Muon이 실제로 더 나은 모델을 만든다”는 주장은 아니다.

References

• [1] Jordan, “Muon: An optimizer for hidden layers in neural networks” (2024).
• [2] Bernstein and Newhouse, “Old Optimizer, New Norm: An Anthology”, arXiv:2409.20325 (2024).