arXiv:2606.27315v1 cs.LG

Blackwell Approachability와 Gradient Equilibrium의 동등성

Blackwell Approachability and Gradient Equilibrium are Equivalent

Brian W. Lee, Nika Haghtalab, Michael I. Jordan, Ryan J. Tibshirani

제출 2026-06-25

한국어 초록

그래디언트 균형(GEQ)은 최근 도입된 온라인 최적화(optimization) 프레임워크로, 오프라인 최적화의 1차 정상성(first-order stationarity)을 일반화하고 온라인 conformal prediction과 같은 문제를 추상화한다. GEQ는 후회 최소화(regret minimization)와 같은 알려진 온라인 학습(online learning) 프레임워크와 놀라운 유사성을 보이지만, 기존 연구는 GEQ 오류와 regret이 비교 불가능한 목표임을 보여 주었으며, GEQ가 더 넓은 온라인 학습 지형에서 어떻게 자리 잡는지에 대한 정확한 이해는 여전히 열려 있다. 본 연구에서는 GEQ가 알고리즘적 의미에서 Blackwell approachability와 동등함을 보인다. 즉, Blackwell approachability 문제는 블랙박스 GEQ 오라클에 대한 질의(query)만으로 항상 풀 수 있으며, 오라클의 오류율(error rate)에 대한 점근적(asymptotic) 손실 없이 역방향도 성립한다. approachability, regret minimization, calibration 사이의 알려진 동등성과 합치면, 이 결과는 GEQ가 이들 프레임워크와도 동등함을 시사한다. 우리의 환원(reduction)은 효율적이며, 낙관성(optimism)과 강한 적응성(strong adaptivity)과 같은 정교한 보장을 regret minimization에서 GEQ로 전달하는 데 사용할 수 있다. 또한 GEQ에 대한 필요충분 조건을 규명하고, 제약이 없는(unconstrained) 및 제약이 있는(constrained) 의사결정 집합(decision set)을 갖는 GEQ의 서로 다른 개념들 사이의 환원을 확립한다.

원문 초록

Gradient equilibrium (GEQ) is a recently introduced online optimization framework that generalizes first-order stationarity from offline optimization and abstracts problems like online conformal prediction. While GEQ has curious similarities with known online learning frameworks, namely regret minimization, prior work has shown that GEQ error and regret are incomparable objectives, leaving open a precise understanding of how GEQ fits into the broader online learning landscape. In this work, we show that GEQ is equivalent to Blackwell approachability in the algorithmic sense. That is, a Blackwell approachability problem can always be solved using queries to a black-box GEQ oracle, with no asymptotic loss in the oracle's error rate, and vice versa. Taken together with known equivalences between approachability, regret minimization, and calibration, these results imply that GEQ is equivalent to these frameworks, as well. Our reductions are efficient and can be used to transfer refined guarantees, such as optimism and strong adaptivity, from regret minimization to GEQ. Along the way, we also identify necessary and sufficient conditions for GEQ, and establish reductions between different notions of GEQ with unconstrained and constrained decision sets.

요약

최근 도입된 온라인 최적화 프레임워크 그래디언트 균형(GEQ)은 후회(regret)와 목표가 비교 불가능해 온라인 학습 지형에서의 위치가 불분명했으나, 블랙박스 오라클 환원으로 Blackwell approachability와 알고리즘적으로 동등함을 증명한다. approachability·후회 최소화·calibration 간의 기존 동등성과 합치면 GEQ도 이들과 동등하며, 효율적인 환원으로 낙관성과 강한 적응성 같은 정교한 보장을 regret minimization에서 GEQ로 옮길 수 있다.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2606.27315v1제출 시각 미확인

함께 살펴볼 논문

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

arXiv:2609.26978v1stat.ML공통 태그 Sequential Decision Making, online learning, regret minimization

다중 스케일 행렬 가중치를 통한 온라인 역 선형 최적화의 정밀 후회 상한

Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights

고정된 알려지지 않은 선형 효용(utility)을 갖는 온라인 역 선형 최적화를 연구한다. 각 라운드에서 환경(environment)은 컴팩트 행동 집합을 제시하고, 학습자(learner)는 그 집합에서 행동(action)을 추천하며, 환경은 동일한 집합 위에서 효용을 최대화하는 행동을 반환한다. 효용 벡터와 행동이 $d$차원 유클리드 단위 구(unit ball) 안에 있을 때, 시간 지평(time horizon)을 알 필요 없이 모든 시간 지평에 대해 기대 후회(regret)---최적 행동 대비 누적 효용 부족분---가 $O(\sqrt d)$인 무작위 알고리즘을 제시한다. $d$에 대한 의존성은 $T\ge d$인 지평에 대한 알려진 $\Omega(\sqrt d)$ 하한에 의해 상수 배수까지 최적이다. 우리 알고리즘은 기하학적으로 간격을 둔 스케일에서 다항식 특징(feature) 공간上的 행렬 곱셈 가중(matrix multiplicative weights)을 유지한다. 선형 프로그램(linear program)을 풀어 추천 분포를 선택하고, 이용 가능한 행동과 피드백 행동을 비교하여 점수 행렬을 갱신한다. 유리수 oracle 출력과 피드백 행동 하에서, 선형 최적화 oracle에 상대적으로 계산 가능한 구현이 $O(\sqrt d)$ 후회 상한을 유지한다. 차원, 지평, 입력 길이에 대해 다항 시간 실행 복잡도로 동일한 rate를 달성할 수 있는지는 열려 있다.

arXiv:2609.27206v1stat.ML공통 태그 Multi-Armed Bandits, online learning, regret minimization

전문가 조언을 활용한 예측: 다수 전문가 환경에서 상시 후회가 고정 시간 상수에 일치함

Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant

전문가 조언을 활용한 예측(prediction with expert advice)은 온라인 학습(online learning)의 근본적인 문제입니다. 시간 범위(time horizon) $T$가 사전에 알려져 있을 때, $n$명의 전문가에 대한 미니맥스 누적 후회(minimax cumulative regret)는 점근적으로 $\sqrt{\frac{T \ln n}{2}}$입니다. 이는 $T$에 맞추어 조정된 학습률을 사용하는 곱셈 가중치 업데이트(Multiplicative Weights Update) 알고리즘을 통해 달성되며, 타이트한(tight) 것으로 알려져 있습니다. 반면 후회 상한(regret bound)이 모든 시점 $t$에서 동시에 성립해야 하는 경우, 기존에 알려진 최선의 보장은 $\sqrt{2}$배 더 나쁜 $\sqrt{t \ln n}$이었으며, 이 $\sqrt{2}$ 계수가 필수적인지는 알려지지 않은 채로 남아 있었습니다. 본 연구에서는 이것이 필수적이지 않음을 보입니다. 본 논문에서는 시간 범위에 대한 사전 지식을 요구하지 않으면서도, 누적 후회가 모든 $t \ge 1$에 대해 동시에 $R_t \le \bigl(1 + O(\sqrt{\ln \ln n / \ln n})\bigr)\sqrt{t \ln n / 2}$를 만족하는 알고리즘을 제시합니다.

arXiv:2607.14418v1cs.LG공통 태그 Multi-Armed Bandits, Sequential Decision Making, online learning

스폰서 검색 시장을 위한 적응형 광고 부하 설계: 증거, 이론, 배포

Adaptive Ad Load Design for Sponsored Search Markets: Evidence, Theory, and Deployment

광고 부하(ad-load) 설계는 스폰서 검색에서 공급 측의 핵심 의사결정이다. 스폰서 슬롯을 늘리면 수익을 높일 수 있지만, 자연 검색 결과를 밀어내고 사용자 결과를 악화시킬 수 있다. 우리는 안드로이드 앱 스토어에서 수행한 대규모 무작위 현장 실험을 통해 이 트레이드오프를 연구했으며, 500만 명 이상의 사용자가 1개부터 6개까지의 스폰서 슬롯에 노출되었다. 광고 부하를 늘리면 수익이 최대 43% 증가하지만, 총 검색 전환은 최대 5% 감소하고 일일 참여도는 최대 2.2% 감소한다. 이러한 평균 효과는 상당한 이질성을 가린다. 추가 슬롯은 광고 전환율이 높은 쿼리에서 큰 수익 증가를 만들지만, 전환율이 낮은 쿼리에서는 한계 수익이 거의 없거나 음수이다. 이 트레이드오프는 브랜드 광고주 존재와 같이 광고주 구성이 변함에 따라 쿼리 내에서도 이동한다. 이러한 발견에 동기를 받아, 우리는 새로운 적응형 알고리즘인 탐험(exploration) 보강 국소 적응형 광고 부하(exploration-augmented Locally Adaptive Ad Load, e-LAAL)를 설계하고 배포했다. e-LAAL은 최근 결과를 사용해 광고 부하 권장값을 갱신하는 모델(model)-free 쿼리 수준 의사결정 규칙인 LAAL과, 지지(support)를 유지하고 고정 정책 반사실(counterfactual) 벤치마크를 제공하는 정적 탐험(exploration) arm을 결합한다. 우리는 e-LAAL 아키텍처에 대한 유한 시간 동적 후회(dynamic-regret) 보장을 제공한다. 2,230만 명의 사용자와 7,760만 건의 검색을 처리하는 플랫폼 수준의 프로덕션 배포에서 e-LAAL은 배포된 정적 벤치마크 대비 실증적 수익–전환 트레이드오프를 개선하고, 균일한 정적 벤치마크 및 과거 쿼리 의존적 정적 벤치마크를 능가한다.

arXiv:2607.15229v1cs.LG공통 태그 Multi-Armed Bandits, Sequential Decision Making, regret minimization

데이터 기반 블록 교체 스케줄링

Data Driven Block Replacement Scheduling

우리는 \textit{블록 교체 정책(block replacement policy)} 하에서 $N$대의 독립 동형 기계를 유지·관리하기 위한 데이터 기반 알고리즘을 개발한다. 이 정책에서는 각 기계가 고장 시 교체되고, 모든 기계가 길이 $k$의 정규 간격으로 일괄 교체된다. 수명 분포가 알려지지 않은 경우 운영 데이터로부터 비용을 최소화하는 간격 $k^*$를 학습하는 것이 목표이다. 각 의사결정 시점마다 운영자는 $k \in \{1, 2, \ldots, K\}$를 선택하고, 그 결과 고장 이력(완전 수명과 우측 검열(right-censored) 수명의 혼합)을 관측하며, 갱신 함수(renewal function)에 의해 결정되는 단위 시간당 비용을 부담한다. 이를 확률적 다중 팔 밴딧(stochastic multi-armed bandit)으로 형식화하고, $O(K \log T)$ 후회(regret)를 달성하는 Hoeffding 및 Bernstein 기반 하한 신뢰 구간(lower-confidence-bound) 알고리즘을 제안하며, 이는 Lai--Robbins 하한과 일치한다. 블록 교체에 고유한 중첩 관측(nested observation) 성질을 활용한 상관 변형(correlated variants)은 $O((K-k^*)\log T)$ 후회를 달성하고, 차선 arm $k < k^*$에 대한 직접 pull은 $O(1)$번만 필요하다. 보완적으로 Kaplan--Meier 갱신 알고리즘은 검열 데이터로부터 수명 분포를 비모수적으로 추정하여, 거의 확실(almost-sure)한 정책 일관성을 달성하고 장기 구간에서 실증적으로 거의 0에 가까운 추가 후회를 보인다. 또한 평균 비용 MDP 두 가지를 분석한다. 경과 시간(time-elapsed) 형식화는 임의의 수명 분포에 대해 블록 교체가 해당 정책 클래스 내에서 최적임을 보이고, 연령 벡터(age-vector) 형식화는 증가하는 고장률(increasing failure rate) 분포 하에서 단조 임계값(monotone threshold) 구조를 증명하며 gold-standard 비용 벤치마크를 제공한다. 수치 실험은 이론적 순서를 확인하고, 최적 블록 교체와 연령 의존(age-dependent) 교체 사이의 구조적 비용 격차를 밝힌다.

토론

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