Repeated Operators

This example considers composite optimization problems with two functions

\[\begin{align*} \beta^* \in \argmin f(\beta) + g(\beta). \end{align*}\]

Gradients \(\nabla f\) are ‘easy’ to evaluate, while subgradients \(\partial g\) are computationally expensive and ‘hard’. The easy operation \(\nabla f\) can be computed \(h\) times at every iteration \(k\). The hard operation \(\partial g\) is computed only once per iteration \(k\), and \(\partial g\) does not use information from \(\nabla f_1\).

These requirement are formulated using information structures and repeated operator evaluation. The associated inclusions and information structure at \(h=3\) is

\[\begin{align*} \mat{c}{w^1_k \\ w^2_k \\ w^3_k \\ w^4_k } &\in \mat{c}{\nabla f(w^1_k) \\ \nabla f(w^2_k) \\ \nabla f(w^3_k) \\ \partial g(w^4_k)}, & \text{Sparsity}(\Dcl): & \mat{ccc:c}{0 & 0 & 0 & 0 \\ \bullet & 0 & 0 & 0 \\ \bullet & \bullet & 0 & 0 \hdl 0 & 0 & 0 & \bullet }. \end{align*}\]

Synthesis is used to find a algorithm that is convergent for all \(f \in S_{1, 8}\) and \(g \in S_{0,\infty}\), that also satisfies the information structure and repetition requirement. Two rounds of Synthesis/Analysis alternation are performed using order = {1, 1}. The Analysis-certified convergence rates for Repeated Evaluations are

# \(f\) evaluations	\(\rho\) bound (Round 1)	\(\rho\) bound (Round 2)
\(h=1\)	0.7979	0.7982
\(h=3\)	0.9967	0.7050

Figure 1 compares convergence behavior of trajectories solving a constrained optimization problem, each starting at \(x_0 = 0\).

Figure 1: Convergence conditions for 1-step and 3-step algorithms

Figure 1: Convergence conditions for 1-step and 3-step algorithms

Code for Repeated Synthesis

rng(33, 'twister');

m = 1;
L = 8;
Nrep = 3;

op1 = op_sml(m, L);
op2 = op_pcc();
ops = {op1, op2};

config = opt_config();
config.syn.elimination = false;


%form the system
bind =[ones(Nrep, 1); 2];
sys = opt_system(ops, [], [], bind);


%set the information structure

info_1 = tril(ones(Nrep), -1);

config.syn.D_mask = blkdiag(info_1, 1); 
man = opt_synthesis(sys, config);

Niter = 2;
order = {1, 1};
[sol_rep, history_rep] = man.alternate(Niter, order);


%% compare against an algorithm without repeated evaluation
sys_simple = opt_system(ops,[], []);
config_simple = opt_config;
config_simple.syn.elimination = false;
config_simple.syn.D_mask = [0, 0; 0, 1];

man_simple = opt_synthesis(sys_simple, config_simple);
[sol_simple, history_simple] = man_simple.alternate(Niter, order);