JMLR: Workshop and Conference Proceedings 1:1–7, 2016

ICML 2016 AutoML Workshop

Parameter-Free Convex Learning through Coin Betting
Francesco Orabona

FRANCESCO @ ORABONA . COM

Dávid Pál

DPAL @ YAHOO - INC . COM

Yahoo Research, New York

Abstract
We present a new parameter-free algorithm for online linear optimization over any Hilbert space. It
is theoretically optimal, with regret guarantees as good as with the best possible learning rate. The
algorithm is simple and easy to implement. The analysis is given via the adversarial coin-betting
game, Kelly betting and the Krichevsky-Trofimov estimator. Applications to obtain parameter-freeconvex optimization and machine learning algorithms are shown.

1. Introduction
We consider the Online Linear Optimization (OLO) (Cesa-Bianchi and Lugosi, 2006; Shalev-Shwartz,2011) over a Hilbert space H. In each round t, an algorithm chooses a point wt ∈ H and then receives a loss vector `t ∈ H. The algorithm’s goal is to keep its regret small, defined as the difference
between its cumulative reward and the cumulative reward of a fixed strategy u ∈ H, that is
RegretT (u) =

T
X
t=1

h`t , wt i −TXh`t , ui .

t=1

where h·, ·i is the inner product in H.
OLO is a basic building block of many machine learning problems. For example, Online Convex
Optimization (OCO) is a problem analogous to OLO where the linear function u 7→ h`t , ui is generalized to an arbitrary convex function ft (u). OCO is solved through a reduction to OLO by feeding
the algorithm `t = ∇ft (wt ) (Shalev-Shwartz, 2011). Batch and stochastic convex optimization
can also be solved through a reduction to OLO by taking the average of w1 , w2 , . . . , wT (ShalevShwartz, 2011).
To achieve optimal regret, most of the existing online algorithms (e.g. Online Gradient Descent, Hedge) require the user to set the learning rate to an unknown/oracle value. Recently, newparameter-free algorithms have been proposed for OLO/OCO (Chaudhuri et al., 2009; Chernov andVovk, 2010; Streeter and McMahan, 2012; Orabona, 2013; McMahan and Abernethy, 2013; McMahan and Orabona, 2014; Luo and Schapire, 2014; Orabona, 2014; Luo and Schapire, 2015; Koolen
and van Erven, 2015). These algorithms adapt to the characteristics of the optimal predictor, without
the need to tune parameters. However, their design and underlying intuition is still a challenge.
Our contributions are as follows. We connect algorithms for OLO with coin betting. Namely,
we show that an algorithm for OLO can be viewed as an algorithm for betting on outcomes ofadversarial coin flips. The wealth the algorithm can generate for the betting problem is connectedto the regret in OLO setting. This insight allows us to design novel parameter-free algorithms,

c 2016 F. Orabona & D. Pál.

O RABONA P ÁL

which are extremely simple and natural. We also show some applications of our results to convex
optimization and machine learning, as well as some empirical results.

2. How to Tune the Learning Rates?
p
Denote by k·k = h·, ·i the induced norm in H and assume that k`t k ≤ 1. Consider OLO over a
Hilbert Space H. Online Gradient Descent (OGD) with learning rate η satisfies (Shalev-Shwartz,
2011)
2
ηT
∀u ∈ H
RegretT (u) ≤ kuk(1)
2η + 2 .
It is obvious that the optimal tuningof the learning rate depends on the unknown norm of u.
√
The simple choice η = 1/ T leads to an algorithm that satisfies√T .
∀u ∈ H
RegretT (u) ≤ 12 1 + kuk2

(2)

However, in this bound the dependency on kuk is suboptimal: The quadratic dependency can be
replacedby an (almost) linear dependency. Starting from (1), if we choose the learning rate η =√D/ T , we get a family of algorithms parameterized by D ∈ [0, ∞) that satisfy√∀u ∈ H : kuk ≤ D =⇒ RegretT (u) ≤ D T .
(3)
Instead of a family of algorithms parameterized by D ∈ [0, ∞) satisfying the bound (3), one would
like to have a single algorithm (without any tuning parameters) satisfying√∀u ∈ H
RegretT (u) ≤ kuk T .
(4)
Notice that (4) is stronger than (3) in the following sense: A single algorithm satisfying (4) implies(3) for all values of D ∈ [0, ∞). However, a family of algorithms {AD : D ∈ [0, ∞)} parameterized by D where AD satisfies (3), does not yield a single algorithm that satisfies (4). Finally, notethat (4) has better dependency on kuk than (2).
Better guarantees are indeed possible. In fact, there have been a lot of work on algorithms(Streeter and McMahan, 2012; Orabona, 2013; McMahan and Abernethy, 2013; McMahan andOrabona, 2014; Orabona, 2014) that satisfy a slightly weaker version of (4). Namely, their regret
satisfies√∀u ∈ H
RegretT (u) ≤ O(1) + polylog(1 + kuk) kuk T .
(5)
It can be shown that for OLO over Hilbert space the extra poly-logarithmic factor is necessary (McMahan and Abernethy, 2013; Orabona, 2013). Algorithms satisfying (5) are called parameter-free,since they do not need to know D, yet they have an optimal dependency on kuk.

3. Parameter-Free Algorithm From Coin Betting
Here, we present our new parameter-free algorithm for OLO over a Hilbert space H, stated as
Algorithm 1. We would like to stress the extreme simplicity of the algorithm. The theorem below
upper bounds its regret in the form of (5), the proof can be found in Orabona and Pál (2016).

2

PARAMETER -F REE C ONVEX L EARNING THROUGH C OIN B ETTING

Algorithm 1 Algorithm for OLO over Hilbert space H based on Krichevsky-Trofimov estimator
1: for t = 1, 2, . . . do

P
P
t−1
2:
Predict with wt ← − 1t 1 − t−1
h`
,
w
i
i
i=1 i
i=1 `i
3:
Receive loss vector `t ∈ H such that k`t k ≤ 1
4: end for
Theorem 1 (Regret Bound for Algorithm 1) Let {`t }∞t=1 be any sequence of loss vectors in a
Hilbert space H such that k`t k ≤ 1. Algorithm 1 satisfiesr∀ T ≥ 0 ∀u ∈ H

RegretT (u) ≤ kuk

T ln 1 + 4T 2 kuk2 + 1 .

We now explain how Algorithm 1 is derived from the Krichevsky-Trofimov solution to theadversarial coin-betting problem.
Adversarial Coin Betting. Consider a gambler making repeated bets on the outcomes of adversarial coin flips. The gambler starts with an initial endowment of 1 dollar. In each round t, hebets on the outcome of a coin flip ct ∈ {−1, 1}, where +1 denotes heads and −1 denotes tails. The
outcome ct is chosen by an adversary. The gambler can bet any amount on either heads or tails.
However, he cannot borrow any additional money. If he loses, he loses the betted amount; if hewins, he gets the betted amount back and, in addition to that, he gets the same amount as a reward.
We encode the gambler’s bet in round t by a single number βt ∈ [−1, 1]. The sign of βt encodes
whether he is betting on heads or tails. The absolute value encodes the betted amount as the fractionof his current wealth. Let Wealtht be gambler’s wealth at the end of round t. It satisfies
Wealth0 = 1

Wealtht = (1 + ct βt ) Wealtht−1

andfor t ≥ 1 .

(6)

Note that since βt ∈ [−1, 1], gambler’s wealth stays always non-negative.
Kelly Betting and Krichevsky-Trofimov Estimator. For sequential betting on i.i.d. coin flips,
the optimal strategy has been proposed by Kelly (1956). The strategy assumes that the coin flips{ct }∞
t=1 , ct ∈ {+1, −1}, are generated i.i.d. with known probability of heads. If p ∈ [0, 1] is theprobability of heads, the Kelly bet is βt = 2p − 1. He showed that, in the long run, this strategy will
provide more wealth than betting any other fixed fraction (Kelly, 1956).
For adversarial coins, Kelly betting does not make sense. Krichevsky and Trofimov (1981)
proposed to replacePp with an estimate: After seeing coin flips c1 , c2 , . . . , ct−1 , use the empiricalestimate kt =

1/2+

t−1
i=1 1[ci =+1]

t

. Their estimate is commonly called KT estimator1 and it results in
Pt−1

c

i
the betting strategy βt = 2kt − 1 = i=1. Krichevsky and Trofimov showed that this strategytguarantees almost the same wealth that one would obtain knowing in advance the fraction of heads.
Namely, if we denote by Wealtht (β) the wealth of the strategy that bets the fraction β in every
round, then the wealth of the Krichevsky-Trofimov betting strategy satisfies∀β ∈ [−1, 1]

Wealtht ≥Wealtht (β)
√
.
2 t

(7)

Moreover, this guarantee is optimal up to constant multiplicative factors (Cesa-Bianchi and Lugosi,2006).
Pt−1

1. Compared to the standard maximum likelihood estimate

3

i=1 1[ci =+1]

t−1

, KT estimator “shrinks” slightly towards 12 .

O RABONA P ÁL

Algorithm 2 SGD algorithm based on KT estimator
Require: Convex functions f1 , f2 , . . . , fN and desired number of iterations T
1: Initialize Wealth0 ← 1 and θ0 ← 0
2: for t = 1, 2, . . . , T do
3:
Set wt ← Wealtht−1 θt−1
t4:
Select an index j at random from {1, 2, . . . , N } and compute `t = ∇fj (wt−1 )5:Update θt ← θt−1 − `t and Wealtht ← Wealtht−1 −h`t , wt i
6: end forPT
7: Output w T = T1
t=1 wtFrom betting to OLO. In AlgorithmP
1, the “coin outcome”
P is the vector ct ∈ H where ct = −`tand algorithm’s wealth is Wealtht = 1+ ti=1 hci , wi i = 1− ti=1 h`i , wi i. The algorithm explicitly
Pt−1

c

Pt−1

`

i
i
keeps track of its wealth and it bets “vectorial fraction” βt = i=1= − i=1
of its currenttt
wealth. The regret bound (Theorem 1) is a consequence of Krichevsky-Trofimov lower bound (7)on the wealth and the duality between regret and wealth. For more details, see Orabona and Pál(2016).

4. From Online Learning to Convex Optimization and Machine Learning
The result in Section 3 immediately implies new algorithms and results in convex optimization andmachine learning. We will state some of them here, see Orabona (2014) for more results.
Convex Optimization. Consider an empirical risk minimization problem of the formNF (w) =1 X
fi (w),
N

(8)

i=1

where fi : Rd → R is convex.2 It is immediate to transform Algorithm 1 into a Stochastic Gradient
Descent (SGD) algorithm for this problem, obtaining Algorithm 2. In Algorithm 2, ∇fj (w) denotes
a subgradient of fj at a point w. We assume that the norm of the subgradient of fj is bounded by 1.
Beside the simplicity of the Algorithm 2, it has the important property is that it does not havea learning rate to be tuned, yet it achieves the optimal convergence rate. In fact, denoting by wb=
arg minw F (w) the optimal solution of (8), the following theorem states the rate of convergence of
Algorithm 2.
Theorem 2 The average wT produced by Algorithm 2 is an approximate minimizer of the objectivefunction (8):qbb ≤ k√wk
E [F (wT )] − F (w)T

log(1 + 4T 2 kwk
b 2 ) + T1 .

Note that in the above theorem, T can be larger (multiple epochs) or smaller than N .
Machine Learning. In machine learning, the minimization of a function (8) is just a proxy
to minimize the true risk over an unknown distribution. For example, fi (w) can be of the formfi (w) = f (w, Xi , Yi ) where {(Xi , Yi )}N
i=1 is a sequences of labeled sampled generated i.i.d. fromsome unknown distribution and f (w, Xi , Yi ) is the logistic loss of a weight vector w on a sample
2. The algorithm can also be implemented and analyzed with kernels (Orabona, 2014).

4

PARAMETER -F REE C ONVEX L EARNING THROUGH C OIN B ETTING

Algorithm 3 Averaging algorithm based on KT estimator
Require: Sample (X1 , Y1 ), (X2 , Y2 ), . . . , (XN , YN )1: Initialize Wealth0 ← 1 and θ0 ← 0
2: for i = 1, 2, . . . , N do
3:
Set wi ← Wealthi−1 θi−1
i
i ,Yi )
4:
Compute `i = ∂f (w,X
|w=wi
∂w
5:
Update θi ← θi−1 − `i and Wealthi ← Wealthi−1 −h`i , wi i
6: end for
1 PN
7: Output w N = N
i=1 wi(Xi , Yi ). A common approach to have a small risk on the test set is to minimize a regularized
objective function over the training set:
1Reg
Fλ (w) = λ kwk2 +NNX

f (w, Xi , Yi ) .

(9)

i=1

This problem is strongly convex, so there are very efficient methods to minimize it, hence we canRegassume to be able to get the minimizer of Fλ with arbitrary high precision and algorithms that
do not require to tune learning rates. Yet, this is not enough. In fact, we are rarely interested inReg
the value of the objective function Fλ or its minimizer, rather we are interested in the true risk ofa solution w, that is E[f (w, X, Y )], where (X, Y ) is an independent “test” sample from the same
distribution from which the training set {(Xi , Yi )}N
i=1 came from. Hence, in order to get a good
performance we have to select a good regularization parameter. In particular, from Sridharan et al.
(2009) we get
1
E[f (wbλ , X, Y )] − E[f (w∗ , X, Y )] ≤ O(λ kw∗ k2 + λN),Reg

bλ = arg minw Fλ (w). From the above bound, it
where w∗ = arg minw E[f (w, X, Y )] and w
is clear that the optimal value of λ depends on the kw∗ k that is unknown. Yet another possibility
is to select the optimal learning rate and/or the number of epochs of SGD to directly minimize
E[f (w∗ , X, Y )]. However, all these methods are equivalent (J. Lin, 2016) and they still require totune at least one parameter. We would like to stress that this is not just a theoretical problem: Anypractitioner knows how painful it is to find the right regularization for√ the problem at hand.
Assuming we would know kw∗ k, we could set λ = O(1/(kw∗ k N )) to achieve the worst-case
optimal bound
 ∗ 
k
√
E[f (wbλ , X, Y )] − E[f (w∗ , X, Y )] ≤ O kw.
(10)
N
However, we can get the same guarantee without knowing kw∗ k or the optimal λ, by doing a single
pass over the data set. More precisely, we derive Algorithm 3 from Algorithm 1 by applying thestandard online-to-batch reduction (Shalev-Shwartz, 2011). The algorithm makes only a single passover the dataset and it does not have any tuning parameters. Yet, it has almost the same guarantee(10) without knowing kw∗ k or the optimal regularization parameter λ or the learning rate, or any
other tuning parameter.

5

O RABONA P ÁL

cpusmall dataset, absolute loss

yearPredictionMSD dataset, absolute loss

1.2

SGD
0.69

14

cadata dataset, absolute loss

5

16

0.7

x 10

1.15

KT-based

1.1

0.68

12
SGD

0.67

0.66

Test loss

Test loss

Test loss

1.05

10

0.95

8
0.65

0.64

KT-based
1

0.9

6
SGD

0.85

KT-based
0.63

−1

10

0

10
Learning rate SGD

1

10

(a)

4

−1

10

0

10

1

10
Learning rate SGD

(b)

2

10

3

10

0.8

2

10

4

10
Learning rate SGD

6

10

(c)

Figure 1: Test loss versus learning rate parameter of SGD (in log scale), compared with the parameter-free Algorithm 3.

Theorem 3 Assume that (X, Y ), (X1 , Y1 ), (X2 , Y2 ), . . . , (XN , YN ) are i.i.d. The output wN of
Algorithm 3 satisfiesqkw∗ k
E[f (wN , X, Y )] − E[f (w∗ , X, Y )] ≤ √log(1 + 4N 2 kw∗ k2 ) + N1 .
N
Comparing this guarantee to the one in (10), we see that, just paying a sub-logarithmic price, we
obtain the optimal convergence rate and we remove all the parameters.

5. Empirical Evaluation
We have also run a small empirical evaluation to show that the theoretical difference between classic
learning algorithms and parameter-free ones is real and not just theoretical. In Figure 1, we haveused three regression datasets,3 and solved the OCO problem through OLO. In all the three cases,
we have used the absolute loss and normalized the input vectors to have L2 norm equal to 1.
The dataset were split in two parts: 75% training set and the remaining as test set. The training
is done through one pass over the training set and the final classifier is evaluated on the test set. We
used 5 different splits of training/test and we report average and standard deviations.
We have run SGD with different learning rates and shown the performance of its last solution
on the test set. For Algorithm 3, we do not have any parameter to tune so we just plot its test set
performance as a line.
From the empirical results, it is clear that the optimal learning rate is completely data-dependent.
It is also interesting to note how the performance of SGD becomes very unstable with large learning
rates. Yet our parameter-free algorithm has a performance very close to the unknown optimal
tuning of the learning rate of SGD.

Acknowledgments
The authors thank Jacob Abernethy, Nicolò Cesa-Bianchi, Satyen Kale, Chansoo Lee, and Giuseppe
Molteni for useful discussions on this work.
3. Datasets available at https://www.csie.ntu.edu.tw/˜cjlin/libsvmtools/datasets/.

6

PARAMETER -F REE C ONVEX L EARNING THROUGH C OIN B ETTING

References
N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
K. Chaudhuri, Y. Freund, and D. Hsu. A parameter-free hedging algorithm. In Y. Bengio, D. Schuurmans,
J. D. Lafferty, C. K. I. Williams, and A. Culotta, editors, Advances in Neural Information Processing
Systems 22 (NIPS 2009), December 7-12, Vancouver, BC, Canada, pages 297–305, 2009.
A. Chernov and V. Vovk. Prediction with advice of unknown number of experts. In Peter Grünwald and Peter
Spirtes, editors, Proc. of the 26th Conf. on Uncertainty in Artificial Intelligence (UAI 2010), July 8-11,
Catalina Island, California, USA. AUAI Press, 2010.
L. Rosasco J. Lin, R. Camoriano. Generalization properties and implicit regularization for multiple passes
SGM. In Proc. of International Conference on Machine Learning (ICML), 2016.
J. L. Kelly. A new interpretation of information rate. Information Theory, IRE Transactions on, 2(3):185–189,
September 1956.
W. M. Koolen and T. van Erven. Second-order quantile methods for experts and combinatorial games. In
Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Proc. of the 28th Conf. on Learning Theory (COLT
2015), July 3-6, Paris, France, pages 1155–1175, 2015.
R. E. Krichevsky and V. K. Trofimov. The performance of universal encoding. IEEE Transactions on Information Theory, 27(2):199–206, 1981.
H. Luo and R. E. Schapire. A drifting-games analysis for online learning and applications to boosting. In
Z. Ghahramani, M. Welling, C. Cortes, N.D. Lawrence, and K.Q. Weinberger, editors, Advances in Neural
Information Processing Systems 27, pages 1368–1376. Curran Associates, Inc., 2014.
H. Luo and R. E. Schapire. Achieving all with no parameters: AdaNormalHedge. In Peter Grünwald, Elad
Hazan, and Satyen Kale, editors, Proc. of the 28th Conf. on Learning Theory (COLT 2015), July 3-6, Paris,
France, pages 1286–1304, 2015.
H. B. McMahan and J. Abernethy. Minimax optimal algorithms for unconstrained linear optimization. In
C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors, Advances in Neural
Information Processing Systems 26 (NIPS 2013), pages 2724–2732, 2013.
H. B. McMahan and F. Orabona. Unconstrained online linear learning in Hilbert spaces: Minimax algorithms
and normal approximations. In Vitaly Feldman, Csaba Szepesvri, and Maria Florina Balcan, editors, Proc.
of The 27th Conf. on Learning Theory (COLT 2014), June 13-15, Barcelona, Spain, pages 1020–1039,
2014.
F. Orabona. Dimension-free exponentiated gradient. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 26, pages 1806–
1814. Curran Associates, Inc., 2013.
F. Orabona. Simultaneous model selection and optimization through parameter-free stochastic learning. In
Advances in Neural Information Processing Systems 27, pages 1116–1124, 2014.
F. Orabona and D. Pál. From coin betting to parameter-free online learning, 2016. Available from: http://arxiv.org/pdf/1602.04128.pdf.
S. Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine
Learning, 4(2):107–194, 2011.
K. Sridharan, S. Shalev-Shwartz, and N. Srebro. Fast rates for regularized objectives. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems 21, pages
1545–1552. Curran Associates, Inc., 2009.
M. Streeter and B. McMahan. No-regret algorithms for unconstrained online convex optimization. In
F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information
Processing Systems 25 (NIPS 2012), Decmber 3-8, Lake Tahoe, Nevada, USA, pages 2402–2410, 2012.

7