PaperlayerView exact revision on arXiv

Source-linked AI summary

Defensive Boosting for Online Probabilistic Forecasting

Georgy Noarov, Aaron Roth

arXiv:2608.13554v1cs.LGcs.CCcs.DSstat.ML

TL;DR

Online probabilistic forecasting에는 span에 대해 경쟁력 있는 Brier 성능과 weak-to-strong classification 보장을 결합하는 효율적인 booster 하나가 필요하다. Defensive Booster는 defensive forecasting을 통해 두 목표를 모두 달성하며, realizable span case에서는 O(1/T) bound를, 목표 rate에서는 weak-learning guarantees를 제공한다.

  • 문제

    기존 online boosting methods는 span-competitive Brier guarantees 또는 weak-to-strong classification guarantees를 각각 제공할 뿐이어서, 두 보장의 결합은 아직 해결되지 않은 forecasting objective로 남아 있다.

  • 방법

    Defensive Booster는 weak class와 self-orthogonality auditors를 사용하는 간단한 black-box reduction이다.

  • 결과

    이 방법은 gradient-boosting-style span guarantees를 달성하고, realizable cases에서 O(1/T) bound를 얻으며, smooth weak learning을 목표 rate의 strong classification으로 전환한다.

  • 시사점 및 한계

    이 접근법은 probabilistic forecasting과 weak-to-strong boosting guarantees를 모두 달성하는 통합적이고 효율적인 경로를 제공한다.

  • 시사점 및 한계

    이 분석은 symmetric weak class H를 가정하며, weak-to-strong guarantee는 (ρ, γ)-smooth weak-learning condition에 조건부이다.

Abstract

from arXiv · show

We study online probabilistic forecasting of binary outcomes chosen by an adaptive adversary. Given an online learning algorithm for a weak hypothesis class $H$, we would like to efficiently obtain two incomparable guarantees that existing online boosting techniques provide separately. Online gradient boosting competes in Brier score with the best predictor induced by the span of $H$ on every sequence, but promises nothing when the span does not contain an accurate predictor. Online weak-to-strong boosting drives classification error to zero under a weak-learning condition, but promises little when that condition fails. We give a simple defensive forecasting algorithm, the Defensive Booster, that obtains both guarantees. On every adaptive sequence, its Brier score is competitive with the best prediction induced by the span of $H$ at the same rate as online gradient boosting; simultaneously, whenever the realized transcript satisfies the smooth weak-learning condition, its Brier score and randomized classification error satisfy the same rate guarantee as online classification boosting. This is achieved by operationalizing the "dual view" of boosting: When the algorithm's randomized classification error is persistently high, its mistake weights form a smooth reweighting on which every weak hypothesis has low edge, yielding an ex-post hard-core certificate that the weak-learning condition fails. We also develop a strongly adaptive variant, which satisfies both guarantees on every time interval. The Defensive Booster is very efficient: it accesses just one weak-class learner, whereas the prior online boosting methods we compare against maintain large weak-learner ensembles. Experiments on synthetic and real data streams demonstrate its strong predictive performance (sometimes substantially improving over all prior baselines) coupled with orders-of-magnitude faster runtime.

1 서론

Defensive Booster는 adaptive sequence에서 unconditional span-comparator guarantee와 conditional weak-to-strong classification guarantee를 결합하는 single-oracle online forecasting algorithm이다. 또한 hard-core failure certificate, strongly adaptive interval guarantee, binary outcome을 넘어서는 확장도 제공한다.

  • 주요 guarantee: Defensive Booster는 모든 adaptive sequence에서 online gradient boosting과 동시에 같은 성능을 내며, 실현된 transcript가 smooth weak learnability를 만족할 때 weak-to-strong guarantee를 달성한다.이 guarantee들은 서로 incomparable하므로 span comparator가 weak-learning condition을, 또는 그 반대가 다른 하나를 포괄하지 않는다.
  • Span guarantee: 모든 adaptive sequence에서 Defensive Booster의 Brier score는 H의 Λ-norm-bounded span이 유도하는 모든 predictor와 online gradient boosting과 동일한 rate로 경쟁한다.second-order bound는 realizable span case에서 O(1/T)를 제공한다.
  • Weak-to-strong guarantee: (ρ, γ)-smooth weak-learning condition하에서 Brier score와 randomized classification error는 모두 max{ρ, ˜O(1/(γ^2T))} 이하이다.ρ = O(ε)이면 두 error는 ˜O(1/(γ^2ε)) rounds 후 ε에 도달하며, forecast를 1/2에서 thresholding하면 deterministic error는 randomized error의 두 배 이하이다.
  • Failure certificate: Persistent large error는 ex-post hard-core certificate를 산출한다. 즉, mistake weight가 모든 weak hypothesis의 edge가 낮은 smooth reweighting을 이루어 weak-learning condition의 실패를 인증한다.이 certificate는 boosting의 dual view를 사용하며 error가 높게 유지될 때 weak-learning condition을 contradiction으로 바꾼다.
  • 확장: Strongly adaptive variant는 O(log T)의 active oracle copy를 사용해 모든 contiguous interval에서 polylogarithmic factor를 제외한 두 guarantee를 제공한다.이 algorithm은 arbitrary bounded real-valued outcome에 대한 squared-loss span guarantee도 유지하며, chronological regression stream에서 해당 확장을 평가한다.
  • 방법과 효율성: Ensemble-based online boosting과 달리 Defensive Booster는 weak learner 하나와 두 개의 scalar adaptive-gradient state를 유지하므로, round마다 oracle call 한 번과 O(1) arithmetic만 필요로 한다.그 forecast는 probability-valued이며 여러 weak-learner copy를 결합하는 대신 dual view를 operationalize한다.

2 설정 및 알고리즘 구성 요소

이 논문은 adaptive adversary에 대한 sequential Brier forecasting을 연구하며, multiaccuracy와 self-orthogonality를 정식화하기 위해 [−1,1] encoding을 사용한다. 알고리즘 도구는 second-order oracle를 갖는 symmetric weak class를 가정하고, 나머지 일차원 업데이트에는 scalar adaptive OGD를 사용한다.

  • Online forecasting: 각 라운드마다 adversary가 x_t를 공개하면 learner는 p_t ∈ [0,1]을 예측하고, 이후 binary Y_t를 관측한 뒤 Brier loss (Y_t − p_t)^2를 받는다.이 sequence는 learner의 과거 예측에 적응할 수 있으며, binary 설정은 probability 해석과 classification 해석을 모두 지원한다.
  • Weak class and comparators: Weak class H는 X → [−1,1]인 함수들을 포함하며 symmetric하다고 가정한다. 그렇지 않으면 learner는 negated hypotheses를 추가하고 두 부호 모두에 대해 실행한다.이 framework는 norm-bounded span도 정의하고 span comparator를 probability scale로 재조정하지만, 그 결과 얻는 forecast가 반드시 [0,1]에 속하는 것은 아니다.
  • Forecast representation: [−1,1] encoding은 σ_t = 2Y_t − 1, μ_t = 2p_t − 1, residual r_t = σ_t − μ_t = 2(Y_t − p_t)를 설정한다.Multiaccuracy test는 residual을 H와 대조하고, self-orthogonality test는 residual을 forecast 자체와 대조한다.
  • Weak-class oracle: 문제에 의존하는 유일한 primitive는 second-order weak-class oracle이며, 그 regret는 누적 제곱 coefficient의 제곱근에 따라 증가하고 여기서는 forecast residual이 coefficient를 제공한다.이 self-bounding residual-energy 구조는 1/(γ^2ε)의 weak-to-strong sample complexity를 제공한다. 이는 first-order guarantee의 1/(γ^2ε^2)와 대비되며, 더 강한 oracle model을 사용함에도 [Beygelzimer et al., 2015b]의 기존 model과 동일한 최적 rate를 달성한다.
  • Class-independent machinery: 나머지 모든 online machinery는 class-independent하다. 이 방법은 scalar adaptive OGD 두 개를 사용하며, 업데이트를 [−1,1]에 projection하고 second-order scalar regret bound를 만족한다.이 routine은 a_1 = 0 및 V_0 = 4로 초기화한다. 유한 class에는 second-order experts implementation을 사용할 수 있고, 더 넓은 class에는 adaptive 또는 scale-free online linear optimization을 사용할 수 있다.

3 Defensive Booster

Defensive Booster는 하나의 weak-class oracle과 두 개의 scalar adaptive-OGD 상태를 결합하고, 정확한 one-dimensional root rule로 각 예측을 계산한다. 이 구성은 명시적인 weak-hypothesis ensemble 없이 모든 adaptive binary sequence에서 second-order multiaccuracy와 self-orthogonality 보장을 제공한다.

  • 알고리즘: Defensive Booster는 weak-class oracle을 self-auditor state S 및 auditor-aggregation state A와 결합하며, one-dimensional scalar adaptive OGD routine 하나만 사용한다.S는 self-orthogonality를 확립하고, A는 weak-class auditor와 self auditor를 집계한다.
  • 알고리즘: 각 라운드에서 affine function F_t(µ)=q_H,t b_H,t+q_S,t θ_t µ를 구성하고, root rule로 µ_t를 선택한 뒤 forecast p_t=(1+µ_t)/2를 산출한다.root는 constant time에 계산할 수 있으므로, 각 라운드에는 oracle prediction/update 한 번과 O(1) arithmetic만 필요하다.
  • 알고리즘: forecast는 weak hypotheses의 linear combination이나 weighted vote가 아니라 exact affine root에서 직접 생성되는 probability다.이 방법은 Farina and Perdomo (2026)의 online-learning 및 variational-inequality framework에 속하는 deterministic one-dimensional instance로 설명된다.
  • 보장: root rule은 매 라운드 aggregated auditor gain을 nonpositive로 만들며, endpoint comparison을 통해 weak-class와 self-auditor의 cumulative gain을 모두 제어할 수 있게 한다.두 endpoint comparator는 각각 weak-class auditor만 선택하거나 self auditor만 선택하는 경우에 해당한다.
  • 보장: Theorem 3.3은 H에 대한 second-order multiaccuracy와 self-orthogonality를 A_H=a_H+4, B_H=b_H+8, A_S=8, B_S=16인 상수와 함께 확립한다.이 정리는 binary label을 갖는 모든 adaptive sequence에 적용되며, 제시된 multiaccuracy rate에는 √S_T+B_H가 포함된다.

4 주요 보장

이 절은 Brier/span-regret 보장과 hard-core weak-to-strong 보장을 병렬로 확립한다. 전자는 모든 adaptive sequence에서 성립하고, 후자는 실현된 transcript가 smooth weak learning을 만족할 때 적용된다. 핵심 연결고리는 Booster의 mistake weighting이 Brier 및 classification error가 이미 작지 않은 한 낮은 edge를 갖는다는 점이다.

  • 4.1 Brier/span 보장: Defensive Booster는 모든 adaptive binary sequence와 모든 f ∈spanΛ(H)에 대해 Brier/span 보장을 달성하며, Λ = 1일 때 conv(H)도 포괄한다.
  • 4.1 Brier/span 보장: 비교 대상의 loss가 0이면, resulting Brier loss는 BT = O((C^2 + D)/T)를 만족한다.
  • 4.2 Hard-core mistake weighting: smooth weak-learning condition은 ex post 조건이며, 그 bounded smooth reweighting은 SmoothBoost 와 hard-core construction 에서 사용되는 smooth distribution과 동치다.
  • 4.2 Hard-core mistake weighting: Theorem 4.4는 Booster의 randomized mistake weighting이 모든 h ∈H에 대한 edge bound를 통해 hard-core certificate를 제공함을 보인다.가중치는 wt = |Yt − pt|이므로, 이 certificate는 알고리즘 자체의 실현된 mistake를 대상으로 한다.
  • 4.3 Weak-to-strong rate: (ρ0, γ0)-smooth weak-learning condition하에서 Brier error, randomized classification error, thresholded deterministic classification error는 모두 상수배를 제외하면 at most ε다.Threshold classifier의 average classification error는 at most 2ρw다. 목표 error ε을 달성하려면 smoothness ρ0 = O(ε)가 필요하며, BH가 logarithmic이거나 lower order일 때 1/(γ0^2ε)에 의존한다.

5 모든 구간에서의 Boosting

강한 적응형 Defensive Booster는 전체 horizon에서 성립하던 두 예측 보장을 모든 연속 구간으로 확장하며, polylogarithmic factor만큼의 비용이 든다. weak-learning 가정 없이 span-regret을 유지하는 동시에 local weak-to-strong rate를 보존하지만, logarithmic overhead와 여러 active oracle copy가 필요하다.

  • 구간 wrapper: second-order specialist wrapper는 local residual energy에 대한 의존성을 보존해, 일반적인 O(|I|) interval-regret bound가 초래하는 rate loss를 피한다.dyadic interval에서 새 learner를 결합하고 second-order confidence-rated experts algorithm을 적용한다.
  • 구현: wrapper는 매 라운드 weak learner의 active copy를 최대 1 + ⌈log_2 T⌉개 유지해 명시적인 logarithmic overhead를 부과한다.동일한 wrapper를 weak-class oracle과 두 scalar routine에 각각 적용한다.
  • 강한 적응형 Defensive Booster: Theorem 5.2는 모든 adaptive binary sequence와 모든 interval I에 대해 simultaneous interval certificate를 제공해, Defensive Booster의 두 보장을 full horizon 너머로 확장한다.구성에서는 weak-class oracle과 scalar routine에 second-order interval wrapper를 적용한 뒤, 원래의 root rule을 재사용한다.
  • 강한 적응형 boosting: 모든 interval에서 ρ_I > 0이면 mistake weight가 local hard-core witness를 이루고, threshold classifier의 error는 2ρ_I 이하이다.이 결론은 full-horizon certificate argument를 I에 국소적으로 적용해 얻는다.
  • 강한 적응형 boosting: local weak-learning condition이 ρ_0 = O(ε)로 성립할 때, target interval error ε을 달성하려면 n = O(log^2(T)/(γ_0^2ε))이 필요하며, span-regret은 unconditional하게 유지된다.보장은 simultaneous하게 성립하므로 transcript를 관찰한 뒤 interval comparator와 span comparator를 선택할 수 있으며, I 바깥의 가정은 필요하지 않다.

6 실험

실험 결과, Defensive Booster는 하나의 learner만 사용하면서 상호보완적인 synthetic stream에서 더 강한 baseline 계열을 추적하며, mistake weight가 예측된 smooth하고 low-edge인 hard-core witness를 보임을 확인했다. 또한 stream별로 달라지지 않는 고정 tuning protocol에서도 경쟁력 있는 predictive performance를 유지했다.

  • Protocol: 실험에서는 두 개의 controlled synthetic stream과 네 개의 naturally ordered real dataset에서 Defensive Booster를 online gradient boosting, online weak-to-strong boosting, Brier aggregator 및 boosting을 적용하지 않은 control과 비교했다.Synthetic stream은 각각 span guarantee와 smooth weak-learning condition을 별도로 검증하며, real stream은 기록된 순서대로 처리했다.
  • Results: Defensive Booster는 binary aggregation stream에서 .0026 classification error와 .0018 Brier loss를 달성해 OGB와 모든 개별 ensemble을 앞섰으며, 100개가 아니라 하나의 learner만 사용했다.OGB의 error는 .0331이었고, Brier aggregator의 loss는 .0025였다.
  • Results: random-label mixture에서 Defensive Booster의 .1965 Brier loss는 OGB의 .1933에 근접했으며 모든 weak-to-strong booster를 앞서, 이들의 guarantee가 적용되지 않을 때도 경쟁력을 보였다.Brier aggregator는 .1937에 도달했으며, OSBoost, AdaBoost.OL, Online BBM은 각각 .2467, .2708, .2963에 도달했다.
  • Results: random-label mixture에서 multiaccuracy와 self-orthogonality error 및 weak-class edge가 감소하는 동안 mistake-weight density는 비자명한 수준을 유지해, 예측된 smooth하고 low-edge인 witness를 생성했다.진단값은 20개 seed에 대해 평균했으며, random-label component 때문에 randomized error는 비자명한 수준을 유지했다.
  • 하나의 learner 대 ensemble: Defensive Booster와 boosting을 적용하지 않은 control은 round당 CH + O(1)로 확장되는 반면, 각 ensemble baseline의 비용은 NCH + O(N)이며 Brier aggregator는 네 개의 ensemble을 모두 실행한다.보고된 protocol에서 각 boosting baseline은 N = 100개의 learner를 유지하므로, aggregator는 이에 따라 400개의 learner를 실행한다.
  • Results: Synthetic stream 전반에서 informative span comparator가 존재할 때는 OGB가 가장 강하고, smooth weak learning에서는 classification booster가 가장 강하며, Defensive Booster는 공통 tuning하에서 두 경우 모두 경쟁력을 유지한다.모든 synthetic 결과는 T = 3000을 사용하고 20개 seed에 대한 평균을 보고했으며, real stream은 shuffling 없이 한 번 처리했다.

7 관련 연구

이 연구는 defensive boosting을 online gradient 및 weak-to-strong boosting, strongly adaptive learning, smooth boosting과 hard-core constructions, multicalibration, defensive forecasting에 연결한다. 가장 밀접한 선행 연구들은 이 접근법의 span-regret, classification, interval-adaptive, transcript-certificate 측면에 동기를 부여한다.

  • Online gradient boosting: Online gradient boosting은 여러 online learner를 사용해 convex hulls 또는 norm-bounded spans와 경쟁하며, 관련 연구는 adversarial streams에서의 gradient boosting과 convex-hull regret을 다룬다.Beygelzimer et al. (2015a)은 smooth convex losses에 대해 N개의 복사본을 사용한다. Hu et al. (2017)은 더 강한 edge 가정하에 분석을 adversarial streams로 확장한다. Hazan and Singh (2021)은 multiplicative weak learner를 사용한다.
  • Online weak-to-strong boosting: Online weak-to-strong boosting은 SmoothBoost 기반 방법부터 약한 online learnability 가정하에서 rate-optimal한 Online BBM까지 포괄한다.Oza and Russell (2001)은 실용적인 online bagging과 boosting을 시작했다. Chen et al. (2012)은 smooth distributions를 사용해 SmoothBoost를 적용했다. Beygelzimer et al. (2015b)은 자신들의 모델에서 Online BBM과 일치하는 lower bounds를 제시했다.
  • Strong adaptivity: Strongly adaptive learning은 geometric-cover reductions 또는 local-energy confidence bounds를 통해 모든 contiguous interval에서 낮은 regret을 얻으며, parameter-free adaptivity와는 다르다.Daniely et al. (2015), Cutkosky (2020), Gaillard et al. (2014)은 관련 도구를 제공한다. 한편 Beygelzimer et al. (2015b)은 adaptive이지만 interval 의미에서 strongly adaptive하지는 않다.
  • Smooth boosting과 hard-core sets: 이 논문의 smooth transcript reweightings는 boosting의 minimax 및 hard-core-set traditions와 연결되며, smooth boosting, agnostic adaptive boosting, algorithmic hard-core constructions를 포함한다.인용된 기초 연구로는 Servedio (2003), Gavinsky (2003), Freund and Schapire (1996), Impagliazzo (1995), Klivans and Servedio (2003), Barak et al. (2009)이 있다.
  • Multicalibration과 hard-core measures: 이 연구의 weak-to-strong 분석은 multiaccuracy와 hard-core measures 사이의 연결을 사용하며, 더 강한 calibrated variants가 아니라 only multiaccuracy만을 요구한다.이는 Trevisan et al. (2009), Casacuberta et al. (2024), Casacuberta et al. (2025)와 연결된다. 한편 sequential adversarial calibration은 online 환경에서의 한계를 보여준다.
  • Defensive forecasting: 이 알고리즘은 defensive forecasting의 틀 안에서 개발되며, 여기서 probabilities는 continuous skeptic betting strategies를 차단하고 현재 forecast에 의존해 조언하는 second-guessing experts를 지원한다.Vovk et al. (2005a,b)은 이 framework를 도입했고, Vovk (2007)은 second-guessing capability를 확립했으며, 이는 root rule에서 사용되는 affine test와 일치한다.

A 유보된 증명 … A.3 강한 적응형 확장

부록은 논문의 online learning 도구, 전체 구간 certificate의 귀결, 강한 적응형 확장에 대한 증명을 제공한다. 적응형 구성은 dyadic specialist interval과 confidence-rated aggregation을 사용해 interval guarantee와 self-orthogonality inequality를 확립한다.

  • A 유보된 증명: 부록은 본문에서 사용한 표준 online-learning 도구와 일상적인 귀결의 증명을 모은다.
  • A.1 Scalar second-order regret: scalar second-order regret 증명은 비증가 learning rate, projection nonexpansiveness, bounded gradient, 최종 square-root inequality를 사용한다.η_t = 1/√V_{t−1}로 설정하고, 첫 번째 항들은 2√V_T로 bound하며, 두 번째 항들은 g_t^2 ≤ 4 ≤ V_{t−1}를 사용해 bound한다.
  • A.2 전체 구간 certificate의 귀결: 전체 구간 certificate는 weighted residual average가 weak-learning threshold보다 낮은지 높은지에 따라 나누어, 제시된 randomized-error bound를 얻는다.threshold가 충족되면 smooth weak-learning condition과 Theorem 4.4가 bound를 제공하고, 그렇지 않으면 certificate가 error를 직접 제어한다.
  • A.2 전체 구간 certificate의 귀결: 같은 certificate는 deterministic threshold error도 weighted residual average의 두 배로 bound한다. 모든 threshold mistake의 residual magnitude가 최소 1/2이기 때문이다.
  • A.3 강한 적응형 확장: strongly adaptive 구성은 4T개 미만의 interval을 포함하는 canonical dyadic interval family에서 새로운 booster copy를 시작하며, 각 round에 active한 copy는 최대 1 + ⌈log2 T⌉개다.임의의 interval은 최대 M_T개의 dyadic member로 분해되며, active copy는 second-order confidence-rated experts algorithm으로 aggregate된다.
  • A.3 강한 적응형 확장: confidence-regret reduction과 second-order excess-loss bound를 결합하고 Cauchy–Schwarz를 사용해, dyadic copy와 interval comparator로 strongly adaptive guarantee를 증명한다.
  • A.3 강한 적응형 확장: 알려지지 않은 horizon은 fixed-horizon 구성을 doubling epoch에서 재시작해 처리하며, logarithmic factor를 추가하는 대신 현재 epoch의 wrapper만 active하게 유지한다.어떤 interval도 최대 1 + ⌈log2 T⌉개의 epoch와 교차하며, second-order 항과 additive 항에는 각각 1 + ⌈log2 T⌉ factor가 붙는다.
  • A.3 강한 적응형 확장: 모든 interval에서 root sign property는 aggregated auditor gain을 nonpositive로 만들고, endpoint, weak-oracle, sign comparator에 대한 interval regret는 self-orthogonality를 확립한다.두 sign을 모두 취하고 H의 symmetry를 사용하면 inequality의 absolute-value form을 얻는다.

B 분리: 보장들은 서로 비교 불가능하다 · C 추가 실험 세부 사항 및 결과

Brier/span 보장과 weak-to-strong 보장은 서로 비교 불가능하다. smooth weak learning이 constant span loss와 공존할 수도 있고, 작고 비정보적인 부분집합이 weak learning을 무너뜨리면서 평균 span loss에는 거의 영향을 주지 않을 수도 있다. binary 실험에서는 Brier/span 경쟁과 randomized classification error를 사용해 이 보장들을 각각 측정한다.

  • B 분리: 보장들은 서로 비교 불가능하다: 두 보장은 서로 비교 불가능하다. 모든 reweighting에서 positive weak-class edge가 존재해도 모든 span-induced score의 squared loss는 constant일 수 있다.이는 squared loss가 numerical score에 의존하는 반면, weak-to-strong boosting은 그 부호를 활용할 수 있기 때문이다.
  • B 분리: 보장들은 서로 비교 불가능하다: 첫 번째 분리에서는 어떤 단일 hypothesis도 항상 정답을 맞히지 못하지만 uniform hypothesis average는 완벽하게 분류하며, 모든 span score는 nonzero loss를 초래한다.average는 매 라운드 positive signed margin을 갖지만, best squared loss는 (1−δ)^2/(8(1+δ^2))이다.
  • B 분리: 보장들은 서로 비교 불가능하다: 고정된 coefficient-norm budget으로 span score를 clipping한 뒤에도 첫 번째 분리는 유지된다. δ ≤1/(2Λ)이면 transcript의 average Brier loss는 여전히 최소 1/(8(Λ + 1)^2)이다.따라서 clipping은 bounded norm에서 이 분리를 제거하지 못한다.
  • B 분리: 보장은 서로 비교 불가능하다: δ가 0에 가까워질수록 span의 최적 제곱 손실은 1/8에 가까워지는 반면, Defensive Booster의 Brier score와 classification error는 smooth weak learning 하에서 사라진다.따라서 span-regret만으로는 smooth weak-learning condition이 거의 완벽한 예측을 강제하는 transcript에서도 상수 손실이 허용될 수 있다.
  • B 분리: 보장들은 서로 비교 불가능하다: 반대로 smooth weak-learning condition은 density m/T인 부분집합에서 실패할 수 있지만, span comparator는 여전히 average squared loss m/(4T)를 달성한다.comparator는 부분집합 바깥에서는 완벽하게 예측하고 그 안에서는 probability 1/2를 출력하므로, m/T가 작으면 부분집합의 기여는 작다.
  • B 분리: 보장들은 서로 비교 불가능하다: 반대 방향의 구성에서는 exceptional subset에 지지되는 reweighting을 사용하며, 그 weak-class edge는 zero이다. 이는 ρ ≤ m/T인 모든 smooth condition의 실패를 증명한다.동일한 부분집합에서 두 hypothesis는 서로 반대되는 방식으로 불일치하고, 그 밖에서는 label과 일치한다.
  • C 추가 실험 세부 사항 및 결과: binary 실험에서는 Brier loss와 offline least-squares comparator를 사용해 span 경쟁을, randomized classification error를 사용해 weak-to-strong 성능을 각각 평가한다.후자는 forecaster의 mistake weighting의 density와 같다. real stream에서는 기록된 example order를 유지하며, regression과 strongly adaptive 실험은 Appendices D.1 및 E에 제시한다.

C.1 프로토콜 및 구현

비교에서는 Defensive, strongly adaptive Defensive, unboosted control, ensemble baseline, Brier aggregator를 포함한 8개 방법을 평가한다. 구현은 확률 출력을 표준화하고, 사전 선언된 tuning 및 stream 프로토콜을 사용하며, 계산 비용이 크게 다른 방법들을 비교한다.

  • 알고리즘: 주요 비교에는 8개 방법이 포함된다: Defensive, strongly adaptive Defensive, 2개의 unboosted control, 4개의 ensemble baseline, Brier aggregator다.Defensive는 class-independent scalar adaptive-OGD state 2개를 사용하고, strongly adaptive Defensive는 active dyadic scale마다 weak learner 1개를 유지한다.
  • 알고리즘: unboosted control은 weak class에 대한 squared-loss regression과 3개의 boosting baseline이 사용하는 base online binary classifier를 짝지어 boosting의 기여를 분리한다.두 대조군 모두 단일 learner를 유지한다.
  • 알고리즘: ensemble baseline은 주요 비교에서 weak learner 100개를 사용하며, Brier aggregator는 exponential weight로 이들의 확률을 결합하고 초과 누적 Brier loss를 최대 2 log 4로 제한한다.learner-count sweep에서는 ensemble size N ∈ {1, 5, 20, 100}을 평가한다.
  • 실험 프로토콜: 실험에서는 algorithm family마다 사전 선언된 tuning rule 1개를 사용한다. synthetic 결과는 T = 3000 rounds에 대해 seed 20개의 평균을 내는 반면, real stream은 chronological order를 유지하고 deterministic run 1회를 사용한다.experiments directory에는 보고된 모든 결과를 위한 generator, loader, implementation, command가 포함되어 있다.
  • 실행 시간: Defensive와 unboosted control의 라운드당 비용은 CH + O(1)인 반면, ensemble baseline의 비용은 NCH + O(N)이며, OSBoost는 O(N log N)의 simplex projection overhead를 추가한다.여기서 CH는 weak-class learner 1개의 prediction/update 비용이고, 주요 비교의 ensemble은 N = 100을 사용한다.

C.2 통제된 합성 스트림

통제된 합성 스트림은 weak-learning condition의 동작과 span-comparator의 동작을 분리한다. Defensive Booster는 binary aggregation에서 효과적으로 집계하고, 두 보장이 갈라지는 linear stream에서도 하나의 weak learner만으로 경쟁력을 유지한다.

  • 실험 설계: 다섯 개 스트림은 smooth weak-learning condition 검정과 span 경쟁 검정을 구분한다. planted decoy와 binary aggregation은 해당 condition을 만족하는 반면, 세 linear stream에는 noisy label 또는 weak signal이 포함된다.finite-class stream은 weak rule 값의 벡터만 노출하는 반면, linear stream은 Euclidean unit ball을 사용한다.
  • Planted decoy: 하나의 hidden base rule이 sign-perfect인 planted decoy에서는 unboosted classifier와 OSBoost가 이를 가장 빠르게 식별하고, Defensive Booster도 낮은 error에 도달한다.이 스트림은 boosting을 요구하기보다 큰 weak class 내 식별을 검증한다.
  • Linear stream: 세 linear stream에서 Defensive Booster는 .0570 Brier loss를 달성해 offline span score의 .0900과 비교되며, 비교 전반에서 더 나은 method family와 경쟁력을 유지한다.random-label mixture에서는 OGB, unboosted regressor, Defensive Booster가 classification-boosting baseline보다 우수하다. 이 데이터에서는 OGB가 가장 강력하고, 두 비교 모두에서 Defensive Booster는 더 나은 family와 경쟁력을 보인다.
  • 효율성: Defensive Booster는 100개 learner의 ensemble이 아니라 one online weak learner로 이러한 비교 성능을 달성한다.Table 4는 globally fixed tuning rule하에서 이 효율성을 보고한다.

C.3 자연스럽게 정렬된 실수 스트림 · D 유계 실수값 결과로의 확장

시간순 실데이터 스트림에서 Defensive Booster는 Electricity와 Occupancy에서 가장 우수한 Brier 성능을 달성하면서 Bank Marketing와 Airlines에서도 경쟁력을 유지한다. 또한 이 방법은 유계 실수값 결과로 변경 없이 확장되며, affine encoding 이후에도 span 및 low-loss 보장을 보존한다.

  • C.3 자연스럽게 정렬된 실수 스트림: 실수 스트림 평가는 기록된 시간순으로 정렬된 네 개의 공개 binary prediction stream인 Bank Marketing, Electricity, Airlines, Occupancy를 사용한다.모든 데이터셋은 128차원 deterministic signed-hash 표현과 Euclidean unit-ball weak class를 사용한다.
  • C.3 자연스럽게 정렬된 실수 스트림: 전처리는 causal하다. 현재 numeric value에는 이전 문맥의 통계를 사용하고, 미래 feature와 label은 표현에 절대 들어가지 않으며, Bank Marketing에서는 사용할 수 없는 통화 지속 시간을 제거한다.각 행에는 bias feature가 포함되며 unit norm으로 정규화된다. numeric value는 standardize한 뒤 running standard deviation 5개까지 clip하고 hash한다.
  • C.3 자연스럽게 정렬된 실수 스트림: Defensive Booster는 Electricity와 Occupancy에서 Brier loss가 가장 낮다. Occupancy에서는 .007 loss로, OGB의 .016보다 절반 이하이다.Figure 10은 Electricity에서 표시된 여섯 개 baseline 모두보다 실질적으로 낮은 Brier loss를, Occupancy에서는 가장 낮은 loss를 보고한다. 또한 Occupancy에서 deterministic error도 가장 낮다.
  • C.3 자연스럽게 정렬된 실수 스트림: AdaBoost.OL은 Occupancy에서 randomized error가 가장 낮고 Electricity에서 두 classification error가 모두 가장 낮으며, 이는 직접적인 classification objective와 일치한다.반면 Defensive Booster는 probabilistic forecasting을 목표로 하며, Brier 향상은 단순히 더 적은 learner를 유지하기 때문이라고 설명할 수 없다. 두 unboosted control 모두 Electricity와 Occupancy에서 상당히 더 나쁜 성능을 보이기 때문이다.
  • C.3 자연스럽게 정렬된 실수 스트림: Brier aggregator는 Bank Marketing에서 .0010 차이로 가장 우수하고, Airlines에서는 OGB가 가장 작다. 이때 세 방법의 차이는 6·10−5 미만이다.Bank Marketing에서는 OGB와 Defensive Booster가 비슷하며, Airlines에서는 unboosted regressor도 경쟁력 있다.
  • D 유계 실수값 결과로의 확장: 결과 Y_t가 [0,1]에 있을 때 affine encoding σ_t = 2Y_t −1, μ_t = 2p_t −1, r_t = 2(Y_t −p_t)을 사용하면 변경 없이 Defensive Booster를 bounded regression stream에 적용할 수 있다.다른 고정 유계 구간도 affine rescaling을 통해 이 설정으로 환원된다.
  • D 유계 실수값 결과로의 확장: Y_t ∈[0,1]인 모든 adaptive sequence에 대해 Proposition D.1은 Theorem 3.3의 multiaccuracy 및 self-orthogonality 보장과 이에 대응하는 average-squared-error low-loss 결론을 보존한다.Lemma 3.2가 σ_t ∈[−1,1]을 허용하고 이후 논증이 동일한 certificate와 squared-loss expansion을 사용하므로 증명은 변경 없이 이어진다.

D.1 bounded outcome 회귀 실험

timestamp 순으로 정렬된 세 bounded-outcome 회귀 stream에서 Defensive Booster는 최종 squared error가 가장 낮았으며, 100-learner online gradient boosting을 앞서면서도 weak learner 하나만 사용했다. 공통의 chronological evaluation protocol에서도 unboosted 및 running-mean control 대비 우위가 유지됐다.

  • Datasets: 실험에는 Appliance Energy, Bike Demand, Interstate Traffic이 포함되며, normalized MSE와 original-unit RMSE는 고정된 scale factor만큼만 다르고 outcome clipping은 적용하지 않았다.세 stream에는 가정용 appliance 사용량, 자전거 대여량, westbound I-94 교통량과 관련 sensor, calendar 또는 weather 측정값이 포함된다.
  • Experimental setup: 평가는 각 chronologically ordered stream의 처음 10%를 initialization에 사용하고 나머지 remaining 90%에 대한 prediction을 보고하며, features는 이전 row에서만 standardize했다.Contexts에는 calendar, sensor, weather variable이 포함되며, Bike와 Traffic에는 한 시간, 하루, 일주일 전에 관측된 target도 포함된다.
  • Experimental setup: 모든 learned method는 128차원의 normalized feature-hashed context, unit-ball linear weak class, dataset 간 고정 hyperparameter를 공유한다.Defensive Booster는 second-order linear oracle 하나를 사용하는 반면, OGB는 이러한 oracle을 N = 100개 유지한다.
  • Results: Appliance Energy, Bike Demand, Interstate Traffic에서 각각 OGB보다 18%, 29%, and 17% lower normalized MSE를 기록했으며, 모든 stream에서 최종 loss가 가장 낮았다.두 control은 Bike와 Traffic에서 모두 상당히 더 나빴으므로, 이러한 향상은 running mean을 예측하거나 shared weak learner를 한 번 적용한 결과로 설명되지 않는다.

E 강한 적응형 실험

강한 적응성은 효율적인 온라인 업데이트를 유지하면서 분포 변화 상황에서 성능을 향상한다. 또한 구간 수준의 forecasting 동작을 weak-class edge 조건과 연결하는 국소 hard-core witness를 산출한다.

  • 실제 스트림 비교: Electricity에서 강한 적응성은 Brier loss를 .0772에서 .0644로, deterministic error를 .1077에서 .0851로, randomized error를 .1538에서 .1289로 낮춘다.또한 Airlines의 Brier loss를 .2094에서 .2066으로, Occupancy의 Brier loss를 .0071에서 .0069로 낮추지만, Bank의 Brier loss는 .0800에서 .0807로 높인다.
  • 구현 및 효율성: 강한 적응성은 기본 forecaster보다 runtime이 약 6배 많이 들지만, 원래 실제 스트림에서는 100-learner ensemble보다 여전히 3–10× 빠르다.적응형 구현은 실제 스트림에서 라운드당 85–89 microseconds, INSECTS에서는 라운드당 83–85 microseconds가 걸린다.
  • 실제 스트림 비교: 적응형 변형은 Bank와 Airlines에서 기본 forecaster를 밀접하게 추적하고, 이후의 high-loss Electricity 구간을 개선하며, Occupancy의 full-stream loss에서는 적응성을 선호한다.이 국소 비교는 데이터셋 전체에 동일한 window를 적용한 trailing 1,000-round Brier loss를 사용한다.
  • Controlled drift benchmark: Adaptive boosting은 controlled-drift INSECTS 스트림 4개에서 두 metric을 모두 낮추며, continuously incremental stream에서의 차이는 최대 .0012다.적응형 구현은 라운드당 83–85 microseconds가 걸린다.
  • 국소 hard-core witness: 국소 hard-core witness는 trailing dyadic interval 전반에서 조밀한 mistake weight와 낮은 normalized weak-class edge를 짝지어 식별한다.Figure 14는 abrupt INSECTS stream에서 이러한 witness를 시각화하며, 점선은 발표된 change point 5개를 표시한다.
Loading 2608.13554v1…