An arXiv preprint reports a result on alternating regret in the expert problem: its worst-case rate is logarithmic in the number of experts and independent of the number of rounds. The conclusion follows from lower and upper bounds that match in order, with constant factors suppressed. Regret is the gap between a learner's result and the fixed benchmark it is trying to match; minimax asks what guarantee remains under the hardest permitted loss sequence.
The paper asks the minimax question in two settings: the expert problem and general online convex optimization. In the second, decisions lie in a d-dimensional compact convex set, and the loss functions are convex and bounded from -1 to 1. In everyday terms, the analysis compares a learner with a fixed expert or comparator while asking how much regret must be allowed for the hardest permitted sequence.
The expert rate
To establish the lower bound for experts, the paper uses an oblivious halving construction. The sequence is fixed rather than adjusted to the learner, and each active round reveals another bit about the final comparator. Under the theorem's stated horizon and dimension conditions, every possibly randomized expert algorithm faces an expected lower bound equal to the floor of the base-two logarithm of d, where d is the number of experts.
That lower bound is matched in order by an upper-bound algorithm based on exponential weights. The method adds carefully designed linear and quadratic corrections to the distribution it plays. For every adaptive expert loss sequence, setting eta to 1/10 guarantees alternating regret of at most 10 log d. Together, the two bounds give the expert minimax rate as logarithmic in d and independent of the horizon, up to constant factors.
A continuous extension
For the broader online convex setting, the lower-bound construction starts with a two-point instance and repeats it across geometrically decreasing spatial scales. For each stated dimension and horizon, the theorem supplies a compact convex domain such that every possibly randomized learner on it can be paired with an oblivious sequence of continuous convex losses producing an expected lower bound of the paper's dimension-horizon logarithmic order. Because the domain is supplied as part of the construction, the theorem does not say that every fixed compact convex domain reaches that lower-bound order.
On the upper-bound side, the continuous algorithm uses a corrected density, a probability distribution spread across the decision space. It can either play the density's mean, or average decision, as a deterministic strategy, or sample from the density instead. Across every compact convex domain and every adaptive sequence of bounded convex losses, the method gives a dimension-horizon logarithmic upper bound. The mean-action option is interpreted deterministically; the sampling option is interpreted in expectation.
The result's boundary
Taken together, the continuous lower and upper results characterize worst-case minimax alternating regret up to universal constants. The paper also derives improved convergence guarantees for alternating learning in the stated convex-game settings, including deterministic convergence for the mean-action option.
The general lower bound is existential in the domain: it identifies a compact convex set on which the hard rate occurs, but it does not show that every fixed compact convex domain reaches that order. The continuous method also leaves open whether a fully efficient implementation can rely on approximate sampling and integration, and whether similarly sharp guarantees hold under partial-information feedback.
The document is an arXiv version-one preprint dated 25 August 2026. Its acknowledgments disclose GPT-5.6 assistance with writing and proof-strategy exploration, while stating that the author checked the arguments and accepts responsibility.
Paper data and sources
Original title: Minimax Alternating Regret for the Experts Problem and Online Convex Optimization
Authors: Mengxiao Zhang
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text