Elastic Net Regularizer using Forward Backward Splitting (FOBOS) implemented in Python

fobos_enr.py

#!/usr/bin/env python3

# Efficient online and batch learning using forward backward splitting
# John Duchi and Yoram Singer
# Journal of Machine Learning Research 10 (2009) 2899-2934
# http://www.jmlr.org/papers/volume10/duchi09a/duchi09a.pdf

# Efficient Elastic Net Regularization for Sparse Linear Models
# Zachary C. Lipton and Charles Elkan (2015)
# https://arxiv.org/pdf/1505.06449.pdf

import math


class ElasticNetRegularizer(object):

    def __init__(self, l1_factor, l2_factor):
        self.l1_factor = l1_factor
        self.l2_factor = l2_factor
        self.alpha = [0.0]
        self.beta = [0.0]

    def regularize(self, w, prev, current):
        if w > 0:
            return max(0, (w + self.beta[prev]) * math.exp(self.alpha[current] - self.alpha[prev]) - self.beta[current])
        else:
            return min(0, (w - self.beta[prev]) * math.exp(self.alpha[current] - self.alpha[prev]) + self.beta[current])

    def increment(self, eta):
        self.alpha.append(math.log(1.0 - eta * self.l2_factor) + self.alpha[-1])
        self.beta.append(eta * self.l1_factor + self.beta[-1] * (1.0 - eta * self.l2_factor))


def main():
    # testcase
    l1 = 0.1
    l2 = 0.2
    regularizer = ElasticNetRegularizer(l1, l2)
    phis = [1, 0, 0, 1, -1, 0, 0, 0, 1, 0]
    etas = [0.5, 0.3, 0.2, 0.15, 0.12, 0.09, 0.07, 0.06, 0.05, 0.04]

    # Normal Regularization Example
    w = 0
    cnt = 0
    for phi, eta in zip(phis, etas):
        w += phi * eta
        if w > 0:
            w = max(w - l1 * eta - l2 * eta * w, 0)
        else:
            w = min(w + l1 * eta - l2 * eta * w, 0)
        cnt += 1
    print("Normal regularization:", w)

    # FOBOS Regularization Example
    w = 0
    prev = 0
    cnt = 0
    for phi, eta in zip(phis, etas):
        regularizer.increment(eta)
        if not phi:
            cnt += 1
            continue
        w = regularizer.regularize(w, prev, cnt)
        prev = cnt
        w += phi * eta
        cnt += 1
    w = regularizer.regularize(w, prev, cnt)
    print("FOBOS regularization: ", w)


if __name__ == "__main__":
    main()