LAD_example.py

"""
This script compare our Algorithm 2 with PDHG and SPDHG algorithms in the following Non-strongly convex example:

    l_1-regularized least absolute deviation problem (LAD)
    min_{x, x0} sum_{j=1,...,m} f[j]( A[j,:] * x ) + g(x),
    where f[j](r) = |r - b_j|, g(x) = beta/2 sum_{i=1,...,d} |x_i|.

with synthetic data generated by:

    A: a sparse m * d matrix whose non-zeros elements are i.i.d. N(0,1)
    b: A * zeros(m,1) + 0.1 * C. The elements of C are i.i.d. L(0,1),
    where L stands for laplace noise.

If you want to quickly take a look at the performance of the algorithms:

    run the last part of this script: "Plot the result".
"""

from __future__ import division, print_function

import numpy as np
from argParse import argParser_block
from scipy.sparse import random
from scipy.stats import norm
from scipy.sparse import linalg
import math
import sys

from solver_block.original_alg2 import original_alg2
from solver_block.spdc import spdc
from solver_block.spdhg import spdhg
from solver_block.pdhg import pdhg

# Read Parameters
num_blk, data_name, num_epoch = argParser_block()

num_blk = int(num_blk)
num_epoch = int(num_epoch)
# fix a seed
np.random.seed(0)

# Generate Data
# b, A, beta
# exp_m = 3
# exp_d = 3
# density = 0.5
# exp_m = 3
# exp_d = 4
# density = 0.1
exp_m = 4
exp_d = 4
density = 0.01
# exp_m = 4
# exp_d = 5
# density = 0.001
m = 10 ** exp_m
d = 10 ** exp_d
A = random(m, d, density, data_rvs=norm().rvs, format='csr')
normA = linalg.norm(A)
At = A.transpose()
x = np.zeros(d)
Ax = A.dot(x)
noise = np.random.laplace(0, 1, m)
b = Ax + 0.1 * noise
beta = 1 / m

# fix the initial point and iterations
x0 = np.zeros(d)
niter = num_blk*num_epoch


# Define objective functions
def primal_obj_func(x):
    return np.linalg.norm(A.dot(x) - b, 1) + beta * np.linalg.norm(x, 1)


def dual_obj_func(y):
    z = -At.dot(y)
    if (y >= -1).all() and (y <= 1).all() and (z >= -beta).all() and (z <= beta).all():
        return -b.dot(y)
    else:
        return - math.inf


# partition into blk_x blocks
blk_x = num_blk
bat_size_x = d // blk_x + 1
Ablk_x = []
index_x = []
for k in range(blk_x):
    mask = range((k % blk_x) * bat_size_x, min((k % blk_x + 1) * bat_size_x, d))
    index_x.append(mask)
    Ablk_x.append(A[:, mask])
Atblk_x = [Ablk_x[i].transpose() for i in range(blk_x)]

# partition into blk_x blocks
blk_r = num_blk
bat_size_r = m // blk_r + 1
Ablk_r = []
index_r = []
for k in range(blk_r):
    mask = range((k % blk_r) * bat_size_r, min((k % blk_r + 1) * bat_size_r, m))
    index_r.append(mask)
    Ablk_r.append(A[mask, :])
Atblk_r = [Ablk_r[i].transpose() for i in range(blk_r)]

# decide to run which algorithms
alg_list = dict(original_alg2=1, spdhg=1, pdhg=1)

# Define the solution set
Sol = dict()


# Define proximal operators
def proximal_x(x, sigma):
    return np.minimum(np.maximum(x - beta * sigma, 0), x + beta * sigma)


def proximal_r(r, sigma):
    return np.minimum(np.maximum(r - sigma, b), r + sigma)


"""
Run our Algorithm 2
"""
if alg_list["original_alg2"]:
    def proximal_r_star(r, sigma):
        return np.minimum(np.maximum(r - sigma * b, -1), 1)


    if_average = 1
    tau0 = 1 / blk_x  # 1/(blk_x*blk_r)
    rho0 = 0.5 / normA / density  # penalty parameter for r , 8 for w8a
    sigma = 1 / normA / density  # penalty parameter for x, 8 for w8a
    if exp_m == 3 and exp_d == 3:
        rho0 = 10 / normA / density  # penalty parameter for r , 8 for w8a
        sigma = 10 / normA / density  # penalty parameter for x, 8 for w8a
    if exp_m == 4 and exp_d == 5:
        rho0 = 0.1 / normA / density  # penalty parameter for r , 8 for w8a
        sigma = 0.1 / normA / density  # penalty parameter for x, 8 for w8a
    c_eta = 1  # 1 for w8a
    c_tau = 1 / tau0  # 2 for w8a

    Sol["original_alg2"] = original_alg2(x0, proximal_x, proximal_r_star, A, Ablk_x, Atblk_x, index_x, if_average,
                                         niter,
                                         primal_obj_func=primal_obj_func, dual_obj_func=dual_obj_func,
                                         rho0=rho0, tau0=tau0, sigma=sigma, c_tau=c_tau, c_eta=c_eta, verbose=1,
                                         print_dist=int(max(niter/20, 1)))
"""
Run PDHG algorithm
"""
if alg_list["pdhg"]:
    def proximal_r_star(r, sigma):
        return np.minimum(np.maximum(r - sigma * b, -1), 1)


    gamma = 1
    tau = gamma / normA
    if exp_m == 3 and exp_d == 3:
        tau = 0.0014
        sigma = 0.2
    if exp_m == 3 and exp_d == 4:
        tau = 0.001
        sigma = 0.01
    if exp_m == 4 and exp_d == 4:
        tau = 0.0011
        sigma = 0.1
    if exp_m == 4 and exp_d == 5:
        tau = 0.001
        sigma = 0.5
    if_average = 1
    Sol["pdhg"] = pdhg(x0, proximal_x, proximal_r_star, A, tau, sigma, if_average, niter,
                       primal_obj_func=primal_obj_func, dual_obj_func=dual_obj_func,
                       verbose=1, print_dist=int(max(niter / 20, 1)))
"""
Run SPDHG algorithm
"""
if alg_list["spdhg"]:
    def proximal_r_star(mask, r, sigma):
        return np.minimum(np.maximum(r - sigma * b[mask], -1), 1)


    theta = 1
    if_average = 1
    if exp_m == 3 and exp_d == 3:
        tau = 0.005
        sigma = 0.01
        theta = 10
    if exp_m == 3 and exp_d == 4:
        tau = 0.005
        sigma = 0.01
    if exp_m == 4 and exp_d == 4:
        tau = 0.03
        sigma = 0.01
    if exp_m == 4 and exp_d == 5:
        tau = 0.01
        sigma = 0.05
        theta = 3
        if_average = 0
    Sol["spdhg"] = spdhg(x0, proximal_x, proximal_r_star, A, Ablk_r, Atblk_r, index_r, tau, sigma, if_average, niter,
                         primal_obj_func=primal_obj_func, dual_obj_func=dual_obj_func, theta=theta, verbose=1,
                         print_dist=int(max(niter/20, 1)))

"""
save data
"""
import pickle

data = dict(dim_dual=m, dim_primal=d, blk_x=blk_x, blk_r=blk_r, density=density)
pickle.dump(data, open("result/lad/lad_" + str(exp_m) + "_" + str(exp_d) + "_base", "wb"))

# calculate the initial primal value
x0 = np.zeros(d)
y0 = np.zeros(m)
primal_obj_x0 = primal_obj_func(x0)


if alg_list["spdhg"]:
    Sol["spdhg"]["primal_obj_val"] = [primal_obj_x0] + Sol["spdhg"]["primal_obj_val"]
    pickle.dump(Sol["spdhg"], open("result/lad/lad_" + str(exp_m) + "_" + str(exp_d) + "_spdhg", "wb"))

if alg_list["pdhg"]:
    Sol["pdhg"]["primal_obj_val"] = [primal_obj_x0] + Sol["pdhg"]["primal_obj_val"]
    pickle.dump(Sol["pdhg"], open("result/lad/lad_" + str(exp_m) + "_" + str(exp_d) + "_pdhg", "wb"))

if alg_list["original_alg2"]:
    Sol["original_alg2"]["primal_obj_val"] = [primal_obj_x0] + Sol["original_alg2"]["primal_obj_val"]
    pickle.dump(Sol["original_alg2"], open("result/lad/lad_" + str(exp_m) + "_" + str(exp_d) + "_original_alg2", "wb"))

"""
Plot the result
"""

import pickle
import matplotlib
import matplotlib.pyplot as plt
import numpy as np
from matplotlib import rc

matplotlib.use('TkAgg')
rc('text', usetex=True)

# set the figure
markersize = 8
mark_num = 10

# load the data
if ('exp_m' not in locals()) or ('exp_d' not in locals()):
    exp_m = 4
    exp_d = 4
data = pickle.load(open("result/lad/lad_" + str(exp_m) + "_" + str(exp_d) + "_base", "rb"))
m = data["dim_dual"]
d = data["dim_primal"]
blk_x = data["blk_x"]
blk_r = data["blk_r"]
sol_original_alg2 = pickle.load(open("result/lad/lad_" + str(exp_m) + "_" + str(exp_d) + "_original_alg2", "rb"))
sol_pdhg = pickle.load(open("result/lad/lad_" + str(exp_m) + "_" + str(exp_d) + "_pdhg", "rb"))
sol_spdhg = pickle.load(open("result/lad/lad_" + str(exp_m) + "_" + str(exp_d) + "_spdhg", "rb"))
Fmin = sol_pdhg["primal_obj_val"][-1]
total_iter = len(sol_original_alg2["primal_obj_val"])
iters = np.array(range(0, total_iter))
num_epoch = int(total_iter / blk_r)

obj_val = np.array(sol_original_alg2["primal_obj_val"]) - Fmin
plt.semilogy(iters / blk_x, obj_val, 'C1-', marker='o', markevery=int(total_iter / mark_num),
             markersize=markersize, label=r'Original Algorithm 2')

obj_val = np.array(sol_spdhg["primal_obj_val"]) - Fmin
plt.semilogy(iters / blk_x, obj_val, 'C2-', marker='s', markevery=int(total_iter / mark_num),
             markersize=markersize, label=r'SPDHG')

obj_val = np.array(sol_pdhg["primal_obj_val"]) - Fmin
mask = np.array(range(num_epoch))
plt.semilogy(mask, obj_val[mask], 'C4-', marker='*', markevery=int(num_epoch / mark_num),
             markersize=markersize, label=r'PDHG')

plt.title("LAD" + ": m = " + str(m) + ", n = " + str(d))
# plt.xlim(1, num_epoch + 1)
plt.xlabel("Epochs")
plt.ylabel("Primal Objective Value")
# plt.ylim(1e-3, 5)
# plt.legend(loc='lower left')
plt.legend()
plt.show()