Triple Momentum

The Triple Momentum (TMM) algorithm is an explicit first-order accelerated method to optimize a function \(f \in S_{m, L}\) [1]. The worst-case linear convergence rate for the triple momentum scheme is \(\rho \leq 1 - \sqrt{\frac{m}{L}}\) .

The Triple Momentum method was extended to composite optimization in [2]. The composite triple momentum algorithm minimizes the sum of functions \(f_1 + f_2\) with \(f_1 \in S_{m, L}\) and \(f_2 \in S_{0, \infty}\), and maintains the worst-case convergence rate \(\rho \leq 1 - \sqrt{\frac{m}{L}}\).

Analysis is used to numerically verify the rate \(1 - \sqrt{\frac{m}{L}}\) using IQCs of order [1, 1]. Figure 1 plots the results of the a parameter sweep. The left plots are the computed upper bounds (solid) v.s. the true rate (dotted lines). The right plots are the error between the computed bounds and the true rate. The top plots report a sweep of \(m \in [0.0033 , 1]\) with \(L=1\). The bottom plots report a sweep of \(L \in [1, 1/0.0033]\) (\(L \in [1,303.0303]\)).

Figure 2: Triple Momentum sweeps

Figure 2: Triple Momentum sweeps

The \(m\) sweep is more faithful to the true rate than the \(L\) sweep at high values of \(m = 1/L\), while the opposite is true for low values of \(m\).

Code for Triple Momentum analysis at \(m=1, L=10\)

%define the operators
m = 1;L = 10;
op1= op_sml(m, L);
op2 = op_sml(0, inf);
ops = {op1, op2};

%define the controller (unconstrained and constrained/composite)
K_uncon = tmm(m, L);
K_con = tmm_prox(m, L);

%form the system
sys_uncon = opt_system(op1, [], K_uncon);
sys_con= opt_system(ops, [], K_con);

%pose the analysis problem
order = [1,1];

man_uncon = opt_analysis(sys_uncon);
man_con = opt_analysis(sys_con);

%solve the analysis problem
sol_uncon = man_uncon.bisect(order);
sol_con = man_con.bisect(order);

best_rho = 1 - sqrt(m/L);
[best_rho, sol_uncon.rho, sol_con.rho]
%0.6838    0.6838    0.6838
 

%% functions to generate algorithms
function K = tmm(m, L)
    %triple momentum algorithm
    rho=1-1/sqrt(L/m);
    al=(1+rho)/L;
    be=rho^2/(2-rho);
    ga=rho^2/((1+rho)*(2-rho));
    A=[1+be -be;1 0];B=[-al;0];C=[1+ga -ga];
    K = ss(A,B,C,0,1);
end

function K = tmm_prox(m, L)
    %composite triple momentum
    A = [(1.0 - sqrt(m / L)) / (1.0 + sqrt(m / L)),  2.0 * sqrt(m / L) / (1.0 + sqrt(m / L));
        sqrt(m / L) * (1.0 - sqrt(m / L)) / (1.0 + sqrt(m / L)), 1.0 - sqrt(m / L) + 2.0 * m / L / (1.0 + sqrt(m / L))];

    B = [-1.0 / L, -1.0 / L;
        -1.0 / (sqrt(m / L) * L), -1.0 / (sqrt(m / L) * L)];
    C = [    (1.0 - sqrt(m / L)) / (1.0 + sqrt(m / L)),2.0 * sqrt(m / L) / (1.0 + sqrt(m / L));   
        sqrt(m / L) * (1.0 - sqrt(m / L)) / (1.0 + sqrt(m / L)),    1.0 - sqrt(m / L) + 2.0 * m / L / (1.0 + sqrt(m / L))];

    D = [0.0, 0.0;
        -1.0 / (sqrt(m / L) * L), -1.0 / (sqrt(m / L) * L)];

    K = ss(A, B, C, D, 1);
end

Code for Triple Momentum sweep analysis

mlist = mlist(2:end);
rho = zeros(Nm, 2, 3);

parfor i = 1:Nm
    for j = 1:2
        if j==1
            m = 1;
            L = 1/mlist(i);
        else
            m = mlist(i);
            L = 1;
        end
        
        %define the operators
        op1= op_sml(m, L);
        op2 = op_sml(0, inf);
        ops = {op1, op2};
        
        %define the controller (composite)              
        K_uncon = tmm(m, L);
        K_con = tmm_prox(m, L);
        
        %form the system
        sys_uncon = opt_system(op1, [], K_uncon);
        sys_con= opt_system(ops, [], K_con);
        
        
        %pose and solve the problem
        order = [1,1];
        
        man_uncon = opt_analysis(sys_uncon);
        man_con = opt_analysis(sys_con);
        
        sol_uncon = man_uncon.bisect(order);
        sol_con = man_con.bisect(order);
    
        best_rho = 1 - sqrt(m/L);
    
        rho(i,j,  :) = [sol_uncon.rho, sol_con.rho, best_rho];
    end
end

%% plot the sweep
figure(1)
clf
tiledlayout(2, 2)
for j = 1:2
nexttile
hold on
if j == 1
    xla = "$m$";
else
    xla = "$1/L$";
end
plot(mlist, squeeze(rho(:, j,  1:2)), 'linewidth', 2)
plot(mlist, squeeze(rho(:, j, 3)), '--', 'linewidth', 2, 'color', 0.5*[1,1,1]);
xlabel(xla, 'interpreter', 'latex', 'fontsize', 16)
ylabel('$\rho$', 'interpreter', 'latex', 'fontsize', 16)
xlim([0, 1]);
ylim([0, 1])
if j ==1
legend({'TMM', 'Composite TMM', '$1-\sqrt{m/L}$'}, 'location','northeast', 'interpreter', ...
    'latex', 'fontsize', 16,'location', 'northeast')
end
nexttile
hold on
plot(mlist, squeeze(rho(:, j, 1:2)-rho(:, j, 3)), 'linewidth', 2)
xlabel(xla, 'interpreter', 'latex', 'fontsize', 16)
ylabel('$\rho - \left(1-\sqrt{m/L}\right)$', 'interpreter', 'latex', 'fontsize', 16)
xlim([0, 1]);
set(gca, 'yscale', 'log')
end

%% functions to generate algorithms
function K = tmm(m, L)

---

[1]

Bryan Van Scoy, Randy A Freeman, and Kevin M Lynch. The Fastest Known Globally Convergent First-Order Method for Minimizing Strongly Convex Functions. IEEE Control Systems Letters, 2(1):49–54, 2018.

[2]

Manu Upadhyaya, Daniel Berg Thomsen, Aymeric Dieuleveut, and Adrien B Taylor. An optimal first-order method for smooth and strongly convex composite optimization and its stationary limit. arXiv preprint arXiv:2605.22929, 2026.