Gradient-Variation Interval Regret를 이용한 온라인 학습

본 논문은 온라인 알고리즘이 모든 시간 간격(time interval)에 대해 우수한 성능을 발휘할 것을 요구하는 구간 후회(interval regret) 지표를 사용하여 비정상성(non-stationary) 온라인 학습을 조사합니다. 우리는 온라인 함수 기울기(gradient)의 누적 변화를 나타내는 근본적인 척도인 기울기 변화량(gradient variation)에 따라 스케일링되는 구간 후회 경계(interval regret bound)를 달성하는 최초의 온라인 학습 알고리즘을 제안합니다. 기울기 변화량은 다양한 문제 의존적 양(problem-dependent quantities)과 관련이 있으며, 확률적 최적화(stochastic optimization) 및 기타 문제들과 밀접하게 연결되어 있습니다. 우리의 방법은 강력한 이론적 보장을 달성하는 단순하고 효율적인 2층 온라인 앙상블(two-layer online ensemble) 구조를 채택합니다. 구체적으로, 이 방법은 최악의 경우에 minimax-optimal rate를 유지하면서 동시에 다양한 문제 의존적 양에 적응하는 후회 경계(regret bound)를 누립니다. 또한, 하이퍼파라미터 튜닝의 어려움을 인식하여, 잠재적으로 알 수 없는 이러한 상수들에 자동으로 적응하는 Lipschitz 및 매끄러움(smoothness) 불가지론적(agnostic) 변형을 도입합니다. 이는 주로 독자적인 관심 대상이 될 수 있는 새로운 Lipschitz-adaptive 메타 알고리즘에 의해 가능해집니다. 구간 후회(interval regret)를 넘어, 우리의 방법은 더 넓은 함의를 제공합니다. 즉, 임의의 간격에 대해 변화하는 비교 대상(comparators)과 경쟁하는 더 강력한 척도인 구간 동적 후회(interval dynamic regret)에 대한 다각적인 경계를 제공하며, 확률적 확장적 적대적 최적화(stochastic extended adversarial optimization)에 대한 최초의 조각별 특성(piecewise characterization)을 도출합니다. 이론적 결과는 실험을 통해 검증되었습니다.