벡터 값 선형 회귀에서 가중치 부여 데이터 선택의 정확한 복원 임계값
Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression
한국어 초록
본 논문에서는 Hanneke, Moran, Shlimovich, Yehudayoff의 COLT 2025 미해결 문제인 "회귀 태스크를 위한 데이터 선택"의 질문 4 중 임계값 부분을 해결합니다. 우리는 $x\in\mathbb{R}^d$ 및 $y\in\mathbb{R}^m$에 대해 제곱 손실(loss) $\ell_{(x,y)}(W)=\lVert Wx-y\rVert_2^2$을 갖는 벡터 값 선형 회귀를 연구합니다. 학습기는 최소 프로베니우스 노름(Frobenius-norm) 경험적 위험 최소화기를 반환합니다. 우리는 모든 유한 데이터셋(dataset)에서 전체 데이터 손실을 복원하기 위한 가중치 부여 예제의 최소 예산이 정확히 $n^{\star}(d,m)=(m+1)d$임을 증명합니다. 또한 임계값에 근접한 예산에서의 가중치 부여 선택 프로파일 $F_{\mathrm{weighted}}(d,m,n)$을 규명하여 $F_{\mathrm{weighted}}(d,m,(m+1)d-1)=1+1/(dm^2)$임을 보입니다. 우리는 모든 $m$에 대해 이미 알려진 생성 예산(spanning-budget) 값인 $F_{\mathrm{weighted}}(d,m,d)=d+1$과 $n<d$일 때 $F_{\mathrm{weighted}}(d,m,n)=\infty$임을 재현합니다. 미해결된 가장 작은 중간 셀인 $(d,m)=(2,2)$에 대해 $F_{\mathrm{weighted}}(2,2,3)\in[13/8,15/8]$ 및 $F_{\mathrm{weighted}}(2,2,4)\in[5/4,3/2]$임을 증명합니다. 추측된 정확한 값인 $13/8$과 $5/4$를 최대 7개의 원자를 갖는 원 위의 유한 모멘트 문제로 귀결시키고 이에 대한 구조적 증거를 제시합니다. 상한은 고정 기저 원뿔 압축 보조정리(fixed-basis conic compression lemma), 극대 인증(maximal certificate)에 대한 행렬식-면 강성 정리(determinant--facet rigidity theorem), 그리고 평균이 0인 가중치 부여 점 시스템에 대한 샤프 희소화 보조정리(sharp sparsification lemma)를 사용합니다. 이러한 도구들은 그 자체로도 독립적인 관심을 가질 수 있습니다. 또한 우리는 $2d$개의 점으로 이루어진 어떤 가중치 부여 선택도 최적 손실을 복원하지 못하는 $d=m=2$인 명시적인 6개 점 정수 데이터셋을 제시합니다. 따라서 스칼라에서 충분했던 예산 $2d$는 벡터 값 출력으로 확장되지 않습니다. $m\ge2$에 대한 우리의 새로운 회귀 프로파일 결과는 $m=1$에 대한 스칼라 이론을 확장합니다.
원문 초록
We resolve the threshold part of Question 4 of the COLT 2025 open problem "Data Selection for Regression Tasks" of Hanneke, Moran, Shlimovich and Yehudayoff. We study vector-valued linear regression with square loss $\ell_{(x,y)}(W)=\lVert Wx-y\rVert_2^2$, where $x\in\mathbb{R}^d$ and $y\in\mathbb{R}^m$. The learner returns the minimum-Frobenius-norm empirical risk minimizer. We prove that the minimal budget of weighted examples for recovering the full-data loss on every finite dataset is exactly $n^{\star}(d,m)=(m+1)d$. We determine the weighted selection profile $F_{\mathrm{weighted}}(d,m,n)$ at the near-threshold budget: $F_{\mathrm{weighted}}(d,m,(m+1)d-1)=1+1/(dm^2)$. We recover the known spanning-budget value $F_{\mathrm{weighted}}(d,m,d)=d+1$ for every $m$, and $F_{\mathrm{weighted}}(d,m,n)=\infty$ for $n<d$. For the smallest open intermediate cell $(d,m)=(2,2)$ we prove $F_{\mathrm{weighted}}(2,2,3)\in[13/8,15/8]$ and $F_{\mathrm{weighted}}(2,2,4)\in[5/4,3/2]$. We reduce the conjectured exact values $13/8$ and $5/4$ to a finite moment problem on the circle with at most seven atoms and assemble structural evidence for it. The upper bounds use a fixed-basis conic compression lemma, a determinant--facet rigidity theorem for maximal certificates, and sharp sparsification lemmas for zero-mean weighted point systems. These tools may be of independent interest. We also exhibit an explicit six-point integer dataset with $d=m=2$ on which no weighted selection of $2d$ points recovers the optimal loss. Thus the scalar sufficient budget $2d$ does not extend to vector-valued outputs. Our new regression-profile results for $m\ge2$ extend the scalar theory for $m=1$.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2608.30254v2
- arXiv:2608.30254v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
선형 회귀에서 가중치 기반 데이터 선택의 정확한 위험 비율
Exact Risk Ratios for Weighted Data Selection in Linear Regression
고정된 학습자(learner)는 얼마나 많은 데이터를 유지해야 하는가? Hanneke, Moran, Shlimovich, Yehudayoff(COLT 2025)는 최소 노름 경험적 위험 최소화기(minimum-norm empirical risk minimizer)를 사용하는 선형 회귀에 대해 이 질문을 제기했다. 선택기(selector)는 유한 데이터셋 $D\subseteq R^d\times R$를 확인하고 음이 아닌 가중치를 갖는 최대 $n$개의 예제를 유지하며, $F_w(d,n)$은 학습된 예측기의 전체 데이터 손실과 최적 손실 사이의 최악의 경우 비율이다. 이 값은 $n<d$일 때 $\infty$, $n=d$일 때 $d+1$, $n\ge2d$일 때 $1$이며, $d<n<2d$ 영역은 미해결 과제로 남아 있었다. 본 연구에서는 여러 사례를 해결한다. 모든 $d$에 대해 $F_w(d,2d-1)=1+1/d$임을 증명하여, 원 논문에서 증명 없이 언급되었던 주장을 확인한다. 또한 해당 공식으로 다루어지지 않는 가장 작은 세 셀인 $F_w(3,4)=5/3$, $F_w(4,5)=2$, $F_w(4,6)=3/2$를 증명한다. 모든 중간 예산 $n=d+k$에 대해 하한 $F_w(d,d+k)\ge1+Γ_{d,k}$를 증명하며, 여기서 $Γ_{d,k}$는 $d$의 균형 분할에 대한 명시적인 조화 수량이다. 이 하한은 백색화된 시스템(whitened systems)이 직교 회로 블록으로 분할되는 데이터셋 클래스에서의 정확한 미니맥스(minimax) 값이다. 증명된 모든 값은 $1+Γ_{d,k}$와 같으며, 본 연구는 미해결 영역 전체에서도 이것이 성립할 것이라고 추측한다. 본 연구의 상한은 손실 기울기(loss gradient)의 양의 생성 구성(positive spanning configurations)에 대한 강성 정리와 $R^3$ 및 $R^4$에서의 작은 양의 기저(positive bases)의 표준형을 결합한다. 이러한 형태는 Cornaz, Kerleau, Royer 분류의 특수한 경우이며, 기저 외부의 모든 기울기 또한 제어한다. 차원 독립적인 극대 기저 논증은 부호 원뿔(sign-cone) 기하학을 $d+1$개 점의 선택으로 변환한다. 명시적인 반례를 통해 몇 가지 더 짧은 경로를 배제한다. 모든 상한은 구성적(constructive)이며, 고정된 차원에 대해 점 수에 대한 다항식 선택 절차를 갖는다. 특정 인스턴스에 대한 모든 수치적 주장은 정확한 유리수 또는 대수적 항등식이며, 보충 자료에서 정확한 산술로 재계산된다.
OLS 회귀를 위한 데이터 분할에 대한 분산 스케칭
Distributed Sketching on Data Partitions for OLS Regression
HARN: 이벤트 기반 다중 시간대 예측을 위한 계층적 연상 공명 네트워크
HARN: Hierarchical Associative Resonance Network for Event-Driven Multi-Timeframe Forecasting
미관측 교란 변수에 강건한 위험 점수 학습
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%까지 개선한다.
IID를 넘어서: 표 형식 파운데이션 모델은 실제로 얼마나 일반적인가?
Beyond IID: How General Are Tabular Foundation Models, Really?
DNA 파운데이션 모델이 서열 조성을 넘어 학습하는 것
What DNA Foundation Models Learn Beyond Sequence Composition
유전체 파운데이션 모델(FM)은 단순한 서열 조성을 넘어선 예측 정보를 제공하는가? 본 연구에서는 57개의 유전체 분류(classification) 데이터셋과 2개의 탐색적 유전자 발현 회귀 태스크에 걸쳐 정규화된 k-mer 빈도와 5개 DNA FM의 동결된(frozen) 표현을 비교 평가한다. 단순한 k-mer 피처는 대부분의 모델과 대등한 경쟁력을 유지한 반면, NTv3는 일관된 우위를 보였으며, 이러한 순위는 전역적으로 고정된 베이스라인, 다중 스케일 k-mer 베이스라인, 대안적인 다운스트림 프로브 전반에서 견고하게 유지된다. 추가적인 예측 유용성을 직접 검증하기 위해, 일치된 Random Forest 프로토콜 하에서 전역 6-mer 피처와 각 FM 임베딩(embedding)을 결합(concatenation)한 피처를 비교한다. NTv3는 57개 데이터셋 중 46개에서 성능을 향상시켰으나(평균 $Δ$MCC = +0.072), Caduceus는 더 작은 이득만을 제공했고 다른 모델들은 평균 MCC를 향상시키지 못했다. 또한 임베딩을 6-mer 빈도로부터 선형적으로 예측 가능한 성분과 릿지 잔차로 분해하여 선형적 복원 가능성이 다운스트림 유용성을 안정적으로 나타내지 못함을 발견했다. 정확한 6-mer 보존 셔플을 통해 태스크 관련 서열 순서 민감도를 추가로 규명했으며, 이는 NTv3에서 가장 두드러지게 나타났으나 순서 민감도 자체만으로는 예측 향상을 보장하지 않는다. 본 연구 결과는 조성 피처를 필수적인 대조군으로 확립하고 미세조정(fine-tuning) 능력에 대한 주장 없이도 동결된 유전체 표현의 부가가치를 평가하기 위한 상호보완적인 진단 방법을 제시한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
36 pages