Profile picture
Kishan Chakraborty
Research Scholar
Home
Blog
Back

Online Convex Optimization 2: Regularization

The goal of an OCO algorithm is to minimize the regret unlike traditional convex optimization problems. This motivates a family of algorithm called Regularized Follow the Leader. This is based on a simple idea of taking the optimal decision on the hindsight. Formally,

xt+1=arg min⁡x∈K∑τ=1tfτ(x) x_{t+1} = \argmin_{x\in \mathcal{K}} \sum_{\tau=1}^t f_{\tau}(x)xt+1​=x∈Kargmin​τ=1∑t​fτ​(x)

This is called Follow the Leader strategy in Machine Learning. This strategy fails miserably in worst case scenario. Consider the formulation K=[−1,1],Let,f1(x)=12x,f2(x)=−12x\mathcal{K} = [-1, 1], \text{Let}, f_1(x) = \frac{1}{2} x, f_2(x) = -\frac{1}{2} xK=[−1,1],Let,f1​(x)=21​x,f2​(x)=−21​x and Let fτf_{\tau}fτ​ for τ=2,⋯ ,T\tau=2, \cdots, Tτ=2,⋯,T alternate between −x-x−x and xxx. Thus,

∑τ=1tfτ(x)={12x,     t is odd−12x,  otherwise\sum_{\tau=1}^t f_{\tau}(x) = \begin{cases} \frac{1}{2}x, ~~~~~ t \text{ is odd} \\ -\frac{1}{2}x, ~~ \text{otherwise} \end{cases}τ=1∑t​fτ​(x)={21​x,     t is odd−21​x,  otherwise​

The FTL strategy keeps shifting between xt=1x_t=1xt​=1 and xt=−1x_t=-1xt​=−1, always making the wrong choice. The algorithm can be modified to make it more stable. Such means of stablization is called regularization.

1. Regularization Functions

Def 1: A function fff is called α\alphaα- strongly convex if

f(y)≥f(x)+∇f(x)T(y−x)+α2∣∣y−x∣∣2 f(y) \ge f(x) + \nabla f(x)^T(y-x) + \frac{\alpha}{2}||y-x||^2f(y)≥f(x)+∇f(x)T(y−x)+2α​∣∣y−x∣∣2

Def 2: A function fff is called β\betaβ- smooth if

f(y)≤f(x)+∇f(x)T(y−x)+β2∣∣y−x∣∣2 f(y) \le f(x) + \nabla f(x)^T(y-x) + \frac{\beta}{2}||y-x||^2f(y)≤f(x)+∇f(x)T(y−x)+2β​∣∣y−x∣∣2

Regularization functions R:K→R\mathcal{R}: \mathcal{K} \rightarrow \mathbb{R}R:K→R, are strongly convex and smooth.