원문 초록
We consider the sure independence screening (SIS) method, a standard feature screening approach that aims to eliminate non-informative features in ultrahigh-dimensional datasets. Although effective, SIS incurs a computational cost of order $O(np)$ for a predictor matrix of size $n\times p$, which can be prohibitively expensive when both n and p are considerable. Motivated by the multi-armed bandit (MAB) problem, we propose a more computationally efficient feature screening algorithm that reduces the cost to $O(\sqrt{n}p)$. The core idea is to progressively increase the subsample size and eliminate variables with small empirical marginal Pearson correlations, thereby avoiding unnecessary computation on unpromising features. We develop a new interpretable statistical theoretical analysis that characterizes how the subsample size affects screening accuracy, thereby revealing the balance between computational efficiency and statistical reliability. Moreover, we show that the proposed method retains the sure screening property under mild regularity conditions. Extensive numerical experiments on synthetic and real-world datasets show that BanditSIS achieves screening and prediction performance comparable to SIS while substantially reducing computational time. Our method offers a scalable and adaptive alternative to SIS, particularly well-suited for large-sample, high-dimensional applications where computational efficiency is critical.
요약
초고차원 특징 스크리닝(feature screening) 표준법인 SIS(Sure Independence Screening)의 O(np) 계산 비용을, 다중 armed bandit(MAB)에서 영감을 받은 BanditSIS가 서브샘플 크기를 점진적으로 늘리며 작은 주변 Pearson 상관 변수를 조기 제거하는 적응형 서브샘플링으로 O(√np)까지 낮춘다. 완만한 정규성 조건에서 sure screening 성질을 유지함을 보이고, 합성·실데이터 실험에서 SIS와 대등한 스크리닝·예측 성능을 훨씬 짧은 계산 시간으로 달성한다.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2509.16085v2제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
지속적 후보 집합을 활용한 선형 밴딧 가속화
Accelerating Linear Bandits with Persistent Candidate Sets
행동의 수가 $K$개로 매우 큰 고정된 집합을 갖는 선형 밴딧(linear bandit)에서는 완전 낙관적 점수 산출(exhaustive optimistic scoring)로 인해 라운드당 $\mathcal{O}(K)$회의 점수 평가가 필요하여 행동 선택 비용이 커질 수 있습니다. 본 논문에서는 $k$개의 활성 행동을 유지하고 매 라운드마다 나머지 $K-k$개 행동 중에서 $q$개의 도전자(challenger)를 균등하게 표본추출하는 Persistent Candidate LinUCB(\textsc{PC-LinUCB})를 제안합니다. 이 $k+q$개의 후보에 대해서만 점수를 평가함으로써, \textsc{PC-LinUCB}는 라운드당 점수 평가 횟수를 $\mathcal{O}(k+q)$로 줄입니다. 고정된 신뢰 수준에서 표준 선형 밴딧 학습 항과 $\mathcal{O}\left((K-k)\log(K-k)/q\right)$ 차수의 추가적 탐색 비용(discovery cost)으로 구성된 문제 독립적(problem-independent) 및 문제 의존적(problem-dependent) 고확률 후회 경계(regret bound)를 증명합니다. 특히, 이 추가 비용은 시간 지평(horizon)에 따라 증가하지 않습니다. 고정된 간격(gap)과 충분히 긴 시간 지평에 대해 균등 도전자 표본추출 조건 하에서 $\Omega\left((K-k)/q\right)$ 후회 하한을 도출하여, 부분 후보 접근 자체가 불가피한 후회 비용을 수반함을 보여줍니다. 실험 결과, \textsc{PC-LinUCB}는 유사한 수준의 후회를 유지하면서 LinUCB의 속도를 대폭 가속하며, 지속적 후보 메커니즘이 LinUCB를 넘어 다른 알고리즘으로도 확장될 수 있음을 보입니다.
FORTE: 산업용 추천 시스템을 위한 특징 평가 및 폐기 프로덕션 프레임워크
FORTE: A Production Framework for Feature Evaluation and Deprecation in Industrial Recommender Systems
프로덕션 추천 시스템에는 특징(feature) 생애주기의 비대칭성이 존재한다: 새로운 특징을 추가할 때는 어떤 지표에서든 성능 향상을 만들어내야 하지만, 특징을 제거할 때는 어떤 지표도 저하시키지 않아야 한다. 실제로는 특징 폐기의 우선순위를 정하기가 어려운데, 특징이 다른 특징들과 상호작용하는 경우, 그 중요도가 매일 변하는 경우, 프로덕션 모델이 변경되거나 데이터 드리프트가 발생하기 전에는 평가할 수 없는 경우, 다른 출시 건들과 A/B 테스트 공간을 두고 경쟁하는 경우, 온라인 A/B 테스트에서 회귀(regression)를 일으키는 경우, 또는 폐기를 조율해야 하는 여러 모델에서 소비되는 경우에는 해당 특징을 제거하지 못할 수 있기 때문이다. 우리는 특징을 발견, 검증, 제거하기 위한 모델에 구애받지 않는(model-agnostic) 프로덕션 프레임워크인 FORTE를 제시한다. 효율적인 교란(perturbation) 구현을 통해 매일 특징 평가가 가능하다. 상호작용을 고려하기 위해, FORTE는 그룹화된 제거(ablation)를 통해 모든 저랭크(low-rank) 특징으로부터 구성된 후보 특징 집합을 평가하며, 이 오프라인 결과는 온라인 A/B 테스트를 충분히 예측할 수 있어 폐기 작업을 자신 있게 온라인 테스트로 진행할 수 있게 한다. 계보 추적(lineage tracing)은 학습 데이터셋에서 특징을 제거함으로써 얻는 전체 절감 효과를 실현하기 위해 모든 다운스트림 소비 모델을 식별한다. 우리는 2개의 대규모 추천 시스템에서 FORTE를 검증하였으며, FORTE가 온라인 회귀를 일으키지 않는 폐기 가능한 특징 집합을 식별함을 확인하였다. 다만 효율성에 대한 영향은 모델 특성에 따라 달라진다. 검색 관련성(search-relevance) 모델에서 FORTE는 32개, 48개, 59개 특징으로 구성된 3개의 중첩된 후보 집합을 도출하였다. 온라인 가드레일은 가장 큰 처리(treatment)를 거부하였다. 48개 특징 집합이 폐기 대상으로 선정되어 해당 모델 특징의 43.3%가 제거되었다. 대규모 랭킹(ranking) 모델에서는 FORTE가 제거 후보로 8개를 식별하였다. 재학습과 A/B 테스트를 통해 회귀가 없음을 확인하였다. 이 배포로 학습 가능한 파라미터가 29.9% 감소하였고, 서빙 처리량(serving throughput)이 19.8~25.5% 향상되었으며, 연간 학습 비용이 수십만 달러 절감되었다.
가산적 양자화 표현을 통한 밴딧
Bandits via Additive Quantized Representations
맥락적 밴딧(contextual bandit)은 비선형 보상(reward) 모델링과 온라인 효율성 사이의 균형을 필요로 한다. 트리 앙상블과 신경망 기반 방법은 비선형성을 포착할 수 있지만 주기적인 재학습과 대규모 리플레이 버퍼를 필요로 한다. 선형 모델은 관측값마다 O(1) 메모리로 효율적으로 업데이트할 수 있지만, 근본적으로 선형 보상 구조에만 제한된다. 우리는 이러한 간극을 메우기 위한 표현 층(representation layer)으로 잔차 양자화(Residual Quantization, RQ)를 제안한다. 오프라인으로 학습된 RQ 코드북(codebook)은 연속적인 맥락(context)을 여러 수준에 걸친 이산적 중심점(centroid) 할당으로 매핑하며, 이 수준들은 섀도 메커니즘(shadow mechanism)을 통해 동적으로 설정된다. 이를 통해 엄격하게 제한된 메모리로 비선형 표현력을 달성하는 다양한 가산적(additive) 밴딧 알고리즘을 구현할 수 있다. 13개의 데이터셋(dataset)에 걸쳐, RQ 변형들은 13개 중 11개 데이터셋에서 비-RQ 대응 모델을 종종 큰 차이로 능가했으며, 더블링 재학습(doubling-retrain) 방식의 XGBoost 및 신경망 베이스라인과 비슷한 성능을 최대 1000배 적은 메모리로 달성했다.
비용 제약 조건 하에서 언어 모델 응답의 온라인 검증
Online Verification of Language Model Responses Under Cost Constraints
대규모 언어 모델(LLM)이 다단계 추론(multi-step reasoning)에 점점 더 많이 활용됨에 따라, 대규모 환경에서 신뢰성을 유지하기 위해 출력의 정확성을 검증하는 것이 필수가 되었습니다. 대규모 언어 모델 출력의 정확성 검증은 주로 많은 비용이 드는 정답 오라클(ground-truth oracle)에 질의하여 수행되지만, 온라인 환경에서 매 단계마다 이를 호출하는 것은 비현실적입니다. 기존 연구에서는 매 단계마다 단일 약한 검증기(weak verifier)에 질의하고, 그 점수를 활용해 비용이 많이 드는 강력한 검증기에도 질의할지 여부를 결정함으로써, 소수의 단계에서만 강력한 검증을 수행하도록 하여 이 문제를 해결했습니다. 그러나 유입되는 쿼리의 주제나 난이도가 시간에 따라 변함에 따라 단일 고정 약한 검증기는 일관되게 우수한 성능을 내지 못할 수 있으며, 사전에 하나를 정해두는 것은 지나치게 많은 비용이 들거나 부정확한 검증으로 이어질 위험이 있습니다. 본 논문에서는 비용과 검증 성능이 서로 다른 $K$개의 후보 약한 검증기 풀을 유지하고, 온라인 점수 결합기(online score combiner) 및 지수 가중치 라우팅 정책(exponential-weights routing policy)을 통해 선택된 검증기로 매 라운드의 결정을 적응형으로 라우팅하는 알고리즘인 OMVV(Online Multi-Verifier Verification)를 제안합니다. OMVV는 전체 검증기 풀에 걸쳐 위양성(false-accept) 및 위음성(false-reject) 비율에 대한 분포 무관(distribution-free) 유한 시간 보장을 제공하며, 비용과 일관성을 결합한 목적 함수 하에서 사후 최적의 고정 검증기 대비 준선형 리그릿(sublinear regret)을 추가로 달성합니다. 추론 데이터셋 벤치마크에 대한 실험 결과, OMVV는 다양한 운영 예산 범위 전반에서 단일 고정 검증기보다 더 낮은 검증 비용으로 더 높은 정확도를 달성함을 보여줍니다.
자연 가시성 그래프 기반 사이버 공격 탐지를 위한 위상 지표의 다중 방식 중요도 및 성능 효율성 분석
A Multi Method Importance and Performance Efficiency Analysis of Topological Metrics for Natural Visibility Graph Based Cyber Attack Detection
자연 가시성 그래프(Natural Visibility Graph, NVG) 기반 분석은 서로 다른 구조적 특성을 반영하는 위상 기술자(topological descriptor)를 통해 네트워크 트래픽을 특성화합니다. 그러나 모든 기술자가 사이버 공격 분류에 동일하게 기여하는 것은 아니며, 대규모 지표 집합을 추출하는 것은 계산 비용을 증가시킬 수 있습니다. 본 연구에서는 NVG에서 유도된 21개의 위상 지표를 평가하고, 축소된 하위 집합이 계산 효율성을 개선하면서도 분류 성능을 유지할 수 있는지 조사합니다. SHAP, 그룹화된 순열 중요도(Permutation Importance), Boruta, 재귀적 특징 제거(Recursive Feature Elimination, RFE)의 네 가지 중요도 분석 방법을 합의 순위(Consensus Ranking) 전략을 통해 통합합니다. 이 순위를 바탕으로 Full21, Top15, Top10, Top7, Top5, Top3 구성을 CICIDS2018 데이터셋, CNN 분류기, 계층화된 5겹 교차 검증을 사용하여 평가합니다. 가장 높은 순위를 기록한 세 가지 지표는 avg_clustering_coeff_median, avg_clustering_coeff_std, avg_clustering_coeff_mean입니다. Top3는 97.148%의 정확도, 97.055%의 가중 F1 점수, 0.9675의 MCC를 기록하여 Full21의 95.999%, 95.521%, 0.9549와 비교해 관측된 최고 평균 성능을 달성했습니다. 또한 전체 실행 시간을 14,961.39초에서 589.22초로 96.06% 단축했습니다. 이러한 결과는 중요도 기반의 지표 축소가 평가된 환경에서 더 높은 관측 평균 예측 성능과 실질적으로 훨씬 낮은 계산 비용을 갖춘 간결한 NVG 표현을 제공할 수 있음을 보여줍니다.
JOVE: 자원 인지형 LLM 태스크 그래프를 위한 공동 실행 및 검증
JOVE: Joint Execution and Verification for Resource-Aware LLM Task Graphs
복잡한 추론 질의는 방향성 비순환 그래프(DAG) 형태의 태스크 그래프로 분해되어 이종 대규모 언어 모델(LLM)에 분산될 수 있으며, 이를 통해 병렬 처리를 통한 지연 시간을 줄이고 더 작은 모델이 복잡한 태스크를 해결하도록 지원할 수 있습니다. 그러나 실제로는 주어진 서브태스크에 대한 특정 LLM의 적합성을 사전에 알 수 없을 수 있으며, 단순 실행만으로는 출력의 정확성을 파악할 수 없습니다. 본 논문에서는 실행기 LLM을 할당하는 동시에 유료 검증을 거칠 중간 출력을 함께 선택하는 온라인 프레임워크인 JOVE를 제안합니다. 검증은 비동기식으로 실행되며 향후 할당 결정을 개선하는 데 사용되므로, 시스템은 현재 실행에 드는 비용과 향후 학습을 위한 지출 사이의 균형을 유지해야 합니다. 본 연구에서는 확률적이며 초기에는 알려지지 않은 LLM 서비스 품질, 호출 비용 및 실행 시간 환경에서 장기 예산과 질의별 지연 시간 제약 조건 하에 이러한 트레이드오프를 최적화하는 방법을 연구합니다. JOVE는 질의별 일련의 혼합 정수 선형 계획법(MILP) 문제를 해결하여 실행 및 검증 결정을 내립니다. 온라인 학습은 검증 피드백을 기반으로 LLM 품질에 대한 태스크 의존적 추정치를 업데이트하며, 정보 이득 보너스를 통해 학습의 가치를 할당 결정에 반영합니다. 자연스러운 일련의 가정 하에 본 연구는 JOVE의 준선형(sublinear) 품질 학습 후회(regret)를 입증합니다. 4가지 추론 벤치마크 전반에서 JOVE는 표준 추론(inference) 베이스라인 대비 경쟁력 있는 정확도를 달성하는 동시에 평균 비용과 지연 시간을 최소 3.17배 단축합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.