Julien Grand-Clément, Joon Kwon, Francesco Orabona
A central topic in online and stochastic optimization is to design algorithms that do not require tuning of hyperparameters. Successful strategies in online learning include AdaGrad-style learning rates, Conic Blackwell algorithms, and parameter-free algorithms. However, these classes require different, often difficult, analyses. We develop a unifying family of Online Convex Optimization (OCO) algorithms that require no user-tuned learning rate on convex domains that may be unbounded. The construction lifts the domain to a cone by adding one scalar coordinate, an idea going back to Blackwell (1954). The lifted subgradients are orthogonal to the corresponding lifted decisions, leaving the comparator scale free to optimize in the regret analysis. Applying Follow-the-Regularized-Leader (FTRL) and Online Mirror Descent (OMD) on the cone recovers Conic Blackwell Algorithm (CBA) and Conic Blackwell Algorithm Plus (CBA$^+$) on bounded domains in Hilbert spaces and extends them to finite-dimensional normed spaces with a strongly convex squared norm. For arbitrary nonempty closed convex domains in these spaces, a known gradient bound yields parameter-free regret guarantees. Surprisingly, on an unconstrained Hilbert space, the construction recovers the Krichevsky--Trofimov (KT) coin-betting algorithm exactly. We also give a parameter-free algorithm for unconstrained domains that requires no gradient bound.
Testing by betting is a powerful framework that recasts hypothesis testing as a betting game. A popular approach spreads the initial wealth over fixed bets according to a prior distribution, using a universal portfolio algorithm. For suitable priors, this approach achieves the optimal expected rejection time as the error probability goes to zero at a fixed alternative. Yet, priors with this guarantee can behave quite differently near the null. This motivates the question: Which prior should we use in testing-by-betting algorithms? We study bounded scalar payoffs and, under technical conditions, prove a sharp formula for expected rejection time, uniform over all bounded alternatives as the error probability tends to zero. The formula shows how the prior's mass around the zero bet determines the cost of adapting to an unknown alternative. We characterize the priors that attain the best possible leading constant when the error probability and alternative vary together. We also show that no valid test can uniformly improve on this cost across ranges of alternatives near the null. In particular, the uniform prior can require arbitrarily more observations than suitable priors that concentrate around the zero bet. A general inversion argument converts our results into sharp expected times to reach a prescribed confidence-sequence width. We also give a concrete prior choice and an FFT-based algorithm with almost linear computational complexity.