arXiv:2212.07551

Faster Maximum Inner Product Search in High Dimensions

Mo Tiwari, Ryan Kang, Je-Yong Lee, DongHyun Lee, Chris Piech, Sebastian Thrun, Ilan Shomorony, Martin Jinye Zhang

제출 2022-12-14

원문 초록

Maximum Inner Product Search (MIPS) is a ubiquitous task in machine learning applications such as recommendation systems. Given a query vector and $n$ atom vectors in $d$-dimensional space, the goal of MIPS is to find the atom that has the highest inner product with the query vector. Existing MIPS algorithms scale at least as $O(\sqrt{d})$, which becomes computationally prohibitive in high-dimensional settings. In this work, we present BanditMIPS, a novel randomized MIPS algorithm whose complexity is independent of $d$. BanditMIPS estimates the inner product for each atom by subsampling coordinates and adaptively evaluates more coordinates for more promising atoms. The specific adaptive sampling strategy is motivated by multi-armed bandits. We provide theoretical guarantees that BanditMIPS returns the correct answer with high probability, while improving the complexity in $d$ from $O(\sqrt{d})$ to $O(1)$. We also perform experiments on four synthetic and real-world datasets and demonstrate that BanditMIPS outperforms prior state-of-the-art algorithms. For example, in the Movie Lens dataset ($n$=4,000, $d$=6,000), BanditMIPS is 20$\times$ faster than the next best algorithm while returning the same answer. BanditMIPS requires no preprocessing of the data and includes a hyperparameter that practitioners may use to trade off accuracy and runtime. We also propose a variant of our algorithm, named BanditMIPS-$\alpha$, which achieves further speedups by employing non-uniform sampling across coordinates. Finally, we demonstrate how known preprocessing techniques can be used to further accelerate BanditMIPS, and discuss applications to Matching Pursuit and Fourier analysis.

함께 살펴볼 논문

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

arXiv:2607.13686v2cs.LG공통 태그 Recommendation Systems, Multi-Armed Bandits

일반 함수 근사 하에서의 최적·효율적 문맥적 조합 세미-밴딧

Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation

본 논문은 맥락적 조합 세미밴딧(CCSB) 문제를 연구한다. 이 문제에서 학습자는 매 라운드마다 맥락을 관측하고, 기본 팔들의 부분집합으로 이루어진 조합 행동을 선택하며, 선택된 각 팔의 보상을 받는다. 목표는 시간에 따른 누적 보상을 최대화하는 것이다. 기존의 많은 연구가 선형 보상 함수 근사를 갖는 CCSB 문제에 초점을 맞춘 반면, 일반 보상 함수 근사를 갖는 CCSB 문제에 대한 효율적인 알고리즘 설계는 제한적이다. 본 연구에서는 학습자가 참 보상 함수를 포함하는 보상 함수 클래스 $\mathcal{F}$에 접근할 수 있는 실현 가능(realizable) 설정을 연구하고 $\mathrm{SquareCB{.}Comb}$ 알고리즘을 제안한다. $\mathrm{SquareCB{.}Comb}$가 $O(\sqrt{m A T \log |\mathcal{F}|})$의 미니맥스 최적 후회 한계를 달성함을 증명한다. 여기서 $A$는 팔의 수, $m$은 조합 행동에 포함되는 팔의 최대 개수, $T$는 시간 지평이다. 또한 맥락이 주어졌을 때 모든 팔의 보상을 효율적으로 예측할 수 있는 온라인 회귀 오라클이 있고, 조합 행동 집합이 효율적인 선형 최적화 또는 팔에 대한 임의의 목표 주변 확률이 주어졌을 때의 효율적인 샘플링 중 하나를 허용하면 $\mathrm{SquareCB{.}Comb}$는 계산적으로 효율적이다. 웹페이지 추천과 맥락적 최단 경로 문제에서 알고리즘의 효과를 실험적으로 검증한다.

arXiv:2607.22935v1cs.LG공통 태그 Recommendation Systems, Multi-Armed Bandits

정적·시간 가변 노출 하한을 갖는 불일치 반올림 공정 밴딧

Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors

최소 노출 제약은 추천, 콘텐츠 큐레이션, 규제된 할당에서 각 공급자, arm, 또는 그룹이 집계적으로만이 아니라 기간 내에 보장된 노출을 받아야 할 때 발생한다. 우리는 정확한 노출 하한을 갖는 확률적 밴딧(stochastic bandits)을 연구하고, 핵심 대상은 반올림 문제임을 보인다. 분수 공정 스케줄이 정수 pull로 실현되며, 노출 오차는 정확히 불일치 벡터(discrepancy vector)이다. 주요 기여는 시간 가변 하한을 갖는 블록 단위 모델이다. BDQ-UCB는 모든 블록 하한을 결정적으로 만족하며, horizon $T$가 아닌 비필수 예산 $R$에 의해 지배되는 공정 regret을 갖고, 높은 확률에서 regret $O(\sqrt{KR\log(KT)})$를 달성한다. MOSS 잔차(residual) 변형은 $O(\sqrt{KR})$를 달성하고, 일치하는 하한이 양의 필수 노출(mandatory exposure)에서도 minimax rate $Θ(\sqrt{KR})$를 제공한다. kl-UCB$^{++}$ 잔차 규칙은 instance-dependent 최적성을 추가한다. 이 정식화는 겹치는 그룹 하한에 필수적이다. arm별 반올림은 그룹 크기에 대해 $Ω(s)$만큼 그룹 제약을 위반할 수 있는 반면, Beck--Fiala 영공(null-space) 반올림은 블록 예산 내에서 모든 그룹 하한을 만족하며 위반을 arm degree $t$ 미만으로 유지하고, 동일한 $R$-매개변수 regret과 UCB를 결합한다. 학습된 그룹 계획에 대해, 우리는 disjoint system을 $\widetildeΘ(\sqrt{KT})$에서 닫고, 겹침 하에서 naive index 규칙이 실패하는 이유를 설명하는 이중 원장(dual-ledger) 분해를 제시하며, 초기 cover-slack 조건 하에서 pathwise feasible한 plan-sampling 규칙을 증명하고 조건부 $\widetilde O(\sqrt{KT})$ 보장을 달성하되, 조건 없는 겹침 rate는 열어둔다. 합성 하한, MovieLens-100k 장르 노출, 배포 스트레스 테스트에 대한 실험은 penalty tuning 없이 정확한 feasibility를 보여주며, tuned Lagrangian baseline과 경쟁력 있는 regret을 보인다.

arXiv:2606.29221v2cs.LG공통 태그 Recommendation Systems, Multi-Armed Bandits

온라인 다중 인간-다중 로봇 팀 구성을 위한 선형 매칭 밴딧 접근법

A Linear Matching Bandit Approach to Online Multi-Human Multi-Robot Teaming

우리는 선형 매칭 밴딧 프레임워크 관점에서 온라인 다중 인간-다중 로봇 매칭 문제를 다룬다. 여기서 학습자(learner)는 고정된 풀에서 알려지지 않은 특징을 가진 로봇들을 여러 라운드에 걸쳐 서로 다른 인간 에이전트 집합에 배정한다. 이 문제를 해결하기 위해, 우리는 알려지지 않은 특징의 신뢰 구간을 갱신하고 불확실성 하에서 낙관적 매칭(optimistic matching)을 수행하는 온라인 학습 알고리즘 LinMatch를 제안한다. 본 연구의 기여와 새로움은 두 가지이다. 첫째, 각 라운드의 낙관적 매칭 문제를 최대 가중 매칭의 선형 프로그램으로 재구성하며, 이는 잘 알려진 헝가리안 알고리즘(Hungarian algorithm)으로 효율적으로 풀 수 있다. 둘째, 선형 특징을 갖는 매칭 문제에 대한 새로운 경계를 제공하며, 총 라운드 수 $T$에 대한 최적 달성 가능 후회(regret)가 $Θ(\sqrt{T})$임을 보인다. 제안된 알고리즘과 경계는 인간-로봇 매칭을 넘어 주택 배정, 추천 시스템 등 다양한 매칭 문제에 적용할 수 있다.

arXiv:2607.22012v1cs.LG공통 태그 Recommendation Systems, Multi-Armed Bandits

문맥적 밴딧을 위한 교차 도메인 오프-정책 평가 및 학습

Cross-Domain Off-Policy Evaluation and Learning for Contextual Bandits

문맥적 밴딧에서 오프-정책 평가 및 학습(OPE/L)은 과거에 기록된 로그 데이터만으로 새로운 정책을 안전하게 평가하고 학습할 수 있기 때문에 실제 시스템에서 빠르게 주목받고 있다. 그러나 OPE/L의 기존 방법들은 퓨샷(few-shot) 데이터, 결정론적 로깅 정책, 새로운 행동(action)과 같이 도전적이지만 널리 존재하는 많은 시나리오를 다룰 수 없다. 맞춤형 의료, 콘텐츠 추천, 교육, 광고 등 많은 응용 분야에서는 이러한 과제가 있는 상황에서 새로운 정책을 평가하고 학습해야 한다. 기존 방법들은 로그 데이터의 잘 알려진 분산 문제나 제한된 탐험(exploration) 때문에 이러한 상황에서 효과적으로 평가하고 최적화할 수 없다. 이러한 미해결 과제 하에서도 OPE/L을 가능하게 하기 위해, 새로운 정책이 구현될 대상(target) 도메인의 로그 데이터뿐만 아니라 다른 도메인에서 수집된 로그 데이터셋에도 접근할 수 있는 교차 도메인 OPE/L이라는 새로운 문제 설정을 제안한다. 이 새로운 공식화는 대상 병원, 국가, 기기, 사용자 세그먼트뿐만 아니라 다른 병원, 국가, 기기, 세그먼트의 과거 데이터도 활용할 수 있기 때문에 널리 적용 가능하다. 우리는 대상 및 소스(source) 데이터셋을 모두 활용하여 OPE/L을 해결하는 새로운 추정량(estimator)과 정책 그래디언트(policy gradient) 방법을 개발했으며, 실험 평가에서 이전에 해결되지 않았던 상황에서 OPE/L 성능이 실질적으로 향상되었다.

arXiv:2607.11684v1stat.ML공통 태그 Recommendation Systems, Multi-Armed Bandits

다양화 다항 로짓 맥락 밴딧

Diversified Multinomial Logit Contextual Bandits

기존의 맥락적 다항 로짓(MNL) 밴딧은 관련성 기반 선택을 모델링하지만 품목 구성 내 다양성의 잠재적 이점을 무시하는 반면, 서브모듈러/조합적 밴딧은 보상에 다양성을 인코딩하지만 구조화된 선택 확률이 부재하다. 우리는 $\textit{다양화 다항 로짓}$(DMNL) 맥락 밴딧으로 이 간극을 해소한다. 이 모델은 MNL 선택 확률에 일반적 서브모듈러 다양성 함수를 결합하여 단일 모델 내에서 관련성-다양성 트레이드오프를 공식화한다. 다양성을 통합하면 정확한 MNL 품목 구성 최적화가 난해해진다. 우리는 낙관적 한계 이득을 최대화하여 항목별로 품목 구성을 구성하고 블랙박스 최적화 오라클을 회피하는 $\textit{화이트박스}$ UCB 기반 알고리즘 $\texttt{OFU-DMNL}$을 제안한다. $\texttt{OFU-DMNL}$이 적어도 $(1-\frac{1}{e+1})$-$\textit{근사}$ 후회 경계 $\tilde{O}\left(d \sqrt{T/K}\right)$를 달성함을 보이는데, 여기서 $d$는 맥락 차원, $K$는 최대 품목 구성 크기, $T$는 기간이며, 표준 서브모듈러 기준선 대비 향상된 근사 인수를 달성한다. 실험에서는 일관된 성능 향상을 보였으며, 전수 열거 대비 유사한 후회 수준을 유지하면서도 실행 시간을 크게 단축하였다. 전반적으로, DMNL 밴딧은 불확실성 하에서 다양성을 고려한 품목 구성 최적화를 위한 실용적 기반을 제공하며, $\texttt{OFU-DMNL}$은 통계적·계산적으로 효율적인 해법을 제시한다.

arXiv:2607.08971v1cs.LG공통 태그 Recommendation Systems, Multi-Armed Bandits

부분 관측 행동을 갖는 확률적 선형 밴딧

Stochastic Linear Bandits with Partially Observed Actions

확률적 선형 밴딧(stochastic linear bandit)은 행동을 벡터로 표현하고 보상이 선형인 순차적 의사결정의 핵심 패러다임이다. 본 연구에서는 학습 에이전트가 각 행동에 대해 좌표의 무작위 부분집합만을 관측하는 부분 관측(partially observed) 변형 문제를 다룬다. 이러한 부분 관측 가능성은 추천 및 의료와 같이 전체 행동 기술(description)을 얻는 것이 비용이 많이 들거나 불가능한 환경에서 자연스럽게 발생한다. 일반적으로 이는 준선형 후회(sublinear regret)를 정보이론적으로 불가능하게 만든다. 그러나 행동 벡터의 내재적 차원(intrinsic dimension)이 낮을 경우 이 장벽을 극복할 수 있음을 보인다. 우리는 마스킹된 행동으로부터 잠재 행동 부분공간(latent action subspace)을 추정하고, 에포크 단위로 고정된 표현을 이용해 현재 행동을 대체(impute)하며, 그 결과 얻어진 저차원 좌표에서 OFUL을 실행하는 알고리즘 TOFU-POV를 제안한다. 이론적으로 TOFU-POV는 주변 차원(ambient dimension)이 아닌 내재적 행동 부분공간 차원에 비례하는 $\sqrt{T}$ 후회를 달성하며, 이들 수량과 결측률, 결정 집합 크기, 부분공간 조건화(subspace conditioning) 간의 상호작용을 정량화한다. 또한 내재적 차원에 대한 사전 지식 없이도 동작하는 랭크 적응형(rank-adaptive) 알고리즘도 고안한다. 이러한 보장을 보완하기 위해, 통상적인 보상 학습 불확실성과 부분 관측에 내재된 결측 의존적 비용을 분리하는 새로운 곱 구성(product construction)에 기반한 하한을 제시한다. 합성 및 실제 데이터 실험을 통해 이론을 뒷받침하고, TOFU-POV가 이 어려운 문제에서 자연스러운 베이스라인에 비해 상당한 성능 향상을 달성할 수 있음을 보인다.

토론

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