[SOLVED] COMP6211E Final Assignment

1.  Consider the following finite sum optimization problem

,

where x_i ∈ R^d and y_i ∈ {±1}.

• (1 points) Derive the dual formulation, as in the SDCA procedure.
• (1 point) Write down the formula for closed form solution for SDCA (Option I of Algorithm 11.1).
• (1 point) Write down the dual free SDCA update rule for ∆α_i in Algorithm 14.3.
• (1 point) Write down the SGD update rule.
• (2 points) Implement the three methods (SDCA, dual-free SDCA, SGD) in prob1() of progtemplate.py, and plot the convergence curves (wrt primal-suboptimality) until SDCA converges (error < 10⁻¹⁰).

2. (6 points) Consider the minimax problem:

.

• (2 points) Write down the optimal solution of x as a function of y. Write the optimization problem in terms of y by eliminating x. Explain the derivations.
• (1 points) Write down the GDA update rule for this problem with learning rate η.
• (3 points) Implement GDA, extra gradient, optimistic GDA in prob2() of prog-temp.py, and plot the convergence curves (wrt gradient norm of x and y; 2-norm of) for 100 iterations.

3. (6 points) Consider zero-th order optimization.
   • (2 points) In Theorem 18.6, if we further assume that f(x) is λ strongly convex, and take η_t = (λt)⁻¹. Derive the corresponding convergence result. (2 points) the optimization problem

minEx∼π(x|θ)f(x), θ

where x ∈ R^d. Assume we want to solve this problem using policy gradient, with θ = (µ,ρ), where µ is d-dimensional vector, and ρ ∈ R. Both are part of model parameters. Consider distribution π(x|θ) = N(µ,e^−ρI). Derive the policy gradient update rule for θ including both (µ,ρ).

1

• (2 points) Consider the zero-th order optimization problem over discrete set x ∈ {0,1}^d. Implement policy gradients in Example 18.10 and Example 18.11 to solve the objective function

on prob3() of prog-template.py, plot convergence curves (wrt f(x)) and report your x_∗, θ_∗ (refer to the Example, p(x_i = 1) = θ_i).

4. (6 points) Consider the setting of decentralized computing, where we are given m A vector x = [x₁,…,x_m] has m components, and each node contains a local component x_i of the vector, with local objective function f_i(x_i) + g_i(x_i). At any time step, in addition to local algebraic operations, we can perform the following function calls simultaneously on all nodes:
   • (gradient computation) call grad(x): each node computes the local gradient ∇f_i(x).
   • (proximal mapping) call prox(η,z): each node computes the local proximal mapping

argmin.

u_i

• (communication) call communicate(z) = [(z_i−1+z_i+1)/2]_i=1,…,m: each node sends its local vector z_i over the network, then it receives vectors from the neighboring nodes i − 1 and i + 1 via the network, and computes the average (z_i−1 + z_i+1)/2 (where z₀ = z_m and z_m+1 = z₁).

If we have a variable w = [w₁,…,w_m], with w_i stored on node i, then node j 6= i cannot access the information w_i on node i directly, except through calling communicate(). We want to use the above function calls to jointly optimize the following objective function:

                  x₁ = x₂ = ··· = x_m = z₁ = ··· = z_m,

by rewriting the above problem as

,

with [Bz]_i = z_i − (z_i−1 + z_i+1)/2, f(x) = ^P_i f_i(x_i), g(z) = ^P_i g_i(z_i).

• (3 points) Write down an algorithm for decentralized optimization using linearized ADMM. Try to combine redundant communications so that no more than two communication calls are needed for each gradient computation.
• (3 points) Implement and plot convergence curves (wrt primal-suboptimality) with different parameters (eta and rho in ADMM) to solve the objective function in prob4() of prog-template.py.

2