arXiv:1905.07342

Pair-Matching: Links Prediction with Adaptive Queries

Christophe Giraud, Yann Issartel, Luc Lehéricy, Matthieu Lerasle

제출 2019-05-17

원문 초록

The pair-matching problem appears in many applications where one wants to discover good matches between pairs of entities or individuals. Formally, the set of individuals is represented by the nodes of a graph where the edges, unobserved at first, represent the good matches. The algorithm queries pairs of nodes and observes the presence/absence of edges. Its goal is to discover as many edges as possible with a fixed budget of queries. Pair-matching is a particular instance of multi-armed bandit problem in which the arms are pairs of individuals and the rewards are edges linking these pairs. This bandit problem is non-standard though, as each arm can only be played once. Given this last constraint, sublinear regret can be expected only if the graph presents some underlying structure. This paper shows that sublinear regret is achievable in the case where the graph is generated according to a Stochastic Block Model (SBM) with two communities. Optimal regret bounds are computed for this pair-matching problem. They exhibit a phase transition related to the Kesten-Stigum threshold for community detection in SBM. The pair-matching problem is considered in the case where each node is constrained to be sampled less than a given amount of times. We show how optimal regret rates depend on this constraint. The paper is concluded by a conjecture regarding the optimal regret when the number of communities is larger than 2. Contrary to the two communities case, we argue that a statistical-computational gap would appear in this problem.

함께 살펴볼 논문

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

arXiv:2607.09441v1math.ST공통 태그 Community Detection, Stochastic Block Model

다항 시간 내 준최적 노드-프라이빗 커뮤니티 추정

Near-optimal node-private community estimation in polynomial-time

이 논문에서 우리는 Klopp & Zadik (2026)의 미해결 문제를 해결하여, 확률적 블록 모델(stochastic block model)에서의 정확 복원(exact recovery)에 대해 그들의 지수 시간 노드-프라이빗 알고리즘의 성능에 근접하는, 높은 확률을 보장하는 다항 시간 노드-프라이빗 알고리즘을 제시한다. 우리의 결과는 페널티 가능도 함수에 대해 명시적으로 구성된 립시츠 대리 함수(Lipschitz surrogate)와, 다항 시간 내에 지수 메커니즘(exponential mechanism)으로부터 커뮤니티 레이블을 샘플링하는 신중하게 고안된 수용-기각 알고리즘(accept-reject algorithm)을 포함한다. 우리는 제안 알고리즘의 프라이버시, 실행 시간, 유용성을 엄밀하게 분석하며, 커뮤니티 수 K가 노드 수 n에 대해 로그 수준으로 증가하는 경우에도 프라이버시 매개변수 epsilon이 log(n)으로 증가할 때 정확 복원에 대한 미니맥스 수렴률을 달성할 수 있음을 보임으로써, 이 설정에서 프라이버시 비용에 관해 알려진 하한과 일치함을 증명한다.

arXiv:2606.25986v2cs.LG공통 태그 Prediction

지정가 주문서 예측을 위한 추론-연산 프런티어

The Inference-Compute Frontier for Limit Order Book Prediction

우리는 FI-2010에서 지정가 주문서 예측에 대한 경험적 추론-연산 프런티어를 규명한다. 저연산 및 중연산 모델에 적합시킨 멱법칙은, 해당 적합에서 가장 큰 예산의 $56$--$2{,}515$배에 달하는 연산량을 가진, 제외된 MLPLOB 방식의 믹서 계열까지 외삽된다. 아홉 개의 폴드와 다섯 개의 예측 수평선에 걸쳐, 실현된 목표 프런티어에서 통합 $R^2$는 $0.934$이며 상수 종점 외삽보다 RMSE가 59\% 낮고, 제외된 모든 운용점에서는 $0.731$이다. 측정된 지연 시간은 더 약한 관계를 보이며 모델 계열의 순위를 바꾼다. 따라서 우리는 연산을 조밀한 시간 및 특징 혼합에 집약하도록 FastBiNLOB을 설계한다. H120은 다섯 개의 시드 모두에서 네 개의 수평선 중 두 개에서 발표된 최첨단 macro-F1을 능가한다. 우리의 CPU/MPS 프로토콜에서 H96은 W128 MLPLOB 기준 대비 중앙값 지연 시간을 23.6\% 줄이고, H120은 TLOB에서 착안한 이중 축 어텐션 기준 대비 60.2\% 줄인다.

arXiv:2609.27144v2cs.LG공통 태그 Prediction

미관측 교란 변수에 강건한 위험 점수 학습

Learning Risk Scores Robust to Unobserved Confounders

미관측 교란의 영향을 받는 역사적 관찰 데이터로부터, 희소 자원이나 개입 대상 개인의 우선순위를 정하기 위한 위험 점수를 학습하는 문제를 다룬다. 누가 희소 자원을 받을지에 대한 결정은 설문 응답과 같이 기록된 특성에 기반한 위험 점수에 의해 종종 안내된다. 이러한 위험 점수는 개인의 특성, 배분 결정, 결과에 대한 역사적 기록인 관찰 데이터로부터 직접 학습되는 경우가 점점 늘고 있다. 역사적 배분 정책이 도입한 바이어스를 보정하는 역 성향 가중치(inverse propensity weighting, IPW)와 같은 표준 방법은, 역사적 결정 과정이 기록된 특성으로 완전히 설명될 수 있다면 정확한 위험 점수를 학습하는 데 사용될 수 있다. 그러나 실무에서는 역사적 결정이 종종 기록되지 않은 정보에 의존하여, 학습된 위험 점수가 과거 우선순위를 이끌었던 기록되지 않은 상황을 가진 개인들을 정확히 체계적으로 과소 우선순위화하게 만든다. IPW를 기반으로, 이러한 종류의 미관측 교란에 강건한 위험 점수를 학습하는 방법을 제안한다. 미관측 교란 하에서는 성향 가중치를 신뢰할 수 있게 추정할 수 없으므로, 대신 관측 가능한 데이터와 교란 정도에 대한 도메인 정보 기반 추정치로 결정되는 불확실성 집합에 속하는 것으로 취급하며, 인과 추론(causal inference)의 민감도 분석(sensitivity analysis)과 Wasserstein 분포적 강건 최적화(Wasserstein distributionally robust optimization)를 결합한다. 그 결과 강건 위험 점수 학습 문제는 표본 기반 근사를 허용하며, 이를 기성 솔버와 호환되는 지수 원뿔 프로그램(exponential cone program)으로 재공식화한다. UCI Machine Learning Repository의 데이터셋에서 파생된 반합성(semi-synthetic) 데이터에서 접근법의 효과를 입증한다. 제안 방법은 다른 지표를 손상하지 않으면서, 전통적 벤치마크 대비 보정(calibration)을 최대 29.2%까지, 최신(state of the art) 대비 최대 11.1%까지 개선한다.

arXiv:2609.32652v2cs.AI공통 태그 Prediction

기하학 기반 소프트 상태 추상화의 예측 한계 및 쿱만 폐포

Prediction Limits and Koopman Closure of Geometry-Induced Soft State Abstractions

소프트 상태 표현(soft state representation)은 각 상태에 합이 1인 음이 아닌 클래스 가중치 벡터를 할당합니다. 본 연구에서는 이러한 가중치의 구성과 상태 동역학이 선형 예측의 정확도를 어떻게 공동으로 결정하는지 조사합니다. 고정된 임의의 가측 표현(measurable representation)에 대해, 지정된 스펙트럼 노름(spectral norm) 한계를 가진 행렬들 중 모집단 최소 평균 제곱근 예측 오차에 대한 유한 표본 신뢰 하한을 유도합니다. 이 한계는 각 참조 클래스 내 후속 좌표의 변동과 소프트 입력이 제공할 수 있는 개선 정도를 비교합니다. 또한 예측 행렬을 적합하지 않고도 독립적인 평가 쌍으로부터 계산됩니다. 선택된 허용 오차를 초과하는 한계는 해당 행렬 클래스 전체에 대해 그 허용 오차를 배제하며, 0인 한계는 결론을 내릴 수 없음을 의미합니다. 커널 아핀 헐 머신(Kernel Affine Hull Machines)을 사용하여 구성된 좌표의 경우, 재구성 점수 마진이 참조 라벨과의 불일치를 제어하며 예측 오차 한계에 반영됩니다. 정확한 결정론적 선형 진화 하에서, 잉여 계수 벡터를 고려하여 쿱만(Koopman) 및 재생핵 힐베르트 공간(RKHS) 수반 해석도 확립합니다. 4개 상태 연구에서는 보고된 117,000개의 복제 데이터셋에 걸쳐 신뢰 하한을 해석적으로 알려진 최적값과 비교합니다. 그런 다음 파일럿 데이터에서 선택된 반데르폴(Van der Pol) 표현을 두 가지 전이 법칙 각각에 대해 32개의 독립적인 데이터셋에서 평가합니다. 보고된 한계는 적합된 행렬 노름에서는 양수이지만, 더 큰 노름 한계에서는 0이 될 수 있습니다. 추가적인 예측 연구를 통해 좌표 변동, 공통 예측 목표, 장기 시계(long-horizon) 오차를 검토합니다. 이러한 결과는 재구성 클래스와의 일치도, 달성 가능한 예측 정확도, 정확한 연산자 폐포(operator closure)를 구별합니다.

arXiv:2609.30277v2cs.LG공통 태그 Community Detection

고정된 확산 없는 고정점: 수렴하는 테스트 시점 연산을 위한 암시적 신경 층

Fixed Points Without Fixed Diffusion: Implicit Neural Sheaves for Convergent Test-Time Computation

암시적 그래프 신경망(IGNN)은 노드 표현을 그래프 신경 연산자의 고정점(fixed point)으로 정의하여 실질적으로 무한한 깊이의 전파, 반복(iteration) 독립적인 매개변수화, 유연한 테스트 시점 연산(test-time computation)을 가능하게 합니다. 그러나 이러한 이점은 평형점이 유일하며 고정점 반복을 통해 도달할 수 있는지 여부에 달려 있습니다. 기존의 구조들은 이러한 보장을 얻기 위해 순환 업데이트에 제약을 가하는 경우가 많아 평형 상태에서 사용 가능한 변환을 제한했습니다. 이는 핵심적인 질문을 제기합니다: IGNN이 평형 정식화의 고유한 강점을 유지하면서 더 풍부한 엣지 의존적 변환을 통해 표현력을 얻을 수 있을까요? 본 논문에서는 적응형 신경 층(neural-sheaf) 전파를 갖춘 준동차(subhomogeneous) 심층 평형 아키텍처인 SheafDEQ를 소개합니다. 학습된 행렬 값 층 제한 사상(sheaf restriction map)은 이웃한 표현들을 정렬, 혼합 또는 반전시킬 수 있습니다. 완만한 정칙성 조건 하에서, SheafDEQ가 임의의 양의 초기 상태로부터 고정점 반복을 통해 전역적으로 도달 가능한 유일한 평형점을 가짐을 증명합니다. 나아가 축약성(contractivity)은 유계된 통신 지연(staleness) 하에서도 수렴을 보장합니다. 본 연구는 반복적인 비국소적 집계가 필요한 분산 추론(inference) 태스크와 연결 재구성이 점차 커뮤니티 간 상호작용을 선호하게 되는 커뮤니티 탐지 태스크에서 SheafDEQ를 평가합니다. SheafDEQ는 Sums, MNIST Terrain, Coordinates 태스크 및 연결성이 점차 이종친화적(heterophilic)으로 변하는 커뮤니티 탐지에서 암시적 베이스라인보다 향상된 성능을 보입니다. 또한 SheafDEQ는 평형 보장이 없는 순환 모델들과 비교해도 경쟁력을 유지합니다. 연속 반복 진단 결과 유한 구간(finite-horizon) 대조군과 달리 100회 반복까지 잔차가 감소하고 테스트 정확도가 유지됨을 확인하였으며, 지연 업데이트 실험에서는 유계된 통신 지연에 대해 낮은 민감도를 나타냈습니다.

arXiv:2610.02442v1cs.LG공통 태그 Prediction

AI 기반 열 인지형 데이터 센터 용량 계획

AI-driven Thermal-aware Data Center Capacity Planning

대규모 언어 모델(LLM)의 등장은 데이터 센터의 열 관리에 중대한 도전 과제를 안겨주었습니다. LLM을 위한 집중적인 GPU 연산은 국소적인 핫스팟(hotspot)을 발생시킵니다. 더욱이 학습(training) 및 추론(inference) 급증 시 발생하는 급격한 열 부하 변동은 실시간 냉각 대응을 예측하고 제어하기를 더욱 어렵게 만듭니다. 데이터 센터의 열 인지형(thermal-aware) 용량 계획에는 막대한 비용이 드는 고정밀 CFD 시뮬레이션이 다수 필요합니다. AI 모델은 이전에 보지 못한 설계에 대해서도 실시간 예측을 수행할 수 있습니다. 그러나 기존 연구들은 예측 오차가 크거나 데이터 센터 운영에 대해 지나치게 단순화된 가정을 두고 있습니다. 본 연구에서는 실제 데이터 센터를 대상으로 수 초 만에 열 인지형 용량 계획을 수행할 수 있는 AI 기반 프레임워크를 제시합니다. 내장된 AI 모델은 수많은 주요 파라미터(랙 전력, 서버 전력, 서버 배치, HVAC 설정 등)로부터 학습하며, 수 밀리초 이내에 온도 예측을 제공합니다. 이 AI 모델을 고정밀 CFD 시뮬레이션을 기준으로 검증한 결과, 보지 못한 새로운 데이터 센터 설계에 대해서도 10,000배의 속도 향상과 함께 높은 정확도를 달성할 수 있음을 보여줍니다. 저자들은 이 AI 모델을 바탕으로 열 인지형 용량 계획 프레임워크를 설계했습니다. 이 프레임워크는 데이터 센터 설계자와 운영자가 워크로드 분배와 HVAC 냉각 효율을 즉각적으로 최적화할 수 있도록 지원합니다.

토론

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