also separates as $g^*({\bm{y}}) = \sum_i g_i^*(y_i)$. Therefore, the two optimization problems and write as $$\begin{aligned}
    {\mathcal{O}_{\hspace{-1pt}A}}({\bm{x}}) :=&\ f(A{\bm{x}})
    + \textstyle\sum_i g_i(x_i) \label{eq:primalS}\tag{SA}\\
    {\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}) :=&\ f^*({\bm{w}})
    + \textstyle\sum_i g_i^*(-{\bm{a}}_i^\top{\bm{w}}) \ ,\label{eq:dualS}\tag{SB}\\end{aligned}$$ where ${\bm{a}}_i \in {\mathbb{R}}^d$ denotes the $i$-th column of $A$.

Crucially in this case, the optimality conditions and  now become separable, that is

$$\begin{aligned}
-{\bm{a}}_i^\top {\bm{w}}\in&\ \partial g_i(x_i) &&\forall i \label{eq:opt_gi} \ . 
\\
 x_i \in&\ \partial g_i^*(-{\bm{a}}_i^\top{\bm{w}}) &&\forall i \label{eq:opt_gistar} \ .\end{aligned}$$

Note that the two other conditions and are unchanged in this case.

Duality Gap and Certificates {#sec:duality_gap_certificates}
============================

The duality gap for our problem structure provides an optimality certificate for our class of optimization problems. It will be the most important tool for us to provide guaranteed information about the optimal point (as in Section \[sec:info\]), which will then be the foundation for the second step, to perform screening on the optimal point (as we will do in the later Sections \[sec:screening\_constrained\] and \[sec:screening\_penalized\]).

Duality Gap Structure
---------------------

For the problem structure and as given by Fenchel-Rockafellar duality, the *duality gap* for any pair of primal and dual variables ${\bm{x}}\in{\mathbb{R}}^n$ and ${\bm{w}}\in{\mathbb{R}}^d$ is defined as ${G}({\bm{w}},{\bm{x}}) := {\mathcal{O}_{\hspace{-1pt}A}}({\bm{x}}) + {\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}})$. Non-negativity of the gap – that 