Parameter-Free Convex Learning through Coin Betting
Francesco Orabona Dávid PálYahoo Research, New YorkARE YOU STILL TUNING HYPERPARAMETERS?

PARAMETER-FREE SGD BASED ON THE KT ESTIMATOR

Regularized empirical risk minimization:
λ2
arg min kwk +2w ∈RdNX

f (w, xi, yi )

(1)

i =1

where f is convex in w.
• How do you choose the regularizer weight λ?
Stochastic approximation:w t = w t −1 − η t ∇ f ( w t −1 , x t , y t )(2)where f is convex in w.
• How do you choose the learning rate ηt?
• Why is the algorithm not able to select λ and/or ηtautomatically?
FROM COIN-BETTING TO MACHINE LEARNING

Require: Function f (w, x, y) convex in w
Require: Training set { xi, yi }iN=1
Require: Desired number of iterations T
Initialize Wealth0 ← 1 and θ0 ← 0for t = 1, 2, . . . , T do
θ t −1
Set wt ← Wealtht−1 t
Select an index j at random from {1, 2, . . . , N }Update θt ← θt−1 − ∇ f (wt, x j, y j )Wealtht ← Wealtht−1 −h∇ f (wt, x j, y j ), wt iend for1 PT
Output w T = T t=1 wt

LEARNING RATES IN ONLINE LINEAR LEARNING• Define

RegretT (u) =• Coin flip outcome ct ∈ {+1, −1}.
i =1 ci fraction of your current
wealth on the most common outcome till time t.
• KT algorithm for coin betting gives rise to optimal
parameter-free algorithms for Online Learning, Convex
Optimization and Machine Learning!
• Key idea: Treat the gradient as the outcome of a coin flip.
• In other words: Learning rates are the results of suboptimalalgorithms, they must be removed, not tuned/learned/adapted!

Multiple epochs: T > N
The average w T is an approximate minimizer of the training setPNerror F (w) = i=1 f (w, xi, yi ):qbkwk√22b) ≤b k ) + T1 .
log(1 + 4T kw
E [ F (w T )] − F (w+22k`t k .

•kukqOptimal oracle choice: η = PT.
2k`kt =1 t

• Many algorithms adapt to the norms of the gradients (e.g.

AdaGrad) while neglecting dependency on kuk.
• Adapting to u is more difficult and more important.
• Better guarantees are indeed possible: Streeter&McMahan(2012), Orabona (2013), McMahan&Abernethy (2013),
McMahan&Orabona (2014), Orabona (2014)√∀u ∈ H
RegretT (u) ≤ O(1) + polylog(1 + kuk) kuk
T.
REGRET GUARANTEEDOES IT WORK FOR REAL?
• Split data into 75% training + 25% test
• Train with one pass over the training set and evaluate the finalclassifier on the test set.
• Use 5 different splits into training+test. Report average andstandard deviation.
• We have run SGD with different learning rates and shown theperformance of its last solution on the test set.
cpusmall dataset, absolute loss

yearPredictionMSD dataset, absolute loss

1.2

14

cadata dataset, absolute loss

5160.7• Streeter&McMahan (2012): regret in R that depends on

AutoML Workshop @ ICML 2016

TX
η

TSGD

self-tuning SVMs, and a data dependent bound.
• A parallel line of work on adaptive learning with expert advice:
Chaudhuri et al. (2009), Chernov&Vovk (2010), Luo&Schapire(2014, 2015), Koolen&van-Erven (2015), Foster et al. (2015).
• Orabona&Pál (2016): parameter-free algorithms for online
learning from coin-betting.

2t =1

One epoch: T ≤ N
The average w T is an approximate minimizer of the risk
E[ f (w, X, Y )]:qw∗ kk√2
∗12∗
E[ f (w T , X, Y )] − E[ f (w , X, Y )] ≤log(1 + 4T kw k ) + T .

0.69• Orabona (2013): generalization top
Hilbert space.
• McMahan&Orabona (2014): kuklog(kuk + 1) regret.
• Orabona (2014): link between new online algorithms andh`t, ui .

t =1kukRegretT (u) ≤ 2η∀u ∈ HTHEORETICAL GUARANTEES

7 YEARS OF PARAMETER-FREE ALGORITHMS

x 10

1.15

KT-based

1.1

0.68

12SGD

0.67

0.66

Test loss

Test loss

1.05
Test loss

2|u| log |u| instead of |u| + 1.

TX

• OGD with learning rate η satisfies

Pt −1
1

• Krichevsky-Trofimov: Bet t

h`t, wt i −t =1

Tis equivalent toTX

100.65−10.8510010
Learning rate SGD

1104−1

10010

110Learning rate SGD

2103RegretT (u) ≤ kuk

T ln

221 + 4T kuk

+1.

Proof Sketch.
• Duality between wealth and regret: Let F : H → R be convex.
For any w1, . . . , wT and g1, . . . , gT ,
TTTXXXh gt , u − w t i ≤ F ∗ ( u ) .
h gt , w t i ≥ F gt  ⇔ ∀ u ∈ H ,RewardT

6KT-based0.63∀ T ≥ 0, ∀u ∈ H|t=1 {z0.9SGD

r

10.95

80.64

KT-based∞Theorem. Let {`t }t=1 be any sequence of loss vectors in a Hilbert space
H such that k`t k ≤ 1. The KT-based online algorithm satisfies0.810210410Learning rate SGD

610• Clearly, the optimal learning rate of SGD is completely

data-dependent.
• Interestingly, the performance of SGD becomes very unstablewith large learning rates.
• Yet our parameter-free algorithm has a performance very close to theunknown optimal tuning of the learning rate of SGD.
June 24, 2016

t =1}

|t=1

{zRegretT (u)}• Consider the 1-dimensional case H = R1.
• Set wt = β t Wealtht−1 where β t is the KT estimator.
• If `t ∈ {+1, −1}, the results follows directly from the guaranteeon the KT estimator and duality above.
• Extend to `t ∈ [−1, 1] by convexity: worst `t is in {+1, −1}.
• Extend 1-d case to Hilbert space: Worst direction of `t is thePt −1same as the direction of s=1 `s.

New York, NY, USA