A Modular Algorithm for Non-Stationary Online Convex-Concave Optimization
By: Qing-xin Meng, Xia Lei, Jian-wei Liu
Potential Business Impact:
Helps games find fair wins even when rules change.
This paper investigates the problem of Online Convex-Concave Optimization, which extends Online Convex Optimization to two-player time-varying convex-concave games. The goal is to minimize the dynamic duality gap (D-DGap), a critical performance measure that evaluates players' strategies against arbitrary comparator sequences. Existing algorithms fail to deliver optimal performance, particularly in stationary or predictable environments. To address this, we propose a novel modular algorithm with three core components: an Adaptive Module that dynamically adjusts to varying levels of non-stationarity, a Multi-Predictor Aggregator that identifies the best predictor among multiple candidates, and an Integration Module that effectively combines their strengths. Our algorithm achieves a minimax optimal D-DGap upper bound, up to a logarithmic factor, while also ensuring prediction error-driven D-DGap bounds. The modular design allows for the seamless replacement of components that regulate adaptability to dynamic environments, as well as the incorporation of components that integrate ``side knowledge'' from multiple predictors. Empirical results further demonstrate the effectiveness and adaptability of the proposed method.
Similar Papers
Dual Adaptivity: Universal Algorithms for Minimizing the Adaptive Regret of Convex Functions
Machine Learning (CS)
Helps computers learn better in changing situations.
Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints
Machine Learning (CS)
Learns to make good choices, even when things change.
A Convexity-dependent Two-Phase Training Algorithm for Deep Neural Networks
Machine Learning (CS)
Makes computer learning faster and more accurate.