In terms of efficient algorithms to solve these problems, using an accelerated proximal gradient descent algorithm applied to the convex linear and gated ReLU programs, one can achieve an \(\epsilon \) -optimal solution in \(\mathcal {O}(1/\sqrt{\epsilon })\)  iterations [1]}. For the convex ReLU formulation,[2]} proposes a Frank-Wolfe algorithm for convex MLPs which can be adapted to this case, which in the general case requires \(\mathcal {O}(1/\epsilon )\)  iterations for \(\epsilon \) -optimality [3]}.
