arXiv:2111.14778

Contextual Combinatorial Multi-output GP Bandits with Group Constraints

Sepehr Elahi, Baran Atalar, Sevda Öğüt, Cem Tekin

제출 2021-11-29

원문 초록

In federated multi-armed bandit problems, maximizing global reward while satisfying minimum privacy requirements to protect clients is the main goal. To formulate such problems, we consider a combinatorial contextual bandit setting with groups and changing action sets, where similar base arms arrive in groups and a set of base arms, called a super arm, must be chosen in each round to maximize super arm reward while satisfying the constraints of the rewards of groups from which base arms were chosen. To allow for greater flexibility, we let each base arm have two outcomes, modeled as the output of a two-output Gaussian process (GP), where one outcome is used to compute super arm reward and the other for group reward. We then propose a novel double-UCB GP-bandit algorithm, called Thresholded Combinatorial Gaussian Process Upper Confidence Bounds (TCGP-UCB), which balances between maximizing cumulative super arm reward and satisfying group reward constraints and can be tuned to prefer one over the other. We also define a new notion of regret that combines super arm regret with group reward constraint satisfaction and prove that TCGP-UCB incurs $\tilde{O}(\sqrt{\lambda^*(K)KT\overline{\gamma}_{T}} )$ regret with high probability, where $\overline{\gamma}_{T}$ is the maximum information gain associated with the set of base arm contexts that appeared in the first $T$ rounds and $K$ is the maximum super arm cardinality over all rounds. We lastly show in experiments using synthetic and real-world data and based on a federated learning setup as well as a content-recommendation one that our algorithm performs better then the current non-GP state-of-the-art combinatorial bandit algorithm, while satisfying group constraints.

함께 살펴볼 논문

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

arXiv:2607.11600v1cs.LG공통 태그 Gaussian Processes, Federated Learning

프라이버시를 고려한 협력적 분산 베이지안 최적화

Privacy-Aware Collaborative and Distributed Bayesian Optimization

우리는 원시 데이터 교환 없이 중앙 집중식 성능에 부합하는 분산 베이지안 최적화(Bayesian optimization)를 위한 협력적 메타학습(meta-learning) 프레임워크를 제안한다. 그래디언트 공유가 클라이언트 관측값을 유출하며, 탐색이 수렴하고 쿼리가 최적점 근방에 집중될수록 유출이 심화됨을 보인다. 차등 프라이버시(differential privacy) 방어 기법을 평가하고 그 프라이버시-유용성 트레이드오프를 분석한다.

arXiv:2605.27991v5stat.ML공통 태그 Gaussian Processes

동적 랜덤 효과 추론으로서의 그래디언트 플로우 최적화: 심층 학습에의 적용을 위한 검정 및 조기 종료

Gradient-Flow Optimization as Dynamic Random-Effects Inference: Testing and Early Stopping with Applications to Deep Learning

그래디언트 플로우 최적화는 보통 경험적 손실을 최소화하는 알고리즘적 절차로 간주되며, 학습 기간은 검증 또는 휴리스틱 조기 종료 규칙에 의해 선택된다. 우리는 그래디언트 플로우 학습을 위한 통계적 추론 프레임워크를 개발한다. 적합값(fitted values)이 시불변(time-invariant) 양반정치(positive semidefinite) 학습 연산자를 통해 진화할 때마다, 각 시점에서의 출력이 대응하는 랜덤 효과 모델 하의 최량 선형 불편 예측기(best linear unbiased predictor)와 동등함을 보인다. 학습 시간은 잔차 노이즈에서 구조적 신호로의 분산 재할당을 제어하는 분산 성분(variance-component) 매개변수가 된다. 이는 두 가지 학습 결정을 추론 문제로 전환한다: 학습이 필요한지 여부는 초기화 이상의 신호에 대한 분산 성분 검정이 되고, 얼마나 오래 학습할지는 학습 시간 분산 성분의 제한 최대 가능도(restricted maximum likelihood, REML) 추정이 된다. REML 유도 조기 종료 규칙은 최적화된 스펙트럴 손실이 학습 연산자 고유값과 무상관(decorrelated)이 되는 시점을 선택함을 보인다. REML 유도 조기 종료 시간의 점근적 예측 최적성은 고정 설계 표본 내 위험(fixed-design in-sample risk) 및 랜덤 설계 표본 외 위험(random-design out-of-sample risk)에 대해 확립된다. 고정 커널 그래디언트 체제의 심층 학습 모델은 우리 결과의 표준적 구체화를 제공한다. 수치 실험 및 UK Biobank 프로테오믹스 응용은 검증 분할 및 반복적 체크포인트 평가에 대한 의존도를 줄이면서 REML 유도 조기 종료 시간의 경쟁적 정확도를 보인다.

arXiv:2607.09645v2stat.ML공통 태그 Gaussian Processes

방향 비순환 그래프 위의 심층 가우시안 과정

Deep Gaussian Processes on Directed Acyclic Graphs

많은 실제 과정은 방향 비순환 그래프(DAG)를 따르는 함수들의 합성으로 표현할 수 있다. 인과 모델링에서 이는 기저 메커니즘에, 공학에서는 다중 충실도 수준에, 유전자 조절 네트워크에서는 전사 인자에 해당한다. 이러한 함수들은 DAG 전반에서 잡음이 있고 이질적으로 샘플링된 측정값으로 부분적으로만 관측되므로, 재구성, 불확실성 전파, 추론에 상당한 어려움을 야기한다. 이러한 어려움을 해결하기 위해 함수에 대한 사전분포를 두어 자연스럽게 DAG 위의 심층 가우시안 과정에 도달한다. 우리는 이들의 사전분포 붕괴 거동과, 그래프 위상 및 중간 관측이 정보 보존에 미치는 영향을 이론적으로 연구한다. 입력 간 구별이 보존되는 깊이의 점근적 빈도에 대한 거의 확실한 하한을 얻고, 이것이 성립하는 폭넓은 커널 클래스를 규명하며, 입력 연결의 역할에 관한 \citep{dunlop2018}의 관찰을 증명한다. 또한 그래프 의존성을 유지하고 합성적 불확실성을 보존하며 충돌자(collider)의 설명 소거(explaining-away) 거동을 포착하는 구조적 변분 근사를 제시한다. 마지막으로 대규모 및 DAG 오지정 상황에서 이론과 방법론을 경험적으로 검증한다. 이어서 잠재 충돌자 DAG, 단백질 신호 전달 네트워크, 다중 충실도 \mbox{heavy-ion} 충돌 에뮬레이션 과제를 모델링하여, 최고 수준의 성능을 달성하는 동시에 저충실도 기여를 복원하고 시뮬레이터 계층에 대한 해석 가능성을 제공한다.

arXiv:2606.18071v2cs.LG공통 태그 Gaussian Processes

마르코프 리프팅을 통한 볼테라 생성 모델

Volterra Generative Models via Markovian Lifting

확산 기반 생성 모델은 보통 브라운 운동이 구동하는 마르코프 과정으로 데이터를 교란한다. 볼테라 과정은 더 유연한 시간적 의존성을 허용하지만, 그 비마르코프 구조는 스코어 학습과 역방향 시뮬레이션을 복잡하게 만든다. 우리는 볼테라 생성 모델을 개발하고 마르코프 근사를 제공한다. 이후 가우시안 조건화를 통해 잡음 제거 문제를 원래의 데이터 차원으로 축소한다. 분산 폭발 및 분산 보존 표현과의 연결을 제시한다. 또한 본 프레임워크는 EDM2 네트워크와 같은 사전 학습된 잡음 제거기의 재사용을 허용한다. 하나의 보조 인자를 두면, 처음부터 학습한 모델은 MNIST에서 FID $0.547$, 조건부 CIFAR-10에서 $1.860$을 달성한다. 오토가이던스를 적용하면 ImageNet64 FID는 미세 조정 후 $1.912$에 도달하며, ImageNet512 FID는 고정된 사전 학습 네트워크를 사용하여 $1.903$에 도달한다.

arXiv:2607.07888v2cs.LG공통 태그 Federated Learning

OLS 회귀를 위한 데이터 분할에 대한 분산 스케칭

Distributed Sketching on Data Partitions for OLS Regression

본 논문은 분산 스케치에 기반한 최소제곱(OLS) 회귀의 확장 가능한 접근법을 연구한다. 대규모 데이터 집합의 작은 스케치를 여러 워커에 분산하고, 각 워커가 자신의 스케치로부터 로컬 OLS 추정량을 구성하며, 로컬 추정량들을 평균하여 전역 추정량을 얻는다. 기존 연구는 각 스케치가 전체 데이터로부터 생성된다고 가정하지만, 이 스케치 단계는 계산 비용이 높아 때로는 표준 OLS보다 더 높다. 이에 우리는 데이터를 분할한 부분집합으로부터 각 스케치를 생성할 것을 제안하며, 이로써 워커 수가 늘어날수록 스케치 비용이 감소한다. 고정 설계 설정에서 전역 추정량의 정확한 초과 손실을 규명한다. 이 손실은 기존 연구에서 확립된 손실보다 크지만, 부분집합 공분산 간의 평균 Burg 발산이 작을 때는 그에 가깝게 유지된다. 제안한 분할 설계에서는 워커가 많을수록 발산이 커지는 경향이 있으므로, 이는 추정량의 계산 효율성과 통계적 효율성 사이의 상충 관계를 드러낸다.

토론

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