is organized as follows: In Section \[sec:primaldual\], we discuss our framework for screening. Section \[sec:duality\_gap\_certificates\] is devoted to deriving the information about optimal points in terms of gap functions. Sections \[sec:screening\_constrained\] and \[sec:screening\_penalized\] utilizes the framework and tools derived in previous sections to provide screening rules for constrained and penalized case respectively. In the end, we provide a small illustrative experiment for screening on simplex and $L_1$-constrained and also discuss that which of the existing results can be recovered using our algorithm in Section \[sec:exp\].

Setup and Primal-Dual Structure {#sec:primaldual}
===============================

In this paper, we consider optimization problems of the following primal-dual structure. As we will see, the relationship between primal and dual objectives has many benefits, including computation of the duality gap, which allows us to have a certificate for approximation quality.

A very wide range of machine learning optimization problems can be formulated as and , which are dual to each other: $$\begin{aligned}
    \label{eq:primal}\tag{A}\ \ \ \         \min_{{\bm{x}}\in {\mathbb{R}}^{n}} \quad& \Big[ \ \ 
    {\mathcal{O}_{\hspace{-1pt}A}}({\bm{x}}) \,:= \ \ f(A{\bm{x}})
    \ +\ g({\bm{x}}) &\Big]\ 
\\
    \label{eq:dual}\tag{B}\ \ \ \         \min_{{\bm{w}}\in {\mathbb{R}}^{d}} \quad& \Big[ \ \ 
    {\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}) :=  \ \ f^*({\bm{w}})
    \ +\ g^*(-A^\top{\bm{w}}) \!\!\!&\Big]\ \end{aligned}$$ The two problems are associated 