---
abstract: 'We propose a new framework for deriving screening rules for convex optimization problems. Our approach covers a large class of constrained and penalized optimization formulations, and works in two steps. First, given any approximate point, the structure of the objective function and the duality gap is used to gather information on the optimal solution. In the second step, this information is used to produce screening rules, i.e. safely identifying unimportant weight variables of the optimal solution. Our general framework leads to a large variety of useful existing as well as new screening rules for many applications. For example, we provide new screening rules for general simplex and $L_1$-constrained problems, Elastic Net, squared-loss Support Vector Machines, minimum enclosing ball, as well as structured norm regularized problems, such as group lasso.'
---

Introduction
============

\[sec:intro\] [^1]Optimization techniques for high-dimensional problems have become the work-horses for most data-analysis and machine-learning methods. With the rapid increase of available data, major challenges occur as the number of optimization variables (weights) grows beyond capacity of current systems.

The idea of screening refers to eliminating optimization variables that are guaranteed to *not* contribute to any optimal solution, and can therefore safely be removed from problem. Such screening techniques have received increased interest in several machine learning related applications in recent years, and have been shown to lead to very significant computational efficiency improvements in various cases, in particular for many types of sparse methods. Screening techniques can be used either as a pre-processing before passing the problem to the optimizer, or also interactively during any iterative solver (called dynamic screening), to gradually reduce the problem complexity during optimization.

While existing screening methods were mainly relying on geometric and problem-specific properties, we in this paper take a different approach. We propose a new framework allowing screening on general convex optimization problems, using simple tools from convex duality instead of any geometric arguments. Our framework applies to a very large class of optimization problems both for constrained as well as penalized problems, including most machine learning methods of interest.

Our main contributions in this paper are summarized as follows:

1.  We propose a new framework for screening for a more general class of optimization problem with a simple primal-dual structure.

2.  The framework leads to a large set of new screening rules for machine learning problems that could not be screened before. Furthermore, it also recovers many existing screening rules as special cases.

3.  We are able to express all screening rules using general optimization complexity notions such as smoothness or strong convexity, getting rid of problem-specific geometric properties.

4.  Our proposed rules are dynamic (allowing any existing algorithm to be additionally equipped with screening) and safe (guaranteed to only eliminate truly unimportant variables).

#### Related Work.

The concept of screening in the sense of eliminating non-influential data points to reduce the problem size has originated relatively independently in at least two communities. Coming from computational geometry, [@Ahipasaoglu:2008il] has proposed a screening technique for the minimum enclosing ball problem for a given set of data points. Here screening can be interpreted as simply removing points which are guaranteed to lie in the strict interior of the final ball. Later [@Kallberg:2014kd] improve the threshold for this rule in the minimum enclosing ball setting.

Independently, the breakthrough work of [@Ghaoui:2010tu] gave the first screening rules for the important case of sparse regression, as given in the Lasso. Since then, there have been many extensions and alterations of the general concept. While [@Ghaoui:2010tu] exploits geometric quantities to bound the the Lasso dual solution within a compact region, we recommend the survey paper by [@Xiang:2014vi] for an overview of geometric methods for Lasso screening. Sphere-region based methods differ from dome-shaped regions as used in [@Ghaoui:2010tu] in choosing different centers and radii to bound the dual optimal point. Apart from being geometry specific, most existing approaches such as [@Wang:2013uq; @Wang:2014un; @Liu:2014uz; @Ghaoui:2010tu; @Ogawa:2013ul] are not agnostic to the regularization parameter used, but instead are restricted to perform screening along the entire regularization path (as the regularization parameter changes). This is known as sequential screening, and restricts its usability to optimization algorithms obtaining paths. In contrast, our proposed framework here allows any internal optimization algorithms to be equipped with screening.

Despite the importance of constrained problems in many applications, much less is known about screening for constrained optimization, in contrast to the case of penalized optimization problems. For the dual of the hinge loss SVM, which is a box-constrained optimization problem, [@Ogawa:2014vw] proposed a geometric screening rule based on the intersection region of two spheres, in the sequential setting of varying regularizer. More recently, [@Zimmert:2015ue] provided new screening rules for that case in the dynamic setting using a method similar to our approach. However their method is restricted to the SVM case.

As a first step to allow screening for more general optimization objectives, [@Ndiaye:2015wj] gives duality gap based screening rules for multi-task and multi-class problems (in the penalized setting) under for a wider class of objectives $f$. Nevertheless, their approach is restricted to assume separability of $f$ over the group structure, which limits the screening rules, in the sense of not covering standard group lasso for example. Also in [@Shibagaki:2016ts], authors assume the similar problem formulation as in [@Ndiaye:2015wj] but a bit more general. The focus in [@Shibagaki:2016ts] is on screening rules for SVM problems rather than general framework. They derive the screening rules for SVM by considering standard hinge and $\epsilon$-insensitive loss with regularization formulation which is close to the empirical risk minimization framework here, but has more limited applications in terms of generalization of the screening rules. We here provide screening rules for a more general framework of box constrained optimization, while hinge-loss SVM happens to be a special case of this. Our proposed approach can be shown to recover many of the other existing rules including e.g. [@Ndiaye:2015wj] and [@Zimmert:2015ue], but significantly generalizing the method to general objectives and constraints as well as regularizers. The rest of the paper 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 to a given data matrix $A\in{\mathbb{R}}^{d\times n}$, and the functions $f : {\mathbb{R}}^d \rightarrow {\mathbb{R}}$ and $g : {\mathbb{R}}^n \rightarrow {\mathbb{R}}$ are allowed to be arbitrary closed convex functions. The functions $f^*,g^*$ in formulation  are defined as the *convex conjugates* of their corresponding counterparts $f,g$ in . Here ${\bm{x}}\in {\mathbb{R}}^n$ and ${\bm{w}}\in {\mathbb{R}}^d$ are the respective variable vectors. For a given function $h: {\mathbb{R}}^d\rightarrow {\mathbb{R}}$, its conjugate is defined as $$h^*({\bm{v}}) := \max_{{\bm{u}}\in{\mathbb{R}}^d} {\bm{v}}^\top {\bm{u}}- h({\bm{u}}) \, .$$ The association of problems and is a special case of Fenchel Duality. More precisely, the relationship is called *Fenchel-Rockafellar Duality* when incorporating the linear map $A$ as in our case, see e.g. [@Borwein:2005ge Theorem 4.4.2] or [@Bauschke:2011ik Proposition 15.18], see the Appendix \[app:primaldual\] for a self-contained derivation. The two main powerful features of this general duality structure are first that it includes many more machine learning methods than more traditional duality notions, and secondly that the two problems are fully symmetric, when changing respective roles of $f$ and $g$. In typical machine learning problems, the two parts typically play the roles of a data-fit (or loss) term as well as a regularization term. As we will see later, the two roles can be swapped, depending on the application.

#### Optimality Conditions.

The first-order optimality conditions for our pair of vectors ${\bm{w}}\in {\mathbb{R}}^d, {\bm{x}}\in {\mathbb{R}}^n$ in problems  and  are given as

$$\begin{aligned}
 {\bm{w}}\in&\ \partial f(A{\bm{x}}) \label{eq:opt_f} \ ,\\ 
A{\bm{x}}\in&\ \partial f^*({\bm{w}}) \label{eq:opt_fstar} \ ,\end{aligned}$$

$$\begin{aligned}
 -A^\top {\bm{w}}\in&\ \partial g({\bm{x}}) \label{eq:opt_g} \ ,\\ 
 {\bm{x}}\in&\ \partial g^*(-A^\top{\bm{w}}) \!\!\!\!\!\!&\label{eq:opt_gstar}\end{aligned}$$

see e.g. [@Bauschke:2011ik Proposition 19.18]. The stated optimality conditions are equivalent to ${\bm{x}},{\bm{w}}$ being a saddle-point of the Lagrangian, which is given as $\mathcal{L}({\bm{x}},{\bm{w}}) =f^*({\bm{w}}) - \langle A{\bm{x}},{\bm{w}}\rangle - g({\bm{x}}) $ if ${\bm{x}}\in \operatorname{dom}(g)$ and ${\bm{w}}\in \operatorname{dom}(f^*)$, see Appendix \[app:primaldual\] for details.

#### The Constrained Case.

Any constrained convex optimization problem of the form $$\label{eq:constrainedOpt}
\min_{{\bm{x}}\in{\mathcal{C}}} f(A{\bm{x}})$$ for a constraint set ${\mathcal{C}}$ can be directly written in the form by using the indicator function of the constraint set as the penalization term $g$. (The indicator function ${\bm{\iota}}_{{\mathcal{C}}}$ of a set ${\mathcal{C}}\subset {\mathbb{R}}^n$ is defined as ${\bm{\iota}}_{{\mathcal{C}}}({\bm{x}}) := 0$ if ${\bm{x}}\in{\mathcal{C}}$ and ${\bm{\iota}}_{{\mathcal{C}}}({\bm{x}}) := +\infty$ otherwise.)

#### The Partially Separable Case.

A very important special case arises when one part of the objective becomes separable. Formally, this is expressed as $g({\bm{x}}) = \sum_{i=1}^{n} g_i(x_i)$ for univariate functions $g_i:{\mathbb{R}}\rightarrow{\mathbb{R}}$ for $i\in[n]$. Nicely in this case, the conjugate of $g$ 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 is weak duality – is satisfied by all pairs.

Most importantly, the duality gap acts as a certificate of approximation quality — the true optimum values ${\mathcal{O}_{\hspace{-1pt}A}}({\bm{x}}^*)$ and $-{\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}^*)$ (which are both unknown) will always lie within the (known) duality gap.

#### The Gap Function.

For the special case of differentiable function $f$, we can study a simpler duality gap $$\label{eq:gap}
{G}({\bm{x}}) := {\mathcal{O}_{\hspace{-1pt}A}}({\bm{x}}) + {\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}({\bm{x}}))$$ purely defined as a function of ${\bm{x}}$, using the optimality relation , i.e. ${\bm{w}}({\bm{x}}) := \nabla f( A{\bm{x}})$.

#### The Wolfe-Gap Function.

For any constrained optimization problem defined over a bounded set ${\mathcal{C}}$ and ${\bm{x}}\in{\mathcal{C}}$, the Wolfe gap function (also known as Hearn gap or Frank-Wolfe gap) is defined as the difference of $f$ to the minimum of its linearization over the same domain. Formally, $$\label{eq:wolfe_gap}
{G_{\mathcal{C}}}({\bm{x}}) := \underset{{\bm{y}}\in {\mathcal{C}}}{\max}\; (A{\bm{x}}-A{\bm{y}})^\top\nabla f(A{\bm{x}}).$$ It is not hard to see that the convenient Wolfe gap function is a special case of our above defined general duality gap ${G}({\bm{x}}) := {\mathcal{O}_{\hspace{-1pt}A}}({\bm{x}}) + {\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}({\bm{x}}))$, for $g$ being the indicator function of the constraint set ${\mathcal{C}}$, and ${\bm{w}}({\bm{x}}) := \nabla f(A{\bm{x}})$. For more details, see Appendix \[app:eq\_fw\_gd\], or also [@LacosteJulien:2013ue Appendix D].

Obtaining Information about the Optimal Points {#sec:info}
----------------------------------------------

As we have mentioned, any type of screening will crucially rely on first deriving safe knowledge about the unknown optimal points of our given optimization problem. Here, we will use the duality gap to obtain such knowledge on the optimal points ${\bm{x}}^\star\in{\mathbb{R}}^n$ and ${\bm{w}}^\star\in{\mathbb{R}}^d$ of the respective optimization problems and respectively. Proofs are provided in Appendix \[app:optimal\_point\].

Our first lemma shows how to bound the distance between any (feasible) current dual iterate and the solution ${\bm{w}}^\star$ using standard assumptions on the objective functions.

\[lem:stronglyconvex\] Consider the problem with optimal solution ${\bm{w}}^\star\in {\mathbb{R}}^d$. For $f$ being $\mu$-smooth, we have $${\left\lVert{\bm{w}}- {\bm{w}}^\star\right\rVert}^2 \le \frac{2}{\mu}(f^*({\bm{w}})-f^*({\bm{w}}^\star))$$

The following corollary will be important to derive screening rules for penalized problems in Section \[sec:screening\_penalized\], as well as box-constrained problems (Section \[subsec:box\_screening\]).

\[cor:Dgaprestriction\] We consider the problem setup and , and assume $f$ is $\mu$-smooth. Then $${\left\lVert{\bm{w}}- {\bm{w}}^\star\right\rVert}^2 \le \frac{2}{\mu}{G}({\bm{x}}).$$ Here ${G}({\bm{x}})$ is the duality gap function as defined in equation .

The following two results hold for general constrained optimization problems of the form , where $g$ is the indicator function of a constraint set ${\mathcal{C}}\subset{\mathbb{R}}^n$ and hence are useful for deriving screening rules for such problems.

\[lem:FWgaprestriction\] Consider problem and assume that $f$ is $\mu$-strongly convex over a bounded set ${\mathcal{C}}$. Then it holds that $$\label{eq:FWgaprestriction}
{\left\lVertA{\bm{x}}-A{\bm{x}}^\star\right\rVert}_2^2 \le \frac{1}{\mu}{G_{\mathcal{C}}}({\bm{x}}),$$ where ${\bm{x}}^\star$ is an optimal solution and ${G_{\mathcal{C}}}$ is the Wolfe-Gap function of $f$ over the bounded set ${\mathcal{C}}$.

\[cor:restric:smooth\] Assuming $f$ is $L$-smooth as well as $\mu$-strongly convex over a bounded set ${\mathcal{C}}$, we have $${\left\lVert\nabla f(A{\bm{x}})-\nabla f(A{\bm{x}}^\star)\right\rVert} \le \frac{L}{\sqrt{\mu}}\sqrt{{G_{\mathcal{C}}}({\bm{x}})}$$

Screening Rules for Constrained Problems {#sec:screening_constrained}
========================================

In the following, we will develop screening rules for constrained optimization problems of the form , by exploiting the structure of the constraint set for a variety of sparsity-inducing problems. First of all, we give a general lemma which we will be using in rest of the paper to derive screening rules when any of the function in \[eq:primal\] and \[eq:dual\] is indicator function.

\[lem:general\_constrained\_lemma\] For general constrained optimization $\min_{{\bm{x}}\in {\mathcal{C}}} f(A{\bm{x}})$, the optimality condition  gives rise to the following optimality rule at the optimal point: $$\label{eq:general_constrained_rule}
(A{\bm{x}}^\star)^\top {\bm{w}}^\star = \min_{{\bm{z}}\in {\mathcal{C}}} (A{\bm{z}})^\top {\bm{w}}^\star \vspace{-1mm}$$

The above equation also suggest that ${\bm{x}}^\star = \operatorname*{arg\,min}_{{\bm{z}}\in {\mathcal{C}}}(A{\bm{z}})^\top {\bm{w}}^\star$. Lemma \[lem:general\_constrained\_lemma\] is very crucial in further deriving screening rules for constrained optimization problem as well as norm penalized problems whose conjugate is indicator function of the dual norm.

Simplex Constrained Problems {#subsec:simplex_screening}
----------------------------

Optimization over unit simplex ${\triangle}:= \{{\bm{x}}\in{\mathbb{R}}^n \ | \ x_i \ge 0,\quad \sum_{i=1}^{n} x_i = 1 \}$ is a important class of constrained problems , as it includes optimization over any finite polytope. In this case, the columns of $A$ describe the vertices, and ${\bm{x}}$ are barycentric coordinates representing the point $A{\bm{x}}$. Formally, $g({\bm{x}})$ is the indicator function of the unit simplex ${\mathcal{C}}= {\triangle}$ in this case.

The following two theorems provide screening rules for simplex constrained problems. We provide all proofs in Appendix \[app:simplex\_screening\].

\[thm:simplexcondition\] For general simplex constrained optimization $\min_{{\bm{x}}\in{\triangle}} f(A{\bm{x}})$, the optimality condition  gives rise to the following screening rule at the optimal point, for any $i \in [n]$ $$\label{eq:simplexcondition}
({\bm{a}}_i - A{\bm{x}}^\star)^\top{\bm{w}}^\star > 0 
\ \Rightarrow \ x_i^\star = 0 \ .$$

In the following Theorem \[thm:simplex\_smooth\] we now assume smoothness and strong convexity of function $f$ to provide screening rules for simplex problems, in terms of an arbitrary iterate ${\bm{x}}$, without knowing ${\bm{x}}^\star$.

\[thm:simplex\_smooth\] Let $f$ be $L$-smooth and $\mu$-strongly convex over the unit simplex ${\mathcal{C}}= {\triangle}$. Then for simplex constrained optimization $\min_{{\bm{x}}\in{\triangle}} f(A{\bm{x}})$ we have the following screening rule, for any $i \in [n]$ $$({\bm{a}}_i -A{\bm{x}})^\top\nabla f(A{\bm{x}}) > L\sqrt{\frac{{G_{\mathcal{C}}}({\bm{x}})}{\mu}}{\left\lVert{\bm{a}}_i-A{\bm{x}}\right\rVert} 
\ \Rightarrow \ x_i^\star=0 \ .$$

Our general screening rules for simplex constrained problems as in Theorem \[thm:simplex\_smooth\] allows many practical implications. For example, new screening rules for squared loss SVM and minimum enclosing ball problem come as a direct consequence.

#### Squared Hinge Loss SVM.

The squared hinge-loss SVM problem in its dual form is formulated as $$\begin{aligned}
 \label{eq:sq:loss:svm}
\min_{{\bm{x}}\in {\triangle}} \ \big[\ f(A{\bm{x}}) := \tfrac12 {\bm{x}}^\top A^\top A{\bm{x}}\ \big] \vspace{-1mm}
 $$ over a unit simplex constraint ${\bm{x}}\in{\triangle}\subset{\mathbb{R}}^n$. Here for given data examples $\bar{\bm{a}}_1,\dots,\bar{\bm{a}}_n\in{\mathbb{R}}^d$ and corresponding labels $y_i\in\pm1$, the matrix $A$ collects the columns ${\bm{a}}_i=y_i\bar{\bm{a}}_i$, see e.g. [@Tsang:2005up]. We obtain the following novel screening rule for square loss SVM:

\[cor:square\_svm\] For the squared hinge loss SVM we have the screening rule $$\begin{aligned}
({\bm{a}}_i - A{\bm{x}})^\top A{\bm{x}}&>\sqrt{\max_{i}\; (A{\bm{x}}-{\bm{a}}_i)^\top A{\bm{x}}} \,\|{\bm{a}}_i - A{\bm{x}}\| \notag \\
& \Rightarrow \ x_i^\star = 0.\end{aligned}$$

#### Minimum Enclosing Ball.

The primal and dual for the minimum enclosing ball problem is given as the following pair of optimization formulations and respectively. $$\begin{aligned}
& \min_{{\bm{c}}\in{\mathbb{R}}^d,r\in{\mathbb{R}}} \ \ \ r^2  \quad \text{s.t.} \ \ {\left\lVert{\bm{c}}-{\bm{a}}_i\right\rVert}^2_2\le r^2 \quad \forall i \in [n] \label{eq:min_enclosing_ball} \\
\qquad &~ \min_{{\bm{x}}\in{\triangle}\subset{\mathbb{R}}^n} \ \ \ {\bm{x}}^\top A^\top A{\bm{x}}+ {\bm{c}}^\top {\bm{x}}\ , \label{eq:dualball}\end{aligned}$$ where ${\bm{c}}$ is a vector whose $i^{th}$ element $c_i$ is $-{\bm{a}}_i^\top {\bm{a}}_i$, see for example [@Matousek:2007ub] or our Appendix \[app:simplex\_screening\].

\[cor:min\_enclosing\_ball\] For the minimum enclosing ball problem we have the screening rule $$\begin{aligned}
\label{eq:ballcor}
(\bm{e}_i-{\bm{x}})^\top &(2A^\top A{\bm{x}}+{\bm{c}}) > \notag \\ &2\sqrt{\tfrac{1}{2}\max_i({\bm{x}}-\bm{e}_i)^\top (2A^\top A{\bm{x}}+{\bm{c}})}{\left\lVert{\bm{a}}_i-A{\bm{x}}\right\rVert}  \notag
\\ \ \Rightarrow \ x_i^\star = 0 \ .\end{aligned}$$

Our result improves upon the known rules by [@Kallberg:2014kd; @Ahipasaoglu:2008il] by providing a broader selection criterion .

$L_1$-Constrained Problems {#subsec:l1ball_screening}
--------------------------

$L_1$-constrained formulations are very widely used in order to induce sparsity in the variables. Here below we provide results for screening on general $L_1$-constrained problems, that is $\min_{{\bm{x}}\in{\mathcal{C}}} f(A{\bm{x}})$ for ${\mathcal{C}}= L_1 \subset{\mathbb{R}}^n$ (or a scaled version of the $L_1$-ball). Proofs are provided in Appendix \[app:l1ball\_screening\].

\[thm:l1\_constrained\_screening\] For general $L_1$-constrained optimization $\min_{{\bm{x}}\in L_1} f(A{\bm{x}})$, the optimality condition  gives rise to the following screening rule at the optimal point, for any $i \in [n]$ $$\label{eq:l1_constrained}
{\left\lvert{\bm{a}}_i^\top {\bm{w}}^\star\right\rvert}  + (A {\bm{x}}^\star)^\top{\bm{w}}^\star <0 
\ \Rightarrow \ x_i^\star  = 0\ .$$

Using only a current iterate ${\bm{x}}$ instead of an optimal point, we obtain screening for general smooth and strongly convex function $f$:

\[thm:l1\_smooth\_constrained\] Let $f$ be $L$-smooth and $\mu$-strongly convex over the $L_1$-ball. Then for $L_1$-constrained optimization $\min_{{\bm{x}}\in L_1} f(A{\bm{x}})$ we have the following screening rule, for any $i \in [n]$ $$\begin{aligned}
{\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} + &(A{\bm{x}})^\top \nabla f(A{\bm{x}}) \notag \\ +& L({\left\lVert{\bm{a}}_i\right\rVert}_2 + {\left\lVertA{\bm{x}}\right\rVert}_2)\sqrt{\frac{{G_{\mathcal{C}}}({\bm{x}})}{\mu}} < 0  \notag
\\ \Rightarrow \ {\bm{x}}_i^\star = 0 \label{eq:l1_constrained_screening}\end{aligned}$$

Elastic Net Constrained Problems
--------------------------------

Elastic net regularization as an alternative to $L_1$ is often used in practice, and can outperform the Lasso, while still enjoying a similar sparsity of representation [@Zou:2005EN]. The elastic net is given by the expression $$\alpha {\left\lVert{\bm{x}}\right\rVert}_1 + \frac{(1 - \alpha) }{2} {\left\lVert{\bm{x}}\right\rVert}_2^2
\ .$$ Here below we provide novel result for screening on general elastic net constrained problems, that is $\min_{{\bm{x}}\in{\mathcal{C}}} f(A{\bm{x}})$ for ${\mathcal{C}}$ being the elastic net constraint, or a scaled version of it. Proofs are provided in Appendix \[app:elastic\_net\_screening\].

\[thm:elastic\_net\_constrained\] For general elastic net constrained optimization $\min_{{\bm{x}}\in L_E} f(A{\bm{x}})$ where $L_E := \{{\bm{x}}\in{\mathbb{R}}^n\ |\ \alpha {\left\lVert{\bm{x}}\right\rVert}_1 + \frac{(1 - \alpha) }{2} {\left\lVert{\bm{x}}\right\rVert}_2^2 \le 1\}$, the optimality condition  gives rise to the following screening rule at the optimal point, for any $i \in [n]$ $$\begin{aligned}
|{\bm{a}}_i^\top {\bm{w}}^\star | + (A{\bm{x}}^\star)^\top  {\bm{w}}^\star \Big [ \frac{ \alpha  }{ 1 + \frac{(1 - \alpha) }{2} \|{\bm{x}}^\star\|_2^2} \Big ] < 0  \Rightarrow x_i^\star = 0\end{aligned}$$

Using only a current iterate ${\bm{x}}$ instead of an optimal point, we obtain screening for general smooth and strongly convex function $f$:

\[thm:elastic\_smooth\_constrained\] Let $f$ be $L$-smooth and $\mu$-strongly convex over the elastic net norm ball. Then for elastic net constrained optimization $\min_{{\bm{x}}\in L_E} f(A{\bm{x}})$ we have the following screening rule, for any $i \in [n]$ $$\begin{aligned}
{\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} + &(A{\bm{x}})^\top \nabla f(A{\bm{x}}) \big[ \frac{2\alpha}{3-\alpha} \big ] \notag \\ +& L({\left\lVert{\bm{a}}_i\right\rVert}_2 + {\left\lVertA{\bm{x}}\right\rVert}_2\big[ \frac{2\alpha}{3-\alpha} \big ])\sqrt{\frac{{G_{\mathcal{C}}}({\bm{x}})}{\mu}} < 0  \notag
\\ \Rightarrow \ {\bm{x}}_i^\star = 0 \label{eq:l1_constrained_screening}\end{aligned}$$

Note that both above results also recover the $L_1$ constrained case as a special case, when $\alpha \rightarrow 1$.

Screening for Box Constrained Problems {#subsec:box_screening}
--------------------------------------

Box-constrained problems are important in several machine learning applications, including SVMs. After variable rescaling, w.l.o.g. we can assume the constraint set ${\mathcal{C}}= \Box := \{{\bm{x}}\in{\mathbb{R}}^n \ | \ 0 \le x_i \le 1 \}$. We derive screening rules for predicting both if a variable will take the upper or lower constraint.

\[thm:box\_constrained\] Let $f$ be $L$-smooth. Then for box-constrained optimization $\min_{{\bm{x}}\in \Box} f(A{\bm{x}})$, we obtain the following screening rules, for any $i \in [n]$ $$\begin{aligned}
&{\bm{a}}_i^\top \nabla f(A{\bm{x}}) -  {\left\lVert{\bm{a}}_i\right\rVert}_2\sqrt{2L {G}({\bm{x}})}>0 
\ \Rightarrow \  x_i^\star =0 \ , \ \text{ and}\\
&{\bm{a}}_i^\top \nabla f(A{\bm{x}}) +  {\left\lVert{\bm{a}}_i\right\rVert}_2\sqrt{2L\,{G}({\bm{x}})} < 0 
\ \Rightarrow \  x_i^\star =1 \ . $$

Box constrained opptimization problems arise very often in machine learning probelm. Hinge loss SVM happens to one of many special cases of box-constrained optimizaion problem.

#### Hinge Loss SVM.

The dual of the classical support vector machine with hinge loss, when not using a bias value, is a box-constrained problem. As a direct consequence of Theorem \[thm:box\_constrained\] we therefore obtain screening rules for SVM with hinge loss and no bias. The primal formulation of the SVM in this setting, for a regularization parameter $C>0$, is$$\begin{aligned}
 &\underset{{\bm{w}}\in{\mathbb{R}}^d,{\bm{\epsilon}}\in{\mathbb{R}}^n}{\min}  \tfrac{1}{2} {\bm{w}}^\top{\bm{w}}+ C {\mathbf{1}}^\top{\bm{\epsilon}}\\
 &\text{s.t.}  \quad  {\bm{w}}^\top{\bm{a}}_i \ge 1-\varepsilon_i  \ \ \forall i \in [n]  \\
\qquad  & \varepsilon_i \ge 0  \quad \forall i \in [n] \label{eq:primal:svm_hinge}
\end{aligned}$$

\[cor:SVMhinge\] For SVM with hinge loss and no bias as given in , we have the screening rules $$\begin{aligned}
&{\bm{a}}_i^\top A{\bm{x}}-{\left\lVert{\bm{a}}_i\right\rVert}_2\sqrt{2{G}({\bm{x}})} >0 \ \Rightarrow \ x_i^\star = 0 \ , \ \text{ and}\\
&{\bm{a}}_i^\top A{\bm{x}}+{\left\lVert{\bm{a}}_i\right\rVert}_2\sqrt{2{G}({\bm{x}})} <0 \ \Rightarrow \ x_i^\star = C \ .\end{aligned}$$ where ${\bm{x}}\in{\mathbb{R}}^n$ is any feasible dual point.

We get similar screening rules for hinge loss SVM as in [@Zimmert:2015ue] as well as in [@Shibagaki:2016ts]. The closest known result to our Corollary \[cor:SVMhinge\] for screening in hinge loss SVM is given in [@Zimmert:2015ue] and [@Shibagaki:2016ts]. The work of [@Zimmert:2015ue] also covers the kernelized SVM case, and improves the threshold given in our Corollary \[cor:SVMhinge\] by a constant of $\sqrt{2}$. In Appendix \[app:box\_screening\], we show that our more general approach here can also be adjusted to gain this constant factor.

Screening for Penalized Problems {#sec:screening_penalized}
================================

In this section we will develop screening methods for general penalized convex optimization problems of the form and . The cornerstone application are $L_1$ regularized problems, for which we now develop screening rules with general cost function $f$. We show in Appendix \[app:penalized\_problem\_l1\] that our method can reproduce the screening rules of [@Ndiaye:2015wj] as special cases, whereas their method does not directly extend to general $f$. Beyond $L_1$ problems, we also describe new screening rules for elastic net regularized problems, as well as the important case of structured norm regularized optimization.

$L_1$-Penalized Problems
------------------------

The next theorem describes a screening rule for general $L_1$-penalized problems, under a smoothness assumption on function $f$. Proofs for are given in Appendix \[app:penalized\_problem\_l1\].

\[thm:smooth\_pen\_lasso\] Consider an $L_1$-regularized optimization problem of the form $$\begin{aligned}
\label{eq:l1_regularized}
 \min_{{\bm{x}}\in {\mathbb{R}}^n} \ \ f(A{\bm{x}}) +  \lambda {\left\lVert{\bm{x}}\right\rVert}_1\end{aligned}$$ If $f$ is $L$-smooth, then the following screening rule holds for all $i\in[n]$: $$\begin{aligned}
{\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} < \lambda - {\left\lVert{\bm{a}}_i\right\rVert}_2\sqrt{2L\,{G}({\bm{x}})} 
\ \Rightarrow \ {\bm{x}}_i^\star=0\end{aligned}$$

By careful observation of the expression in Theorem \[thm:smooth\_pen\_lasso\], it is easy to find a connection between our screening rule and the geometric sphere test method based screening [@Xiang:2014vi]. The general idea behind the sphere test is to consider the maximum value of the objective function in a spherical region which contains the optimal dual variable. We discuss this connection in more detail in Appendix \[app:connection\_sphere\_test\].

Also, in Appendix \[app:penalized\_problem\_l1\], we discuss the special cases of squared loss regression and logistic loss regression with $L_1$ penalization. These results are presented in Corollaries \[cor:pen\_lasso\] and \[cor:logistic\_l1\] as direct consequences of Theorem \[thm:smooth\_pen\_lasso\]. Both of the corollaries can also be derived from the framework discussed in the paper [@Ndiaye:2015wj].

Elastic-Net Penalized Problems
------------------------------

In the next corollary, we present a novel screening rule for the elastic net squared loss regression problem.

\[cor:elastic\_net\_regr\] Consider the elastic net regression formulation $$\label{eq:elastic}
\min_{{\bm{x}}\in{\mathbb{R}}^n} \ \tfrac{1}{2} \|A{\bm{x}}- {\bm{b}}\|_2^2 + \lambda_2  \|{\bm{x}}\|_2^2 + \lambda_1 \|{\bm{x}}\|_1$$ The following screening rule holds for all $i\in[n]$: $$\begin{aligned}
&{\left\lvert({\bm{a}}_i^\top A + 2\lambda_2 \bm{e}_i^\top){\bm{x}}-  {\bm{a}}_i^\top {\bm{b}}\right\rvert} < \\ &\quad  \qquad \lambda_1 - \sqrt{2({\bm{a}}_i^\top {\bm{a}}_i + 2\lambda_2) {G}({\bm{x}})} \ \Rightarrow \ x_i^\star = 0.\end{aligned}$$

We also recover existing screening rules for elastic net regularized problem with more general objective $f$ using our frameworks, in Appendix \[app:penalized\_problem\_l1\], see Lemma \[lem:smooth\_elastic\] and Theorem \[thm:elasticnet\_genral\] which has been earlier derived in [@Shibagaki:2016ts]. In the proof, we derive screening rules from both the formulation and using optimality condition and which is novel as well as help us to understand the property useful in deriving screening rules for elastic net penalized problems.

Structured Norm Penalized Problems {#subsec:l1_l2_genral}
----------------------------------

Here in this section we present screening rules for non-overlapping group norm regularized problems. Group-norm regularization is widely used to induce sparsity in terms of groups of variables of the the solution of the optimization problem. The most prominent example is the group lasso ($\ell_2/\ell_1$-regularization). Here in this section we mostly discuss screening for general objectives with an $\ell_2/\ell_1$-regularization. Proofs are provided in Appendix \[app:structured\_norm\].

#### Group Norm - $\ell_2/\ell_1$ Regularization. {#par:l1_l2_group}

In the following, we use the notation $\{ {\bm{x}}_1 \cdots {\bm{x}}_G\}$ to express a vector ${\bm{x}}$ as a partition of the groups of variables, such that ${\bm{x}}^\top = \left[ {\bm{x}}_1^\top, {\bm{x}}_2^\top \cdots {\bm{x}}_G^\top \right]$. Correspondingly, the matrix $A$ can be denoted as the concatenation of the respective columns $A = [A_1 \ A_2 \cdots A_G]$.

\[thm:smooth\_grp\_lasso\] For $\ell_2/\ell_1$-regularized optimization problem of the form $$\begin{aligned}
\ \quad  \min_{{\bm{x}}} f(A{\bm{x}}) + \sum_{g=1}^G \sqrt{\rho_g} \|{\bm{x}}_g\|_2 \vspace{-2mm}\end{aligned}$$ Assuming $f$ is $L$-smooth, then the following screening rule holds for all groups $g$: $$\begin{aligned}
\|A_g^\top \nabla f(A{\bm{x}}) \|_2 + \sqrt{2L} {\left\lVertA_g\right\rVert_{\textsf{Fro}}} < \sqrt{\rho_g} \ \Rightarrow\  {\bm{x}}_g^\star = 0 \ .\end{aligned}$$

\[grplassbasic\_spc\] **Group Lasso Regression with Squared Loss** - For the group lasso formulation $$\begin{aligned}
\min_{{\bm{x}}} \ \tfrac{1}{2} \|  A {\bm{x}}-{\bm{b}}\|_2^2 + \lambda \sum_{g=1}^G \sqrt{\rho_g} \|{\bm{x}}_g\|_2 \end{aligned}$$ we have the following screening rule for all groups $g$: $$\begin{aligned}
\|A_g^\top (A{\bm{x}}- {\bm{b}})\|_2 + \sqrt{2{G}({\bm{x}})}   {\left\lVertA_g\right\rVert_{\textsf{Fro}}} <\lambda \sqrt{\rho_g} \ \Rightarrow \ {\bm{x}}_g^\star = 0 \ .\end{aligned}$$

Group lasso regression is widely used in applications as an working example case of structured norm penalization. The framework of [@Ndiaye:2015wj] does not directly provide screening rules for the group lasso, due to the fact that they require $f$ to be partially separable over the groups as well as special structural requirement of the formulation, in contrast to our more general Theorem \[thm:smooth\_grp\_lasso\]. Similarly, [@Lee:2014wb] is also restricted to least-squares $f$ objective.

Illustrative Experiments {#sec:exp}
========================

While the contribution of our paper is on the theoretical generality and the collection of new screening applications, we will still briefly illustrate the performance of some of the proposed screening algorithms, for the classical examples of simplex constrained and $L_1$-constrained problems. We compare the fraction of active variables and the Wolfe-Gap function as optimization algorithm progress. We consider the optimization problem of the form $\underset{{\bm{x}}\in {\mathcal{B}}_{L_1}}\min \|A{\bm{x}}- {\bm{b}}\|_2^2$. ${\mathcal{B}}_{L_1}$ is a scaled $L_1$-ball with radius $35$. $A \in \mathbb{R}^{3000\times600}$ is a random Gaussian matrix and a noisy measurement ${\bm{b}}= A{\bm{x}}^\star$ where ${\bm{x}}^\star$ is a sparse vector of $+1$ and $-1$ with only $70$ non zeros entries. We solve the above optimization problem using the Frank-Wolfe algorithm (pair-wise variant, see [@LacosteJulien:2015wj]). Before putting this optimization problem into the solver we convert this problem into the barycentric representation which is $\underset{{\bm{x}}_{{\triangle}} \in {\triangle}}\min \|A_{{\triangle}}{\bm{x}}_{{\triangle}} - {\bm{b}}\|_2^2$. The relation between the transformed variable and original variable can be given by $A_{{\triangle}} = [A\,|-A]$ and ${\bm{x}}= [I_n\,| - I_n]{\bm{x}}_{{\triangle}}$. For more details see [@Jaggi:2014co].

  -------------------- ------------------ ---------------
      **Dataset/**      **No Screening**   **Screening**
   **No. of Samples**    **(Simplex)**     **(Simplex)**
     *Synth1* 5000          13.1 sec          11.7sec
     *Synth2* 10000         28.3 sec         23.1 sec
      *RCV1* 20242          18.6 min         13.5 min
    *news20B* 19996         33.4 min         25.2 min
  -------------------- ------------------ ---------------

  : Simplex-constrained screening, clock time[]{data-label="tab:tab1"}

  -------------------- ------------------------ ------------------------
      **Dataset/**         **No Screening**          **Screening**
   **No. of Samples**   **($\ell_1$-constr.)**   **($\ell_1$-constr.)**
     *Synth1* 5000               13.1                   12.2 sec
     *Synth2* 10000            28.3 sec                 24.7 sec
      *RCV1* 20242             18.6 min                 14.9 min
    *news20B* 19996            33.4 min                 27.1 min
  -------------------- ------------------------ ------------------------

  : $L_1$-constrained screening, clock time[]{data-label="tab:tab2"}

Now we apply our Theorems \[thm:l1\_smooth\_constrained\] and \[thm:simplex\_smooth\] on variable of ${\bm{x}}$ and ${\bm{x}}_{{\triangle}}$ respectively to screen, in order to compare the two alternative screening approaches on the same problem. Note that the Wolfe gap is identical in both parameterizations, for any ${\bm{x}}$. One important point to note here is that dimension of ${\bm{x}}_{{\triangle}}$ is the double of the dimension of ${\bm{x}}$, and any $L_1$-coordinate value $x_i$ is zero if and only if both “duplicate” variables $x_{{\triangle},i}$ and $x_{{\triangle},n+i}$ are zero, where $n$ is the dimensionality of ${\bm{x}}$.

Therefore, the simplex variant (with more variables) performs a more fine-grained variant of screening, where we can screen each of the sign patterns separately for each variable. In Fig \[fig:fig1\], the blue curve illustrates the screening efficiency for the $L_1$-constrained screening case, while the red curve illustrate simplex constrained screening. Our theorems \[thm:l1\_smooth\_constrained\] and \[thm:simplex\_smooth\] are well in line with the phenomena in Fig \[fig:fig1\]. For the $L_1$-constrained case, the screening starts relatively at later stage than simplex case due to the fact that in Equation , two out of three terms are absolute values of some quantity and hence it is very tough to compensate both of them by the third quantity, in order for the entire sum to become negative. Hence in the beginning this rule can often be ineffective. As algorithm progresses, the duality gap becomes smaller and screening starts but at the same time the gradient (and therefore gap) also starts to decay which brings the trade-off shown in the plot. For both variants, screening becomes slow towards the end.

We also report the time taken to reach a duality gap of $10^{-7}$ with both the approaches mentioned above (simplex constrained and $L_1$-constrained) on for different datasets. The first two datasets (*Synth1* and *Synth2*) are generated under the same setting described earlier but *Synth1* with 5000 samples and *Synth2* with 10000 samples. *RCV1* is a real world dataset having $20,242$ samples and $47,236$ data dimensions. *news20Binary* is also a real world dataset having $19,996$ entries and $ 1,355,191$ dimensions. Below in Tables \[tab:tab1\] and \[tab:tab2\], we describe the running time of the optimization methods to reach a duality gap threshold of $10^{-7}$ with or without screening. On *RCV1* dataset we try the feature learning with $L_1$-norm ball constraint of $200$ and on *news20Binary* we use $L_1$-norm ball constraint of $35$. In the case of *RCV1* and *news20Binary*, $A$ is the data matrix and ${\bm{b}}$ is the label of each instance in the dataset. From Tables \[tab:tab1\] and \[tab:tab2\] it is also evident that simplex screening rule is more tighter than the $L_1$-constrained screening rule.\

Discussion
==========

We have presented a unified way to derive screening rules for general constrained and penalized optimization problems. For both cases, our framework crucially utilizes the structure of piece-wise linearity of the problem at hand. For the constrained case, we showed that screening rules follow from the piece-wise linearity of the boundary of the constraint set.\
The crucial property is that at non-differentiable boundary points, the normal cone – i.e. the sub-differential of the indicator function of the constraint set – becomes a relatively large set. Under moderate assumptions on the objective function, we are able to guarantee that also the gradient of an optimal point must lie in this same cone region, leading to screening.\
On the other hand for penalized optimization problems, we are able to derive screening rules from either piece-wise linearity of the penalty function, or as well from exploiting piece-wise linearity of the constraint set arising from the dual (conjugate) of the penalty function.

#### Acknowledgements.

The authors would like to thank Julia Wysling, Rohit Babbar and Peter Bühlmann for valuable discussions.

Primal Dual Structure (Section \[sec:primaldual\]) {#app:primaldual}
==================================================

The relation of our primal and dual problems and is standard in convex analysis, and is a special case of the concept of Fenchel Duality. Using the combination with the linear map $A$ as in our case, the relationship is called *Fenchel-Rockafellar Duality*, see e.g. [@Borwein:2005ge Theorem 4.4.2] or [@Bauschke:2011ik Proposition 15.18]. For completeness, we here illustrate this correspondence with a self-contained derivation of the duality.

Starting with the original formulation , we introduce a helper variable vector ${\bm{v}}\in {\mathbb{R}}^d$ representing ${\bm{v}}=A{\bm{\alpha}}$. Then optimization problem  becomes: $$\label{eq:constrainedprimal}
\min_{{\bm{\alpha}}\in{\mathbb{R}}^n} \quad  f({\bm{v}}) + g( {\bm{\alpha}}) \quad \text{such that} \ {\bm{v}}=A{\bm{\alpha}}\, .$$ Introducing Lagrange multipliers ${\bm{w}}\in {\mathbb{R}}^d$, the Lagrangian is given by: $$L({\bm{\alpha}}, {\bm{v}}; {\bm{w}}) := f({\bm{v}}) +   g({\bm{\alpha}}) + {\bm{w}}^\top\left(A{\bm{\alpha}}-{\bm{v}}\right) \, .$$ The dual problem of follows by taking the infimum with respect to both ${\bm{\alpha}}$ and ${\bm{v}}$: $$\begin{aligned}
\inf_{{\bm{\alpha}}, {\bm{v}}} L({\bm{w}}, {\bm{\alpha}}, {\bm{v}}) & =   \inf_{{\bm{v}}} \left\{ f({\bm{v}}) - {\bm{w}}^\top {\bm{v}}\right\} + \inf_{{\bm{\alpha}}} \left\{ g({\bm{\alpha}}) +  {\bm{w}}^\top A{\bm{\alpha}}\right\} \notag \\
& =  - \sup_{{\bm{v}}} \left\{  {\bm{w}}^\top {\bm{v}}- f({\bm{v}}) \right\}- \sup_{{\bm{\alpha}}} \left\{(-{\bm{w}}^\top A){\bm{\alpha}}-  g({\bm{\alpha}}) \right\} \label{eq:optimlity_proof}\\
& = - f^*({\bm{w}}) - g^*(-A^\top {\bm{w}}) \label{eq:Lagrangian}\, .\end{aligned}$$

We change signs and turn the maximization of the dual problem into a minimization and thus we arrive at the dual formulation $\eqref{eq:dual}$ as claimed: $$\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] \, .$$

#### The Partially Separable Case.

For $g({\bm{x}})$ is separable, i.e. $g({\bm{x}}) = \sum_{i=1}^{n} g_i(x_i)$ for univariate functions $g_i:{\mathbb{R}}\rightarrow{\mathbb{R}}$ for $i\in[n]$, the primal-dual structure remains the separable. In this case, the conjugate of $g$ also separates as $g^*({\bm{y}}) = \sum_i g_i^*(y_i)$. Therefore, in terms of the the primal-dual structure and we obtain the separable special case and .

#### Optimality Conditions.

The first-order optimality conditions follow from the standard definition of the conjugate functions in the Fenchel dual problem, see also e.g. [@Borwein:2005ge; @Bauschke:2011ik].

The first-order optimality conditions for our pair of vectors ${\bm{w}}\in {\mathbb{R}}^d, {\bm{x}}\in {\mathbb{R}}^n$ in problems  and are given by equations , , and . The proof directly comes from equation by separately writing optimizing conditions for two expressions ${\bm{w}}^\top {\bm{v}}- f({\bm{v}})$ and $(-{\bm{w}}^\top A){\bm{\alpha}}-  g({\bm{\alpha}})$ in equation .

Crucially in the partially separable case, the optimality conditions and  become separable. Comparing the expressions and , we see that $g({\bm{x}}) = \sum_i g_i(x_i)$ and hence $$g^*({\bm{x}}) = \sum_i g_i^*(x_i)$$ Hence by applying and we obtain the separable optimality conditions and .

Duality Gap and Objective Function Properties {#app:duality_gap_certificates}
=============================================

Wolfe Gap as a Special Case of Duality Gap {#app:eq_fw_gd}
------------------------------------------

To see this as a special case of general duality gap of the problem formulation, we consider the constraint as indicator function of set ${\mathcal{C}}$ such that $g({\bm{x}}) = {\bm{\iota}}_{{\mathcal{C}}}({\bm{x}})$. Now from the definition of the Wolfe gap function $${G_{\mathcal{C}}}({\bm{x}}) := \underset{{\bm{y}}\in {\mathcal{C}}}{\max}\; (A{\bm{x}}-A{\bm{y}})^\top\partial f(A{\bm{x}})$$ Here $\partial f(A{\bm{x}})$ is an arbitrary subgradient of $f$ at the candidate position ${\bm{x}}$, and ${\bm{\iota}}_{{\mathcal{C}}}^*({\bm{y}}) := \sup_{{\bm{s}}\in {\mathcal{C}}}\langle {\bm{s}},{\bm{y}}\rangle$ is the support function of ${\mathcal{C}}$. Now writing the general duality gap ${G}({\bm{x}})$ as $$\begin{aligned}
{G}({\bm{x}}) &:= {\mathcal{O}_{\hspace{-1pt}A}}({\bm{x}}) + {\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}({\bm{x}}))  \\
&:=  f(A{\bm{x}}) + {\bm{\iota}}_{{\mathcal{C}}}({\bm{x}}) + f^*({\bm{w}}({\bm{x}}) ) + {\bm{\iota}}_{{\mathcal{C}}}^*(-(A^\top{\bm{w}}({\bm{x}})))\end{aligned}$$ the last term disappears since we assumed ${\bm{x}}\in{\mathcal{C}}$. Using the definition of the Fenchel conjugate, one has the Fenchel-Young inequality, i.e. $$f^*({\bm{w}}) := \max_{{\bm{u}}\in{\mathbb{R}}^d} {\bm{w}}^\top {\bm{u}}- f({\bm{u}}) \ \Rightarrow \ f^*({\bm{w}}) +  f({\bm{u}}) \ge {\bm{w}}^\top {\bm{u}}$$ The above holds with equality if ${\bm{w}}$ is chosen as a subgradient of $f$ at ${\bm{u}}=A{\bm{x}}$. Therefore, using our first-order optimality mapping ${\bm{w}}({\bm{x}}) := \partial f(A{\bm{x}})$, we have $${G}({\bm{x}}) = (A{\bm{x}})^\top \partial f(A{\bm{x}}) + {\bm{\iota}}_{{\mathcal{C}}}^*(-(A^\top{\bm{w}}({\bm{x}}))) = {G_{\mathcal{C}}}({\bm{x}})$$ This derivation is adapted from [@LacosteJulien:2013ue Appendix D].

Obtaining Information about the Optimal Points {#app:optimal_point}
----------------------------------------------

  \[lem:conjugates\]

1.  The conjugate of the indicator function ${\bm{\iota}}_{{\mathcal{C}}}$ of a set ${\mathcal{C}}\subset {\mathbb{R}}^n$ (not necessarily convex) is the support function of the set ${\mathcal{C}}$, that is $\quad {\bm{\iota}}_{{\mathcal{C}}}^*({\bm{x}}) = \sup_{{\bm{s}}\in{\mathcal{C}}} \langle {\bm{s}},{\bm{x}}\rangle$

2.  The conjugate of a norm is the indicator function of the unit ball of the dual norm.

[@Boyd:2004uz Example 3.24 and 3.26]

\[lem:smooth\_convex\_condition\] Assume that $f$ is a closed and convex function then $f^*$ is $\mu$-strongly convex with respect to a norm ${\left\lVert\cdot\right\rVert}$ if and only if $f$ is $1/\mu$-Lipschitz gradient with respect to dual norm ${\left\lVert\cdot\right\rVert}_*$.

[@Kakade:2009wh Theorem 3]

From the definition of $\mu$-strongly convex function, we know that $$\begin{aligned}
 f^*({\bm{w}}) &\ge f^*({\bm{w}}^\star) + ({\bm{w}}-{\bm{w}}^\star)^\top\nabla f^*({\bm{w}}^\star) + \frac{\mu}{2} \|{\bm{w}}- {\bm{w}}^\star\|_2^2\\
 &\ge f^*({\bm{w}}^\star) + \frac{\mu}{2} \|{\bm{w}}- {\bm{w}}^\star\|_2^2 \end{aligned}$$ The first inequality follows directly by using the first order optimality condition for ${\bm{w}}^\star$ being optimal. For any optimal point ${\bm{w}}^\star$ and another feasible point ${\bm{w}}$, $$({\bm{w}}-{\bm{w}}^\star)^\top\nabla f^*({\bm{w}}^\star) \ge 0.$$\
Hence,$ \qquad{\left\lVert{\bm{w}}^\star - {\bm{w}}\right\rVert}_2^2 \le \frac{2}{\mu}(f^*({\bm{w}})-f^*({\bm{w}}^\star))$

This statement directly comes from and the definition of the duality gap. By definition we know that the true optimum values ${\mathcal{O}_{\hspace{-1pt}A}}({\bm{x}}^*)$ and $-{\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}^*)$ respectively for primal and dual formulation will always lie within the duality gap which implies $${G}({\bm{x}})  \ge {\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}) - {\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}^\star)$$ By equation , we know that $ \ \qquad {\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}) = f^*({\bm{w}}) + g^*(-A^\top{\bm{w}}^\star)$\
Now since $f^*$ is $\mu$-strongly convex function and $g^*$ is convex hence, $$\begin{aligned}
f^*({\bm{w}}) \ge f^*({\bm{w}}^\star) + \nabla f^*({\bm{w}}^\star)^\top({\bm{w}}- {\bm{w}}^\star) + \frac{\mu}{2}{\left\lVert{\bm{w}}- {\bm{w}}^\star\right\rVert}_2^2 \label{eq:f_star_strng_convex} \\
g^*(-A^\top {\bm{w}})\ge g^*(-A^\top{\bm{w}}^\star) + \nabla g^*(-A^\top {\bm{w}}^\star)^\top(-A^\top{\bm{w}}+ A^\top{\bm{w}}^\star)  \label{eq:g_star_strng_convex}  \end{aligned}$$

Hence by adding equation and , we get $${\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}) \ge {\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}^\star) + (\nabla f^*({\bm{w}}^\star) -A \nabla g^*(-A^\top{\bm{w}}^\star)) ^\top({\bm{w}}- {\bm{w}}^\star)+ \frac{\mu}{2}{\left\lVert{\bm{w}}- {\bm{w}}^\star\right\rVert}_2^2$$ $$\Rightarrow {\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}) \ge {\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}^\star) + \nabla {\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}^\star)^\top({\bm{w}}- {\bm{w}}^\star)+ \frac{\mu}{2}{\left\lVert{\bm{w}}- {\bm{w}}^\star\right\rVert}_2^2$$ At optimal point ${\bm{w}}^\star$, $\nabla  {\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}^\star)^\top({\bm{w}}- {\bm{w}}^\star) \ge 0$.\
Hence, $${G}({\bm{x}})  \ge {\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}) - {\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}^\star) \ge \frac{\mu}{2}{\left\lVert{\bm{w}}- {\bm{w}}^\star\right\rVert}_2^2$$

From the definition of $\mu$-strong convexity of $f$ and using optimality condition, $$\begin{aligned}
\mu{\left\lVertA{\bm{x}}-A{\bm{x}}^\star\right\rVert}^2 & \le & (A{\bm{x}}-A{\bm{x}}^\star)^\top(\nabla f(A{\bm{x}})-\nabla f(A{\bm{x}}^\star)) \label{eq:definition_strng_convex}\\
& \le & (A{\bm{x}}-A{\bm{x}}^\star)^\top\nabla f(A{\bm{x}}) \label{eq:optimality_cond_f}\\
& \le & {G_{\mathcal{C}}}({\bm{x}})\label{eq:definition_wolfe_gap}\end{aligned}$$ Equation comes from the definition of $\mu$-strong convexity.\
Equation is first order optimality condition for ${\bm{x}}^\star$ being optimal which implies $$(A{\bm{x}}-A{\bm{x}}^\star)^\top\nabla f(A{\bm{x}}^\star) \ge 0$$ The inequality follows by the definition of the gap function given in .

This comes by definition of $L$-smooth functions and Lemma \[lem:FWgaprestriction\]. From the definition, $$\begin{aligned}
{\left\lVert\nabla f(A{\bm{x}})-\nabla f(A{\bm{x}}^\star)\right\rVert} &\le L {\left\lVertA{\bm{x}}-A{\bm{x}}^\star\right\rVert} \\
& \le  \frac{L}{\sqrt{\mu}}\sqrt{{G_{\mathcal{C}}}({\bm{x}})}\end{aligned}$$ Second inequality directly comes from Lemma \[lem:FWgaprestriction\].

Screening on Constrained Problems {#app:constrained}
=================================

\[lem:subgrad\_ind\] Let ${\mathcal{C}}$ be a convex set, and ${\bm{\iota}}_{\mathcal{C}}$ be its indicator function, then

1.  For ${\bm{x}}\notin {\mathcal{C}}$, $\partial {\bm{\iota}}_{\mathcal{C}}({\bm{x}}) = \emptyset$

2.  For ${\bm{x}}\in {\mathcal{C}}$, we have that ${\bm{w}}\in  \partial {\bm{\iota}}_{\mathcal{C}}({\bm{x}})$ if $ {\bm{w}}^\top({\bm{z}}-{\bm{x}}) \le 0 \quad \forall {\bm{z}}\in {\mathcal{C}}$

Let ${\mathcal{C}}\subseteq {\mathbb{R}}^n$ be a closed convex set. Then subgradient of indicator function ${\bm{\iota}}_{{\mathcal{C}}}({\bm{x}})$ at ${\bm{x}}$ will be vectors ${\bm{u}}$ which satisfy $$\begin{aligned}
&{\bm{\iota}}_{{\mathcal{C}}}({\bm{z}}) \ge {\bm{\iota}}_{{\mathcal{C}}}({\bm{x}}) + {\bm{u}}^\top({\bm{z}}- {\bm{x}}) \quad \forall {\bm{z}}\in \operatorname{dom}({\bm{\iota}}_{{\mathcal{C}}}) \notag \\
&\Rightarrow {\bm{\iota}}_{{\mathcal{C}}}({\bm{z}}) \ge {\bm{\iota}}_{{\mathcal{C}}}({\bm{x}}) + {\bm{u}}^\top({\bm{z}}- {\bm{x}}) \quad \forall {\bm{z}}\in {\mathbb{R}}^n \label{app:eq:sub_diff}\end{aligned}$$ If $\operatorname{int}({\mathcal{C}})$ represents the interior of the set ${\mathcal{C}}$ such that it contains $n$-dimensional ball of radius $r >0$, and $\mathop{Bd}({\mathcal{C}})$ represents boundary of the set ${\mathcal{C}}$. Now we have to assume various cases for proving Lemma \[lem:subgrad\_ind\].

1.  We evaluate Equation when ${\bm{x}}\in \operatorname{int}({\mathcal{C}})$. Equation becomes $${\bm{\iota}}_{{\mathcal{C}}}({\bm{z}})  \ge {\bm{u}}^\top({\bm{z}}- {\bm{x}}) \quad \forall {\bm{z}}\in {\mathbb{R}}^n$$ Now since the above equation is satisfied for all ${\bm{z}}\in {\mathbb{R}}^n$ , we assume ${\bm{z}}\in \operatorname{int}({\mathcal{C}})$ such that $({\bm{z}}- {\bm{x}})$ can be anywhere in the ball. Hence ${\bm{u}}$ needs to be $0$ in this case.

2.  In this case we assume ${\bm{x}}\in \mathop{Bd}({\mathcal{C}})$. That gives $${\bm{\iota}}_{{\mathcal{C}}}({\bm{z}})  \ge {\bm{u}}^\top({\bm{z}}- {\bm{x}}) \quad \forall {\bm{z}}\in {\mathbb{R}}^n$$ If we take ${\bm{z}}\in {\mathcal{C}}$ then ${\bm{u}}$ satisfies ${\bm{u}}^\top({\bm{z}}-{\bm{x}}) \le 0 \quad \forall {\bm{z}}\in {\mathcal{C}}$\
    If ${\bm{z}}\not\in  {\mathcal{C}}$ then ${\bm{u}}$ can take all the value. Hence taking intersection, ${\bm{u}}$ satisfies $${\bm{u}}^\top({\bm{z}}-{\bm{x}}) \le 0 \quad \forall {\bm{z}}\in {\mathcal{C}}$$

3.  When we assume ${\bm{x}}\not \in {\mathcal{C}}$, we get $${\bm{\iota}}_{{\mathcal{C}}}({\bm{z}}) \ge +\infty + {\bm{u}}^\top({\bm{z}}- {\bm{x}}) \quad \forall {\bm{z}}\in {\mathbb{R}}^n$$ If we again take ${\bm{z}}\in {\mathcal{C}}$ then no finite ${\bm{u}}$ can satisfy the equation ${\bm{\iota}}_{{\mathcal{C}}}({\bm{z}}) \ge +\infty + {\bm{u}}^\top({\bm{z}}- {\bm{x}}) \quad \forall {\bm{z}}\in {\mathcal{C}}$ because ${\bm{\iota}}_{{\mathcal{C}}}({\bm{z}}) = 0 \ \textrm{ if} \ \ {\bm{z}}\in {\mathcal{C}}$.\
    And if $ {\bm{z}}\not \in {\mathcal{C}}\ \Rightarrow\  {\bm{\iota}}_{{\mathcal{C}}}({\bm{z}}) = +\infty $ then again nothing can be said about the vector ${\bm{u}}$. Hence by convention it is assumed that ${\bm{x}}\not \in {\mathcal{C}}\ \Rightarrow\  {\bm{u}}\in \emptyset $

By the above arguments we conclude that,

1.  For ${\bm{x}}\notin {\mathcal{C}}$, $\partial {\bm{\iota}}_{\mathcal{C}}({\bm{x}}) = \emptyset$

2.  For ${\bm{x}}\in {\mathcal{C}}$, we have that ${\bm{w}}\in  \partial {\bm{\iota}}_{\mathcal{C}}({\bm{x}})$ if $ {\bm{w}}^\top({\bm{z}}-{\bm{x}}) \le 0 \quad \forall {\bm{z}}\in {\mathcal{C}}$

Hence the claim made in Lemma \[lem:subgrad\_ind\] is proved.

 From Lemma \[lem:subgrad\_ind\], we know the expression for subgradient of the indication function ${\bm{\iota}}_{{\mathcal{C}}}$ $$\begin{aligned}
 \partial g({\bm{x}}^\star)  =& \left\{ {\bm{s}}\ |\   \forall {\bm{z}}\in {\mathcal{C}}\; \ {\bm{s}}^\top({\bm{z}}- {\bm{x}}^\star) \le 0  \quad    \right\} \notag \\
  =& \left\{ {\bm{s}}\ |\   \forall {\bm{z}}\in {\mathcal{C}}\; \ {\bm{s}}^\top {\bm{z}}\le {\bm{s}}^\top {\bm{x}}^\star   \quad     \right\}  \label{eq:subgrad_simplex}\end{aligned}$$ Now, by the optimality condition , $-A^\top {\bm{w}}^\star \in \ \partial g({\bm{x}}^\star)$ and since this holds, hence $-A^\top {\bm{w}}^\star$ should satisfy the required constrained which is needed to be in the set of subgradients of $\partial g({\bm{x}}^\star)$ according to conditions in equation . Hence, $$\begin{aligned}
 &\ (-A^\top {\bm{w}}^\star)^\top {\bm{z}}\le (-A^\top {\bm{w}}^\star)^\top {\bm{x}}^\star   \quad  \forall {\bm{z}}\in {\mathcal{C}}\\
\Rightarrow & \ (A^\top {\bm{w}}^\star)^\top {\bm{x}}^\star  \le (A^\top {\bm{w}}^\star)^\top {\bm{z}}\quad     \forall {\bm{z}}{\mathcal{C}}\\
\Rightarrow  & \  (A^\top {\bm{w}}^\star)^\top {\bm{x}}^\star  \le \underset{z}{\min}(A^\top {\bm{w}}^\star)^\top {\bm{z}}\quad     s.t \ \ \ {\bm{z}}\in {\mathcal{C}}\\
\Rightarrow & \ (A {\bm{x}}^\star )^\top {\bm{w}}^\star  \leq  \underset{{\bm{z}}\in {\mathcal{C}}} {\min}(A{\bm{z}})^\top {\bm{w}}^\star \quad     s.t \ \ \ {\bm{z}}\in {\mathcal{C}}\end{aligned}$$ Since ${\bm{x}}^\star$ is a feasible point hence $(A {\bm{x}}^\star )^\top {\bm{w}}^\star  = \underset{{\bm{z}}\in {\mathcal{C}}} {\min}(A{\bm{z}})^\top {\bm{w}}^\star \quad     s.t \ \ \ {\bm{x}}^\star,{\bm{z}}\in {\mathcal{C}}$.

Screening on Simplex Constrained Problems (Section \[subsec:simplex\_screening\]) {#app:simplex_screening}
---------------------------------------------------------------------------------

#### General Simplex Constrained Screening

In the simplex case, we have $g({\bm{x}})={\bm{\iota}}_{\triangle}({\bm{x}})$ and by Lemma \[lem:subgrad\_ind\] $$\begin{aligned}
 \partial g({\bm{x}}^\star)  =& \left\{ {\bm{s}}\ |\   \forall {\bm{z}}\in {\triangle}\; \ {\bm{s}}^\top({\bm{z}}- {\bm{x}}^\star) \le 0  \quad    \right\} \notag \\
  =& \left\{ {\bm{s}}\ |\   \forall {\bm{z}}\in {\triangle}\; \ {\bm{s}}^\top {\bm{z}}\le {\bm{s}}^\top {\bm{x}}^\star   \quad     \right\}  \label{eq:subgrad_simplex}\end{aligned}$$ Now, by the optimality condition , $-A^\top {\bm{w}}^\star \in \ \partial g({\bm{x}}^\star)$ and since this holds, hence $-A^\top {\bm{w}}^\star$ should satisfy the required constrained which is needed to be in the set of subgradients of $\partial g({\bm{x}}^\star)$ according to conditions in equation . Hence, $$\begin{aligned}
 &\ (-A^\top {\bm{w}}^\star)^\top {\bm{z}}\le (-A^\top {\bm{w}}^\star)^\top {\bm{x}}^\star   \quad  \forall {\bm{z}}\in {\triangle}\\
\Rightarrow & \ (A^\top {\bm{w}}^\star)^\top {\bm{x}}^\star  \le (A^\top {\bm{w}}^\star)^\top {\bm{z}}\quad     \forall {\bm{z}}\in {\triangle}\\
\Rightarrow  & \  (A^\top {\bm{w}}^\star)^\top {\bm{x}}^\star  \le \underset{z}{\min}(A^\top {\bm{w}}^\star)^\top {\bm{z}}\quad     s.t \ \ \ {\bm{z}}\in {\triangle}\ \\
\Rightarrow & \ (A^\top {\bm{w}}^\star)^\top {\bm{x}}^\star  \le \underset{i}{\min} \ {\bm{a}}_i^\top {\bm{w}}^\star \ \label{min_explain_simplex}  \\
\Rightarrow & \ (A{\bm{x}}^\star)^\top{\bm{w}}^\star  \le \underset{i}{\min} \ {\bm{a}}_i^\top {\bm{w}}^\star \  \\
\Rightarrow & \ (A{\bm{x}}^\star)^\top{\bm{w}}^\star  = \underset{i}{\min} \ {\bm{a}}_i^\top {\bm{w}}^\star \  \label{last_line_simplex}\end{aligned}$$

Equation is due to the fact that ${\bm{z}}$ lie in the simplex, hence minimum value of $(A^\top {\bm{w}}^\star)^\top {\bm{z}}$ is $\underset{i}{\min} \ {\bm{a}}_i^\top {\bm{w}}^\star$ and equation also comes from the same fact that ${\bm{x}}^\star$ lie in the simplex and hence $(A{\bm{x}}^\star)^\top{\bm{w}}^\star$ can not be smaller than $\underset{i}{\min} \ {\bm{a}}_i^\top {\bm{w}}^\star$. That implies these two quantities need to be equal and all the $i$’s where this equality doesn’t hold refers to $x_i^\star = 0$ for all such $i$’s. $$\begin{aligned}
\ {\bm{a}}_i^\top {\bm{w}}^\star > \ (A^\top {\bm{w}}^\star)^\top {\bm{x}}^\star  \ \Rightarrow\  x_i = 0 \\
\ ({\bm{a}}_i - A{\bm{x}}^\star)^\top {\bm{w}}^\star > 0 \ \Rightarrow\  x_i = 0\end{aligned}$$

From the optimality condition , we have ${\bm{w}}^\star = \nabla f(A{\bm{x}}^\star)$ since $f$ is differentiable. Hence, $$\begin{aligned}
({\bm{a}}_i - A{\bm{x}}^\star)^\top {\bm{w}}^\star  &= ({\bm{a}}_i - A{\bm{x}}^\star)^\top\nabla f(A{\bm{x}}^\star) \qquad \qquad \qquad \qquad \qquad \qquad\\
&= ({\bm{a}}_i - A{\bm{x}}^\star +  A{\bm{x}}-  A{\bm{x}})^\top\nabla f(A{\bm{x}}^\star) \\
&= ({\bm{a}}_i -  A{\bm{x}})^\top\nabla f(A{\bm{x}}^\star) + (A{\bm{x}}-A{\bm{x}}^\star )^\top\nabla f(A{\bm{x}}^\star) \\ 
&\ge ({\bm{a}}_i -  A{\bm{x}})^\top\nabla f(A{\bm{x}}^\star) \quad \{\textrm{From the optimality of } f(A{\bm{x}})\} \label{eq:optmilatity_Ax} \\
&=({\bm{a}}_i -  A{\bm{x}})^\top\nabla f(A{\bm{x}}) - ({\bm{a}}_i -  A{\bm{x}})^\top(\nabla f(A{\bm{x}}) - \nabla f(A{\bm{x}}^\star))\\
&\ge ({\bm{a}}_i -  A{\bm{x}})^\top\nabla f(A{\bm{x}}) - {\left\lVert{\bm{a}}_i -  A{\bm{x}}\right\rVert} {\left\lVert\nabla f(A{\bm{x}}) - \nabla f(A{\bm{x}}^\star)\right\rVert}\\
&\ge ({\bm{a}}_i -  A{\bm{x}})^\top\nabla f(A{\bm{x}}) - L\sqrt{\frac{{G_{\mathcal{C}}}({\bm{x}})}{\mu}}{\left\lVert{\bm{a}}_i-A{\bm{x}}\right\rVert} \label{lastline}\end{aligned}$$ Eq. comes from the fact that at the optimal point ${\bm{x}}^\star$, the inequality $(A{\bm{x}}-A{\bm{x}}^\star )^\top\nabla f(A{\bm{x}}^\star) \ge 0$ holds $\forall \ {\bm{x}}$. Equation comes from Corollary \[cor:restric:smooth\] for smooth function $f$ over a constrained set ${\mathcal{C}}$.\
Hence from Theorem \[thm:simplexcondition\], we obtain the screening rule $$({\bm{a}}_i -A{\bm{x}})^\top\nabla f(A{\bm{x}}) > L\sqrt{\frac{{G_{\mathcal{C}}}({\bm{x}})}{\mu}}{\left\lVert{\bm{a}}_i-A{\bm{x}}\right\rVert} \ \Rightarrow\  x_i^\star=0$$

#### Screening for Squared Hinge Loss SVM.

Theorem \[thm:simplex\_smooth\] is directly applicable to problems of the form . The objective function $f({\bm{y}}) = f(A{\bm{x}})= \frac{1}{2}{\bm{x}}^\top A^\top A{\bm{x}}$ is strongly convex with parameter $\mu=1$. Also the derivative $\nabla f$ is Lipschitz-continuous with parameter $L=1$. To obtain an upper bound on the distance between any approximate solution and the optimal solution $\|A{\bm{x}}- A{\bm{x}}^\star\|$, we employ Lemma \[lem:FWgaprestriction\]. Since the constrained of the optimization problem is unit simplex and hence the value of Wolfe gap function ${G_{\mathcal{C}}}({\bm{x}}) := \max_{{\bm{y}}\in {\mathcal{C}}}\; (A{\bm{x}}-A{\bm{y}})^\top\nabla f(A{\bm{x}})$ as defined in Section \[sec:duality\_gap\_certificates\] will be attained on one of the vertices. So, ${G_{\mathcal{C}}}({\bm{x}})=\max_{i \in 1\dots m}\; (A{\bm{x}}-{\bm{a}}_i)^\top A{\bm{x}}$. Finally, Theorem \[thm:simplex\_smooth\] gives us the screening rule for squared hinge loss SVM: $$({\bm{a}}_i-A{\bm{x}})^\top A{\bm{x}}> \sqrt{\max_{i \in 1\dots m}\; (A{\bm{x}}-{\bm{a}}_i)^\top A{\bm{x}}}{\left\lVert{\bm{a}}_i-A{\bm{x}}\right\rVert} \ \Rightarrow\  x_i^\star = 0$$

#### Screening on Minimum Enclosing Ball.

**\
Minimum Enclosing Ball -** Given a set of $n$ points, ${\bm{a}}_1$ to ${\bm{a}}_n$ in ${\mathbb{R}}^d$, the minimum enclosing ball is defined as the smallest ball $B_{{\bm{c}},r}$ with center ${\bm{c}}$ and radius $r$, i.e.: $B_{{\bm{c}},r} := \{{\bm{x}}\in {\mathbb{R}}^d \ |\  {\left\lVert{\bm{c}}-{\bm{x}}\right\rVert} \le r\}$, such that all points ${\bm{a}}_i$ lie in its interior. In this set-up, screening means to identify points ${\bm{a}}_i$ lying in the interior of the optimal ball $B_{{\bm{c}}^\star,r^\star}$. Removing those points from the problem does not change the optimal ball.

The minimum enclosing ball problem can be formulated as an optimization problem of the form given in Equation : $$\begin{aligned}
& \underset{{\bm{c}},r}{\min} \ \ \ r^2  \quad \text{s.t.} {\left\lVert{\bm{c}}-{\bm{a}}_i\right\rVert}^2_2\le r^2 \quad \forall i \in [n]\end{aligned}$$ As we have seen, the dual formulation can be written in the form of Equation as given in [@Matousek:2007ub Chapter 8.7]: $$\begin{aligned}
 \underset{{\bm{x}}}{\min} \ \ {\bm{x}}^\top A^\top A{\bm{x}}- \sum_{j=1}^{p} {\bm{a}}_j^\top{\bm{a}}_jx_j \quad \text{s.t. }  {\bm{x}}\in {\triangle}\end{aligned}$$ Now the function ${\bm{x}}^\top A^\top A{\bm{x}}- \sum_{j=1}^{p} {\bm{a}}_j^\top{\bm{a}}_jx_j$ is strongly convex in $A{\bm{x}}$ with parameter $\mu=2$. Since the constrained of the optimization problem is unit simplex and hence the value of the Wolfe gap function ${G_{\mathcal{C}}}({\bm{x}}) := \underset{{\bm{y}}\in {\mathcal{C}}}{\max}\; (A{\bm{x}}-A{\bm{y}})^\top\nabla f(A{\bm{x}})$ as defined in Section \[sec:duality\_gap\_certificates\] will be attained at one of the vertices of unit simplex. Hence Corollary \[cor:restric:smooth\] gives ${G_{\mathcal{C}}}({\bm{x}})= \sqrt{\frac{1}{2}\max_{i}({\bm{x}}-{\bm{e}}_i)^\top (2A^\top A{\bm{x}}+{\bm{c}}')}$. Now applying the findings of Theorem \[thm:simplex\_smooth\], we get a sufficient condition for ${\bm{a}}_i$ to be non-influential, i.e. ${\bm{a}}_i$ lies in the interior of the MEB. But before that we will simplify the left hand side of the theorem \[thm:simplex\_smooth\] a bit. $({\bm{a}}_i - A{\bm{x}})^\top \nabla f(A{\bm{x}})$ can we written as $(\bm{e}_i - {\bm{x}})^\top A^\top \nabla f(A{\bm{x}})$. Hence we get our result claimed in Corollary \[cor:min\_enclosing\_ball\]. $$\label{ballcor}
({\bm{e}}_i-{\bm{x}})^\top (2A^\top A{\bm{x}}+{\bm{c}}') > 2\sqrt{\tfrac{1}{2}\underset{j}{\text{max}}({\bm{x}}-{\bm{e}}_i)^\top (2A^\top A{\bm{x}}+{\bm{c}}')}{\left\lVert{\bm{a}}_i-A{\bm{x}}\right\rVert} \ \Rightarrow\  x_i^\star = 0$$ That means ${\bm{a}}_i$ is non influential.

Screening on $L_1$-ball Constrained Problems {#app:l1ball_screening}
--------------------------------------------

In the constrained Lasso case, we have $g({\bm{x}})={\bm{\iota}}_{{\mathcal{B}}_{L_1}}({\bm{x}})$ and by Lemma \[lem:subgrad\_ind\] $$\begin{aligned}
 \partial g({\bm{x}}^\star)  =& \left\{ {\bm{s}}\ |\   \forall {\bm{z}}\in {{\mathcal{B}}_{L_1}} \; \ {\bm{s}}^\top({\bm{z}}-{\bm{x}}^\star) \le 0  \quad  \right\} \notag \\
  =& \left\{ {\bm{s}}\ |\   \forall {\bm{z}}\in {{\mathcal{B}}_{L_1}} \; \ {\bm{s}}^\top {\bm{z}}\le {\bm{s}}^\top {\bm{x}}^\star   \quad      \right\} \label{eq:subgrad_l1_ball}\end{aligned}$$ Now, by the optimality condition , $-A^\top {\bm{w}}^\star \in \ \partial g({\bm{x}}^\star)$ and since this holds, hence $-A^\top {\bm{w}}^\star$ should satisfy the required constrained which is needed to be in the set of subgradients of $\partial g({\bm{x}}^\star)$ according to conditions in equation . Hence, $$\begin{aligned}
 &\ (-A^\top {\bm{w}}^\star)^\top {\bm{z}}\le (-A^\top {\bm{w}}^\star)^\top {\bm{x}}^\star   \quad  \forall {\bm{z}}\in {{\mathcal{B}}_{L_1}}     \\
\Rightarrow & \ (A^\top {\bm{w}}^\star)^\top {\bm{x}}^\star  \le (A^\top {\bm{w}}^\star)^\top {\bm{z}}\quad     \forall {\bm{z}}\in {{\mathcal{B}}_{L_1}} \\
\Rightarrow  & \  (A^\top {\bm{w}}^\star)^\top {\bm{x}}^\star  \le \underset{z}{\min}(A^\top {\bm{w}}^\star)^\top {\bm{z}}\quad     s.t \ \ \ {\bm{z}}\in {{\mathcal{B}}_{L_1}} \ \\
\Rightarrow & \ \ (A^\top {\bm{w}}^\star)^\top {\bm{x}}^\star  \le - \underset{i}{\max} \ {\left\lvert{\bm{a}}_i^\top {\bm{w}}^\star\right\rvert} \ \label{min_explain_l1}  \\
\Rightarrow & \ (A{\bm{x}}^\star)^\top {\bm{w}}^\star \le - \underset{i}{\max} \ {\left\lvert{\bm{a}}_i^\top {\bm{w}}^\star\right\rvert} \\
\Rightarrow & \ (A{\bm{x}}^\star)^\top {\bm{w}}^\star  = - \underset{i}{\max} \ {\left\lvert{\bm{a}}_i^\top {\bm{w}}^\star\right\rvert} \  \label{last_line_l1}\end{aligned}$$ Equation is due to the fact that ${\bm{z}}$ lie in the $L_1$-ball and hence minimum value of $(A^\top {\bm{w}}^\star)^\top {\bm{z}}$ is $ - \underset{i}{\max} \ {\left\lvert{\bm{a}}_i^\top {\bm{w}}^\star\right\rvert}$ and Equation also comes from the same fact that ${\bm{x}}^\star$ lie in the $L_1$-ball and hence $(A{\bm{x}}^\star)^\top{\bm{w}}^\star$ can not be smaller than $- \underset{i}{\max} \ {\left\lvert{\bm{a}}_i^\top {\bm{w}}^\star\right\rvert} $. That implies these two quantities need to be equal and all the $i$’s where this equality doesn’t hold refers to $x_i^\star = 0$ for all such $i$’s. Hence whenever these two quantities are not equal this holds: $$\begin{aligned}
-  {\left\lvert{\bm{a}}_i^\top {\bm{w}}^\star\right\rvert} > (A{\bm{x}}^\star)^\top {\bm{w}}^\star  \ \Rightarrow\  x_i^\star  = 0\\
\ \Rightarrow\  {\left\lvert{\bm{a}}_i^\top {\bm{w}}^\star\right\rvert}  + (A{\bm{x}}^\star)^\top {\bm{w}}^\star <0 \ \Rightarrow\  x_i^\star  = 0\end{aligned}$$

Using optimality condition , we know that $ {\bm{w}}^\star \in \partial f(A{\bm{x}})$ $$\begin{aligned}
 {\left\lvert{\bm{a}}_i^\top {\bm{w}}^\star\right\rvert}  + (A{\bm{x}}^\star)^\top {\bm{w}}^\star &= {\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}}^\star)\right\rvert}  + (A{\bm{x}}^\star)^\top \nabla f(A{\bm{x}}^\star) \quad\\ 
&= {\left\lvert{\bm{a}}_i^\top ( \nabla f(A{\bm{x}}) - \nabla f(A{\bm{x}}) + \nabla f(A{\bm{x}}^\star))\right\rvert}  + (A{\bm{x}}^\star)^\top \nabla f(A{\bm{x}}^\star)\\ 
&\le {\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} + {\left\lvert{\bm{a}}_i^\top ( \nabla f(A{\bm{x}}^\star) - \nabla f(A{\bm{x}}))\right\rvert} \notag\\
& \qquad \qquad \qquad +(A{\bm{x}}^\star - A{\bm{x}}+A{\bm{x}})^\top \nabla f(A{\bm{x}}^\star)\\ &= {\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} + {\left\lvert{\bm{a}}_i^\top ( \nabla f(A{\bm{x}}^\star) - \nabla f(A{\bm{x}}))\right\rvert} \notag\\
& \qquad \qquad \qquad + (A{\bm{x}}) ^\top \nabla f(A{\bm{x}}^\star) - ( A{\bm{x}}- A{\bm{x}}^\star)^\top \nabla f(A{\bm{x}}^\star) \label{eq:optimal_x_star_fAx}\\
&\le {\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} + {\left\lvert{\bm{a}}_i^\top ( \nabla f(A{\bm{x}}^\star) - \nabla f(A{\bm{x}}))\right\rvert}+(A{\bm{x}})^\top \nabla f(A{\bm{x}}^\star) \label{eq_l1_proof_opt_f}\\ &\le {\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} + {\left\lvert{\bm{a}}_i^\top ( \nabla f(A{\bm{x}}^\star) - \nabla f(A{\bm{x}}))\right\rvert}\notag \\
& \qquad \qquad \qquad +(A{\bm{x}})^\top (\nabla f(A{\bm{x}}^\star) - \nabla f(A{\bm{x}}) +  \nabla f(A{\bm{x}}))\\ 
&\le {\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} + {\left\lvert{\bm{a}}_i^\top ( \nabla f(A{\bm{x}}^\star) - \nabla f(A{\bm{x}}))\right\rvert} + (A{\bm{x}})^\top\nabla f(A{\bm{x}}) \notag \\
& \qquad \qquad \qquad +(A{\bm{x}})^\top (\nabla f(A{\bm{x}}^\star) - \nabla f(A{\bm{x}}))\\ 
&\le {\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} + (A{\bm{x}})^\top \nabla f(A{\bm{x}}) + L({\left\lVert{\bm{a}}_i\right\rVert} + {\left\lVertA{\bm{x}}\right\rVert})\sqrt{\frac{{G_{\mathcal{C}}}({\bm{x}})}{\mu}}\label{eq_l1_proof_last} \end{aligned}$$ Eq. comes from the fact that at the optimal point ${\bm{x}}^\star$, the inequality $(A{\bm{x}}-A{\bm{x}}^\star )^\top\nabla f(A{\bm{x}}^\star) \ge 0$ holds $\forall {\bm{x}}$. Hence using Theorem \[thm:l1\_constrained\_screening\], Lemma \[lem:FWgaprestriction\] and Corollary \[cor:restric:smooth\], we get the screening rule for $L_1$ constrained as whenever,\
${\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} + (A{\bm{x}})^\top \nabla f(A{\bm{x}}) + L({\left\lVert{\bm{a}}_i\right\rVert} + {\left\lVertA{\bm{x}}\right\rVert})\sqrt{\frac{{G_{\mathcal{C}}}({\bm{x}})}{\mu}} < 0 \ \Rightarrow\  {\bm{x}}_i^\star = 0$

Screening on Elastic Net Constrained Problems {#app:elastic_net_screening}
---------------------------------------------

Formulation : $$\begin{aligned}
&\min_{{\bm{x}}} f(A{\bm{x}}) \\
s.t \ \ & \alpha \|{\bm{x}}\|_1 + \frac{(1 - \alpha) }{2} \|{\bm{x}}\|_2^2 \leq 1 \\
& \Rightarrow \alpha \sum_{i=1}^n |{\bm{x}}_i| + \frac{(1 - \alpha) }{2} \sum_{i = 1}^n {\bm{x}}_i^2 \leq 1\end{aligned}$$ In the elastic net constrained case, we have $g({\bm{x}})={\bm{\iota}}_{{\mathcal{B}}_{L_E}}({\bm{x}})$ where ${\bm{\iota}}_{{\mathcal{B}}_{L_E}}$ is elastic net norm ball. That implies $${\bm{x}}\in {\bm{\iota}}_{{\mathcal{B}}_{L_E}} \ \ : \ \ \alpha \|{\bm{x}}\|_1 + (1-\alpha) \|{\bm{x}}\|_2^2 \leq 1$$ From the subgradient of indicator function and optimality condition for $A$ and $B$ framework $$\begin{aligned}
 \partial g({\bm{x}}^\star)  =& \left\{ {\bm{s}}\ |\   \forall {\bm{z}}\in {{\mathcal{B}}_{L_1}} \; \ {\bm{s}}^\top({\bm{z}}-{\bm{x}}^\star) \le 0  \quad  \right\} \notag \\
  =& \left\{ {\bm{s}}\ |\   \forall {\bm{z}}\in {{\mathcal{B}}_{L_1}} \; \ {\bm{s}}^\top {\bm{z}}\le {\bm{s}}^\top {\bm{x}}^\star   \quad      \right\} \label{eq:subgrad_l1_ball}\end{aligned}$$ Now, by the optimality condition , $-A^\top {\bm{w}}^\star \in \ \partial g({\bm{x}}^\star)$ and since this holds, hence $-A^\top {\bm{w}}^\star$ should satisfy the required constrained which is needed to be in the set of subgradients of $\partial g({\bm{x}}^\star)$ according to conditions in equation . Hence,

$$\begin{aligned}
 &\ (-A^\top {\bm{w}}^\star)^\top {\bm{z}}\le (-A^\top {\bm{w}}^\star)^\top {\bm{x}}^\star   \quad  \forall {\bm{z}}\in {{\mathcal{B}}_{L_E}}     \\
\Rightarrow & \ (A^\top {\bm{w}}^\star)^\top {\bm{x}}^\star  \le (A^\top {\bm{w}}^\star)^\top {\bm{z}}\quad     \forall {\bm{z}}\in {{\mathcal{B}}_{L_E}} \\
\Rightarrow  & \  (A^\top {\bm{w}}^\star)^\top {\bm{x}}^\star  \le \underset{z}{\min}(A^\top {\bm{w}}^\star)^\top {\bm{z}}\quad     s.t \ \ \ {\bm{z}}\in {{\mathcal{B}}_{L_E}} \\end{aligned}$$

Since ${\bm{x}}^\star$ is a feasible point hence $(A^\top {\bm{w}}^\star)^\top {\bm{x}}^\star  = \underset{z}{\min}(A^\top {\bm{w}}^\star)^\top {\bm{z}}\quad     s.t \ \ \ {\bm{x}}^\star,{\bm{z}}\in {{\mathcal{B}}_{L_E}}$. At the point where above equaliy hold ${\bm{x}}^\star$ would be same as optimal ${\bm{z}}$. Hence the problem reduces to, $$\begin{aligned}
&\min \ \  (A^\top {\bm{w}}^\star)^\top {\bm{z}}\\
s.t \ \ & \alpha \|{\bm{z}}\|_1 + \frac{(1 - \alpha) }{2} \|{\bm{z}}\|_2^2 \leq 1 \\
& \Rightarrow \alpha \sum_{i=1}^n |{\bm{z}}_i| + \frac{(1 - \alpha) }{2} \sum_{i = 1}^n {\bm{z}}_i^2 \leq 1\end{aligned}$$ Without the loss of generality let us assume that for $i \in \{1 \ldots m \}, \ \ z_i \geq 0$ and $i \in \{m+1 \ldots n \}, \ \ z_i \leq 0$. Hence the optimization problem can be written as : $$\begin{aligned}
 \label{eq:min_elastic_ball}
&\min \ \  (A^\top {\bm{w}}^\star)^\top {\bm{z}}\\
s.t \ \ &  \alpha \big( \sum_{i=1}^m {\bm{z}}_i  - \sum_{i=m+1}^n {\bm{z}}_i \big ) + \frac{(1 - \alpha) }{2} \sum_{i = 1}^n {\bm{z}}_i^2 \leq 1 \notag \\
& -z_i \leq 0  \ \ for \ \ i \in \{1 \ldots m \} \notag \\
& z_i \leq 0  \ \ for \ \ i \in \{m+1 \ldots n \}  \notag\end{aligned}$$ Writing lagrangian for optimization problem $$\begin{aligned}
\mathcal{L}({\bm{z}},\lambda, u) =  (A^\top {\bm{w}}^\star)^\top {\bm{z}}- \sum_{i=1}^m \lambda_i z_i + \sum_{i = m+1}^n \lambda_i z_i + u \Big (  \alpha \big( \sum_{i=1}^m {\bm{z}}_i  - \sum_{i=m+1}^n {\bm{z}}_i \big ) + \frac{(1 - \alpha) }{2} \sum_{i = 1}^n {\bm{z}}_i^2 -1  \Big )\end{aligned}$$ Also optimization conditions are $\lambda_i \geq 0$, $\lambda_i z_i = 0$ and $\alpha \big( \sum_{i=1}^m {\bm{z}}_i  - \sum_{i=m+1}^n {\bm{z}}_i \big ) + (1 - \alpha) \sum_{i = 1}^n {\bm{z}}_i^2  =1$. Also we conclude from above that if $\lambda_i > 0 \Rightarrow z_i = 0$. From first order optimality condition,\
For $i \in \{1 \ldots m \}$ $$\begin{aligned}
 \label{eq:till_m1}
{\bm{a}}_i^\top {\bm{w}}^\star - \lambda_i  =  - u\big( \alpha + (1-\alpha)|z_i|\big)\end{aligned}$$ For $i \in \{m+1 \ldots n \}$ $$\begin{aligned}
 \label{eq:till_n1}
{\bm{a}}_i^\top{\bm{w}}^\star + \lambda_i  = - u\big( \alpha + (1-\alpha)|z_i|\big)\end{aligned}$$ Now in equations and we multiply by $z_i$ and add them. We get: $$\begin{aligned}
 \label{eq:final_elastic}
(A^\top {\bm{w}}^\star)^\top {\bm{z}}+ u [1 + \frac{(1 - \alpha) }{2} \|z\|_2^2] = 0\end{aligned}$$ From equations , , and optimality conditions discussed above we get: $$|{\bm{a}}_i^\top {\bm{w}}^\star | + (A^\top {\bm{w}}^\star)^\top z \Big [ \frac{ \alpha + (1 - \alpha)|z_i| }{ 1 + \frac{(1 - \alpha) }{2} \|z\|_2^2} \Big ] < 0  \Rightarrow z_i = 0$$ As discussed above ${\bm{x}}^\star$ share same solution as optimal $z$. Hence $$|{\bm{a}}_i^\top {\bm{w}}^\star | + (A^\top {\bm{w}}^\star)^\top {\bm{x}}^\star \Big [ \frac{ \alpha  }{ 1 + \frac{(1 - \alpha) }{2} \|{\bm{x}}^\star\|_2^2} \Big ] < 0  \Rightarrow x_i^\star = 0$$

Using optimality condition , we know that $ {\bm{w}}^\star \in \partial f(A{\bm{x}})$ $$\begin{aligned}
 |{\bm{a}}_i^\top {\bm{w}}^\star | + (A^\top {\bm{w}}^\star)^\top {\bm{x}}^\star & \Big [ \frac{ \alpha  }{ 1 + \frac{(1 - \alpha) }{2} \|{\bm{x}}^\star\|_2^2} \Big ]  \leq |{\bm{a}}_i^\top {\bm{w}}^\star | + (A^\top {\bm{w}}^\star)^\top {\bm{x}}^\star \big[\frac{2 \alpha}{3-\alpha} \big] \\
&= {\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}}^\star)\right\rvert}  + (A{\bm{x}}^\star)^\top \nabla f(A{\bm{x}}^\star) \big[\frac{2 \alpha}{3-\alpha} \big] \quad\\ 
&= {\left\lvert{\bm{a}}_i^\top ( \nabla f(A{\bm{x}}) - \nabla f(A{\bm{x}}) + \nabla f(A{\bm{x}}^\star))\right\rvert} \notag \\ 
& \qquad \qquad \qquad \qquad   \ \ + (A{\bm{x}}^\star)^\top \nabla f(A{\bm{x}}^\star) \big[\frac{2 \alpha}{3-\alpha} \big]\\ 
&\le {\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} + {\left\lvert{\bm{a}}_i^\top ( \nabla f(A{\bm{x}}^\star) - \nabla f(A{\bm{x}}))\right\rvert} \notag\\
& \qquad \qquad \qquad +(A{\bm{x}}^\star - A{\bm{x}}+A{\bm{x}})^\top \nabla f(A{\bm{x}}^\star) \big[\frac{2 \alpha}{3-\alpha} \big] \\ &= {\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} + {\left\lvert{\bm{a}}_i^\top ( \nabla f(A{\bm{x}}^\star) - \nabla f(A{\bm{x}}))\right\rvert} \notag\\
&  + (A{\bm{x}}) ^\top \nabla f(A{\bm{x}}^\star) \big[\frac{2 \alpha}{3-\alpha} \big] - ( A{\bm{x}}- A{\bm{x}}^\star)^\top \nabla f(A{\bm{x}}^\star) \big[\frac{2 \alpha}{3-\alpha} \big] \label{eq:optimal_x_star_fAx2}\\
&\le {\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} + {\left\lvert{\bm{a}}_i^\top ( \nabla f(A{\bm{x}}^\star) - \nabla f(A{\bm{x}}))\right\rvert} \notag \\ &\qquad \qquad  \ \ \qquad \qquad  \qquad +(A{\bm{x}})^\top \nabla f(A{\bm{x}}^\star) \big[\frac{2 \alpha}{3-\alpha} \big] \label{eq_elastic_proof_opt_f}\\ &\le {\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} + {\left\lvert{\bm{a}}_i^\top ( \nabla f(A{\bm{x}}^\star) - \nabla f(A{\bm{x}}))\right\rvert}\notag \\
& \qquad \qquad  +(A{\bm{x}})^\top (\nabla f(A{\bm{x}}^\star) - \nabla f(A{\bm{x}}) +  \nabla f(A{\bm{x}}))\big[\frac{2 \alpha}{3-\alpha} \big]\\ 
&\le {\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} + {\left\lvert{\bm{a}}_i^\top ( \nabla f(A{\bm{x}}^\star) - \nabla f(A{\bm{x}}))\right\rvert}  \notag \\
& + (A{\bm{x}})^\top\nabla f(A{\bm{x}})\big[\frac{2 \alpha}{3-\alpha} \big] +(A{\bm{x}})^\top (\nabla f(A{\bm{x}}^\star) - \nabla f(A{\bm{x}}))\big[\frac{2 \alpha}{3-\alpha} \big]\\ 
&\le {\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} + (A{\bm{x}})^\top \nabla f(A{\bm{x}})\big[\frac{2 \alpha}{3-\alpha} \big] \notag \\
& \qquad \qquad \qquad \qquad+ L({\left\lVert{\bm{a}}_i\right\rVert} + {\left\lVertA{\bm{x}}\right\rVert} \big[\frac{2 \alpha}{3-\alpha} \big])\sqrt{\frac{{G_{\mathcal{C}}}({\bm{x}})}{\mu}}\label{eq_elastic_proof_last} \end{aligned}$$ Eq. comes from the fact that at the optimal point ${\bm{x}}^\star$, the inequality $(A{\bm{x}}-A{\bm{x}}^\star )^\top\nabla f(A{\bm{x}}^\star) \ge 0$ holds $\forall {\bm{x}}$. Hence using Theorem \[thm:l1\_constrained\_screening\], Lemma \[lem:FWgaprestriction\] and Corollary \[cor:restric:smooth\], we get the screening rule for $L_1$ constrained as whenever,\
$${\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} + (A{\bm{x}})^\top \nabla f(A{\bm{x}}) \big[ \frac{2 \alpha}{3-\alpha} \big ] + L({\left\lVert{\bm{a}}_i\right\rVert}_2 + {\left\lVertA{\bm{x}}\right\rVert}_2\big[ \frac{2 \alpha}{3-\alpha} \big ])\sqrt{\frac{{G_{\mathcal{C}}}({\bm{x}})}{\mu}} < 0  \notag
 \Rightarrow \ {\bm{x}}_i^\star = 0$$

Screening for Box Constrained Problems {#app:box_screening}
--------------------------------------

#### Screening for General Box Constrained Problems (Section \[subsec:box\_screening\])

The box-constrained case can be seen in the form of the partially separable optimization problem pair and . According to optimality condition for this case, we have $$\begin{aligned}
 -{\bm{a}}_i^\top {\bm{w}}^\star \in&\ \partial g_i(x_i^\star) &&\forall i $$ Now from the definition of subgradient for an indicator function as given in Lemma \[lem:subgrad\_ind\]. Also since $x_i$ is a number now, we will get rid of the transpose here. $$\begin{aligned}
 \partial g(x_i^\star)  =& \left\{ s  \ |\    0  \le z  \le C , \; \ s(z-x_i^\star) \le 0  \quad    \right\} \notag \\
  =& \left\{ s  \ |\    0  \le z \le C ,  \; \ s z \le s x_i^\star   \quad     \right\}  \label{eq:subgrad_box}\end{aligned}$$

Now, by the optimality condition , $- {\bm{a}}_i^\top {\bm{w}}^\star \in \ \partial g(x_i^\star)$ and since this holds, hence $- {\bm{a}}_i^\top {\bm{w}}^\star$ should satisfy the required constrained which is needed to be in the set of subgradients of $\partial g(x_i^\star)$ according to conditions in Equation . Hence, $$\begin{aligned}
 \label{part_box}
&   \ (- {\bm{a}}_i^\top {\bm{w}}^\star) z \le (- {\bm{a}}_i^\top {\bm{w}}^\star) x_i^\star   \quad \forall z \ \textrm{ s.t }  \  0  \le z \le C , \;  \nonumber \\
\Rightarrow &\ \underset{z}{\min}({\bm{a}}_i^\top {\bm{w}}^\star) z \ge ({\bm{a}}_i^\top {\bm{w}}^\star) x_i^\star   \quad s.t \ \    \ 0  \le z \le C   $$ Now can be manipulated in two ways\

1.  $$\begin{aligned}
    {\bm{a}}_i^\top {\bm{w}}^\star > 0 \Rightarrow
    & \ \underset{z}{\min}({\bm{a}}_i^\top {\bm{w}}^\star)^\top z \ge ({\bm{a}}_i^\top {\bm{w}}^\star) x_i^\star   \quad  s.t \ \  \ 0  \le z \le C \\
    \Rightarrow&   \ 0 \ge ({\bm{a}}_i^\top {\bm{w}}^\star)^\top x_i^\star   \quad  \end{aligned}$$

    But since ${\bm{a}}_i^\top {\bm{w}}^\star  > 0$ and also $x_i^\star \ge 0$ hence $({\bm{a}}_i^\top {\bm{w}}^\star)x_i^\star \not < 0$. This implies $({\bm{a}}_i^\top {\bm{w}}^\star)x_i^\star = 0$ and hence if $ {\bm{a}}_i^\top {\bm{w}}^\star > 0 \ \Rightarrow\  x_i^\star = 0$

2.  $$\begin{aligned}
    {\bm{a}}_i^\top {\bm{w}}^\star < 0 \Rightarrow
    & \ \underset{z}{\min}({\bm{a}}_i^\top {\bm{w}}^\star) z \ge ({\bm{a}}_i^\top {\bm{w}}^\star) x_i^\star   \quad  s.t \ \  \ 0  \le z \le C \\
    \Rightarrow&   \ ({\bm{a}}_i^\top {\bm{w}}^\star)C \ge ({\bm{a}}_i^\top {\bm{w}}^\star) x_i^\star   \quad  \end{aligned}$$

    But since ${\bm{a}}_i^\top {\bm{w}}^\star  < 0$ and also $x_i^\star \le C$ hence $({\bm{a}}_i^\top {\bm{w}}^\star)x_i^\star \not < ({\bm{a}}_i^\top {\bm{w}}^\star)C$. This implies $({\bm{a}}_i^\top {\bm{w}}^\star)x_i^\star = ({\bm{a}}_i^\top {\bm{w}}^\star)C $ and hence if $ {\bm{a}}_i^\top {\bm{w}}^\star < 0 \ \Rightarrow\  x_i^\star = C$

Final optimality arguments can be given as $$\begin{aligned}
 \label{eq:optimality_argument}
{\bm{a}}_i^\top {\bm{w}}^\star > 0 \ \Rightarrow\  x_i^\star = 0 \notag \\
{\bm{a}}_i^\top {\bm{w}}^\star < 0 \ \Rightarrow\  x_i^\star = C\end{aligned}$$

Now $$\begin{aligned}
{\bm{a}}_i^\top {\bm{w}}^\star = {\bm{a}}_i^\top ({\bm{w}}^\star + {\bm{w}}-{\bm{w}}) = {\bm{a}}_i^\top {\bm{w}}+ {\bm{a}}_i^\top({\bm{w}}^\star - {\bm{w}}) \notag \\
{\bm{a}}_i^\top {\bm{w}}- \|{\bm{a}}_i\|_2 \|{\bm{w}}- {\bm{w}}^\star\|_2 \le {\bm{a}}_i^\top {\bm{w}}^\star \le {\bm{a}}_i^\top {\bm{w}}+ \|{\bm{a}}_i\|_2\|{\bm{w}}- {\bm{w}}^\star\|_2 \label{eq:box_constr_util}\end{aligned}$$ Since $f$ is $L$-Lipschitz gradient hence $f^*$ is $1/L$-strongly convex, hence using Lemmas \[lem:stronglyconvex\] and \[lem:smooth\_convex\_condition\], Equation becomes $$\begin{aligned}
{\bm{a}}_i^\top {\bm{w}}- \|{\bm{a}}_i\|_2 \sqrt{2L\,{G}({\bm{x}})} \le {\bm{a}}_i^\top {\bm{w}}^\star \le {\bm{a}}_i^\top {\bm{w}}+ \|{\bm{a}}_i\|_2 \sqrt{2L\,{G}({\bm{x}})} \label{eq:box_constr_util2}\end{aligned}$$ Hence using equation and earlier arguments we get, $$\begin{aligned}
&{\bm{a}}_i^\top {\bm{w}}^\star > 0 \ \Rightarrow\  x_i^\star   =0 \nonumber \\
\Rightarrow &{\bm{a}}_i^\top {\bm{w}}-  {\left\lVert{\bm{a}}_i\right\rVert}_2\sqrt{2L\,{G}({\bm{x}})}>0 \ \Rightarrow\   x_i^\star =0 \end{aligned}$$ And if $$\begin{aligned}
&{\bm{a}}_i^\top {\bm{w}}^\star < 0 \ \Rightarrow\  x_i^\star   =C \nonumber  \\
\Rightarrow &{\bm{a}}_i^\top {\bm{w}}+  {\left\lVert{\bm{a}}_i\right\rVert}_2\sqrt{2L\,{G}({\bm{x}})}>0 \ \Rightarrow\   x_i^\star =C \end{aligned}$$

#### Screening on SVM with hinge loss and no bias

Here the primal problem is given by: $$\begin{aligned}
& \underset{{\bm{w}},{\bm{\epsilon}}}{\min} & & \tfrac{1}{2} {\bm{w}}^\top{\bm{w}}+ C {\mathbf{1}}^\top{\bm{\epsilon}}\\
& \text{s.t.} & &  {\bm{w}}^\top{\bm{a}}_i \ge 1-\epsilon_i & \forall i \in \{1:p\}\\
& & &  \epsilon_i \ge 0 & \forall i \in \{1:p\} 
\end{aligned}$$ A dual formulation of the problem can be written as: $$\begin{aligned}
& \underset{{\bm{x}}}{\min} & & -{\bm{x}}^\top{\mathbf{1}}+ \tfrac{1}{2} {\bm{x}}^\top A^\top A{\bm{x}}\\
& \text{s.t.} & &  0 \le {\bm{x}}\le C{\mathbf{1}}\end{aligned}$$ Theorem \[thm:box\_constrained\] is applied on the dual formulation. The objective function $\frac{1}{2}{\bm{x}}^\top A^\top A{\bm{x}}- {\bm{x}}^\top{\mathbf{1}}$ is strongly convex with parameter $1$ and its derivative Lipschitz continuous with parameter $1$. The duality gap between primal and dual feasible points ${G}({\bm{w}},{\bm{\epsilon}},{\bm{x}})$ is now used as suboptimality certificate which can play the role of the upper bound $\|{\bm{w}}- {\bm{w}}^\star\|$ using Lemma \[cor:Dgaprestriction\]. For a given ${\bm{x}}$ a primal feasible point can be obtained by setting ${\bm{w}}=A{\bm{x}}$ and ${\bm{\epsilon}}$ minimal such that the first constraint of the primal problem is satisfied. Using the obtained point for the duality gap, it only depends on the point ${\bm{x}}$. All together this gives the screening rule: $$\begin{aligned}
{\bm{a}}_i^\top A{\bm{x}}+1 >   {\left\lVert{\bm{a}}_i\right\rVert} \sqrt{2{G}({\bm{x}})} & \Rightarrow & x_i^\star = 0\\
{\bm{a}}_i^\top A{\bm{x}}+1 < - {\left\lVert{\bm{a}}_i\right\rVert} \sqrt{2{G}({\bm{x}})} & \Rightarrow & x_i^\star = C\end{aligned}$$

**Note -** Since the primal and dual of hinge loss SVM have very nice structure with smooth quadratic function with an addition to piece-wise linear convex function, hence it is not hard to show that both primal and dual function is $1$ strongly convex as shown in [@Zimmert:2015ue]. For more detailed proof, we recommend to go through [@Zimmert:2015ue]. Now for an instance, if we write duality gap function as a function of ${\bm{w}}$ then $${G}({\bm{w}}) \ge {G}({\bm{w}}^\star) + \nabla {G}({\bm{w}}^\star)^\top ({\bm{w}}- {\bm{w}}^\star) + {\left\lVert{\bm{w}}- {\bm{w}}^\star\right\rVert}_2^2$$ Since strong duality hold in SVM case, hence at optimal point ${\bm{w}}^\star$, ${G}({\bm{w}}^\star) = 0$. Finally we get, $${G}({\bm{w}}) \ge  {\left\lVert{\bm{w}}- {\bm{w}}^\star\right\rVert}_2^2$$ Hence the screening rule comes out as given in [@Zimmert:2015ue]: $$\begin{aligned}
{\bm{a}}_i^\top A{\bm{x}}+1 >   {\left\lVert{\bm{a}}_i\right\rVert} \sqrt{{G}({\bm{x}})} & \Rightarrow & x_i^\star = 0\\
{\bm{a}}_i^\top A{\bm{x}}+1 < - {\left\lVert{\bm{a}}_i\right\rVert} \sqrt{{G}({\bm{x}})} & \Rightarrow & x_i^\star = C\end{aligned}$$

Screening on Penalized Problems {#app:penalized}
===============================

Screening $L_1$-regularized Problems {#app:penalized_problem_l1}
------------------------------------

\[lem:l1\_regularized\] Considering general $L_1$-regularized optimization problems $$\label{eq:l1_regularized}
\begin{aligned}
& \underset{{\bm{x}}\in {\mathbb{R}}^p}{\min} & & f(A{\bm{x}}) +  \lambda {\left\lVert{\bm{x}}\right\rVert}_1 
\end{aligned}$$ At optimum points ${\bm{x}}^\star$ and dual optimal point ${\bm{w}}^\star$, the following rule is satisfied for the above problem formulation : $$\begin{aligned}
{\left\lvert{\bm{a}}_i^\top {\bm{w}}^\star\right\rvert} < \lambda 
\ \Rightarrow \ x_i^\star = 0  $$

Since the optimization problem comes under the partially separable framework and we can use the first order optimality condition as well as to derive screening rules for the problem. Also we know that, the conjugate of the norm function is the indicator function of its dual norm ball. By the optimality condition , we know that $$x_i \in \ \partial g_i^*(-{\bm{a}}_i^\top{\bm{w}})$$ here $g_i^*$ is the indicator function written as ${\bm{\iota}}_{L_\infty} (-{\bm{a}}_i^\top {\bm{w}})$. Hence for the indicator function $g^*$ by Lemma \[lem:subgrad\_ind\] $$\begin{aligned}
 \partial g_i^*(-{\bm{a}}_i^\top{\bm{w}}^\star)  =& \left\{ s \vert  \ \ \forall {\bm{z}}\ s.t \ \ {\left\lvert\frac{{\bm{a}}_i^\top {\bm{z}}}{\lambda}\right\rvert} \le 1 \:; \ s(- {\bm{a}}_i ^\top {\bm{z}}+ {\bm{a}}_i^\top{\bm{w}}^\star) \le 0  \quad    \right\} \\
  =& \left\{ s \vert  \ \ \forall {\bm{z}}\ s.t \ \ {\left\lvert{\bm{a}}_i^\top {\bm{z}}\right\rvert}\le \lambda\:; \ s ({\bm{a}}_i ^\top {\bm{z}})\ge s ({\bm{a}}_i^\top{\bm{w}}^\star )\quad   \right\} \end{aligned}$$ Since the optimality condition holds hence $-x_i^\star$ should satisfy the required constrained which is needed to be in the set of subgradients of $\partial g_i^*(-{\bm{a}}_i^\top {\bm{w}}^\star)$ according to conditions given above. That is

$$\begin{aligned}
&-x_i^\star ({\bm{a}}_i ^\top {\bm{z}})\le -x_i^\star ({\bm{a}}_i^\top{\bm{w}}^\star )   \quad \forall {\bm{z}}\ s.t \ \ {\left\lvert{\bm{a}}_i^\top {\bm{z}}\right\rvert}\le \lambda\  \\
&x_i^\star ({\bm{a}}_i ^\top {\bm{z}})\ge x_i^\star ({\bm{a}}_i^\top{\bm{w}}^\star ) \quad \forall {\bm{z}}\ s.t \ \ {\left\lvert{\bm{a}}_i^\top {\bm{z}}\right\rvert}\le \lambda\  \\
\Rightarrow  & \  x_i^\star ({\bm{a}}_i^\top{\bm{w}}^\star )  \le \underset{z}{\min}(x_i^\star ({\bm{a}}_i ^\top {\bm{z}}))  \quad     s.t \ \ \ {\left\lvert{\bm{a}}_i^\top {\bm{z}}\right\rvert}\le \lambda\ \notag \\\end{aligned}$$

-   $x_i^\star > 0$. $$\begin{aligned}
    &\  x_i^\star ({\bm{a}}_i^\top{\bm{w}}^\star )  \le \underset{z}{\min}(x_i^\star ({\bm{a}}_i ^\top {\bm{z}}))  \quad     s.t \ \ \ {\left\lvert{\bm{a}}_i^\top {\bm{z}}\right\rvert}\le \lambda\ \notag \\
    & \Rightarrow \  x_i^\star ({\bm{a}}_i^\top{\bm{w}}^\star )  \le -\lambda x_i^\star \notag \\
    &\Rightarrow ({\bm{a}}_i^\top{\bm{w}}^\star )  \le - \lambda  \notag \\
    &\Rightarrow ({\bm{a}}_i^\top{\bm{w}}^\star )  = - \lambda \label{eq:pen_dual_proof_part1}\end{aligned}$$ Equation comes from the fact that ${\left\lvert{\bm{a}}_i^\top {\bm{w}}^\star\right\rvert} \le \lambda$

-   $x_i ^\star< 0$. $$\begin{aligned}
    &\  x_i^\star ({\bm{a}}_i^\top{\bm{w}}^\star )  \le \underset{z}{\min}(x_i^\star ({\bm{a}}_i ^\top {\bm{z}}))  \quad     s.t \ \ \ {\left\lvert{\bm{a}}_i^\top {\bm{z}}\right\rvert}\le \lambda\ \notag \\
    &\Rightarrow \  x_i^\star ({\bm{a}}_i^\top{\bm{w}}^\star )  \le \lambda x_i^\star \notag \\
    &\Rightarrow ({\bm{a}}_i^\top{\bm{w}}^\star )  \ge  \lambda  \notag \\
    &\Rightarrow ({\bm{a}}_i^\top{\bm{w}}^\star )  =  \lambda \label{eq:pen_dual_proof_part2}\end{aligned}$$ Equation comes from the fact that ${\left\lvert{\bm{a}}_i^\top {\bm{w}}^\star\right\rvert} \le \lambda$

-   $x_i^\star = 0$.\
    Since if we assume $f$ as a continuous smooth function then ${\bm{a}}_i^\top {\bm{w}}^\star$ is also continuous. Now if we consider arguments given for $x_i ^\star< 0$ and $x_i ^\star > 0$ we conclude that ${\left\lvert{\bm{a}}_i^\top {\bm{w}}^\star\right\rvert} = \lambda$ in all of the above two cases. Since $x_i^\star = 0$ is in the domain of the function , hence at $x_i^\star = 0$, ${\bm{a}}_i^\top {\bm{w}}^\star$ will lie in the open range of $-\lambda$ to $\lambda$. Which implies whenever ${\left\lvert{\bm{a}}_i^\top {\bm{w}}^\star\right\rvert} < \lambda$, then $x_i^\star = 0$

Another view on the proof can be derived from the optimality condition .

The optimization problem can be taken as partially separable problem and from the optimality condition kk $$\begin{aligned}
&-{\bm{a}}_i^\top{\bm{w}}^\star \in \partial g_i(x_i^\star) \label{eq:l1_1}\\ &\partial g_i(x_i^\star) \in  \left\{\begin{array}{ll}
         \lambda \frac{x_i^\star}{{\left\lvertx_i^\star\right\rvert}}   &\mbox{if } x_i \neq 0 \\ \relax
        [- \lambda,  \lambda ] & \mbox{if } x_i = 0
    \end{array} \right. \label{eq:l1_2}\end{aligned}$$ From equations and we conclude that if $$\begin{aligned}
{\left\lvert{\bm{a}}_i^\top {\bm{w}}^\star\right\rvert} < \lambda \ \Rightarrow\  x_i^\star = 0\end{aligned}$$

From Equation , we know that ${\bm{w}}^\star \in \partial f(A{\bm{x}}^\star)$. Hence from Lemma \[lem:l1\_regularized\], $$\begin{aligned}
{\left\lvert{\bm{a}}_i^\top {\bm{w}}^\star\right\rvert} &= {\left\lvert{\bm{a}}_i^\top( {\bm{w}}^\star -{\bm{w}}+ {\bm{w}})\right\rvert} \notag \\
& \le {\left\lvert{\bm{a}}_i^\top{\bm{w}}\right\rvert} + {\left\lvert{\bm{a}}_i^\top( {\bm{w}}^\star - {\bm{w}})\right\rvert} \notag \\
& \le {\left\lvert{\bm{a}}_i^\top{\bm{w}}\right\rvert} + {\left\lVert{\bm{a}}_i\right\rVert}_2\|{\bm{w}}^\star - {\bm{w}}\|_2 \notag \\
& \le {\left\lvert{\bm{a}}_i^\top{\bm{w}}\right\rvert} + {\left\lVert{\bm{a}}_i\right\rVert}_2\sqrt{ 2L\,{G}({\bm{x}})} \label{eq:l1_reg_last} \end{aligned}$$ Eq. comes from Corollary \[cor:Dgaprestriction\]. Now using Lemma \[lem:l1\_regularized\] and equation , we get $$\begin{aligned}
{\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} < \lambda - {\left\lVert{\bm{a}}_i\right\rVert}_2\sqrt{2L\,{G}({\bm{x}})} \ \Rightarrow\  {\bm{x}}_i^\star=0\end{aligned}$$

#### Penalized Lasso.

Screening in this case can be derived from the existing “gap safe” paper [@Ndiaye:2015wj]. For completeness we here show that the same result follows from our Theorem \[thm:smooth\_pen\_lasso\]:

\[cor:pen\_lasso\] **Penalized Lasso** Consider an optimization problem of the form: $$\begin{aligned}
\min_{{\bm{x}}\in{\mathbb{R}}^n} \ \tfrac{1}{2} \|A{\bm{x}}- b\|_2^2 + \lambda \|{\bm{x}}\|_1\end{aligned}$$ Then the screening rule is given by: ${\left\lvert{\bm{a}}_i^\top(A{\bm{x}}-{\bm{b}})\right\rvert} < \lambda - {\left\lVert{\bm{a}}_i\right\rVert}_2\sqrt{2{G}({\bm{x}})} \ \Rightarrow\ {\bm{x}}_i^\star=0.$

By observing the cost function for penalized lasso it can be concluded that\
$$f(A{\bm{x}}) = \tfrac{1}{2}{\left\lVertA{\bm{x}}-{\bm{b}}\right\rVert}^2, \quad 
{\bm{w}}=A{\bm{x}}-{\bm{b}}, \quad \textrm{and } L=1$$\
Now results from Theorem \[thm:smooth\_pen\_lasso\] can be directly applied here and hence the screening rule becomes\
$$\begin{aligned}
{\left\lvert{\bm{a}}_i^\top(A{\bm{x}}-{\bm{b}})\right\rvert} < \lambda - {\left\lVert{\bm{a}}_i\right\rVert}\sqrt{2{G}({\bm{x}})} \ \Rightarrow\ {\bm{x}}_i^\star=0.\end{aligned}$$

This result is known in the literature [@Ndiaye:2015wj], and we recover it using our proposed general approach in this paper by using Theorem \[thm:smooth\_pen\_lasso\].\
Also, by applying same trick as mentioned after the end of proof of Corollary \[cor:SVMhinge\], we can show that we can get rid of the factor $2$ here also. Here also it is not hard to see that primal and dual ( and ) both are $1$ strongly convex in the dual variable ${\bm{w}}$. Hence by the same argument as made in the proof of Corollary \[cor:SVMhinge\], we get that $${G}({\bm{w}}) \ge  {\left\lVert{\bm{w}}- {\bm{w}}^\star\right\rVert}_2^2$$ And the improved screening rule comes out to be $${\left\lvert{\bm{a}}_i^\top(A{\bm{x}}-{\bm{b}})\right\rvert} < \lambda - {\left\lVert{\bm{a}}_i\right\rVert}\sqrt{{G}({\bm{x}})} \ \Rightarrow\  {\bm{x}}_i^\star=0.$$

#### Logistic Regression with $L_1$-regularization

\[cor:logistic\_l1\] **Logistic Regression with $L_1$-norm Penalization.** The optimization problem for logistic regression with $L_1$ regularizer can be written in the form of: $$\begin{aligned}
 \label{eq:logistic_l1}
\min_{{\bm{x}}\in{\mathbb{R}}^n} \ \sum_{i=1}^{n} \log(\exp([A{\bm{x}}]_i)+1) + \lambda \|{\bm{x}}\|_1\end{aligned}$$ And screening rule for above problem can be written as : $$\begin{aligned}
{\left\lvert{\bm{a}}_i^\top\left(\frac{\exp(A{\bm{x}})}{\exp(A{\bm{x}})+1}\right)\right\rvert} < \lambda - {\left\lVert{\bm{a}}_i\right\rVert}_2\sqrt{2{G}({\bm{x}})}
\ \Rightarrow \ {\bm{x}}_i^\star=0\end{aligned}$$ where $\left(\frac{\exp(A{\bm{x}})}{\exp(A{\bm{x}})+1}\right)$ is element wise vector whose $i_{th}$ element is $\left(\frac{\exp([A{\bm{x}}]_i)}{\exp([A{\bm{x}}]_i)+1}\right)$

By observation we know that in equation $$f(A{\bm{x}}) = \sum_{i=1}^{n} \log(\exp([A{\bm{x}}]_i)+1) \text{ and }{\bm{w}}\text{ is elementwise vector of } w_i \text{ s.t} \quad w_i=\frac{\exp([A{\bm{x}}]_i)}{\exp([A{\bm{x}}]_i)+1}$$ According to [@Smith:2015ua Lemma 5], we get that the function $f(A{\bm{x}})$ is $1$-smooth. Hence $L = 1$\
Now from theorem \[thm:smooth\_pen\_lasso\], we derive the screening rule for logistic regression with $L_1$-regularization which is $$\begin{aligned}
{\left\lvert{\bm{a}}_i^\top\left(\frac{\exp(A{\bm{x}})}{\exp(A{\bm{x}})+1}\right)\right\rvert} < \lambda - {\left\lVert{\bm{a}}_i\right\rVert}_2\sqrt{2{G}({\bm{x}})} \ \Rightarrow\  {\bm{x}}_i^\star=0\end{aligned}$$ where $\left(\frac{\exp(A{\bm{x}})}{\exp(A{\bm{x}})+1}\right)$ is element wise vector whose $i_{th}$ element is $\left(\frac{\exp([A{\bm{x}}]_i)}{\exp([A{\bm{x}}]_i)+1}\right)$ This result is also known in the literature in [@Ndiaye:2015wj] (or see also [@Wang:2014un] for a similar approach) and we recover it using our prosed general approach in this paper by using Theorem \[thm:smooth\_pen\_lasso\].\

#### Elastic-net regularized regression

$$\begin{aligned}
& \frac{1}{2}\|A{\bm{x}}- {\bm{b}}\|_2^2 + \lambda_2  \|{\bm{x}}\|_2^2 + \lambda_1 \|{\bm{x}}\|_1 \notag \\ 
&=  \frac{1}{2} [{\bm{x}}^\top A^\top A{\bm{x}}-2{\bm{b}}^\top A{\bm{x}}+{\bm{b}}^\top{\bm{b}}] + \lambda_2 {\bm{x}}^\top{\bm{x}}+ \lambda_1 \|{\bm{x}}\|_1 \notag\\
&=  \frac{1}{2}[{\bm{x}}^\top(A^\top A + 2\lambda_2 I){\bm{x}}-2{\bm{b}}^\top A{\bm{x}}+{\bm{b}}^\top{\bm{b}}] + \lambda_1 \|{\bm{x}}\|_1 \label{eq:elastic_formulate}\end{aligned}$$

Now consider $A^\top A + 2\lambda_2 I = Q^\top Q$ and choose vector ${\bm{m}}$ such that $A^\top{\bm{b}}= Q^\top {\bm{m}}$. Hence line can be written as $$\begin{aligned}
&  \tfrac{1}{2}\big[{\bm{x}}^\top(A^\top A + 2\lambda_2 I){\bm{x}}-2{\bm{b}}^\top A{\bm{x}}+{\bm{b}}^\top{\bm{b}}\big]+ \lambda_1 \|{\bm{x}}\|_1 \\
&=  \tfrac{1}{2}\big[{\bm{x}}^\top Q^\top Q{\bm{x}}- 2{\bm{m}}^\top Q{\bm{x}}+ {\bm{m}}^\top{\bm{m}}- {\bm{m}}^\top{\bm{m}}+ {\bm{b}}^\top{\bm{b}}\big] + \lambda_1 \|{\bm{x}}\|_1 \\
&=  \tfrac{1}{2} \|Q{\bm{x}}- {\bm{m}}\|_2^2 + \tfrac{1}{2}\big[ {\bm{b}}^\top{\bm{b}}- {\bm{m}}^\top{\bm{m}}\big]  + \lambda_1 \|{\bm{x}}\|_1\end{aligned}$$ Now the optimization problem can be written as $$\label{eq:modified_elastic}
\min_{{\bm{x}}} \ \tfrac{1}{2}\|Q{\bm{x}}- {\bm{m}}\|_2^2 +  \lambda_1 \|{\bm{x}}\|_1$$ Now results from Corollary \[cor:pen\_lasso\] can be directly applied to .\
From observation, we know that $f(Q{\bm{x}}) = \frac{1}{2}{\left\lVertQ{\bm{x}}-{\bm{m}}\right\rVert}^2, \quad 
{\bm{w}}=Q{\bm{x}}-{\bm{m}}, \quad \textrm{and }
L=1$\
Simplification, $$\begin{aligned}
{\left\lvert\bm{q}_i^\top(Q{\bm{x}}-{\bm{m}})\right\rvert} &= {\left\lvert\bm{q}_i^\top Q{\bm{x}}- \bm{q}_i^\top {\bm{m}}\right\rvert}\notag\\
&= {\left\lvert\bm{q}_i^\top Q{\bm{x}}- {\bm{a}}_i^\top {\bm{b}}\right\rvert}\notag \\
&= {\left\lvert({\bm{a}}_i^\top A + 2\lambda_2 \bm{e}_i^\top){\bm{x}}- {\bm{a}}_i^\top {\bm{b}}\right\rvert} \label{eq:elastic_exp_smpl1}\end{aligned}$$ $$\begin{aligned}
{\left\lvert\bm{q}_i\right\rvert}\sqrt{2{G}({\bm{x}})} &= \sqrt{{\bm{a}}_i^\top {\bm{a}}_i + 2\lambda_2} \sqrt{2{G}({\bm{x}})}\notag \\
&=\sqrt{2({\bm{a}}_i^\top {\bm{a}}_i +2 \lambda_2) {G}({\bm{x}})}\label{eq:elastic_exp_smpl2}\end{aligned}$$ Now using results from Corollary \[cor:pen\_lasso\], equations and , we get screening rules for elastic norm regularization regression problem as: $$\begin{aligned}
{\left\lvert({\bm{a}}_i^\top A + 2\lambda_2 \bm{e}_i^\top){\bm{x}}- {\bm{a}}_i^\top {\bm{b}}\right\rvert} < \lambda_1 - \sqrt{2({\bm{a}}_i^\top {\bm{a}}_i + 2\lambda_2)({G}({\bm{x}}))} \ \Rightarrow \ x_i^\star = 0.\end{aligned}$$

\[lem:smooth\_elastic\] For $\alpha \ \in  \ (0,1]$, the elastic net function $g({\bm{x}}) = \frac{1 - \alpha}{2} \|{\bm{x}}\|_2^2 + \alpha \|{\bm{x}}\|_1$ is the convex conjugate of $$g^*({\bm{x}}) = \sum_i \Big[ \frac{1}{2(1 - \alpha)}\big( \big[ |x_i|  - \alpha \big]_+\big)^2 \Big] = \sum_i  g_i^*(x_i)$$ where $g_i(\beta_i) =  \big[ \frac{1  - \alpha}{2} \beta_i^2 + \alpha |\beta_i| \big ]$ and $[.]_+$ is the positive part operator, $[s]_+ = s \ \  for \ \ s > 0$ , and zero otherwise. Furthermore, this $g^*$ is is smooth, *i.e.* has Lipschitz continuous gradient with constant $1/(1 - \alpha)$.

The complete proof has been given in [@Smith:2015ua Lemma 6] but we also provide proof here below.\
From the definition of convex conjugate function, $$\begin{aligned}
g^*({\bm{x}}) &= \sup_{{\bm{\beta}}}[{\bm{x}}^\top {\bm{\beta}}- g({\bm{\beta}})] \notag \\
& = \sup_{{\bm{\beta}}}\big[{\bm{x}}^\top {\bm{\beta}}- \big( \frac{1 - \alpha}{2} \|{\bm{\beta}}\|_2^2 + \alpha \|{\bm{\beta}}\|_1\big)\big] \notag \\
 & = \sup_{\beta_i}\big[\sum_{i} x_i \beta_i - \big( \sum_{i} \big( \frac{1 - \alpha}{2} \beta_i^2 + \alpha |\beta_i|\big)\big)\big] \ \ \forall \ \ i \in [n] \notag \\
 & = \sum_{i}  \sup_{\beta_i}  \big[x_i \beta_i -  \big( \frac{1  - \alpha}{2} \beta_i^2 + \alpha |\beta_i|\big) \big] \ \ \forall \ \ i \in [n] \notag  \\
 & = \sum_i g_i^*(x_i) \ \text{, where } \ \  g_i(\beta_i) =  \frac{1  - \alpha}{2} \beta_i^2 + \alpha |\beta_i| \notag\end{aligned}$$ Now, $$\begin{aligned}
g_i^*(x_i) = \sup_{\beta_i}  \big[x_i \beta_i -  \big( \frac{1  - \alpha}{2} \beta_i^2 + \alpha |\beta_i|\big) \big]\end{aligned}$$ Consider three cases now :\

-   $\beta > 0$. $$\begin{aligned}
     g_i^*(x_i)   &= \sup_{\beta_i}  \big[x_i \beta_i -  \big( \frac{1  - \alpha}{2} \beta_i^2 + \alpha \beta_i \big) \big] \\
     &\Rightarrow \beta_i = \frac{(x_i - \alpha)}{(1 - \alpha)} \ \ \text{that also implies } \ \  x_i > \alpha \\
     \text{Hence, } g_i^*(x_i)   &= \frac{(x_i - \alpha)^2}{2(1 - \alpha)} \ \ \text{whenevr } \ \ x_i > \alpha
     \end{aligned}$$

-   $\beta < 0$. $$\begin{aligned}
     g_i^*(x_i)   &= \sup_{\beta_i}  \big[x_i \beta_i -  \big( \frac{1  - \alpha}{2} \beta_i^2 - \alpha \beta_i \big) \big] \\
     &\Rightarrow \beta_i = \frac{(x_i + \alpha)}{(1 - \alpha)} \ \ \text{that also implies } \ \  x_i < - \alpha \\
     \text{Hence, } g_i^*(x_i)   &= \frac{(x_i + \alpha)^2}{2(1 - \alpha)} \ \ \text{whenevr } \ \ x_i < -\alpha
     \end{aligned}$$

-   $\beta = 0$. $$\begin{aligned}
     g_i^*(x_i)   &= 0 \ \ \text{that also implies } \ \  |x_i| \leq  \alpha \\
     \end{aligned}$$

Hence, $$\begin{aligned}
 g_i^*(x_i) = \frac{1}{2(1 - \alpha)}\big( \big[ |x_i|  - \alpha \big]_+\big)^2\end{aligned}$$ From all of the above arguments, $g^*({\bm{x}}) = \sum_i \Big[ \frac{1}{2(1 - \alpha)}\big( \big[ |x_i|  - \alpha \big]_+\big)^2 \Big] = \sum_i  g_i^*(x_i)$

\[thm:elasticnet\_genral\] If we consider the general elastic net formulation of the form $$\begin{aligned}
\min_{{\bm{x}}} \ f(A{\bm{x}}) + \frac{(1-\alpha)}{2}  \|{\bm{x}}\|_2^2 + \alpha \|{\bm{x}}\|_1 \label{eq:elasticnet_genral}\end{aligned}$$ If $f$ is L-smooth, then the following screening rule holds for all $i \in [n]$: $${\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} < \alpha - {\left\lVert{\bm{a}}_i\right\rVert}_2\sqrt{2L\,{G}({\bm{x}})} \ \Rightarrow\  {\bm{x}}_i^\star=0$$

Since the optimization problem comes under the partially separable framework and we can use the first order optimality condition as well as to derive screening rules for the problem.

By optimality condition , we know that $$x_i \in \ \partial g_i^*(-{\bm{a}}_i^\top{\bm{w}})$$ From lemma \[lem:smooth\_elastic\], $g_i^*(-{\bm{a}}_i^\top {\bm{w}}^\star) = \frac{1}{2(1 - \alpha)}\big( \big[ |{\bm{a}}_i^\top {\bm{w}}^\star|  - \alpha \big]_+\big)^2$ and also $ \partial g_i^*(-{\bm{a}}_i^\top{\bm{w}}) = 0 \ \text{whenever} \ {\left\lvert{\bm{a}}_i^\top{\bm{w}}\right\rvert} \leq \alpha $\
Hence whenever ${\left\lvert{\bm{a}}_i^\top{\bm{w}}\right\rvert} \leq \alpha \Rightarrow x_i = 0$.\
The same screening rule for elastic net regularized problem can be derived from the optimality condition . The optimization problem can be taken as partially separable problem and from the optimality condition $$\begin{aligned}
&-{\bm{a}}_i^\top{\bm{w}}^\star \in \partial g_i(x_i^\star) \label{eq:l1_1}\\ &\partial g_i(x_i^\star) \in  \left\{\begin{array}{ll}
         \alpha \frac{x_i^\star}{{\left\lvertx_i^\star\right\rvert}} + (1-\alpha) x_i   &\mbox{if } x_i \neq 0 \\ \relax
        [- \alpha,  \alpha ] & \mbox{if } x_i = 0
    \end{array} \right. \label{eq:l1_2}\end{aligned}$$ Hence, whenever ${\left\lvert{\bm{a}}_i^\top{\bm{w}}\right\rvert} \leq \alpha \Rightarrow x_i = 0$.\
The above arguments also show the significance of symmetry in our formulation as structure and . This formulation provides our framework more flexibility to be used in larger class of problem.\
Now, $$\begin{aligned}
{\left\lvert{\bm{a}}_i^\top {\bm{w}}^\star\right\rvert} &= {\left\lvert{\bm{a}}_i^\top( {\bm{w}}^\star -{\bm{w}}+ {\bm{w}})\right\rvert} \notag \\
& \le {\left\lvert{\bm{a}}_i^\top{\bm{w}}\right\rvert} + {\left\lvert{\bm{a}}_i^\top( {\bm{w}}^\star - {\bm{w}})\right\rvert} \notag \\
& \le {\left\lvert{\bm{a}}_i^\top{\bm{w}}\right\rvert} + {\left\lVert{\bm{a}}_i\right\rVert}_2\|{\bm{w}}^\star - {\bm{w}}\|_2 \notag \\
& \le {\left\lvert{\bm{a}}_i^\top{\bm{w}}\right\rvert} + {\left\lVert{\bm{a}}_i\right\rVert}_2\sqrt{ 2L\,{G}({\bm{x}})} \label{eq:elastic_reg_last} \end{aligned}$$ Equation comes directly from corollary \[cor:Dgaprestriction\]. Hence finally we get the screening rules for general elastic net penalty problem which is very similar to screening for $L_1-penalized$ problems:

$${\left\lvert{\bm{a}}_i^\top \nabla f(A{\bm{x}})\right\rvert} < \alpha - {\left\lVert{\bm{a}}_i\right\rVert}_2\sqrt{2L\,{G}({\bm{x}})} \ \Rightarrow\  {\bm{x}}_i^\star=0$$

Now the above mentioned rule can be made a bit tighter under some condition which is not very interesting to discuss here.

Screening for Structured Norms {#app:structured_norm}
------------------------------

\[lem:grplasso\_basic\] If we use the same notation as mentioned in Section \[subsec:l1\_l2\_genral\] to write a vector ${\bm{x}}$ as a concatenation of smaller group vectors $\{ {\bm{x}}_1 \cdots {\bm{x}}_G\}$ such that ${\bm{x}}^\top = \left[ {\bm{x}}_1^\top, {\bm{x}}_2^\top \cdots {\bm{x}}_G^\top \right]$ and correspondingly the matrix $A$ can be denoted as the concatenation of column groups $A = [A_1 \ A_2 \cdots A_G]$. Now if we consider an optimization problem of the form $$\ \  \operatorname*{arg\,min}_{{\bm{x}}} f(A{\bm{x}}) + \sum_{g=1}^G \sqrt{\rho_g} \|{\bm{x}}_g\|_2 \qquad$$\
At the optimal point ${\bm{x}}^\star$ and dual optimal points ${\bm{w}}^\star$, we get rules according to the following equation: $$\begin{aligned}
\|A_g^\top {\bm{w}}^\star\|_2 < \sqrt{\rho_g} \ \Rightarrow\  {\bm{x}}_g^\star = 0\end{aligned}$$

Dual of the problem is given by $$\begin{aligned}
  {\mathcal{O}_{\hspace{-1pt}B}}({\bm{w}}) 
    =f^*({\bm{w}})
    +\sum_g \sqrt{\rho_g}  {\bm{\iota}}_{L_\infty} (\frac {{\left\lVertA_g^\top {\bm{w}}\right\rVert}_2}{\sqrt{\rho_g}} ) \label{eq:dual_l1_regularized}\end{aligned}$$ Hence for the indicator function $g_g^*$ by Lemma \[lem:subgrad\_ind\] $$\begin{aligned}
 \partial g_g^*(-A_g^\top {\bm{w}}^\star)  =& \left\{ {\bm{s}}\vert  \ \ \forall {\bm{z}}\ s.t \ \ {\left\lVert\frac{A_g^\top  {\bm{z}}}{\sqrt{\rho_g}}\right\rVert}_2 \le 1 \:; \ {\bm{s}}^\top(-A_g^\top {\bm{z}}+A_g^\top {\bm{w}}^\star) \le 0  \quad    \right\} \\
  =& \left\{ {\bm{s}}\vert  \ \ \forall {\bm{z}}\ s.t \ \ {\left\lVertA_g^\top  {\bm{z}}\right\rVert}_2 \le \sqrt{\rho_g} ; \ {\bm{s}}^\top (A_g^\top  {\bm{z}})\ge {\bm{s}}^\top  (A_g^\top {\bm{w}}^\star )\quad   \right\} \end{aligned}$$ Now, by the optimality condition ${\bm{x}}_g \in \ \partial g_g^*(-A_g^\top {\bm{w}}^\star)$, and since this holds, hence $xv_g^\star$ should satisfy the required constrained which is needed to be in the set of subgradients of $\partial g^*(-A_g^\top {\bm{w}}^\star)$ according to conditions given above. Hence,

$$\begin{aligned}
&-{{\bm{x}}_g^\star}^\top (A_g^\top  {\bm{z}})\le -{{\bm{x}}_g^\star}^\top  (A_g^\top {\bm{w}}^\star )  \quad \forall {\bm{z}}\ s.t \ \ {\left\lVertA_g^\top  {\bm{z}}\right\rVert}_2 \le \sqrt{\rho_g}  \notag\\
&\Rightarrow {{\bm{x}}_g^\star}^\top (A_g^\top  {\bm{z}})\ge {{\bm{x}}_g^\star}^\top  (A_g^\top {\bm{w}}^\star )  \quad \forall {\bm{z}}\ s.t \ \ {\left\lVertA_g^\top  {\bm{z}}\right\rVert}_2 \le \sqrt{\rho_g} \notag \\
&\Rightarrow   \  {{\bm{x}}_g^\star}^\top  (A_g^\top {\bm{w}}^\star ) \le \underset{z}{\min} \  {{\bm{x}}_g^\star}^\top (A_g^\top  {\bm{z}}) \quad   \ s.t   \ \ {\left\lVertA_g^\top  {\bm{z}}\right\rVert}_2 \le \sqrt{\rho_g} \notag \\
&\Rightarrow   \  {{\bm{x}}_g^\star}^\top  (A_g^\top {\bm{w}}^\star ) \le \underset{z}{\min} \|{\bm{x}}_g\|_2 \|A_g^\top  {\bm{z}}\|_2
\quad   \ s.t   \ \ {\left\lVertA_g^\top  {\bm{z}}\right\rVert}_2 \le \sqrt{\rho_g} \notag \\
&\Rightarrow   \  {\bm{x}}_g^\top  (A_g^\top {\bm{w}}^\star ) \le - \|{\bm{x}}_g^\star\|_2 \sqrt{\rho_g} \notag \\
&\Rightarrow \|A_g^\top {\bm{w}}^\star\|_2 = \sqrt{\rho_g}  \label{eq:aaaa}\end{aligned}$$

Equation comes from the cauchy inequality and true $\forall {\bm{x}}_g^\star \ : \ \ {\bm{x}}_g^\star \neq 0$. Whenever $\|A_g^\top {\bm{w}}^\star\|_2 < \sqrt{\rho_g}$ then ${\bm{x}}_g^\star = 0$

Another view on the screening of above optimization problem can be seen from the optimality condition . The optimization problem in Lemma \[lem:grplasso\_basic\] can be taken as partially separable problem and from the optimality condition $$\begin{aligned}
&-A_g^\top{\bm{w}}^\star \in \partial g({\bm{x}}_g^\star) \label{eq:gl2l1_1}\\
&\partial g({\bm{x}}_g^\star) \in  \left\{\begin{array}{ll}
         \sqrt{\rho_g} \frac{{\bm{x}}_g}{\|x_g\|_2}   &\mbox{if } {\bm{x}}_g \neq 0 \\ \relax
        {\mathcal{B}}_2 & \mbox{if } {\bm{x}}_g = 0 \ and \ {\mathcal{B}}_2 \ \textrm{is norm ball of radius } \sqrt{\rho_g}
    \end{array} \right. \label{eq:gl2l1_2} \end{aligned}$$ From Equations and , we conclude that if $$\|A_g^\top {\bm{w}}^\star\|_2 < \sqrt{\rho_g} \ \Rightarrow\ {\bm{x}}_g^\star = 0$$

From Equation , we know that ${\bm{w}}\in \nabla f(A{\bm{x}})$. Now $$\begin{aligned}
\|  A_g^\top {\bm{w}}^\star  \|_2 &= \| A_g^\top {({\bm{w}}+ {\bm{w}}^\star - {\bm{w}})}  \|_2  \leq \| A_g^\top {\bm{w}}\|_2 + \| A_g^\top ({\bm{w}}^\star - {\bm{w}})\|_2 \notag \\ 
& = \|A_g ^\top {\bm{w}}\|_2 + \sqrt{tr(( A_g^\top ( {\bm{w}}^\star - {\bm{w}}) )(( {\bm{w}}^\star - {\bm{w}}) ^\top) A_g)^\top} \notag \\
& \leq \|A_g^\top {\bm{w}}\|_2 + \sqrt{tr(( {\bm{w}}^\star - {\bm{w}}) ^\top( {\bm{w}}^\star - {\bm{w}}))} \sqrt{tr(A_g^\top A_g)} \notag \\
&=\|A_g^\top {\bm{w}}\|_2 + \| {\bm{w}}^\star -{\bm{w}}\|_2 {\left\lVertA_g\right\rVert_{\textsf{Fro}}} \label{eq:grp_basic_last}\end{aligned}$$ Using Corollary \[cor:Dgaprestriction\] with Equation , we get $$\begin{aligned}
\|  A_g^\top {\bm{w}}^\star  \|_2 \le \|A_g^\top \nabla f(A{\bm{x}}) \|_2 + \sqrt{2L\,{G}({\bm{x}})} {\left\lVertA_g\right\rVert_{\textsf{Fro}}}\end{aligned}$$ Hence using previous Lemma \[lem:grplasso\_basic\], $$\begin{aligned}
\|A_g^\top \nabla f(A{\bm{x}}) \|_2 + \sqrt{2L\,{G}({\bm{x}})} {\left\lVertA_g\right\rVert_{\textsf{Fro}}} < \sqrt{\rho_g} \ \Rightarrow\  {\bm{x}}_g^\star = 0\end{aligned}$$

This is an explicit case of the optimization problem mentioned in Lemma \[lem:grplasso\_basic\]. By observation we know that, $$f(A{\bm{x}}) = \tfrac{1}{2}\|A{\bm{x}}- b\|^2, \quad {\bm{w}}= A{\bm{x}}- b \quad and \quad L = 1$$ Now applying the findings of Theorem \[thm:smooth\_grp\_lasso\], we get $$\begin{aligned}
\|A_g^\top (A{\bm{x}}- {\bm{b}})\|_2 + \sqrt{2{G}({\bm{x}})}   {\left\lVertA_g\right\rVert_{\textsf{Fro}}} <\lambda \sqrt{\rho_g} \ \Rightarrow\  {\bm{x}}_g^\star = 0\end{aligned}$$

In Lemma \[lem:gengrpnorm\] mentioned below, we show that the structured norm setting of [@Ndiaye:2015wj] can be derived from our more general and structure.

\[lem:gengrpnorm\] Sparse Multi-Task and Multi Class Model [@Ndiaye:2015wj] - If we consider general problem of the form $$\label{eq:gengrpnorm}
\min_{X \in {\mathbb{R}}^{p \times q}} \  \sum_{i = 1}^n f_i ({\bm{a}}_i^\top X) + \lambda\Omega(X)$$ where the regularization function $\Omega : {\mathbb{R}}^{p \times q}\rightarrow {\mathbb{R}}_+ $ is such that $\Omega(X) = \sum_{g=1}^p \| {\bm{x}}_g \|_2$ and $X = [{\bm{x}}_1, {\bm{x}}_2 \cdots {\bm{x}}_G]$. We write $W = [{\bm{w}}_1, {\bm{w}}_2 \cdots {\bm{w}}_G]$ for variable of the dual problem. Then the screening rule becomes $$\begin{aligned}
\| {{\bm{a}}^{(g)}}^\top W \|_2 < \lambda  - \|{\bm{a}}^{(g)}\|_2 \, \|W - W^\star\|_2 \ \Rightarrow\  {\bm{x}}_g^\star = 0\end{aligned}$$ Here ${\bm{a}}^{(g)}$ is the vector of the $g^{th}$ element group of each vector ${\bm{a}}_i$.

Equations pair and can be used interchangeably by replacing primal with dual and $f$ with $g$. Hence the partial separable primal-dual pair and can also be used interchangeably. By comparing Equation with and , we observe that separable function $\sum_{i = 1}^n f_i ({\bm{a}}_i^\top X)$ takes the place of separable $g^*$ in and $\lambda\Omega(X)$ takes the place of $f^*$. Hence we apply the optimality condition to get (with exchanged primal dual variable) $$AW^\star \in \partial {\lambda \Omega(X^\star)}$$ Hence if, $$\begin{aligned}
 \label{eq:primary_gen_grp_lass}
\| {{\bm{a}}^{(g)}}^\top W^\star \|_2 < \lambda \ \Rightarrow\  {\bm{x}}_g = 0\end{aligned}$$ Now, $$\begin{aligned}
\| {{\bm{a}}^{(g)}}^\top W^\star \|_2 &= \| {{\bm{a}}^{(g)}}^\top (W^\star - W + W) \|_2 \notag\\
&\le \| {{\bm{a}}^{(g)}}^\top W \|_2 + \|{{\bm{a}}^{(g)}}^\top (W^\star - W ) \|_2 \notag\\
&\le \| {{\bm{a}}^{(g)}}^\top W \|_2 + \|{{\bm{a}}^{(g)}}\|_2 \|(W^\star - W ) \|_2 \label{eq:last_line_gen_grp_lass}\end{aligned}$$ Using equations and , the screening rule comes out to be $$\| {{\bm{a}}^{(g)}}^\top W \|_2 < \lambda  - \|{\bm{a}}^{(g)}\|_2 \, \|W - W^\star\|_2 \ \Rightarrow\  {\bm{x}}_g^\star = 0$$

If for all $i \in [n]$, $f_i$ is $L$-Lipschitz gradient then screening rule for equation is $$\| {{\bm{a}}^{(g)}}^\top W \|_2 < \lambda  - \|{\bm{a}}^{(g)}\|_2 \sqrt{2L\,{G}(X)} \ \Rightarrow\  {\bm{x}}_g^\star = 0$$

Using Lemma \[lem:gengrpnorm\] and Corollary \[cor:Dgaprestriction\], we get the desired expression.

Connection with Sphere Test Method {#app:connection_sphere_test}
----------------------------------

The general idea behind the sphere test method [@Xiang:2014vi] is to consider the maximum value of desired function in a spherical region which contains the optimal dual variable. In context of our general framework and , we obtain this case when considering an $\ell_1$ penalty or $\ell_2/\ell_1$ penalty. That means $g$ is a norm and hence from Lemma \[lem:conjugates\], $g^*$ becomes the indicator function of the dual norm ball of $A^\top {\bm{w}}$. The dual norm function for $\ell_1$ norm is of the form $\max_{i}|{\bm{a}}_i^\top {\bm{w}}|$ and for $\ell_2/\ell_1$ norm, it is $\max_{g}\|A_g^\top {\bm{w}}\|$. Hence, we try to find maximum value of the function of the forms $\max_{\bm{\theta} \in \mathcal{S}(\bm{q},r)} {\bm{a}}_i^\top\bm{\theta}$ where $\mathcal{S}(\bm{q},r) = \{z : \|{\bm{z}}-\bm{q}\|_2 \leq r \}$ the ball $\mathcal{S}$ also contains the optimal dual point ${\bm{w}}^\star$. If the maximum value of ${\bm{a}}_i^\top\bm{\theta}$ is less than some particular value for all the $\bm{\theta}$ in the ball hence ${\bm{a}}_i^\top {\bm{w}}$ will also be less than that particular value and that is the main reason we try to find maximum of ${\bm{a}}_i^\top\bm{\theta}$ over the ball $\mathcal{S}$. $$\begin{aligned}
\max_{\bm{\theta} \in \mathcal{S}(\bm{q},r)} {\bm{a}}_i^\top\bm{\theta} &= {\bm{a}}_i^\top(\bm{\theta} - \bm{q} + \bm{q}) =  {\bm{a}}_i^\top(\bm{\theta} - \bm{q}) + {\bm{a}}_i^\top \bm{q}\\
&\leq \|{\bm{a}}_i\|_2 \|\bm{\theta} - \bm{q}\| + {\bm{a}}_i^\top \bm{q} \leq r \|{\bm{a}}_i\|_2  + {\bm{a}}_i^\top \bm{q}\end{aligned}$$ Similar arguments can be given in the $\ell_2/\ell_1$-norm case. A variety of existing screening test for lasso and group lasso are of this flavor of sphere tests. The difference between these approaches mainly lie in the way of choosing the center and bounding the radius of the sphere, such that the optimal dual variables lie inside the sphere. Our method can be seen as a general framework for such a sphere test based screening with dynamic screening rules. Our method can be interpreted as a sphere test with the current iterate of the dual variable ${\bm{w}}$ as a center of the ball, and we obtain the bound on the radius in terms of duality gap function.

[^1]: Parts of this work have appeared in the Master’s Thesis [@Olbrich:2015kq].
