Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)
원문 초록
The problem of constrained online convex optimization is considered, where at each round, once a learner commits to an action $x_t \in \mathcal{X} \subset \mathbb{R}^d$, a convex loss function $f_t$ and a convex constraint function $g_t$ that drives the constraint $g_t(x)\le 0$ are revealed. The objective is to simultaneously minimize the static regret and cumulative constraint violation (CCV) compared to the benchmark that knows the loss functions and constraint functions $f_t$ and $g_t$ for all $t$ ahead of time, and chooses a static optimal action that is feasible with respect to all $g_t(x)\le 0$. Currently, the best known algorithm is OGD+Projection algorithm of [Vaze and Sinha, 2025] that has simultaneous regret of $O(\sqrt{T})$ and CCV of $O(T^{1/3})$ for $d=2$ [Balasundaram et al., 2026], and simultaneous regret of $O(\sqrt{T})$ and CCV of $O(\sqrt{T})$ for any $d$ [Sarkar and Sinha, 2026]. In this paper, we show that the CCV of the OGD+Projection algorithm is $Ω(T^{\frac{d-1}{2d}})$. This is the first such lower bound result.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2607.10808v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
용량 제약이 있는 지연 피드백 온라인 볼록 최적화
Capacity-Constrained Online Convex Optimization with Delayed Feedback
이점 밴딧 피드백을 이용한 온라인 볼록 최적화의 로그적 고확률 후회 경계
Logarithmic High-Probability Regret for Online Convex Optimization with Two-Point Bandit Feedback
우리는 비선행 적응형 적대자(non-anticipating adaptive adversary)에 대한 이점 밴딧 피드백(two-point bandit feedback)을 이용한 온라인 볼록 최적화(OCO)를 연구한다. 이 설정에서 학습자는 볼록 손실의 적대적 시퀀스와 경쟁하며, 각 손실은 두 번의 함수 평가를 통해서만 관측된다. 강볼록(strongly convex) 손실에 대해, Agarwal, Dekel, Xiao~\citeyearpar{agarwal2010optimal}는 기댓값에서 비교자별 로그적 후회(regret) 경계를 증명하였다. 결과적으로, 확률 공간 외부에서 최소화함으로써 그들의 결과는 $\EB A_T-\min_{x\in\mathcal K}\EB L_T(x)$ 형태의 의사-후회(pseudo-regret) 보장을 산출하는데, 여기서 $A_T$는 알고리즘의 이점 쿼리 누적 손실이고 $L_T(x)$는 비교자의 누적 손실이다. 그들은 동일한 이점 강볼록 설정에서 로그적 고확률 보장이 달성 가능한지 물었다. 우리의 주요 정리는 대응하는 고정 비교자 고확률 명제를 제공한다: 알고리즘적 랜덤 방향과 독립적으로 고정된 임의의 비교자 $x\in\mathcal K$에 대해, 표준 이점 사영 그래디언트 방법은 확률 적어도 $1-δ$로 다음 순서의 이점 쿼리 후회 경계를 보장한다: \[ O\left(\frac{dG^2}μ\left(\log T+\log(1/δ)\right)+dGD\log(1/δ)+G\log T\left(1+\frac{D}{r}\right)\right). \] 비교자별 수준에서, 우리의 선도적 수평선 의존 항은 $d$에 선형인 반면, Agarwal, Dekel, Xiao의 원래 분석에서는 $d^2$ 유형의 항이 존재한다. 핵심 요소는 마팅게일 오차를 강볼록성으로 동시에 흡수하고 이점 방법의 선형-차원 추정기 제어를 보존하는 고신뢰 분석이다. 결정론적 커버링 논증(covering argument)은 이후 $\min_{x\in\mathcal K}L_T(x)$에 대한 실현된 전체 비교자 보장을 산출하며, 표준 커버링 수(covering-number) 인자를 대가로 $T$에 대한 로그적 의존성을 보존한다.
지속적 후보 집합을 활용한 선형 밴딧 가속화
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를 넘어 다른 알고리즘으로도 확장될 수 있음을 보입니다.
양자 다중 팔 밴딧 및 선형 밴딧: 하한과 알고리즘
Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms
본 논문에서는 학습자가 양자 보상(reward) 오라클 또는 그 역원을 통해 각 팔(arm)이나 행동을 질의하는 양자 다중 팔 밴딧(QMAB) 및 양자 선형 밴딧(QLB)을 연구합니다. 이전 연구에서는 $K$개의 팔을 가진 QMAB에 대해 $O(K\log T)$, $d$차원 QLB에 대해 $O(d^2\operatorname{polylog} T)$의 후회(regret)를 달성하는 시간 범위 $T$에 대한 알고리즘을 제시했습니다. 그러나 이는 $K$와 $T$에 대한 최적의 의존성과 $d$에 대한 의존성을 추가로 개선할 수 있는지 여부를 미해결 상태로 남겨두었습니다. 본 연구에서는 QMAB에 대해 $\Theta(K\log(1+T/K))$라는 최초의 엄밀한 미니맥스(minimax) 후회 경계를 증명하고, 유한 행동 QLB에 대해 $T$와 무관한 후회를 배제하는 최초의 하한인 $\Omega(d\log(1+T/d))$를 증명합니다. 본 연구의 하한은 고정된 보상 평균을 대안 구간과 구별하기 위한 고신뢰도 단일 팔 양자 테스팅 하한에 기반합니다. 이후 밴딧-테스팅 축소(reduction)를 통해 이를 QMAB 하한으로 확장하며, 선형 임베딩(embedding)을 통해 유한 행동 QLB 하한을 도출합니다. 이에 대응하는 QMAB 상한은 양자 몬테카를로(QMC) 추정량의 꼬리 경계(tail bound)를 사용하여 도출됩니다. 유한 행동 QLB의 경우, 설계 가중치에 맞춘 질의 할당을 통해 낮은 바이어스(bias) 및 낮은 분산을 갖는 양자 평균 추정량과 작은 지지 집합(small-support)을 갖는 $G$-최적 설계를 결합한 단계별 제거(phased elimination) 알고리즘을 제안합니다. 행동 집합의 크기가 $\operatorname{poly}(d)$일 때, 이 알고리즘의 후회는 $d$에 대해 거의 선형적이며 다항 로그 인자(polylogarithmic factor) 범위 내에서 본 연구의 하한과 일치합니다.
커널 밴딧(Kernel Bandits)에 대한 일반적인 $\widetildeΩ(\sqrt{Tγ_T})$ 하한
A General $\widetildeΩ(\sqrt{T γ_T})$ Lower Bound for Kernel Bandits
커널 밴딧(kernel bandit) 문제는 주어진 재생 커널 힐베르트 공간(Reproducing Kernel Hilbert Space, RKHS)에서 유계 노름(bounded norm)을 갖는 미지의 함수를 잡음이 있는 피드백(noisy feedback)을 통해 순차적으로 최적화하는 문제이다. 커널 밴딧의 후회(regret) 분석에서 중심이 되는 양은 최대 정보 획득량(maximum information gain) $γ_T$이다. 특히, 기존에 알려진 가장 좋은 상한(upper bound)은 로그 항(log factor)을 제외하면 $\sqrt{Tγ_T}$로 스케일링되며, 제곱 지수(squared exponential) 커널과 마테른(Matérn) 커널과 같은 특정 커널에 대해서는 이와 거의 일치하는 하한(lower bound)이 도출되어 왔다. 그러나 일반적인 커널에 대한 하한은 부족하여, 어느 정도의 일반성에서 상한이 근사 최적(near-optimal)인지가 불분명하다. 본 논문에서는 콤팩트 정의역(compact domain) 상의 비상수 연속 커널(non-constant continuous kernel)에 대해 일반적인 $Ω(\sqrt{Tγ_T/\log T})$ 미니맥스 후회 하한을 수립하여, 매우 일반적인 의미에서 (로그 항 범위 내에서의) 근사 최적성을 입증한다. 우리는 이 하한에 나타나는 로그 항이 일반적으로는 피할 수 없음을 보이지만, 특정 조건 하에서는 이를 제거할 수 있음을 보인다. 특히 우리의 결과는 $ν\in (0,2)$인 마테른-$ν$(Matérn-$ν$) 커널, $γ\in (0,2)$인 $γ$-지수(γ-exponential) 커널, 그리고 특정 조각별 다항식(piecewise-polynomial) 커널에 대해 미니맥스 최적 스케일링이 (상수 인자 범위 내에서) 정확히 $Θ(\sqrt{Tγ_T})$임을 함의한다.
BONSAI: 자연스러운 단순성과 해석 가능성을 갖춘 베이즈 최적화
BONSAI: Bayesian Optimization with Natural Simplicity and Interpretability
베이즈 최적화(Bayesian optimization, BO)는 블랙박스 함수의 표본 효율적 최적화(sample-efficient optimization)를 위해 널리 사용되는 기법입니다. 많은 응용 분야에서 튜닝 대상 파라미터는 정교하게 설계된 기본 설정(default configuration)과 함께 제공되며, 실무자들은 꼭 필요한 경우에만 이 기본값에서 벗어나기를 원합니다. 그러나 표준 BO는 기본값으로부터의 편차를 최소화하는 것을 목표로 하지 않으며, 실제로는 중요도가 낮은 파라미터를 탐색 공간의 경계로 밀어내는 경우가 많습니다. 이는 중요 변경사항과 무의미한 변경사항을 구분하기 어렵게 만들고, 최적화 목적함수에 관련 운영 고려사항이 누락되었을 때 추천된 설정을 검토하는 부담을 가중시킵니다. 본 논문에서는 획득 가치(acquisition value)의 손실(loss)을 명시적으로 제어하면서 기본 설정 대비 영향력이 적은 편차를 가지치기(pruning)하는 기본값 인식(default-aware) BO 정책인 BONSAI를 소개합니다. BONSAI는 기대 개선량(expected improvement)과 상한 신뢰 구간(GP-UCB)을 포함한 다양한 획득 함수(acquisition function)와 호환됩니다. 우리는 BONSAI에 의해 발생하는 후회(regret)의 이론적 상계를 제시하여, 적절한 조건 하에서 기본 GP-UCB의 무후회(no-regret) 특성을 유지하면서 무관한 변경사항을 제거함을 증명합니다. 다양한 실제 응용 전반에 걸쳐, BONSAI가 실행 시간(wall time)에 거의 영향을 주지 않으면서 경쟁력 있는 최적화 성능을 유지함과 동시에 추천 설정에서 기본값이 아닌 파라미터의 수를 실질적으로 줄임을 실험적으로 확인했습니다. BONSAI의 후보 생성 비용은 표준 BO 대비 평균 1.5배에 불과하여, 기존 희소(sparse) BO 기법들의 7~34배와 대비됩니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.