arXiv:2410.13548v3 cs.LG

적응형 및 무지형 통계적 적대자의 동등성

Adaptive and oblivious statistical adversaries are equivalent

Guy Blanc, Gregory Valiant

제출 2024-10-17

저자 비고

arXiv Comments

Appeared at STOC' 25

한국어 초록

본 연구에서는 적대자(adversary)가 샘플을 오염시킬 때 학습(learning)과 같은 통계적 작업을 수행할 수 있는 능력에 관한 근본적인 문제를 해결합니다. 이러한 적대자는 가할 수 있는 오염의 유형과 샘플에 대해 보유한 지식 수준에 따라 정의됩니다. 후자는 오염을 선택할 때 샘플의 내용을 알고 있는 샘플-적응형(sample-adaptive) 적대자와, 그렇지 않은 샘플-무지형(sample-oblivious) 적대자를 구분합니다. 우리는 모든 오염 유형에 대해, 샘플-적응형 적대자와 샘플-무지형 적대자가 샘플 크기에서 다항 인자(polynomial factors) 차이에 불과할 정도로 동등함을 증명합니다. 이는 [BLMT22]에서 제기되고 [CHL+23]에서 추가로 탐구되었던 주요 미해결 문제를 해결합니다. 구체적으로, 샘플-무지형 적대자가 입력을 오염시키는 상황에서도 통계적 작업을 해결하는 임의의 알고리즘 $A$를 고려해 보겠습니다. 우리는 그에 대응하는 샘플-적응형 적대자가 입력을 오염시킬 때 동일한 작업을 해결하는 알고리즘 $A'$가 존재함을 보입니다. $A'$의 구성은 단순하며 $A$의 계산 효율성을 유지합니다. 즉, $A$가 사용하는 것보다 다항식만큼 더 큰 샘플을 요청한 다음 균등한 무작위 부분 샘플(subsample)에서 $A$를 실행하는 방식입니다.

원문 초록

We resolve a fundamental question about the ability to perform a statistical task, such as learning, when an adversary corrupts the sample. Such adversaries are specified by the types of corruption they can make and their level of knowledge about the sample. The latter distinguishes between sample-adaptive adversaries which know the contents of the sample when choosing the corruption, and sample-oblivious adversaries, which do not. We prove that for all types of corruptions, sample-adaptive and sample-oblivious adversaries are \emph{equivalent} up to polynomial factors in the sample size. This resolves the main open question introduced by [BLMT22] and further explored in [CHL+23]. Specifically, consider any algorithm $A$ that solves a statistical task even when a sample-oblivious adversary corrupts its input. We show that there is an algorithm $A'$ that solves the same task when the corresponding sample-adaptive adversary corrupts its input. The construction of $A'$ is simple and maintains the computational efficiency of $A$: It requests a polynomially larger sample than $A$ uses and then runs $A$ on a uniformly random subsample.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2410.13548v3

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2609.25576v1stat.ML공통 태그 Computational Efficiency, sample complexity

비점근적 분석을 갖춘 확장 가능한 최소 부피 단체 추정

Scalable Minimum-Volume Simplex Estimation with Non-asymptotic Analysis

본 연구에서는 $K$차원 단체(simplex)의 내부에서 균등하게 추출된 $N$개의 독립항등분포(i.i.d.) 점들로부터 해당 단체를 추정하는 문제를 다룹니다. 관측치는 $K+1$개의 미지 원형(prototype)들의 볼록 결합(convex combination)입니다. 기존의 다항 시간(polynomial-time) 추정량들은 샘플당 3차(cubic) 계산량을 요구하거나 $O(NK)$ 메모리를 필요로 하여, $N\sim 10^6$--$10^8$ 규모에서는 비실용적입니다. 본 논문에서는 최소 부피 원리를 신경 암시적 형태(neural implicit form)로 재표현한 DeepMVSA를 제안합니다. 경량 좌표 네트워크(coordinate network)가 혼합 가중치를 생성하고 삼각 LU 형태의 매개변수화가 쌍대 단체 행렬을 생성함으로써, 학습 가능한 상태 메모리를 $N$과 무관한 $O(K^2)$으로 줄이고 데이터 1회 패스당 비용을 $O(NK^2)$으로 감소시킵니다. 본 연구는 국소화된 대리 추정량에 대해 다항 시간 벤치마크 차수의 비점근적(non-asymptotic) 샘플 복잡도 경계를 증명합니다. 또한 부피 팽창 제어 및 명시적 축소 바이어스를 갖춘 신경망 목적 함수의 모든 전역 최소해(global minimizer)에 대한 오라클 부등식, 명시적 포락선 사건(envelope event)에서 통계적, 근사, 최적화(optimization) 및 포함 잔차 항을 분리하는 조건부 종단간(end-to-end) 오차 예산, 그리고 두 점 하한(two-point lower bounds)을 증명합니다. 즉, $N$과 무관하게 고정된 임의의 노이즈 수준 $\sigma>0$에서 $N^{-1/2}$ 스케일링(scaling)은 $N$ 지수 측면에서 개선될 수 없음을 보입니다. 최대 $N=10^8$개의 합성 관측치를 사용한 실험은 예측된 정확도 및 스케일링과 일치하며, 약 $10^7$ 픽셀의 실제 장면에 대한 실현 가능성을 입증합니다.

arXiv:2609.25498v1cs.NE공통 태그 Computational Efficiency, Adversarial Robustness

범용 프랙털 자연어 의사결정 맵: 이종 도메인 전반의 실시간 엣지 트리아지

Universal Fractal Natural Language Decision Map: Real-Time Edge Triage Across Heterogeneous Domains

대규모 언어 모델(LLM)을 런타임 운영 트리아지에 배치하면 지나친 지연(>100–500 ms), 높은 VRAM 요구(>4–8 GB), 과도한 에너지 소모가 발생한다. Mandelbrot Fractal Neural Synthesis(Dagli et al., 2026)를 확장하여, 본 논문은 werr 머신 네이티브 엣지 반사(reflex) 런타임과 프로덕션 answerr 플랫폼(https://answerr.me)을 통해 구현한 Universal Fractal Natural Language Decision Map을 제시한다. 저장된 가중치 텐서 없이(VRAM 0 Bytes) 전적으로 동작하는 이 엔진은 Mandelbrot 집합의 카오틱 경계를 따라 24바이트 좌표 시드를 동적으로 변조하고 4분면 탈출 동역학을 평가하여 결정론적 의사결정—noul(Boolean), choice(범주형), score(서열형)—을 합성한다. 생물학적 System-One 반사 아크에서 영감을 받아, 엔진은 다음을 도입한다: (i) 도메인 투영기 Phi_D를 갖춘 Auto-Seed Router로 선형 베이스라인 대비 +28.8% 정확도 향상; (ii) 토큰 엔트로피와 음성학적 스펙트럼 밀도에 기반한 정보 이론적 음향 감쇠 필터(Information-Theoretic Acoustic Damping Filter)로 프롬프트 인젝션에 격리(실증 우회 0.0%; 95% Wilson CI: [0.0%, 30.8%])하면서 탈출 반복을 45.8% 가지치기(처리량 2.5배 가속, 지연 3.31 ms); (iii) O(1) 지수 이동 평균(EMA, alpha=0.03)과 분면 위상 회전을 사용하는 Organic Dynamic Calibration 프레임워크로 위치 바이어스 제거. 베어 메탈 인프라(api.answerr.me:4431)에서 1,150건 이상 검증된 의사결정(3,200건 이상 질문)에 대해 벤치마크하고 독립 JevBench 스위트에서 세계 1위(81.65%)를 기록한 이 프레임워크는 92.6% 매크로 정확도(95% CI: [90.8%, 94.1%])와 7.08 ms 중앙값 CPU 지연을 달성한다. OpenAI 호환 API(/v1/chat/completions)를 제공하며 마이크로컨트롤러와 32바이트 EVM 스마트 계약에서의 실현 가능성을 보여준다.

arXiv:2610.10666v2cs.LG공통 태그 Adversarial Robustness

적대적 학습된 신경망의 돌출도 맵 희소성에 대한 규명

Explaining the Saliency Map Sparsity of Adversarially-Trained Neural Networks

심층 신경망이 특정 예측을 수행하는 이유를 이해하는 것은 신경망의 안전한 배포를 위해 매우 중요합니다. 컴퓨터 비전(CV) 분야에서는 예측에 가장 큰 영향을 미치는 이미지 영역을 강조하는 돌출도 맵(saliency map)이 널리 사용되는 설명 방식으로 남아 있습니다. 한 가지 실증적 관찰 결과는 적대적 학습(adversarial training)된 신경망의 그래디언트 돌출도 맵에서 뚜렷한 희소성(sparsity)이 나타난다는 점입니다. 본 논문에서는 2개 층(layer) 렐루(ReLU) 네트워크를 대상으로 이러한 현상에 대한 이론적 설명을 제안합니다. 우리는 특정 손실 함수에서 유효한 것으로 밝혀진 적대적 학습과 가중치 감쇠(weight-decay) 페널티 및 적대적 전변동(total variation) 항이 추가된 경험적 위험 최소화 사이의 기존 동등성 관계를 기반으로 논의를 전개합니다. 데이터 포인트 수와 뉴런 수가 증가하고 정규화 매개변수가 적절한 비율로 0으로 수렴함에 따라, 최소화기(minimizer)가 최소 그래디언트 및 배런 노름(Barron norm)을 갖는 베이즈 분류기(Bayes classifier)로 수렴함을 증명합니다. $\ell_\infty$ 공격을 사용하는 적대적 학습의 경우 그래디언트 노름이 비등방적(anisotropic)이며 축에 정렬된/희소한 그래디언트를 선호하기 때문에 이러한 희소성이 나타납니다. 우리는 자연 학습된 모델과 적대적 학습된 모델의 그래디언트 $\ell_1$-노름 및 임계화된 희소성을 평가하여 이론적 발견을 실험적으로 제시합니다.

arXiv:2609.26705v2quant-ph공통 태그 sample complexity

보손 가우시안 상태는 언제 고전적으로 학습할 수 있는가?

When are bosonic Gaussian states classical to learn?

물리학의 근본적인 질문 중 하나는 양자계에서 고전적 거동이 언제 나타나는가이다. 보손 가우시안 상태(bosonic Gaussian state)는 빛의 고전적 장(field) 거동과 본질적인 양자적 성질을 모두 포착하므로, 이러한 양자-고전 경계를 탐구하기에 자연스러운 환경을 제공한다. 본 연구에서는 학습 이론의 관점에서 이 문제를 다루며 다음과 같이 묻는다. 보손 가우시안 상태는 언제 고전적으로 학습할 수 있는가? 즉, n-모드 보손 가우시안 상태를 고전적인 2n변량 가우시안 분포를 학습할 때 필요한 만큼 적은 샘플과 그만큼 단순한 연산으로 학습할 수 있는 조건은 (있다면) 무엇인가? 우리는 상태의 열적 요동(thermal fluctuation)에 의해 결정되는 학습 가능성의 매끄러운 크로스오버를 규명한다. - 차가운 가우시안 상태는 학습 측면에서 비고전적이다. 공분산 행렬이 $\Sigma\le(\frac12+O(\frac1n))I$를 만족하여 진공 공분산에 가까운 경우, 단일 복사본(single-copy, 즉 얽힘이 없는) 측정 하의 토모그래피(tomography)는 근본적으로 $\Omega(n^3)$개의 복사본을 필요로 하며, 이는 고전적 가우시안 분포를 학습하는 샘플 복잡도 $\Theta(n^2)$를 엄밀하게 초과한다. 우리는 소수 복사본에 대한 얽힘 측정이 허용되더라도 이러한 어려움이 지속됨을 보인다. - 따뜻한 가우시안 상태는 학습 측면에서 고전적이다. 열적 요동이 진공 잡음을 초과하여 임의의 매개변수 $\nu>0$에 대해 $\Sigma\ge(\frac12+\nu)I$로 나타내지는 경우, 단일 복사본 토모그래피에는 $N=\Theta\left(n^2\min(n,1+\nu^{-1})\right)$개의 복사본이 필요함을 증명한다. 이 한계는 타이트(tight)하며, 단순하고 비적응적(non-adaptive)이며 얽힘이 없는 헤테로다인(heterodyne) 측정으로 달성된다. 특히 $\nu=\Omega(1)$인 경우 샘플 복잡도는 $\Theta(n^2)$로 줄어들어 고전적인 경우와 일치한다. 우리의 결과는 보손 가우시안 상태의 학습 가능성에서 나타나는 양자-고전 크로스오버를 엄밀하게 규명하고, 근본 물리학과 통계적 학습 이론 사이의 새로운 연결고리를 드러내며, 실제 센싱 실험에도 시사점을 가진다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.