Sparsity, variance and curvature in multi-armed bandits
원문 초록
In (online) learning theory the concepts of sparsity, variance and curvature are well-understood and are routinely used to obtain refined regret and generalization bounds. In this paper we further our understanding of these concepts in the more challenging limited feedback scenario. We consider the adversarial multi-armed bandit and linear bandit settings and solve several open problems pertaining to the existence of algorithms with favorable regret bounds under the following assumptions: (i) sparsity of the individual losses, (ii) small variation of the loss sequence, and (iii) curvature of the action set. Specifically we show that (i) for $s$-sparse losses one can obtain $\tilde{O}(\sqrt{s T})$-regret (solving an open problem by Kwon and Perchet), (ii) for loss sequences with variation bounded by $Q$ one can obtain $\tilde{O}(\sqrt{Q})$-regret (solving an open problem by Kale and Hazan), and (iii) for linear bandit on an $\ell_p^n$ ball one can obtain $\tilde{O}(\sqrt{n T})$-regret for $p \in [1,2]$ and one has $\tilde{\Omega}(n \sqrt{T})$-regret for $p>2$ (solving an open problem by Bubeck, Cesa-Bianchi and Kakade). A key new insight to obtain these results is to use regularizers satisfying more refined conditions than general self-concordance
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
동치 쿼리로부터의 학습, 재고찰
Learning from Equivalence Queries, Revisited
생성 모델과 추천 시스템 같은 현대 기계학습 시스템은 배포, 사용자 상호작용, 주기적 모델 업데이트의 순환을 통해 발전하는 경우가 많다. 이는 고정된 예측 과제 시퀀스에 대한 손실 또는 후회 최소화에 초점을 맞추는 표준 지도학습 프레임워크와 다르다. 이러한 설정에 착안하여, 우리는 Angluin(1988)이 도입한 동치 쿼리로부터의 학습이라는 고전적 모델을 재고찰한다. 이 모델에서 학습자는 반복적으로 가설을 제안하고, 배포된 가설이 부적절할 경우 반례를 받는다. 그러나 완전 적대적 반례 생성 하에서는 모델이 지나치게 비관적일 수 있다. 또한 대부분의 선행 연구는 학습자가 반례의 올바른 레이블도 관찰하는 완전 정보(full-information) 설정을 가정하는데, 이는 항상 자연스러운 가정이 아니다. 우리는 환경을 덜 적대적인 반례 생성기의 광범위한 부류로 제한함으로써 이러한 문제를 해결하며, 이를 대칭적(symmetric) 생성기라 부른다. 비형식적으로, 이러한 생성기는 가설과 타깃 사이의 대칭 차집합만을 기반으로 반례를 선택한다. 이 부류는 무작위 반례(Angluin and Dohrn, 2017; Bhatia, 2021; Chase, Freitag, and Reyzin, 2024)와 같은 자연스러운 메커니즘뿐 아니라, 주어진 복잡도 척도에 따라 가장 단순한 반례를 반환하는 생성기도 포괄한다. 이 프레임워크 내에서 완전 정보 피드백과 밴딧(bandit) 피드백 양쪽 설정 하에 동치 쿼리로부터의 학습을 연구한다. 두 설정 모두에서 학습 라운드 수에 대한 타이트한 경계를 도출하고, 향후 연구 방향을 제시한다. 우리의 분석은 대칭적 적대자에 대한 게임 이론적 관점과 적응적 가중치 기법, 그리고 미니맥스(minimax) 논증을 결합한다.
필셔 너비: 통계적 다양체에서의 복잡도에 대한 기하학적 척도
Fisher Width: A Geometric Measure of Complexity on Statistical Manifolds
가우시안 너비(Gaussian width)는 고차원 확률론, 압축 감지, 볼록 최적화, 그리고 학습 이론에서 중심적인 기하학적 복잡도 척도입니다. 이는 집합이 무작위 방향으로 가지는 평균 범위를 정량화하여, 제약 조건 집합, 가설 클래스, 하강 원뿔의 유효 차원을 포착합니다. 그러나 이 개념은 본질적으로 유클리드적입니다. 반면 통계 모델은 피셔 정보 메트릭(Fisher information metric)에 의해 유도되는 자연스러운 리만 기하학을 가지며, 여기서 방향은 주변 유클리드 길이가 아닌 통계적 식별 가능성에 따라 조정됩니다. 우리는 통계적 다양체를 위한 가우시안 너비의 피셔 기하학적 유사체인 필셔 너비(Fisher width)를 소개합니다. 매개변수 점 $\theta$에서 필셔 너비는 유클리드 항등 연산자를 국소 메트릭 텐서(tensor) $G(\theta)^{1/2}$로 대체하여, 피셔 재조정(rescaled) 집합의 가우시안 너비를 측정합니다. 이는 결과적인 양이 국소 통계적 곡률에 민감하게 반응하고 매끄러운 재매개변화(reparameterization)에 대해 불변이 되도록 만듭니다. 우리는 필셔 너비의 기본 이론을 개발하여, 집중(concentration), 메트릭 섭동 안정성, 유클리드 기준선(baseline)과의 스펙트럴 비교 바운드를 포함한 가우시안 너비의 핵심 구조적 특징을 유지하면서도, 유클리드 척도에서는 보이지 않는 이방성 기하학적 효과를 포착함을 보여줍니다. 응용으로서, 우리는 Fisher-Lipschitz 가설 클래스에 대한 일반화 바운드를 증명하고 계산 가능한 추정량(estimators)을 제안하며, 이를 세 가지 모델 클래스에 걸쳐 MNIST에서 실증적으로 평가합니다. 필셔 너비는 통계적 다양체에 대하여, 가우시안 너비가 유클리드 볼록체에 대하여 갖는 것과 같은 역할을 합니다. 이 연구는 곡선 통계적 다양체에서의 복잡도와 학습을 연구하기 위한 기초를 마련합니다.
Generalization Bounds in Hybrid Quantum-Classical Machine Learning Models
TreeLoRA: 계층적 그래디언트 유사도 트리 기반 층별 LoRA를 활용한 효율적 지속 학습
TreeLoRA: Efficient Continual Learning via Layer-Wise LoRAs Guided by a Hierarchical Gradient-Similarity Tree
많은 실세계 응용에서는 데이터를 스트리밍 환경에서 수집하며, 학습 태스크가 순차적으로 등장한다. 이는 모델을 온라인으로 갱신하는 지속 학습(CL)을 필요로 하며, 새로운 태스크에 적응하면서 과거 지식을 보존하여 치명적 망각을 방지한다. 최근 대규모 사전학습 모델(LPM)의 성장과 함께, 상당한 계산 요구와 증가하는 매개변수 규모로 인해 CL에서 효율성이 점점 더 중요해졌다. 본 논문에서는 TreeLoRA(K-D Tree of Low-Rank Adapters)를 제안한다. 이는 계층적 그래디언트 유사도를 활용하여 층별 어댑터를 구성하고, 특히 LPM을 위한 효율적인 CL을 가능하게 하는 새로운 접근법이다. 태스크 유사도 추정의 계산 부담을 줄이기 위해, 밴딧(bandit) 기법을 사용하여 하한 신뢰 구간(lower confidence bounds)에 기반한 알고리즘을 개발하고 태스크 구조를 효율적으로 탐색한다. 또한 희소 그래디언트 업데이트를 사용하여 매개변수 최적화를 촉진하고, 이 접근법을 LPM에 더 적합하게 만든다. 접근법의 근거를 정당화하는 이론적 분석을 제공하며, 비전 트랜스포머(ViT)와 대규모 언어 모델(LLM) 모두에 대한 실험을 통해 비전 및 자연어 처리(NLP) 태스크를 포함한 다양한 도메인에서 본 접근법의 효과와 효율성을 입증한다.
Adaptive Action Duration with Contextual Bandits for Deep Reinforcement Learning in Dynamic Environments
From Theory to Practice with RAVEN-UCB: Addressing Non-Stationarity in Multi-Armed Bandits through Variance Adaptation
토론
이 논문과 연결된 포럼 글이 아직 없습니다.