# Dynamic Sasvi: Strong Safe Screening for Norm-Regularized Least Squares

Hiroaki Yamada  Makoto Yamada

###### Abstract

A recently introduced technique for a sparse optimization problem called ”safe
screening” allows us to identify irrelevant variables in the early stage of
optimization. In this paper, we first propose a flexible framework for safe
screening based on the Fenchel-Rockafellar duality and then derive a strong
safe screening rule for norm-regularized least squares by the framework. We
call the proposed screening rule for norm-regularized least squares ”dynamic
Sasvi” because it can be interpreted as a generalization of Sasvi. Unlike the
original Sasvi, it does not require the exact solution of a more strongly
regularized problem; hence, it works safely in practice. We show that our
screening rule can eliminate more features and increase the speed of the
solver in comparison with other screening rules both theoretically and
experimentally.

Machine Learning, ICML

##  1 Introduction

Sparse models such as Lasso (Tibshirani, 1996) and group Lasso (Yuan & Lin,
2006) have been widely studied in the areas of statistics and machine
learning, and are used for various applications such as compressed sensing
(Donoho, 2006) and biomarker discovery (Climente-González et al., 2019), to
name a few. Although sparse models can be formulated as a simple convex
optimization problem, the computational cost can be large if the numbers of
samples and dimensions are extremely large.

To tackle this problem, a technique called safe screening has been introduced
(Ghaoui et al., 2010) for Lasso problems. Specifically, it eliminates
variables that are guaranteed to be zero in the Lasso solution before solving
the original Lasso optimization problem. Many safe screening methods have been
proposed for various problems (Ghaoui et al., 2010; Ogawa et al., 2013; Wang
et al., 2015; Liu et al., 2014; Xiang et al., 2017). These are called
sequential screening rules because they require the solution to a more
strongly regularized problem. A recent technique used to eliminate variables
through an estimated solution in an iterative solver, called dynamic
screening, has been proposed (Bonnefoy et al., 2015). In particular, Gap Safe
(Fercoq et al., 2015; Ndiaye et al., 2015), a dynamic screening framework is
widely used owing to its generality and efficiency (Ndiaye et al., 2017;
Shibagaki et al., 2016; Bao et al., 2020; Raj et al., 2016; Ndiaye et al.,
2020). More specifically, Gap Safe efficiently screens variables by using the
dual form of the original problems, where the screening is characterized by
properly designing the dual safe region. For Lasso, two simple region-based
approaches exist: Gap Safe Sphere and Gap Safe Dome (Fercoq et al., 2015).

In this paper, we propose a dynamic safe screening algorithm that is stronger
than either Gap Safe Sphere or Gap Safe Dome for the _Lasso-Like_ problem,
which includes norm-regularized least squares. To this end, we first propose a
general screening framework based on the Fenchel-Rockafellar duality and then
derive _Dynamic Sasvi_ , a strong safe screening rule for _Lasso-like_
problems. Our framework can be regarded as a generalization of the Gap Safe
framework, and thus we can derive Gap Safe Sphere and Gap Safe Dome simply
using our results. Moreover, thanks to this generalization, we can use a
strong problem adaptive inequality. Interestingly, the derived screening rule
for _Lasso-like_ problems can be seen as a dynamic variant of the safe
screening with variational inequalities (Sasvi) (Liu et al., 2014), a
sequential screening rule for Lasso. Therefore, we call this dynamic Sasvi.
Unlike the original Sasvi, dynamic Sasvi does not require an exact solution to
the problem with another hyper-parameter and hence operates safely in
practice. Moreover, we propose the use of dynamic enhanced dual polytope
projections (EDPP) (Wang et al., 2015), which are a relaxation of dynamic
Sasvi by introducing a minimum radius sphere. We show both theoretically and
experimentally that the screening power and computational costs of Dynamic
Sasvi and Dynamic EDPP compare favorably with those of other state-of-the-art
Gap Safe methods.

Contribution: The contributions of our paper are summarized as follows.

  * •

We propose a flexible screening framework based on Fenchel-Rockafellar
duality, which is a generalization of the Gap Safe framework (Ndiaye et al.,
2017).

  * •

We propose two novel dynamic screening rules for norm-regularized least
squares, which are a dynamic variant of Sasvi (Liu et al., 2014) and a dynamic
variant of EDPP.

  * •

We show that Dynamic Sasvi eliminates more features and increases the speed of
the solver in comparison to Gap Safe (Fercoq et al., 2015; Ndiaye et al.,
2017) both theoretically and experimentally.

##  2 Preliminary

In this section, we first formulate the problem and introduce the key
techniques used in this study.

###  2.1 Notation

Given $h:\mathbb{R}^{m}\to[-\infty,\infty]$, the domain of $h$ is defined by

$\mathrm{dom}(h):=\\{{\bm{z}}\in\mathbb{R}^{m}\mid|h({\bm{z}})|<\infty\\}$

and $h^{\star}:\mathbb{R}^{m}\to[-\infty,\infty]$, the Fenchel conjugate of
$h$, is defined by

$h^{\star}({\bm{v}}):=\sup_{{\bm{z}}\in\mathbb{R}^{d}}{\bm{v}}^{\top}{\bm{z}}-h({\bm{z}}).$

If $h$ is proper, the Fenchel-Young inequality

$h({\bm{z}})+h^{\star}({\bm{v}})\geq{\bm{v}}^{\top}{\bm{z}}$ (1)

can be proven directly from the definition of the Fenchel conjugate. The
subdifferential of a proper function $h:\mathbb{R}^{m}\to(-\infty,\infty]$ at
${\bm{z}}$ is given as

$\displaystyle\partial h({\bm{z}})$ $\displaystyle:=$
$\displaystyle\\{{\bm{v}}\in\mathbb{R}^{m}\mid\forall{\bm{w}}\in\mathbb{R}^{m}\
{\bm{v}}^{\top}({\bm{w}}-{\bm{z}})+h({\bm{z}})\leq h({\bm{w}})\\}.$

The next proposition is important for driving Safe-screening algorithms.

###### Proposition 1

Assume that $h:\mathbb{R}^{m}\to(-\infty,\infty]$ is a proper lower
semicontinuous convex function and ${\bm{z}},{\bm{v}}\in\mathbb{R}^{m}$. We
then have

$\displaystyle{\bm{v}}\in\partial h({\bm{z}})$ $\displaystyle\iff
h({\bm{z}})+h^{\star}({\bm{v}})={\bm{v}}^{\top}{\bm{z}}$
$\displaystyle\iff{\bm{z}}\in\partial h^{\star}({\bm{v}}).$

See (Bauschke et al., 2011) Section 16 for the proof.

For convex set $C\subset\mathbb{R}^{m}$, the relative interior of $C$ is
defined by

$\displaystyle\mathrm{relint}(C)$ $\displaystyle:=$ $\displaystyle\\{v\in
C\mid\forall w\in C\ \exists\epsilon>0\ \mathrm{s.t.}\ v+\epsilon(v-w)\in
C\\}.$

###  2.2 Problem Formulation

In this study, we consider an optimization problem, formulated as

$\underset{{\bm{\beta}}\in\mathbb{R}^{d}}{\mathrm{minimize}}~{}~{}f({\bm{X}}{\bm{\beta}})+g({\bm{\beta}}),$
(2)

where ${\bm{\beta}}\in\mathbb{R}^{d}$ is the optimization variable,
${\bm{X}}\in\mathbb{R}^{n\times d}$ is a constant matrix, and
$f:\mathbb{R}^{n}\to(-\infty,\infty]$ and
$g:\mathbb{R}^{d}\to(-\infty,\infty]$ are proper lower semicontinuous convex
functions. We assume

$\exists{\bm{\beta}}\in\mathrm{relint}(\mathrm{dom}(g))\ \mathrm{s.t.}\
{\bm{X}}{\bm{\beta}}\in\mathrm{relint}(\mathrm{dom}(f))$

and the existence of the optimal point, i.e.,

$\exists\hat{{\bm{\beta}}}\in\mathrm{dom}(P)\ \mathrm{s.t.}\
P(\hat{{\bm{\beta}}})=\inf_{{\bm{\beta}}\in\mathbb{R}^{d}}P({\bm{\beta}}),$

where $P:\mathbb{R}^{d}\to\mathbb{R}$ is defined as
$P({\bm{\beta}})=f({\bm{X}}{\bm{\beta}})+g({\bm{\beta}})$. Note that we have
not assumed the uniqueness of the solution. Moreover, we focus on the cases
where $g$ induces sparsity. Although all theorems in this paper hold, we
cannot eliminate any variables without sparsity.

This class of optimization problem is popular, the most popular example of
which is Lasso (Tibshirani, 1996):

$\underset{{\bm{\beta}}\in\mathbb{R}^{d}}{\mathrm{minimize}}~{}~{}\frac{1}{2}{\|{\bm{y}}-{\bm{X}}{\bm{\beta}}\|}_{2}^{2}+\lambda{\|{\bm{\beta}}\|}_{1}.$

Many extensions of Lasso, including Group-Lasso (Yuan & Lin, 2006), Elastic-
Net (Zou & Hastie, 2005), and sparse logistic regression (Meier et al., 2008)
are in this class. Note that non-convex extensions such as SCAD (Fan & Li,
2001), Bridge (Frank & Friedman, 1993), and MCP (Zhang et al., 2010) do not
satisfy this assumption.

Another example of the problem in Eq. (2) is the dual problem of a support
vector machine (SVM) (Cortes & Vapnik, 1995). The dual problem of SVM can be
formulated as follows:

$\underset{{\bm{\beta}}\in\mathbb{R}^{d}:{\bm{0}}\leq{\bm{\beta}}\leq{\bm{1}}}{\mathrm{minimize}}~{}~{}\frac{1}{2}{\|{\bm{X}}{\bm{\beta}}\|}_{2}^{2}-{\bm{1}}^{\top}{\bm{\beta}}.$

The dual problem of a support vector regression (SVR) (Smola & Schölkopf,
2004) is also a target problem. Note that we cannot eliminate any variables of
the primal problem of the normal SVM and SVR owing to a lack of sparsity.
However, screening methods are available for the primal problem of the feature
sparse variants of SVM and SVR (Ghaoui et al., 2010; Shibagaki et al., 2016).

###  2.3 Dual Problem

To derive a safe screening rule for the optimization problem, Eq. (2), the
Fenchel-Rockafellar dual formulation, plays an important role.

###### Theorem 2

(Fenchel-Rockafellar Duality) If all assumptions for the optimization problem
(2) are satisfied, we have the following:

$\min_{{\bm{\beta}}\in\mathbb{R}^{d}}f({\bm{X}}{\bm{\beta}})+g({\bm{\beta}})=\max_{{\bm{\theta}}\in\mathbb{R}^{n}}-f^{\star}(-{\bm{\theta}})-g^{\star}({\bm{X}}^{\top}{\bm{\theta}}).$
(3)

The proof of Theorem 2 is given in the Appendix. Let us denote
$-f^{\star}(-{\bm{\theta}})-g^{\star}({\bm{X}}^{\top}{\bm{\theta}})$ by
$D({\bm{\theta}})$. For primal/dual solutions, we know many conditions that
are equivalent to the optimality. Herein, we provide a list of such conditions
for convenience.

###### Proposition 3

(Optimal Condition) If all assumptions for the optimization problem (2) are
satisfied, the following are equivalent:

  1. (a)

$\hat{{\bm{\beta}}}\in\mathop{\mathrm{argmin\,}}_{{\bm{\beta}}\in\mathbb{R}^{d}}P({\bm{\beta}})\land\hat{{\bm{\theta}}}\in\mathop{\mathrm{argmax\,}}_{{\bm{\theta}}\in\mathbb{R}^{n}}D({\bm{\theta}})$

  2. (b)

$P(\hat{{\bm{\beta}}})=D(\hat{{\bm{\theta}}})$

  3. (c)

$f({\bm{X}}\hat{{\bm{\beta}}})+f^{\star}(-\hat{{\bm{\theta}}})=-\hat{{\bm{\theta}}}^{\top}{\bm{X}}\hat{{\bm{\beta}}}=-g(\hat{{\bm{\beta}}})-g^{\star}({\bm{X}}^{\top}\hat{{\bm{\theta}}})$

  4. (d)

$-\hat{{\bm{\theta}}}\in\partial
f({\bm{X}}\hat{{\bm{\beta}}})\land{\bm{X}}^{\top}\hat{{\bm{\theta}}}\in\partial
g(\hat{{\bm{\beta}}})$

  5. (e)

${\bm{X}}\hat{{\bm{\beta}}}\in\partial
f^{\star}(-\hat{{\bm{\theta}}})\land\hat{{\bm{\beta}}}\in\partial
g^{\star}({\bm{X}}^{\top}\hat{{\bm{\theta}}})$

(Proof) (a) $\iff$ (b) is directly derived from the strong duality. (b) $\iff$
(c) is derived from the Fenchel-Young inequality (1). (c) $\iff$ (d) $\iff$
(e) are derived from Proposition 1. $\Box$

###  2.4 Relationship of Dual Safe Region and Screening

In this section, we show that we can eliminate some features by constructing a
simple region that contains $\hat{{\bm{\theta}}}$.

###### Theorem 4

Assume that all assumptions for the optimization problem (2) are satisfied.
Let $\hat{{\bm{\beta}}}$ be the primal optimal point. Assume that the dual
optimal point $\hat{{\bm{\theta}}}$ is within the region ${\mathcal{R}}$.
Then,

$\hat{{\bm{\beta}}}\in\bigcup_{{\bm{\theta}}\in{\mathcal{R}}}\partial
g^{\star}({\bm{X}}^{\top}{\bm{\theta}}).$

(Proof) According to Proposition 3, $\hat{{\bm{\beta}}}\in\partial
g^{\star}({\bm{X}}^{\top}\hat{{\bm{\theta}}})\subset\bigcup_{{\bm{\theta}}\in{\mathcal{R}}}\partial
g^{\star}({\bm{X}}^{\top}{\bm{\theta}})$. $\Box$

Theorem 4 provides a general method for feature screening. A simple example is
the following corollary.

###### Corollary 5

Consider an optimization problem, i.e., Eq. (2) with
$g({\bm{\beta}})={\|{\bm{\beta}}\|}_{1}$. Assume that
$\hat{{\bm{\theta}}}\in{\mathcal{R}}$. We then have

$\max_{{\bm{\theta}}\in{\mathcal{R}}}|{\bm{x}}_{i}^{\top}{\bm{\theta}}|<1\implies\hat{{\bm{\beta}}}_{i}=0.$

(Proof) By definition of $g$, we have $\partial
g^{\star}({\bm{X}}^{\top}{\bm{\theta}})\subset\\{{\bm{\beta}}\mid{\bm{\beta}}_{i}=0\\}\iff|{\bm{x}}_{i}^{\top}{\bm{\theta}}|<1$.
When
$\max_{{\bm{\theta}}\in{\mathcal{R}}}|{\bm{x}}_{i}^{\top}{\bm{\theta}}|<1$, we
have $\hat{{\bm{\beta}}}\in\bigcup_{{\bm{\theta}}\in{\mathcal{R}}}\partial
g^{\star}({\bm{X}}^{\top}{\bm{\theta}})\subset\\{{\bm{\beta}}\mid{\bm{\beta}}_{i}=0\\}$
by Theorem 4. $\Box$

Note that the computational cost of
$\bigcup_{{\bm{\theta}}\in{\mathcal{R}}}\partial
g^{\star}({\bm{X}}^{\top}{\bm{\theta}})$ depends on the simplicity of $g$ and
${\mathcal{R}}$.

The key challenge of screening is to determine the simple narrow region
${\mathcal{R}}$. Many regions have been proposed for various problems. In the
next section, we provide a general framework for constructing a safe region.

##  3 General Framework for Constructing Safe Region

Herein, we propose a general framework for constructing a dual region that has
the solution to the optimization problem in Eq. (3). Our framework consists of
a general lower bound and a problem adaptive upper-bound of the optimal value.
Hence, we can derive a narrower region than the framework with a general upper
bound under certain situations. The general lower-bound is given in the next
Theorem.

###### Theorem 6

Consider the optimization problem in Eq. (3) and assume that $f^{\star}$ is
$L$-strongly convex ($L\geq 0$). Let $\hat{{\bm{\theta}}}$ be the solution to
(3). Then, for $\forall\tilde{{\bm{\theta}}}\in\mathbb{R}^{n}$, we have

$l(\hat{{\bm{\theta}}};\tilde{{\bm{\theta}}})\leq D(\hat{{\bm{\theta}}}),$ (4)

where

$l({\bm{\theta}};\tilde{{\bm{\theta}}})=\frac{L}{2}{\|{\bm{\theta}}-\tilde{{\bm{\theta}}}\|}_{2}^{2}+D(\tilde{{\bm{\theta}}}).$

(Proof) According to Proposition 3, ${\bm{X}}\hat{{\bm{\beta}}}\in\partial
f^{\star}(-\hat{{\bm{\theta}}})$ and $\hat{{\bm{\beta}}}\in\partial
g^{\star}({\bm{X}}^{\top}\hat{{\bm{\theta}}})$ hold. Because $f^{\star}$ is
$L$-strongly convex and $g^{\star}$ is convex, for
$\forall\tilde{{\bm{\theta}}}\in\mathbb{R}^{n}$, we have

$\displaystyle
f^{\star}(-\hat{{\bm{\theta}}})+{({\bm{X}}\hat{{\bm{\beta}}})}^{\top}(-\tilde{{\bm{\theta}}}+\hat{{\bm{\theta}}})+\frac{L}{2}{\|\tilde{{\bm{\theta}}}-\hat{{\bm{\theta}}}\|}_{2}^{2}$
$\displaystyle\leq f^{\star}(-\tilde{{\bm{\theta}}}),$ $\displaystyle
g^{\star}({\bm{X}}^{\top}\hat{{\bm{\theta}}})+\hat{{\bm{\beta}}}^{\top}({\bm{X}}^{\top}\tilde{{\bm{\theta}}}-{\bm{X}}^{\top}\hat{{\bm{\theta}}})$
$\displaystyle\leq g^{\star}({\bm{X}}^{\top}\tilde{{\bm{\theta}}}).$

Adding these two inequalities, we have the inequality (4). $\Box$

This means that $\hat{{\bm{\theta}}}$ is within the region of
$\\{{\bm{\theta}}\mid l({\bm{\theta}};\tilde{{\bm{\theta}}})\leq
D({\bm{\theta}})\\}$. Because this region is too complicated for screening, we
use a simple upper bound of $D({\bm{\theta}})$ to construct a simple safe
region. The next theorem can be directly derived from Theorem 6.

###### Theorem 7

Consider the optimization problem in Eq. (3) and assume that $f^{\star}$ is
$L$-strongly convex ($L\geq 0$). Let $\hat{{\bm{\theta}}}$ be the solution to
Eq. (3). Assume $D({\bm{\theta}})$ is upper bounded by $u({\bm{\theta}})$,
i.e., $\forall{\bm{\theta}}\in\mathbb{R}^{n}\ D({\bm{\theta}})\leq
u({\bm{\theta}})$. Then, for $\forall\tilde{{\bm{\theta}}}\in\mathbb{R}^{n}$,
we have

$\hat{{\bm{\theta}}}\in\mathcal{R}(\tilde{{\bm{\theta}}},u)=\\{{\bm{\theta}}\mid
l({\bm{\theta}};\tilde{{\bm{\theta}}})\leq u({\bm{\theta}})\\}.$

The complexity of $\mathcal{R}(\tilde{{\bm{\theta}}},u)$ depends on the
complexity of $u$. For example, if $u$ is linear, then
$\mathcal{R}(\tilde{{\bm{\theta}}},u)$ is a sphere. We can construct a narrow,
simple, and safe region with a tight simple upper-bound $u$.

In fact, the Gap Safe Sphere region (Fercoq et al., 2015; Ndiaye et al., 2017)
can be derived easily from this theorem and weak duality.

###### Corollary 8

(Gap Safe Sphere) Consider the optimization problem in Eq. (3) and assume that
$f^{\star}$ is $L$-strongly convex ($L\geq 0$). Let $\hat{{\bm{\theta}}}$ be
the solution to Eq. (3). For $\forall\tilde{{\bm{\beta}}}\in\mathbb{R}^{d}$
and $\forall\tilde{{\bm{\theta}}}\in\mathbb{R}^{n}$, the region of the Gap
Safe Sphere is given as

${\mathcal{R}}^{\mathrm{GS}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}})=\\{{\bm{\theta}}\mid
l({\bm{\theta}};\tilde{{\bm{\theta}}})\leq P(\tilde{{\bm{\beta}}})\\}.$ (5)

Then,

$\hat{{\bm{\theta}}}\in{\mathcal{R}}^{\mathrm{GS}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}}).$

(Proof) Based on a weak duality, we have $\forall{\bm{\theta}}\
D({\bm{\theta}})\leq P(\tilde{{\bm{\beta}}})$. Using this constant function as
an upper bound in Theorem 7, the corollary is derived directly. $\Box$

Hence, our framework can be seen as a generalization of Gap Safe. Owing to
this generalization, we can use a stronger problem-adaptive upper-bound than a
weak duality. In the next section, we derive specific regions for _Lasso-Like_
problem. Some regions for other problems are given in the Appendix.

##  4 Safe region for Lasso-like problem

In this section, we introduce a strong upper bound for the dual problems of
Lasso and similar problems. The dome region derived from it can be seen as a
generalization of Sasvi (Liu et al., 2014) and is narrower than Gap Safe
Sphere and Gap Safe Dome.

###  4.1 Norm-regularized least squares problem and its generalization

Norm-regularized least squares is an optimization problem and is formulated as

$\underset{{\bm{\beta}}\in\mathbb{R}^{d}}{\rm{minimize}}~{}~{}\frac{1}{2}{\|{\bm{y}}-{\bm{X}}{\bm{\beta}}\|}_{2}^{2}+g({\bm{\beta}})$

where $g$ is a norm. Apparently, this is a subset of problems 2. Although this
formulation includes Lasso (Tibshirani, 1996), (overlapping) group-Lasso (Yuan
& Lin, 2006; Jacob et al., 2009), and ordered weighted L1 regression
(Figueiredo & Nowak, 2016), the non-negative Lasso is not included. To unify
them, we define the _Lasso-like_ problem as follows:

$\underset{{\bm{\beta}}\in\mathbb{R}^{d}}{\mathrm{minimize}}~{}~{}\frac{1}{2}{\|{\bm{y}}-{\bm{X}}{\bm{\beta}}\|}_{2}^{2}+g({\bm{\beta}}),$
(6)

where the problem satisfies all assumptions for Eq. (2) and $g$ satisfies

$\forall k\geq 0,{\bm{\beta}}\in\mathbb{R}^{d}\
g(k{\bm{\beta}})=kg({\bm{\beta}}).$ (7)

For the Lasso-like problem, the Fenchel conjugate function of $f$ and $g$ are
given as

$\displaystyle f^{\star}(-{\bm{\theta}})=$
$\displaystyle\frac{1}{2}{\|{\bm{\theta}}\|}_{2}^{2}-{\bm{y}}^{\top}{\bm{\theta}},$
(8) $\displaystyle g^{\star}({\bm{X}}^{\top}{\bm{\theta}})=$
$\displaystyle\begin{cases}0&(\forall{\bm{\beta}}\ \
{\bm{\theta}}^{\top}{\bm{X}}{\bm{\beta}}-g({\bm{\beta}})\leq 0)\\\
\infty&(\exists{\bm{\beta}}\ \
{\bm{\theta}}^{\top}{\bm{X}}{\bm{\beta}}-g({\bm{\beta}})>0).\end{cases}$ (9)

Note that $\\{{\bm{\theta}}\mid g^{\star}({\bm{X}}^{\top}{\bm{\theta}})=0\\}$
is a closed convex set. Hence, the Lasso-like problem is a class of problems
whose Fenchel-Rockafellar dual can be seen as a convex projection.

###  4.2 Proposed Dome Region for Lasso-like problem

Thanks to Theorem 6, we can construct a safe region by proposing an upper
bound $u({\bm{\theta}})$. In this section, we propose a tight upper bound for
Lasso-like problems.

The direct expression of $f^{\star}$ in Eq. (8) is sufficiently simple. We
only need an upper bound of $-g^{\star}$ to construct a simple region. The
upper bound is given as follows:

###### Lemma 9

For Lasso-like problems (6), for
$\forall\tilde{{\bm{\beta}}}\in\mathbb{R}^{d}$ and
$\forall{\bm{\theta}}\in\mathbb{R}^{n}$, we have

$\displaystyle-g^{\star}({\bm{X}}^{\top}{\bm{\theta}})$
$\displaystyle\leq\inf_{k\geq
0}g(k\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}(k\tilde{{\bm{\beta}}})$
$\displaystyle=\begin{cases}0&(g(\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}\geq
0)\\\
-\infty&(g(\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}<0).\\\
\end{cases}$ (10)

(Proof) Based on a Fenchel-Young inequality (1), we have

$-g^{\star}({\bm{X}}^{\top}{\bm{\theta}})\leq\inf_{k\geq
0}g(k\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}(k\tilde{{\bm{\beta}}}).$

Under the condition of Eq. (7), we have
$g(k\tilde{{\bm{\beta}}})=kg(\tilde{{\bm{\beta}}})$. Therefore, the optimal
value of the upper bound is zero if
$g(\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}(\tilde{{\bm{\beta}}})\geq
0$ and $-\infty$ otherwise. $\Box$

The next theorem can be directly derived from Lemma 9.

###### Theorem 10

Consider Lasso-like problems in Eq. (6). Let

$u^{\mathrm{DS}}({\bm{\theta}};\tilde{{\bm{\beta}}}):=\begin{cases}-f^{\star}(-{\bm{\theta}})&(g(\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}\geq
0)\\\
-\infty&(g(\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}<0)\end{cases}.$
(11)

Then, for $\forall\tilde{{\bm{\beta}}}\in\mathbb{R}^{d}$ and
$\forall{\bm{\theta}}\in\mathbb{R}^{n}$,

$D({\bm{\theta}})\leq u^{\mathrm{DS}}({\bm{\theta}};\tilde{{\bm{\beta}}}).$

Then, Theorem 7 provides a simple and safe region.

###### Theorem 11

Consider the Lasso-like problem in Eq. (6) and its Fenchel-Rockafellar dual
problem in Eq. (3). Let $\hat{{\bm{\theta}}}$ be the dual optimal point. We
assume that $\tilde{{\bm{\beta}}}\in\mathbb{R}^{d}$ and
$\tilde{{\bm{\theta}}}\in\mathrm{dom}(D)$. Then, $\hat{{\bm{\theta}}}$ is
within the Dynamic Sasvi region, which is given as an intersection of a sphere
and a half space:

$\displaystyle{\mathcal{R}}^{\mathrm{DS}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}})$
$\displaystyle:=$ $\displaystyle\\{{\bm{\theta}}\mid
l({\bm{\theta}};\tilde{{\bm{\theta}}})\leq
u^{\mathrm{DS}}({\bm{\theta}};\tilde{{\bm{\beta}}})\\},$ $\displaystyle=$
$\displaystyle\\{{\bm{\theta}}\mid{\left\|{\bm{\theta}}-\frac{1}{2}(\tilde{{\bm{\theta}}}+{\bm{y}})\right\|}_{2}^{2}\leq\frac{1}{4}{\|(\tilde{{\bm{\theta}}}-{\bm{y}})\|}_{2}^{2}$
. $\displaystyle\land 0\leq
g(\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}\\}.$

The proof of Theorem 11 is given in the Appendix. Because of continuity,
${\mathcal{R}}^{\mathrm{DS}}(\tilde{{\bm{\beta}}}^{(t)},\tilde{{\bm{\theta}}}^{(t)})$
converges to
${\mathcal{R}}^{\mathrm{DS}}(\hat{{\bm{\beta}}},\hat{{\bm{\theta}}})=\\{\hat{{\bm{\theta}}}\\}$
if $\lim_{t\to\infty}\tilde{{\bm{\beta}}}^{(t)}=\hat{{\bm{\beta}}}$ and
$\lim_{t\to\infty}\tilde{{\bm{\theta}}}^{(t)}=\hat{{\bm{\theta}}}$ hold.

###  4.3 Relation to Sasvi

In this section, we show that safe screening with variational inequality
(Sasvi) (Liu et al., 2014) is a special case of our screening rule. First, we
review Sasvi. The target task of Sasvi is to minimize
$\frac{1}{2}{\left\|{\bm{y}}-{\bm{X}}{\bm{\beta}}\right\|}_{2}^{2}+\lambda{\|{\bm{\beta}}\|}_{1}$
with many $\lambda$s. Divided by $\lambda^{2}$ and change optimization
variable, we obtain the following:

$\underset{{\bm{\beta}}\in\mathbb{R}^{d}}{\mathrm{minimize}}~{}~{}\frac{1}{2}{\left\|\frac{1}{\lambda}{\bm{y}}-{\bm{X}}{\bm{\beta}}\right\|}_{2}^{2}+{\|{\bm{\beta}}\|}_{1}.$

Let ${\hat{\bm{\beta}}}^{(\lambda)}$ and ${\hat{\bm{\theta}}}^{(\lambda)}$ be
the optimal points of the primal problem and the Fenchel-Rockafellar dual
problem, respectively. Sasvi uses ${\hat{\bm{\theta}}}^{(\lambda_{0})}$ to
construct a safe region for ${\hat{\bm{\theta}}}^{(\lambda)}$. Although Sasvi
was originally proposed for Lasso, it can be easily generalized for the Lasso-
like problem as follows.

###### Theorem 12

Let ${\hat{\bm{\theta}}}^{(\lambda)}$ be the optimal point of the Fenchel-
Rockafellar dual problem of the Lasso-like problem (that is, $g$ satisfies Eq.
(7))

$\underset{{\bm{\theta}}:g^{\star}({\bm{X}}^{\top}{\bm{\theta}})=0}{\mathrm{maximize}}~{}~{}-\frac{1}{2}{\|{\bm{\theta}}-\frac{1}{\lambda}{\bm{y}}\|}_{2}^{2}+\frac{1}{2}{\|\frac{1}{\lambda}{\bm{y}}\|}_{2}^{2}.$

Assume we have an exact ${\hat{\bm{\theta}}}^{(\lambda_{0})}$. We then have

$\displaystyle{\hat{\bm{\theta}}}^{(\lambda)}\in$
$\displaystyle{\mathcal{R}}^{\mathrm{Sasvi}}(\lambda,\lambda_{0})$
$\displaystyle:=$ $\displaystyle\\{{\bm{\theta}}\mid
0\geq{\left(\frac{1}{\lambda}{\bm{y}}-{\bm{\theta}}\right)}^{\top}\left({\hat{\bm{\theta}}}^{(\lambda_{0})}-{\bm{\theta}}\right)$
$\displaystyle\land
0\geq{\left(\frac{1}{\lambda_{0}}{\bm{y}}-{\hat{\bm{\theta}}}^{(\lambda_{0})}\right)}^{\top}\left({\bm{\theta}}-{\hat{\bm{\theta}}}^{(\lambda_{0})}\right)\\}$

(Proof) Because the duality of the Lasso-like problem can be interpreted as a
projection from $\frac{1}{\lambda}{\bm{y}}$ to a closed convex set
$\\{{\bm{\theta}}\mid g^{\star}({\bm{X}}^{\top}{\bm{\theta}})=0\\}$, two
variational inequalities hold. See (Liu et al., 2014) for more details. $\Box$

We can then prove that
${\mathcal{R}}^{\mathrm{Sasvi}}(\lambda_{0}):={\mathcal{R}}^{\mathrm{Sasvi}}(1,\lambda_{0})$
equals
${\mathcal{R}}^{\mathrm{DS}}({\hat{\bm{\beta}}}^{(\lambda_{0})},{\hat{\bm{\theta}}}^{(\lambda_{0})})$.
Note that we can set $\lambda=1$ without a loss of generality because
multiplying the same scalar to ${\bm{y}}$, $\lambda$, and $\lambda_{0}$ does
not change the problem or the region.

###### Theorem 13

Consider the Lasso-like problem

$\underset{{\bm{\beta}}\in\mathbb{R}^{d}}{\mathrm{minimize}}~{}~{}\frac{1}{2}{\left\|\frac{1}{\lambda}{\bm{y}}-{\bm{X}}{\bm{\beta}}\right\|}_{2}^{2}+g({\bm{\beta}}).$

Let ${\hat{\bm{\beta}}}^{(\lambda)}$ and ${\hat{\bm{\theta}}}^{(\lambda)}$ be
the primal/dual optimal points, respectively. We then have

${\mathcal{R}}^{\mathrm{Sasvi}}(\lambda_{0})={\mathcal{R}}^{\mathrm{DS}}({\hat{\bm{\beta}}}^{(\lambda_{0})},{\hat{\bm{\theta}}}^{(\lambda_{0})}).$

where ${\mathcal{R}}^{\mathrm{Sasvi}}(\lambda_{0})$ and
${\mathcal{R}}^{\mathrm{DS}}({\hat{\bm{\beta}}}^{(\lambda_{0})},{\hat{\bm{\theta}}}^{(\lambda_{0})})$
are safe regions for ${\hat{\bm{\theta}}}^{(1)}$.

The proof of Theorem 13 is given in the Appendix. For this reason, we have
labeled it ”Dynamic Sasvi.” This generalization increases the speed of the
solver significantly because the region of our method may be extremely narrow
in the late stage of optimization. As pointed out in (Fercoq et al., 2015),
some sequential safe screening rules, including Sasvi, are not safe in
practice because we do not have the exact solution for $\lambda_{0}$. Dynamic
Sasvi overcomes this problem because its region is safe if it is not the exact
solution.

###  4.4 Comparison to Gap Safe Dome and Gap Safe Sphere

(a) Regions of dynamic Sasvi (dark green) and dynamic EDPP (light green).

(b) Regions of dynamic Sasvi (green), Gap Safe Sphere (light red) and Gap Safe
Dome (dark red).

(c) Regions of dynamic EDPP (green), Gap Safe Sphere (light red), Gap Safe
Dome (dark red).

Figure 1: Comparisons of various safe regions for Lasso
(${\bm{X}}=\begin{pmatrix}2&0\\\ -1&3\\\ \end{pmatrix}$,
${\bm{y}}=\begin{pmatrix}1.5\\\ 1\\\ \end{pmatrix}$). The blue region is the
feasible region. $\tilde{{\bm{\beta}}}$ was obtained by a cycle of coordinate
descent. $\tilde{{\bm{\theta}}}=\phi(\tilde{{\bm{\beta}}})$.

Here, we show that the proposed method is stronger than Gap Safe Dome (Fercoq
et al., 2015) and Gap Safe Sphere (Fercoq et al., 2015), (Ndiaye et al., 2017)
for Lasso-like problems. As shown in (Fercoq et al., 2015), for Lasso, the
regions of the Gap Safe Dome and Gap Safe Sphere are the relaxation of the
intersection of a sphere and the contra of another sphere. We call this
unrelaxed region Gap Safe Moon. Although Gap Safe Moon is defined only for
Lasso in (Fercoq et al., 2015), it can be naturally generalized for Lasso-like
problems. Gap Safe Moon can be derived from Corollary 7.

###### Theorem 14

(Gap Safe Moon) Consider the Lasso-like problem in Eq. (6) and its dual
Fenchel-Rockafellar equation, i.e., Eq. (3). Let $\hat{{\bm{\theta}}}$ be the
dual optimal point. For $\tilde{{\bm{\beta}}}\in\mathbb{R}^{d}$, the Gap Safe
Moon upper bound is given as

$u^{\mathrm{GM}}({\bm{\theta}};\tilde{{\bm{\beta}}})=\begin{cases}-f^{\star}(-{\bm{\theta}})&(-f^{\star}(-{\bm{\theta}})\leq
P(\tilde{{\bm{\beta}}}))\\\
-\infty&(-f^{\star}(-{\bm{\theta}})>P(\tilde{{\bm{\beta}}}))\end{cases}.$ (12)

Then, for $\forall\tilde{{\bm{\beta}}}\in\mathbb{R}^{d}$,
$\forall\tilde{{\bm{\theta}}}\in\mathrm{dom}(D)$, and
$\forall{\bm{\theta}}\in\mathbb{R}^{n}$, we have

$D({\bm{\theta}})\leq u^{\mathrm{GM}}({\bm{\theta}};\tilde{{\bm{\beta}}})$

and hence

$\displaystyle\hat{{\bm{\theta}}}\in$ $\displaystyle\\{{\bm{\theta}}\mid
l({\bm{\theta}};\tilde{{\bm{\theta}}})\leq
u^{\mathrm{GM}}({\bm{\theta}};\tilde{{\bm{\beta}}})\\}$ $\displaystyle=$
$\displaystyle\\{{\bm{\theta}}\mid-f^{\star}(-{\bm{\theta}})\leq
P(\tilde{{\bm{\beta}}})\land{(\tilde{{\bm{\theta}}}-{\bm{\theta}})}^{\top}({\bm{y}}-{\bm{\theta}})\leq
0\\}.$

The proof of Theorem 14 is given in the Appendix. We can then derive the next
theorem.

###### Theorem 15

(Gap Safe Moon and Dynamic Sasvi) For
$\forall\tilde{{\bm{\beta}}}\in\mathbb{R}^{d}$ and
$\forall{\bm{\theta}}\in\mathbb{R}^{n}$, we have

$u^{\mathrm{DS}}({\bm{\theta}};\tilde{{\bm{\beta}}})\leq
u^{\mathrm{GM}}({\bm{\theta}};\tilde{{\bm{\beta}}}).$

(Proof) If
$g(\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}$ is
negative, $u^{\mathrm{DS}}({\bm{\theta}};\tilde{{\bm{\beta}}})=-\infty$, and
thus the inequality holds. If $0\leq
g(\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}$, by
adding the Fenchel-Young inequality (1), we have
$-f^{\star}(-{\bm{\theta}})\leq P(\tilde{{\bm{\beta}}})$ and
$u^{\mathrm{DS}}({\bm{\theta}};\tilde{{\bm{\beta}}})=u^{\mathrm{GM}}({\bm{\theta}};\tilde{{\bm{\beta}}})=-f^{\star}(-{\bm{\theta}})$.
$\Box$

This theorem means that the region of dynamic Sasvi is a subset of the region
of Gap Safe Moon. Because Gap Safe Dome and Gap Safe Sphere are based on the
relaxation of the Gap Safe Moon region, our screening is always stronger than
them. Figure 1(b) shows the regions of Dynamic Sasvi, Gap Safe Dome and Gap
Safe Sphere.

###  4.5 Sphere Relaxation (Dynamic EDPP)

In some situations, even a dome region is too complicated to calculate
$\bigcup_{{\bm{\theta}}\in{\mathcal{R}}}\partial
g^{\star}(-{\bm{X}}^{\top}{\bm{\theta}})$. We propose using a minimum radius
sphere that includes the dynamic Sasvi region in such cases. This method can
be seen as a dynamic variant of the enhanced dual polytope projections (EDPP)
(Wang et al., 2015) because the EDPP is the minimum radius sphere relaxation
of Sasvi.

###### Theorem 16

Consider the Lasso-like problem in Eq. (6) and its Fenchel-Rockafellar dual
problem in Eq. (3). We assume that $\tilde{{\bm{\beta}}}\in\mathbb{R}^{d}$ and
$\tilde{{\bm{\theta}}}\in\mathrm{dom}(D)$. If $n\geq 2$, the minimum radius
sphere including
${\mathcal{R}}^{\mathrm{DS}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}})$ is

${\mathcal{R}}^{\mathrm{DE}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}})=\\{{\bm{\theta}}\mid{\|{\bm{\theta}}-{\bm{\theta}}_{c}\|}_{2}^{2}\leq
r^{2}\\},$ (13)

where

$\displaystyle{\bm{\theta}}_{c}$
$\displaystyle=\frac{1}{2}(\tilde{{\bm{\theta}}}+{\bm{y}})-\alpha{\bm{X}}\tilde{{\bm{\beta}}}$
$\displaystyle r^{2}$
$\displaystyle=\frac{1}{4}{\|\tilde{{\bm{\theta}}}-{\bm{y}}\|}_{2}^{2}-\alpha^{2}{\|{\bm{X}}\tilde{{\bm{\beta}}}\|}_{2}^{2}$
$\displaystyle\alpha$
$\displaystyle=\max\left(0,\frac{1}{{\|{\bm{X}}\tilde{{\bm{\beta}}}\|}_{2}^{2}}\left(\frac{1}{2}{(\tilde{{\bm{\theta}}}+{\bm{y}})}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}-g(\tilde{{\bm{\beta}}})\right)\right).$

The proof of Theorem 16 is given in the Appendix. Figures 1(a) and 1(c) show
the dynamic EDPP region and other regions. Note that the dynamic EDPP region
is not guaranteed to be within the Gap Safe Sphere region. However, its radius
is always smaller than that of Gap Safe Sphere.

##  5 Implementation for Lasso

Algorithm 1 Coordinate descent with Dynamic Sasvi for Lasso

1: Input: ${\bm{X}},{\bm{y}},{\bm{\beta}}^{0},T,c,\epsilon$

2: Initialize $\tilde{{\bm{\beta}}}\leftarrow{\bm{\beta}}^{0}$,
${\mathcal{A}}\leftarrow[\\![d]\\!]$

3: for $t\in[\\![T]\\!]$ do

4: if $k\mod c=1$ then

5: Compute $\tilde{{\bm{\theta}}}=\phi_{\mathcal{A}}(\tilde{{\bm{\beta}}})$

6: if $P(\tilde{{\bm{\beta}}})-D(\tilde{{\bm{\theta}}})\leq\epsilon$ then

7: break

8: end if

9:
${\mathcal{R}}\leftarrow{\mathcal{R}}^{\mathrm{DS}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}})$

10:
${\mathcal{A}}\leftarrow\\{j\in{\mathcal{A}}:\max_{{\bm{\theta}}\in{\mathcal{R}}}|{\bm{x}}_{j}^{\top}{\bm{\theta}}|\geq
1\\}$

11: for $j\in[\\![d]\\!]-{\mathcal{A}}$ do

12: $\tilde{{\bm{\beta}}}_{j}\leftarrow 0$

13: end for

14: end if

15: for $j\in{\mathcal{A}}$ do

16:
$u\leftarrow\tilde{{\bm{\beta}}}_{j}{\|{\bm{x}}_{j}\|}_{2}^{2}-{\bm{x}}_{j}^{\top}({\bm{X}}\tilde{{\bm{\beta}}}-{\bm{y}})$

17:
$\tilde{{\bm{\beta}}}_{j}\leftarrow\frac{1}{{\|{\bm{x}}_{j}\|}_{2}^{2}}\text{sign}(u)\max(0,|u|-1)$

18: end for

19: end for

20: Output:$\tilde{{\bm{\beta}}}$

In this section, we provide a specific solver based on Theorem 11. Because the
algorithm used to calculate $\bigcup_{{\bm{\theta}}\in{\mathcal{R}}}\partial
g^{\star}({\bm{X}}^{\top}{\bm{\theta}})$ depends on $g$, we introduce a Lasso
solver as an example. We must choose an iterative solver to combine with
screening methods because they cannot estimate the solution alone. Although
our methods can work with any iterative method, we use coordinate descent,
which is recommended in (Friedman et al., 2007).

###  5.1 Choice of $\tilde{{\bm{\theta}}}$

As shown in the previous section,
$\lim_{t\to\infty}{\mathcal{R}}^{\mathrm{DS}}({\bm{\beta}}^{t},{\bm{\theta}}^{t})$
converges to $\\{\hat{{\bm{\theta}}}\\}$ when
$\lim_{t\to\infty}{\bm{\beta}}^{t}=\hat{{\bm{\beta}}}$ and
$\lim_{t\to\infty}{\bm{\theta}}^{t}=\hat{{\bm{\theta}}}$ holds. Because the
iterative solver provides such a sequence of primal points and screening does
not harm its convergence, we only need a converging sequence of dual points to
obtain a converging safe region. The next theorem provides such a sequence.

###### Theorem 17

(Converging ${\bm{\theta}}^{t}$) Consider the optimization problem Eq. (6)
with $g({\bm{\beta}})={\|{\bm{\beta}}\|}_{1}$. Let
$\hat{{\bm{\beta}}}\in\mathbb{R}^{d}$ and
$\hat{{\bm{\theta}}}\in\mathbb{R}^{n}$ be the primal/dual solution. Assume
$\lim_{t\to\infty}{\bm{\beta}}^{t}=\hat{{\bm{\beta}}}$. Let us define
$\phi:\mathbb{R}^{d}\to\mathbb{R}^{n}$ as

$\phi({\bm{\beta}}):=\frac{1}{\max(1,{\|{\bm{X}}^{\top}({\bm{y}}-{\bm{X}}{\bm{\beta}})\|}_{\infty})}({\bm{y}}-{\bm{X}}{\bm{\beta}}).$

Then, $\forall{\bm{\beta}}\ \phi({\bm{\beta}})\in\mathrm{dom}(D)$ and
$\lim_{t\to\infty}\phi({\bm{\beta}}^{t})=\hat{{\bm{\theta}}}$ hold.

(Proof) $\phi({\bm{\beta}})\in\mathrm{dom}(D)$ is directly derived from
${\|{\bm{X}}^{\top}\phi({\bm{\beta}})\|}_{\infty}=\min({\|{\bm{X}}^{\top}({\bm{y}}-{\bm{X}}{\bm{\beta}})\|}_{\infty},1)\leq
1$. Because $\phi$ is continuous and
$\phi(\hat{{\bm{\beta}}})=\hat{{\bm{\theta}}}$,
$\lim_{t\to\infty}\phi({\bm{\beta}}^{t})=\hat{{\bm{\theta}}}$ also holds.
$\Box$

Actually, if ${\mathcal{A}}$ is the set of features that is not yet
eliminated, we can use

$\phi_{\mathcal{A}}({\bm{\beta}}):=\frac{1}{\max(1,\max_{j\in{\mathcal{A}}}{\bm{x}}_{j}^{\top}({\bm{y}}-{\bm{X}}{\bm{\beta}}))}({\bm{X}}{\bm{\beta}}-{\bm{y}})$

instead of $\phi({\bm{\beta}})$. Although
$\phi_{\mathcal{A}}({\bm{\beta}})\in\mathrm{dom}(D)$ is not guaranteed,
$\phi_{\mathcal{A}}({\bm{\beta}})$ is guaranteed to satisfy all constraints
that are active in the dual solution. In other words,
$\phi_{\mathcal{A}}({\bm{\beta}})$ is in the domain of the dual problem of the
small primal problem without eliminated features.

Now, we can optimize the problem with the proposed screening. The pseudo code
is described in Algorithm 1. Direct expression of
$\max_{{\bm{\theta}}\in{\mathcal{R}}^{\mathrm{DS}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}})}|{\bm{x}}_{j}^{\top}{\bm{\theta}}|$
is given in the Appendix.

###  5.2 Computational Cost of Dynamic Sasvi Screening

In Dynamic Sasvi screening, the calculation of
$\phi_{\mathcal{A}}(\tilde{{\bm{\beta}}})$ and
$\max_{{\bm{\theta}}\in{\mathcal{R}}}|{\bm{x}}_{j}^{\top}{\bm{\theta}}|$
controls the computational cost. If we have ${\bm{X}}\tilde{{\bm{\beta}}}$,
${\bm{X}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}$, and ${\bm{X}}^{\top}{\bm{y}}$,
we can obtain $\phi_{\mathcal{A}}({\bm{\beta}})$ with $O(n+d)$ calculations.
If we have ${\bm{X}}\tilde{{\bm{\beta}}}$,
${\bm{X}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}$, $\tilde{{\bm{\theta}}}$,
${\bm{X}}^{\top}\tilde{{\bm{\theta}}}$, and ${\bm{X}}^{\top}{\bm{y}}$, we can
obtain
$\max_{{\bm{\theta}}\in{\mathcal{R}}}|{\bm{x}}_{j}^{\top}{\bm{\theta}}|$ for
all $j$ with $O(n+d)$ calculations. Because ${\bm{X}}^{\top}{\bm{y}}$ is
constant and $\tilde{{\bm{\theta}}}=\phi_{\mathcal{A}}(\tilde{{\bm{\beta}}})$
is a linear combination of ${\bm{X}}\tilde{{\bm{\beta}}}$ and ${\bm{y}}$, the
calculations of only ${\bm{X}}\tilde{{\bm{\beta}}}$ and
${\bm{X}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}$ cost $O(nd)$. Hence, the
screening cost is almost the same for all methods, which require
${\bm{X}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}$, including Gap Safe.

###  5.3 Computation of Lasso Path

In practice, we formulate the Lasso problem as follows:

$\underset{{\bm{\beta}}\in\mathbb{R}^{d}}{\rm{minimize}}~{}~{}\frac{1}{2}{\left\|\frac{1}{\lambda}{\bm{y}}-{\bm{X}}{\bm{\beta}}\right\|}_{2}^{2}+{\|{\bm{\beta}}\|}_{1}$

and solve for many values of $\lambda$ to choose the best solution.
Considering the situation in which we have to estimate the solutions
$\hat{{\bm{\beta}}}^{(\lambda_{1})},\hat{{\bm{\beta}}}^{(\lambda_{2})},\cdots,\hat{{\bm{\beta}}}^{(\lambda_{M})}$
corresponds to $\lambda_{1}>\lambda_{2}>\cdots>\lambda_{M}$. Many studies
(e.g., (Fercoq et al., 2015)) recommend using the estimated solution for
$\lambda_{m-1}$ as the initial vector in the estimation of
$\hat{{\bm{\beta}}}^{(\lambda_{m})}$ because
$\hat{{\bm{\beta}}}^{(\lambda_{m-1})}$ and
$\hat{{\bm{\beta}}}^{(\lambda_{m})}$ may be close. In our implementation, we
set the initial vector as $k\tilde{{\bm{\beta}}}^{(\lambda_{m-1})}$, where
$\tilde{{\bm{\beta}}}^{(\lambda_{m-1})}$ is the estimation of
$\hat{{\bm{\beta}}}^{(\lambda_{m-1})}$ and

$\displaystyle k:=$ $\displaystyle\mathop{\mathrm{argmin\,}}_{k\geq
0}\frac{1}{2}{\left\|\frac{1}{\lambda_{m}}{\bm{y}}-k{\bm{X}}\tilde{{\bm{\beta}}}^{(\lambda_{m-1})}\right\|}_{2}^{2}+k{\|\tilde{{\bm{\beta}}}^{(\lambda_{m-1})}\|}_{1}$
$\displaystyle=$
$\displaystyle\frac{1}{{\|{\bm{X}}\tilde{{\bm{\beta}}}^{(\lambda_{m-1})}\|}_{2}^{2}}({\|\tilde{{\bm{\beta}}}^{(\lambda_{m-1})}\|}_{1}-\frac{1}{\lambda_{m}}{\bm{y}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}^{(\lambda_{m-1})}).$

(a) Feature remaining rate (Leukemia).

(b) Computational time (Leukemia).

(c) Computational time (20newsgroup).

Figure 2: (a): Feature remaining rate of each iteration for Lasso on Leukemia (density $n=72,d=7128$). (b) Average computational time of Lasso path on subsampled Leukemia (density of $n=50,d=7128$). (c): Average computational time of Lasso path on subsampled 20newsgroup (sparsity of $n=800,d=18571$) Table 1: Logarithm of acceleration ratio for Leukemia and 20newsgroup. The smaller values indicate a greater speed up. Dataset | -log epsilon | Dynamic Sasvi | Dynamic EDPP | Gap Safe Dome | Gap Safe Sphere
---|---|---|---|---|---
Leukemia | 4 | $-0.468\pm 0.066$ | $-0.487\pm 0.066$ | $-0.349\pm 0.066$ | $-0.358\pm 0.060$
6 | $-0.828\pm 0.072$ | $-0.838\pm 0.067$ | $-0.719\pm 0.074$ | $-0.725\pm 0.072$
8 | $-0.987\pm 0.057$ | $-0.997\pm 0.056$ | $-0.902\pm 0.066$ | $-0.907\pm 0.066$
20newsgroup | 4 | $-0.338\pm 0.020$ | $-0.358\pm 0.025$ | $-0.274\pm 0.023$ | $-0.293\pm 0.024$
6 | $-0.517\pm 0.022$ | $-0.532\pm 0.022$ | $-0.463\pm 0.023$ | $-0.477\pm 0.025$
8 | $-0.604\pm 0.023$ | $-0.617\pm 0.025$ | $-0.562\pm 0.026$ | $-0.572\pm 0.024$

##  6 Experiments

In this section, we show the efficacy of the proposed methods using real-world
data.

###  6.1 Setup

We compared the proposed methods with Gap Safe Sphere and Gap Safe Dome
(Fercoq et al., 2015; Ndiaye et al., 2017), which are state-of-the-art dynamic
safe screening methods. All methods were run on a Macbook Air with a 1.1 GHz
quad-core Intel Core i5 CPU with 16 GB of RAM. We implemented all methods in
C++ using the Accelerate framework, which is the native framework for basic
calculations.

###  6.2 Number of screened variables

First, we compared the number of screened variables among the four dynamic
safe screening methods. We solved the Lasso problem using the Leukemia dataset
(dense data with 72 samples and 7128 features) and
$\lambda=\frac{1}{100}{\|{\bm{X}}^{\top}{\bm{y}}\|}_{\infty}$. We used cyclic
coordinate descent as the iterative algorithm and screen variables for 10
iterations each. Figure 2(a) shows the ratio of the uneliminated features at
each iteration. As guaranteed theoretically, we can see that Dynamic Sasvi
eliminates more variables in earlier steps than Gap Safe Dome and Gap Safe
Sphere. The figure also shows that Dynamic EDPP, relaxed version of Dynamic
Sasvi, eliminated almost the same number of features as Dynamic Sasvi.

###  6.3 Gains in the computation of Lasso paths

Next, we compared the computation time of the path of the Lasso solutions for
various values of $\lambda$. Because $\lambda$ may be defined by a cross
validation in practice, computing the path of the solutions is an important
task. We used
$\lambda_{j}={100}^{-\frac{j}{99}}{\|{\bm{X}}^{\top}{\bm{y}}\|}_{\infty}$
($j=0,\dots,99$). The iterative solver stops when the duality gap is smaller
than $\epsilon(P({\bm{0}})-D({\bm{0}}))$. Note that $P({\bm{0}})-D({\bm{0}})$
makes the stopping criterion independent of the data scale. We used the
Leukemia and tf-idf vectorized 20newsgroup datasets (baseball versus hockey)
(sparse data with 1197 samples and 18571 features). We subsampled the data 50
times and ran all methods for the same 50 subsamples. The subsampled data size
is 50 for leukemia and 800 for 20newsgroup. Figures 2(b) and 2(c) show the
average computation time of the Lasso path for the Leukemia dataset and 20news
datasets, respectively. For all settings, dynamic Sasvi and dynamic EDPP
outperform Gap Safe Dome and Gap Safe Sphere.

Table 1 shows the the average and standard deviations of the logarithm of the
acceleration ratio to the computational time for the same subsample without
screening. Proposed methods are significantly faster than Gap Safe methods. In
addition, Dynamic EDPP is a little faster than Dynamic Sasvi because the
computational cost of Dynamic EDPP screening is smaller than the one of
Dynamic Sasvi.

##  7 Conclusion

In this paper, we proposed a framework for safe screening based on Fenchel-
Rockafellar duality and derived Dynamic Sasvi and Dynamic EDPP, which are
specific safe screening methods for Lasso-like problems. Dynamic Sasvi and
Dynamic EDPP can be regarded as dynamic feature elimination variants of Sasvi
and EDPP, respectively. We proved that Dynamic Sasvi always eliminates more
features than Gap Safe Sphere and Gap Safe Dome. Dynamic EDPP is based on the
sphere relaxation of the Dynamic Sasvi region and eliminates almost the same
number of features as Dynamic Sasvi. We also showed experimentally that the
computational costs of the proposed methods are smaller than those of Gap Safe
Sphere and Gap SafeDome.

## References

  * Bao et al. (2020) Bao, R., Gu, B., and Huang, H.  Fast oscar and owl regression via safe screening rules.  In _ICML_ , 2020.
  * Bauschke et al. (2011) Bauschke, H. H., Combettes, P. L., et al.  _Convex analysis and monotone operator theory in Hilbert spaces_ , volume 408.  Springer, 2011.
  * Bonnefoy et al. (2015) Bonnefoy, A., Emiya, V., Ralaivola, L., and Gribonval, R.  Dynamic screening: Accelerating first-order algorithms for the lasso and group-lasso.  _IEEE Transactions on Signal Processing_ , 63(19):5121–5132, 2015.
  * Climente-González et al. (2019) Climente-González, H., Azencott, C.-A., Kaski, S., and Yamada, M.  Block hsic lasso: model-free biomarker detection for ultra-high dimensional data.  _Bioinformatics_ , 35(14):i427–i435, 2019.
  * Cortes & Vapnik (1995) Cortes, C. and Vapnik, V.  Support-vector networks.  _Machine learning_ , 20(3):273–297, 1995.
  * Donoho (2006) Donoho, D. L.  Compressed sensing.  _IEEE Transactions on information theory_ , 52(4):1289–1306, 2006.
  * Fan & Li (2001) Fan, J. and Li, R.  Variable selection via nonconcave penalized likelihood and its oracle properties.  _Journal of the American statistical Association_ , 96(456):1348–1360, 2001.
  * Fercoq et al. (2015) Fercoq, O., Gramfort, A., and Salmon, J.  Mind the duality gap: safer rules for the lasso.  In _ICML_ , 2015.
  * Figueiredo & Nowak (2016) Figueiredo, M. and Nowak, R.  Ordered weighted l1 regularized regression with strongly correlated covariates: Theoretical aspects.  In _AISTATS_ , 2016.
  * Frank & Friedman (1993) Frank, L. E. and Friedman, J. H.  A statistical view of some chemometrics regression tools.  _Technometrics_ , 35(2):109–135, 1993.
  * Friedman et al. (2007) Friedman, J., Hastie, T., Höfling, H., and Tibshirani, R.  Pathwise coordinate optimization.  _Ann. Appl. Stat._ , 1(2):302–332, 12 2007.
  * Ghaoui et al. (2010) Ghaoui, L. E., Viallon, V., and Rabbani, T.  Safe feature elimination for the lasso and sparse supervised learning problems.  _arXiv preprint arXiv:1009.4219_ , 2010.
  * Jacob et al. (2009) Jacob, L., Obozinski, G., and Vert, J.-P.  Group lasso with overlap and graph lasso.  In _ICML_ , 2009.
  * Liu et al. (2014) Liu, J., Zhao, Z., Wang, J., and Ye, J.  Safe screening with variational inequalities and its application to lasso.  In _ICML_ , 2014.
  * Meier et al. (2008) Meier, L., Van De Geer, S., and Bühlmann, P.  The group lasso for logistic regression.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 70(1):53–71, 2008.
  * Ndiaye et al. (2015) Ndiaye, E., Fercoq, O., Gramfort, A., and Salmon, J.  Gap safe screening rules for sparse multi-task and multi-class models.  In _NIPS_ , 2015.
  * Ndiaye et al. (2017) Ndiaye, E., Fercoq, O., Gramfort, A., and Salmon, J.  Gap safe screening rules for sparsity enforcing penalties.  _Journal of Machine Learning Research_ , 18(1):4671–4703, 2017.
  * Ndiaye et al. (2020) Ndiaye, E., Fercoq, O., and Salmon, J.  Screening rules and its complexity for active set identification, 2020\.
  * Ogawa et al. (2013) Ogawa, K., Suzuki, Y., and Takeuchi, I.  Safe screening of non-support vectors in pathwise svm computation.  In _ICML_ , 2013.
  * Raj et al. (2016) Raj, A., Olbrich, J., Gärtner, B., Schölkopf, B., and Jaggi, M.  Screening rules for convex problems.  _arXiv preprint arXiv:1609.07478_ , 2016.
  * Shibagaki et al. (2016) Shibagaki, A., Karasuyama, M., Hatano, K., and Takeuchi, I.  Simultaneous safe screening of features and samples in doubly sparse modeling.  In _ICML_ , 2016.
  * Smola & Schölkopf (2004) Smola, A. J. and Schölkopf, B.  A tutorial on support vector regression.  _Statistics and computing_ , 14(3):199–222, 2004\.
  * Tibshirani (1996) Tibshirani, R.  Regression shrinkage and selection via the lasso.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 58(1):267–288, 1996.
  * Wang et al. (2015) Wang, J., Wonka, P., and Ye, J.  Lasso screening rules via dual polytope projection.  _Journal of Machine Learning Research_ , 16(1):1063–1101, 2015.
  * Xiang et al. (2017) Xiang, Z. J., Wang, Y., and Ramadge, P. J.  Screening tests for lasso problems.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 39(5):1008–1027, May 2017.
  * Yuan & Lin (2006) Yuan, M. and Lin, Y.  Model selection and estimation in regression with grouped variables.  _Journal of the Royal Statistical Society Series B_ , 68:49–67, 02 2006.
  * Zhang et al. (2010) Zhang, C.-H. et al.  Nearly unbiased variable selection under minimax concave penalty.  _The Annals of statistics_ , 38(2):894–942, 2010\.
  * Zou & Hastie (2005) Zou, H. and Hastie, T.  Regularization and variable selection via the elastic net.  _Journal of the royal statistical society: series B (statistical methodology)_ , 67(2):301–320, 2005.

##  Appendix A Proof of Theorems

###  A.1 Proof of Theorem 2

(Proof) According to ((Bauschke et al., 2011) Theorem 15.23), since we have
assumed that

$\exists{\bm{\beta}}\in\mathrm{relint}(\mathrm{dom}(g))\ \mathrm{s.t.}\
{\bm{X}}{\bm{\beta}}\in\mathrm{relint}(\mathrm{dom}(f)),$

i.e.,
$\mathrm{relint}(\mathrm{dom}(f))\cap{\bm{X}}\mathrm{relint}(\mathrm{dom}(g))$
is not empty, we have

$\inf_{{\bm{\beta}}\in\mathbb{R}^{d}}f({\bm{X}}{\bm{\beta}})+g({\bm{\beta}})=\max_{{\bm{\theta}}\in\mathbb{R}^{n}}-f^{\star}(-{\bm{\theta}})-g^{\star}({\bm{X}}^{\top}{\bm{\theta}}).$

In addition, we have assumed the existence of the optimal point. Hence, we
have

$\min_{{\bm{\beta}}\in\mathbb{R}^{d}}f({\bm{X}}{\bm{\beta}})+g({\bm{\beta}})=\max_{{\bm{\theta}}\in\mathbb{R}^{n}}-f^{\star}(-{\bm{\theta}})-g^{\star}({\bm{X}}^{\top}{\bm{\theta}}).$

$\Box$

###  A.2 Proof of Theorem 11

(Proof) According to Theorem 7, we can easily obtain

$\hat{{\bm{\theta}}}\in{\mathcal{R}}^{\mathrm{DS}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}}):=\\{{\bm{\theta}}\mid
l({\bm{\theta}};\tilde{{\bm{\theta}}})\leq
u^{\mathrm{DS}}({\bm{\theta}};\tilde{{\bm{\beta}}})\\}.$

By the definition of $u^{\mathrm{DS}}$, we have the following:

$l({\bm{\theta}};\tilde{{\bm{\theta}}})\leq
u^{\mathrm{DS}}({\bm{\theta}};\tilde{{\bm{\beta}}})\iff
l({\bm{\theta}};\tilde{{\bm{\theta}}})\leq-f^{\star}(-{\bm{\theta}})\land
0\leq
g(\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}.$

In addition, by Eqs. (8), $g^{\star}({\bm{X}}^{\top}\tilde{{\bm{\theta}}})=0$
and $L=1$, we have

$\displaystyle
l({\bm{\theta}};\tilde{{\bm{\theta}}})\leq-f^{\star}(-{\bm{\theta}})\iff$
$\displaystyle\frac{1}{2}{\|{\bm{\theta}}-\tilde{{\bm{\theta}}}\|}_{2}^{2}-\frac{1}{2}{\|\tilde{{\bm{\theta}}}\|}_{2}^{2}+{\bm{y}}^{\top}\tilde{{\bm{\theta}}}\leq-\frac{1}{2}{\|{\bm{\theta}}\|}_{2}^{2}+{\bm{y}}^{\top}{\bm{\theta}}$
$\displaystyle\iff$
$\displaystyle{\|{\bm{\theta}}\|}_{2}^{2}-{\bm{\theta}}^{\top}(\tilde{{\bm{\theta}}}+{\bm{y}})\leq-{\bm{y}}^{\top}\tilde{{\bm{\theta}}}$
$\displaystyle\iff$
$\displaystyle{\|{\bm{\theta}}-\frac{1}{2}(\tilde{{\bm{\theta}}}+{\bm{y}})\|}_{2}^{2}\leq\frac{1}{4}{\|(\tilde{{\bm{\theta}}}-{\bm{y}})\|}_{2}^{2}.$

Hence, we have

$\hat{{\bm{\theta}}}\in{\mathcal{R}}^{\mathrm{DS}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}}):=\\{{\bm{\theta}}\mid
l({\bm{\theta}};\tilde{{\bm{\theta}}})\leq
u^{\mathrm{DS}}({\bm{\theta}};\tilde{{\bm{\beta}}})\\}=\\{{\bm{\theta}}\mid{\|{\bm{\theta}}-\frac{1}{2}(\tilde{{\bm{\theta}}}+{\bm{y}})\|}_{2}^{2}\leq\frac{1}{4}{\|(\tilde{{\bm{\theta}}}-{\bm{y}})\|}_{2}^{2}\land
0\leq
g(\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}\\}.$

$\Box$

###  A.3 Proof of Theorem 13

(Proof) First, we prove
$g({\hat{\bm{\beta}}}^{(\lambda_{0})})={\hat{\bm{\theta}}}^{(\lambda_{0})\top}{\bm{X}}{\hat{\bm{\beta}}}^{(\lambda_{0})}$.
Because ${\bm{X}}^{\top}{\hat{\bm{\theta}}}^{(\lambda_{0})}\in\partial
g({\hat{\bm{\beta}}}^{(\lambda_{0})})$ (Proposition 3), for
$\forall{\bm{\beta}}$, the inequality

$g({\hat{\bm{\beta}}}^{(\lambda_{0})})+{\hat{\bm{\theta}}}^{(\lambda_{0})\top}{\bm{X}}({\bm{\beta}}-{\hat{\bm{\beta}}}^{(\lambda_{0})})\leq
g({\bm{\beta}})$

holds. We can set ${\bm{\beta}}={\bm{0}}$ and
${\bm{\beta}}=2{\hat{\bm{\beta}}}^{(\lambda_{0})}$ and obtain

$\displaystyle
g({\hat{\bm{\beta}}}^{(\lambda_{0})})-{\hat{\bm{\theta}}}^{(\lambda_{0})\top}{\bm{X}}{\hat{\bm{\beta}}}^{(\lambda_{0})}\leq$
$\displaystyle 0$ $\displaystyle
g({\hat{\bm{\beta}}}^{(\lambda_{0})})+{\hat{\bm{\theta}}}^{(\lambda_{0})\top}{\bm{X}}{\hat{\bm{\beta}}}^{(\lambda_{0})}\leq$
$\displaystyle 2g({\hat{\bm{\beta}}}^{(\lambda_{0})}).$

Hence, we have
$g({\hat{\bm{\beta}}}^{(\lambda_{0})})={\hat{\bm{\theta}}}^{(\lambda_{0})\top}{\bm{X}}{\hat{\bm{\beta}}}^{(\lambda_{0})}$.

In addition,
${\hat{\bm{\theta}}}^{(\lambda_{0})}=\frac{1}{\lambda_{0}}{\bm{y}}-{\bm{X}}{\hat{\bm{\beta}}}^{(\lambda_{0})}$
holds (Proposition 3).

We then have

$\displaystyle{\mathcal{R}}^{\mathrm{DS}}({\hat{\bm{\beta}}}^{(\lambda_{0})},{\hat{\bm{\theta}}}^{(\lambda_{0})})=$
$\displaystyle\\{{\bm{\theta}}\mid{\|{\bm{\theta}}-\frac{1}{2}({\hat{\bm{\theta}}}^{(\lambda_{0})}+{\bm{y}})\|}_{2}^{2}\leq\frac{1}{4}{\|({\hat{\bm{\theta}}}^{(\lambda_{0})}-{\bm{y}})\|}_{2}^{2}\land
0\leq
g({\hat{\bm{\beta}}}^{(\lambda_{0})})-{\bm{\theta}}^{\top}{\bm{X}}{\hat{\bm{\beta}}}^{(\lambda_{0})}\\}$
$\displaystyle=$
$\displaystyle\\{{\bm{\theta}}\mid{\|{\bm{\theta}}\|}_{2}^{2}-{\bm{\theta}}^{\top}({\hat{\bm{\theta}}}^{(\lambda_{0})}+{\bm{y}})+\frac{1}{4}{\|({\hat{\bm{\theta}}}^{(\lambda_{0})}+{\bm{y}})\|}_{2}^{2}\leq\frac{1}{4}{\|({\hat{\bm{\theta}}}^{(\lambda_{0})}-{\bm{y}})\|}_{2}^{2}\land
0\leq{({\hat{\bm{\theta}}}^{(\lambda_{0})}-{\bm{\theta}})}^{\top}{\bm{X}}{\hat{\bm{\beta}}}^{(\lambda_{0})}\\}$
$\displaystyle=$
$\displaystyle\\{{\bm{\theta}}\mid{\|{\bm{\theta}}\|}_{2}^{2}-{\bm{\theta}}^{\top}({\hat{\bm{\theta}}}^{(\lambda_{0})}+{\bm{y}})+{\bm{y}}^{\top}{\hat{\bm{\theta}}}^{(\lambda_{0})}\leq
0\land
0\leq{({\hat{\bm{\theta}}}^{(\lambda_{0})}-{\bm{\theta}})}^{\top}(\frac{1}{\lambda_{0}}{\bm{y}}-{\hat{\bm{\theta}}}^{(\lambda_{0})})\\}$
$\displaystyle=$
$\displaystyle\\{{\bm{\theta}}\mid{({\bm{y}}-{\bm{\theta}})}^{\top}({\hat{\bm{\theta}}}^{(\lambda_{0})}-{\bm{\theta}})\leq
0\land{(\frac{1}{\lambda_{0}}{\bm{y}}-{\hat{\bm{\theta}}}^{(\lambda_{0})})}^{\top}({\bm{\theta}}-{\hat{\bm{\theta}}}^{(\lambda_{0})})\leq
0\\}$ $\displaystyle=$
$\displaystyle{\mathcal{R}}^{\mathrm{Sasvi}}(1,\lambda_{0})={\mathcal{R}}^{\mathrm{Sasvi}}(\lambda_{0})$

$\Box$

###  A.4 Proof of Theorem 14

(Proof) By Eq. (9), we have
$D({\bm{\theta}})\in\\{-\infty,-f^{\star}(-{\bm{\theta}})\\}$. Clearly, the
inequality $D({\bm{\theta}})\leq-f^{\star}(-{\bm{\theta}})$ always holds. If
$-f^{\star}(-{\bm{\theta}})>P(\tilde{{\bm{\beta}}})$, $D({\bm{\theta}})$ must
be $-\infty$ because $D({\bm{\theta}})\leq P(\tilde{{\bm{\beta}}})$. Hence, we
have $D({\bm{\theta}})\leq
u^{\mathrm{GM}}({\bm{\theta}};\tilde{{\bm{\beta}}})$. According to Theorem 7,
we have

$\displaystyle\hat{{\bm{\theta}}}\in$ $\displaystyle\\{{\bm{\theta}}\mid
l({\bm{\theta}};\tilde{{\bm{\theta}}})\leq
u^{\mathrm{GM}}({\bm{\theta}};\tilde{{\bm{\beta}}})\\}$ $\displaystyle=$
$\displaystyle\\{{\bm{\theta}}\mid-f^{\star}(-{\bm{\theta}})\leq
P(\tilde{{\bm{\beta}}})\land\frac{1}{2}{\|{\bm{\theta}}-\tilde{{\bm{\theta}}}\|}_{2}^{2}-f^{\star}(-\tilde{{\bm{\theta}}})-g^{\star}({\bm{X}}^{\top}\tilde{{\bm{\theta}}})\leq-f^{\star}(-{\bm{\theta}})\\}$
$\displaystyle=$
$\displaystyle\\{{\bm{\theta}}\mid-f^{\star}(-{\bm{\theta}})\leq
P(\tilde{{\bm{\beta}}})\land\frac{1}{2}{\|{\bm{\theta}}-\tilde{{\bm{\theta}}}\|}_{2}^{2}-\frac{1}{2}{\|\tilde{{\bm{\theta}}}\|}_{2}^{2}+{\bm{y}}^{\top}\tilde{{\bm{\theta}}}\leq-\frac{1}{2}{\|{\bm{\theta}}\|}_{2}^{2}+{\bm{y}}^{\top}{\bm{\theta}}\\}$
$\displaystyle=$
$\displaystyle\\{{\bm{\theta}}\mid-f^{\star}(-{\bm{\theta}})\leq
P(\tilde{{\bm{\beta}}})\land{\|{\bm{\theta}}\|}_{2}^{2}-{\bm{\theta}}^{\top}\tilde{{\bm{\theta}}}+{\bm{y}}^{\top}\tilde{{\bm{\theta}}}\leq{\bm{y}}^{\top}{\bm{\theta}}\\}$
$\displaystyle=$
$\displaystyle\\{{\bm{\theta}}\mid-f^{\star}(-{\bm{\theta}})\leq
P(\tilde{{\bm{\beta}}})\land{(\tilde{{\bm{\theta}}}-{\bm{\theta}})}^{\top}({\bm{y}}-{\bm{\theta}})\leq
0\\}$

$\Box$

###  A.5 Proof of Theorem 16

Proof of
${\mathcal{R}}^{\mathrm{DS}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}})\subset{\mathcal{R}}^{\mathrm{DE}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}})$:

(Proof) Since $\alpha\geq 0$, we have

$\displaystyle{\mathcal{R}}^{\mathrm{DS}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}})=$
$\displaystyle\\{{\bm{\theta}}\mid{\|{\bm{\theta}}-\frac{1}{2}(\tilde{{\bm{\theta}}}+{\bm{y}})\|}_{2}^{2}\leq\frac{1}{4}{\|(\tilde{{\bm{\theta}}}-{\bm{y}})\|}_{2}^{2}\land
0\leq
g(\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}\\}$
$\displaystyle\subset$
$\displaystyle\\{{\bm{\theta}}\mid{\|{\bm{\theta}}-\frac{1}{2}(\tilde{{\bm{\theta}}}+{\bm{y}})\|}_{2}^{2}\leq\frac{1}{4}{\|(\tilde{{\bm{\theta}}}-{\bm{y}})\|}_{2}^{2}+2\alpha(g(\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}})\\}$
$\displaystyle=$
$\displaystyle\\{{\bm{\theta}}\mid{\|{\bm{\theta}}\|}_{2}^{2}-{\bm{\theta}}^{\top}(\tilde{{\bm{\theta}}}+{\bm{y}})+2\alpha{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}\leq\frac{1}{4}{\|(\tilde{{\bm{\theta}}}-{\bm{y}})\|}_{2}^{2}-\frac{1}{4}{\|\tilde{{\bm{\theta}}}+{\bm{y}}\|}_{2}^{2}+2\alpha
g(\tilde{{\bm{\beta}}})\\}$ $\displaystyle=$
$\displaystyle\\{{\bm{\theta}}\mid{\|{\bm{\theta}}-\frac{1}{2}(\tilde{{\bm{\theta}}}+{\bm{y}})+\alpha{\bm{X}}\tilde{{\bm{\beta}}}\|}_{2}^{2}\leq\frac{1}{4}{\|(\tilde{{\bm{\theta}}}-{\bm{y}})\|}_{2}^{2}-\frac{1}{4}{\|\tilde{{\bm{\theta}}}+{\bm{y}}\|}_{2}^{2}+{\|\frac{1}{2}(\tilde{{\bm{\theta}}}+{\bm{y}})-\alpha{\bm{X}}\tilde{{\bm{\beta}}}\|}_{2}^{2}+2\alpha
g(\tilde{{\bm{\beta}}})\\}$ $\displaystyle=$
$\displaystyle\\{{\bm{\theta}}\mid{\|{\bm{\theta}}-\frac{1}{2}(\tilde{{\bm{\theta}}}+{\bm{y}})+\alpha{\bm{X}}\tilde{{\bm{\beta}}}\|}_{2}^{2}\leq\frac{1}{4}{\|(\tilde{{\bm{\theta}}}-{\bm{y}})\|}_{2}^{2}+\alpha^{2}{\|{\bm{X}}\tilde{{\bm{\beta}}}\|}_{2}^{2}-\alpha{(\tilde{{\bm{\theta}}}+{\bm{y}})}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}+2\alpha
g(\tilde{{\bm{\beta}}})\\}.$

And by
$\alpha\in\\{0,\frac{1}{{\|{\bm{X}}\tilde{{\bm{\beta}}}\|}_{2}^{2}}(\frac{1}{2}{(\tilde{{\bm{\theta}}}+{\bm{y}})}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}-g(\tilde{{\bm{\beta}}}))\\}$,
we have

$\alpha^{2}{\|{\bm{X}}\tilde{{\bm{\beta}}}\|}_{2}^{2}-\alpha{(\tilde{{\bm{\theta}}}+{\bm{y}})}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}+2\alpha
g(\tilde{{\bm{\beta}}})=-\alpha^{2}{\|{\bm{X}}\tilde{{\bm{\beta}}}\|}_{2}^{2}.$

Hence,

$\displaystyle{\mathcal{R}}^{\mathrm{DS}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}})\subset$
$\displaystyle\\{{\bm{\theta}}\mid{\|{\bm{\theta}}-\frac{1}{2}(\tilde{{\bm{\theta}}}+{\bm{y}})+\alpha{\bm{X}}\tilde{{\bm{\beta}}}\|}_{2}^{2}\leq\frac{1}{4}{\|(\tilde{{\bm{\theta}}}-{\bm{y}})\|}_{2}^{2}-\alpha^{2}{\|{\bm{X}}\tilde{{\bm{\beta}}}\|}_{2}^{2}\\}$
$\displaystyle=$
$\displaystyle\\{{\bm{\theta}}\mid{\|{\bm{\theta}}-{\bm{\theta}}_{c}\|}_{2}^{2}\leq
r^{2}\\}$ $\displaystyle=$
$\displaystyle{\mathcal{R}}^{\mathrm{DE}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}})$

holds. $\Box$

Proof of minimality of the radius:

(Proof) Let ${\bm{v}}\in\mathbb{R}^{n}$ be a vector which satisfies
${\bm{v}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}=0$ and
${\bm{v}}^{\top}{\bm{v}}=1$. Note that such a vector exists if $n\geq 2$.
Then, we have ${\bm{\theta}}_{c}\pm
r{\bm{v}}\in{\mathcal{R}}^{\mathrm{DS}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}})$
because

${({\bm{\theta}}_{c}\pm
r{\bm{v}})}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}=\frac{1}{2}{(\tilde{{\bm{\theta}}}+{\bm{y}})}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}-\max(0,\frac{1}{2}{(\tilde{{\bm{\theta}}}+{\bm{y}})}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}-g(\tilde{{\bm{\beta}}}))\leq
g(\tilde{{\bm{\beta}}})$

and

${\|{\bm{\theta}}_{c}\pm
r{\bm{v}}-\frac{1}{2}(\tilde{{\bm{\theta}}}+{\bm{y}})\|}_{2}^{2}={\|-\alpha{\bm{X}}\tilde{{\bm{\beta}}}\pm
r{\bm{v}}\|}_{2}^{2}=\frac{1}{4}{\|(\tilde{{\bm{\theta}}}-{\bm{y}})\|}_{2}^{2}$

hold. Since the distance between these two points is $2r$, the radius of a
sphere which includes
${\mathcal{R}}^{\mathrm{DS}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}})$ can
not be smaller than $r$. $\Box$

##  Appendix B Direct Expression of
$\max_{{\bm{\theta}}\in{\mathcal{R}}^{\mathrm{DS}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}})}{\bm{x}}_{j}^{\top}{\bm{\theta}}$

Let $r=\frac{1}{2}{\|\tilde{{\bm{\theta}}}-{\bm{y}}\|}_{2}$ and
${\bm{\theta}}_{o}=\frac{1}{2}(\tilde{{\bm{\theta}}}+{\bm{y}})$.

If
${({\bm{\theta}}_{o}+\frac{r}{{\|{\bm{x}}_{j}\|}_{2}}{\bm{x}}_{j})}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}\leq
g(\tilde{{\bm{\beta}}})$,
$\mathop{\mathrm{argmax\,}}_{{\bm{\theta}}\in{\mathcal{R}}^{\mathrm{DS}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}})}{\bm{x}}_{j}^{\top}{\bm{\theta}}={\bm{\theta}}_{o}+\frac{r}{{\|{\bm{x}}_{j}\|}_{2}}{\bm{x}}_{j}$
and
$\max_{{\bm{\theta}}\in{\mathcal{R}}^{\mathrm{DS}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}})}{\bm{x}}_{j}^{\top}{\bm{\theta}}={\bm{x}}_{j}^{\top}{\bm{\theta}}_{o}+r{\|{\bm{x}}_{j}\|}_{2}$.

If
${({\bm{\theta}}_{o}+\frac{r}{{\|{\bm{x}}_{j}\|}_{2}}{\bm{x}}_{j})}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}>g(\tilde{{\bm{\beta}}})$,
the constraint ${\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}\leq
g(\tilde{{\bm{\beta}}})$ guaranteed to be active at the solution. Hence, we
have

$\displaystyle\max_{{\bm{\theta}}\in{\mathcal{R}}^{\mathrm{DS}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}})}{\bm{x}}_{j}^{\top}{\bm{\theta}}$
$\displaystyle=$
$\displaystyle\max_{{\|{\bm{\theta}}-{\bm{\theta}}_{o}\|}_{2}^{2}\leq
r^{2}\land{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}=g(\tilde{{\bm{\beta}}})}{\bm{x}}_{j}^{\top}{\bm{\theta}}$
$\displaystyle=$
$\displaystyle{\bm{x}}_{j}^{\top}{\bm{\theta}}_{o}+\frac{{\bm{x}}_{j}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}}{{\|{\bm{X}}\tilde{{\bm{\beta}}}\|}_{2}^{2}}(g(\tilde{{\bm{\beta}}})-{\bm{\theta}}_{o}^{\top}{\bm{X}}\tilde{{\bm{\beta}}})+\max_{{\|{\bm{\theta}}^{\prime}\|}_{2}^{2}\leq
r^{2}\land{{\bm{\theta}}^{\prime}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}=g(\tilde{{\bm{\beta}}})-{\bm{\theta}}_{o}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}}{\left({\bm{x}}_{j}-\frac{{\bm{x}}_{j}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}}{{\|{\bm{X}}\tilde{{\bm{\beta}}}\|}_{2}^{2}}{\bm{X}}\tilde{{\bm{\beta}}}\right)}^{\top}{\bm{\theta}}^{\prime}$
$\displaystyle=$
$\displaystyle{\bm{x}}_{j}^{\top}{\bm{\theta}}_{o}+\frac{{\bm{x}}_{j}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}}{{\|{\bm{X}}\tilde{{\bm{\beta}}}\|}_{2}^{2}}(g(\tilde{{\bm{\beta}}})-{\bm{\theta}}_{o}^{\top}{\bm{X}}\tilde{{\bm{\beta}}})+{\left\|{\bm{x}}_{j}-\frac{{\bm{x}}_{j}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}}{{\|{\bm{X}}\tilde{{\bm{\beta}}}\|}_{2}^{2}}{\bm{X}}\tilde{{\bm{\beta}}}\right\|}_{2}\sqrt{r^{2}-\frac{1}{{\|{\bm{X}}\tilde{{\bm{\beta}}}\|}_{2}^{2}}{(g(\tilde{{\bm{\beta}}})-{\bm{\theta}}_{o}^{\top}{\bm{X}}\tilde{{\bm{\beta}}})}^{2}}.$

Let
$\delta=g(\tilde{{\bm{\beta}}})-{\bm{\theta}}_{o}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}$.
we then have

$\max_{{\bm{\theta}}\in{\mathcal{R}}^{\mathrm{DS}}(\tilde{{\bm{\beta}}},\tilde{{\bm{\theta}}})}{\bm{x}}_{j}^{\top}{\bm{\theta}}=\begin{cases}{\bm{x}}_{j}^{\top}{\bm{\theta}}_{o}+r{\|{\bm{x}}_{j}\|}_{2}&(\frac{r}{{\|{\bm{x}}_{j}\|}_{2}}{\bm{x}}_{j}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}\leq\delta)\\\
{\bm{x}}_{j}^{\top}{\bm{\theta}}_{o}+\frac{{\bm{x}}_{j}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}}{{\|{\bm{X}}\tilde{{\bm{\beta}}}\|}_{2}^{2}}\delta+{\left\|{\bm{x}}_{j}-\frac{{\bm{x}}_{j}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}}{{\|{\bm{X}}\tilde{{\bm{\beta}}}\|}_{2}^{2}}{\bm{X}}\tilde{{\bm{\beta}}}\right\|}_{2}\sqrt{r^{2}-\frac{1}{{\|{\bm{X}}\tilde{{\bm{\beta}}}\|}_{2}^{2}}\delta^{2}}&(\frac{r}{{\|{\bm{x}}_{j}\|}_{2}}{\bm{x}}_{j}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}>\delta)\end{cases}$

##  Appendix C Regions for other problems

According to Theorem 7, we can construct simple safe region by constructing
simple upperbound of $D({\bm{\theta}})$. Herein, we introduce some regions for
non Lasso-like problems.

Elastic-Net: Consider the following problem:

$\underset{{\bm{\beta}}\in\mathbb{R}^{d}}{\mathrm{minimize}}~{}~{}\frac{1}{2}{\|{\bm{y}}-{\bm{X}}{\bm{\beta}}\|}_{2}^{2}+g({\bm{\beta}}),$

where
$g({\bm{\beta}})={\|{\bm{\beta}}\|}_{1}+\frac{\gamma}{2}{\|{\bm{\beta}}\|}_{2}^{2}$
and $\gamma>0$. Then, for $\forall\tilde{{\bm{\beta}}}$, we have

$\displaystyle-g^{\star}({\bm{X}}^{\top}{\bm{\theta}})\leq$
$\displaystyle\inf_{k\geq
0}g(k\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}(k\tilde{{\bm{\beta}}})$
$\displaystyle=$ $\displaystyle\inf_{k\geq
0}k({\|\tilde{{\bm{\beta}}}\|}_{1}-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}})+\frac{\gamma
k^{2}}{2}{\|\tilde{{\bm{\beta}}}\|}_{2}^{2}$ $\displaystyle=$
$\displaystyle\begin{cases}0&({\|\tilde{{\bm{\beta}}}\|}_{1}-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}\geq
0)\\\
-\frac{{({\|\tilde{{\bm{\beta}}}\|}_{1}-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}})}^{2}}{2\gamma{\|\tilde{{\bm{\beta}}}\|}_{2}^{2}}&({\|\tilde{{\bm{\beta}}}\|}_{1}-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}<0).\\\
\end{cases}$

Because this is stronger than the Fenchel–Young inequality in Eq. (1), the
region derived from it and Eq. (8),

$\left\\{{\bm{\theta}}\mid
l({\bm{\theta}};\tilde{{\bm{\theta}}})\leq-\frac{1}{2}{\|{\bm{\theta}}-{\bm{y}}\|}_{2}^{2}+\frac{1}{2}{\|{\bm{y}}\|}_{2}^{2}-\frac{{\min(0,{\|\tilde{{\bm{\beta}}}\|}_{1}-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}})}^{2}}{2\gamma{\|\tilde{{\bm{\beta}}}\|}_{2}^{2}}\right\\},$

is narrower than the region of Gap Safe Sphere. Since this region is a little
complex, we propose to use the sphere relaxation.

General regularized least squares: Except for Elastic-Net, there are many
regularizers that do not satisfy Eq. (7), e.g., squared L1 regularization. In
addition, the dual problem of SVM can be seen as the regularized least
squares. In those cases, we propose using the upper bound

$D({\bm{\theta}})\leq-\frac{1}{2}{\|{\bm{\theta}}-{\bm{y}}\|}_{2}^{2}+\frac{1}{2}{\|{\bm{y}}\|}_{2}^{2}+g(\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}.$

This is based on the Fenchel–Young inequality for $g$ and Eq. (8). Note that
the region

$\\{{\bm{\theta}}\mid
l({\bm{\theta}};\tilde{{\bm{\theta}}})\leq-\frac{1}{2}{\|{\bm{\theta}}-{\bm{y}}\|}_{2}^{2}+\frac{1}{2}{\|{\bm{y}}\|}_{2}^{2}+g(\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}\\}$

is a sphere in the Gap Safe Sphere region.

General norm regularized problems: Here, we extend $f$ to a more general
setup, e.g., the logistic loss. Assume that $g$ satisfies Eq. (7). In those
cases, we propose using

$\displaystyle D({\bm{\theta}})$ $\displaystyle\leq
f({\bm{X}}{\bm{\beta}})+{\bm{\theta}}^{\top}{\bm{X}}{\bm{\beta}}+\inf_{k\geq
0}g(k\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}(k\tilde{{\bm{\beta}}}),$
$\displaystyle=f({\bm{X}}{\bm{\beta}})+{\bm{\theta}}^{\top}{\bm{X}}{\bm{\beta}}+\begin{cases}0&(g(\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}\geq
0)\\\
-\infty&(g(\tilde{{\bm{\beta}}})-{\bm{\theta}}^{\top}{\bm{X}}\tilde{{\bm{\beta}}}<0)\end{cases}.$

This is based on the Fenchel–Young inequality for $f$ and Eq. (10).


# Direct evidence for carbon incorporation on the nitrogen site in AlN

Darshana Wickramaratne  Center for Computational Materials Science, US Naval
Research Laboratory, Washington, D.C. 20375, USA  Mackenzie Siford  Department
of Physics, University of Alabama at Birmingham, Birmingham, Alabama 35233,
USA  Md Shafiqul Islam Mollik  Department of Physics, University of Alabama at
Birmingham, Birmingham, Alabama 35233, USA  John L. Lyons  Center for
Computational Materials Science, US Naval Research Laboratory, Washington,
D.C. 20375, USA  M.E. Zvanut  Department of Physics, University of Alabama at
Birmingham, Birmingham, Alabama 35233, USA

###### Abstract

We use photo-electron paramagnetic resonance (EPR) measurements and first-
principles calculations to identify and explain the properties of carbon in
AlN. We present clear evidence for carbon substitution on the nitrogen site
(CN). We also clarify the origin of a widely observed EPR spectra in AlN that,
although often attributed to a deep donor defect, we demonstrate is
surprisingly due to CN. Finally, we show the presence of CN is consistent with
the absorption spectra at 4.7 eV observed in AlN.

Aluminum nitride (AlN) is one of the most promising ultra-wide band gap
semiconductors for applications in power electronics [1, 2] and
optoelectronics that operate in the deep ultraviolet [3]. Continued progress
in defect spectroscopy and identification have shown that AlN exhibits a rich
array of defects [4, 5, 6, 7, 8, 9, 10, 11]. Within this catalog of defect
levels there has been considerable effort to identify the microscopic origin
of an absorption band at 265 nm (4.7 eV), which can potentially hamper the
operation of AlN light emitters that operate in the deep ultraviolet. Carbon
has been invoked as the origin of this absorption signal [12, 13, 14, 15].
However there is some debate as to whether carbon incorporates by substituting
on the nitrogen site, CN [14], substituting on the Al site, CAl [12], or as a
complex [15]. The question of whether carbon alone provides a sufficient
explanation for this absorption band has also been raised [16].

Defect identification based on optical spectroscopy alone is challenging when
there are multiple overlapping optical bands [9, 10]. Spectroscopy techniques
such as electron-paramagnetic resonance (EPR) provide a more precise
fingerprint of defects and can greatly expand our understanding of the
microscopic origin of defects. Indeed, several EPR studies, including our own,
have identified a spectrum with the following hyperfine (HF) parameters -
$A_{\parallel}$ $\sim$ 3.9 mT and $A_{\perp}$ $\sim$ 1.9 mT [4, 6, 5, 7],
where $A_{\parallel}$ is the HF interaction parallel to the $c$-axis of AlN
and $A_{\perp}$ is the HF interaction determined perpendicular to the
$c$-axis. The defect attributed to this spectrum (which we henceforth refer to
as D5, following Ref. [5]) was initially posited to be a deep donor with the
following suggested candidate defects, an Al interstitial (Ali), a nitrogen
vacancy ($V_{\rm N}$), or oxygen substituting on the nitrogen site (ON). The
suggestion that the D5 defect might be a deep donor was based in part on
electron nuclear double resonance (ENDOR) measurements [7], which revealed the
hyperfine interaction of D5 arises from an $S$=1/2 defect interacting with a
nuclear spin of $I$=5/2, which was assumed to be the Al atoms of AlN. At first
glance, these studies do not appear to offer any insight into the microscopic
origin of the absorption band at 4.7 eV and its potential connection with the
presence of carbon in AlN.

However, there are some issues that contradict the accepted wisdom that the D5
defect is a deep donor. Previous DFT calculations of HF parameters ruled out
Ali as the origin of D5 [17]. Follow-on EPR measurements together with first-
principles calculations [8] cast doubt on D5 being due to $V_{\rm N}$. Since
first-principles calculations predict ON is a $DX$ center [18], it is unlikely
that D5 is due to ON, since the EPR active charge state (O${}_{\rm N}^{0}$) is
metastable, while D5 is observed in as-grown AlN.

In this Letter, we show these two puzzles in AlN, the role of carbon in
causing the 4.7 eV absorption signal and the unknown source of the D5 EPR
signal, are in fact closely linked. We present a unified physical picture
showing that the D5 defect is CN, which is a deep acceptor in AlN. Measuring
the EPR activity as a function of photon energy leads to two clear transitions
that either quench or excite the EPR signal. Our first-principles calculations
indicate that the hyperfine parameters and the optical transitions are
explained by the CN (0/$-$) acceptor level. Our study corrects a long-standing
misconception that the D5 defect in AlN is a deep donor, and provides clear
evidence for the incorporation of CN in AlN.

We performed our photo-EPR measurements on AlN substrates from Hexatech and
Crystal IS, both of which were grown via physical vapor transport. The 7 mm
$\times$ 7 mm $\times$ 0.5 mm AlN substrate from Hexatech, which has surface
coloration changing from amber to clear, was cut into 2.3 mm wide pieces, and
labeled sample A, sample B and sample C. Several similarly sized pieces,
collectively called sample D, were cut from an AlN wafer grown by Crystal IS.
In Table 1 we list the concentration of common impurities that were measured
by secondary ion mass spectrometry (SIMS) to a depth of 6 um on sample D and
sample A, a piece with color and EPR response similar to sample B.

Table 1: Secondary ion mass spectrometry (SIMS) measurements of the concentration of common impurities Si, O, and C in sample A and sample D Impurity | Sample A (cm-3) | Sample D (cm-3)
---|---|---
Si | 2$\times$ 1018 | 2$\times$ 1017
O | 3$\times$ 1018 | 3$\times$ 1017
C | 1 $\times$ 1019 | 2$\times$ 1017

10 GHz EPR measurements were obtained from each AlN sample between 300 K and 4
K with the magnetic field parallel to the $c$-axis. Additional room
temperature measurements were obtained from sample B with the magnetic field
rotated in the a-plane. The spectra at different orientations were simulated
using EasySpin [19] to determine the $g$-factor and hyperfine values.

Photo-EPR was carried out on samples C and D using light-emitting diodes
(LEDs) with the magnetic field along the $c$-axis. For the photo-quenching
experiments, first, a 265 nm LED (4.68 eV) with 0.5 mW power illuminated the
sample through the slits of the EPR cavity to generate the D5 signal. Then,
the sample was illuminated with LEDs of selected photon energy from 1.2 eV to
3.4 eV, using neutral density filters to maintain a constant photon flux.
Between the measurements with each LED, the EPR signal was regenerated using
the 265 nm LED. Since the shape of the EPR signal did not change as the sample
was illuminated, a comparison of the EPR amplitude at a selected wavelength
with that obtained using the 265 nm LED was used to determine the relative
number of spins measured at each wavelength. The error in the relative
amplitude is $\pm$0.1. A similar procedure was followed for photo-excitation
of the EPR signal, except the signal always started near zero amplitude. LEDs
with peak photon energy between 3.22 eV and 4.68 eV were used to increase the
EPR signal, and a 470 nm (2.64 eV) LED was used to quench the signal after
each excitation. The number of spins generated after illumination with the 265
nm LED for 30 minutes was 8$\times$1014 for sample C and 2$\times$1014 for
sample D. The average spin density, obtained by dividing by the sample volume,
was 1$\times$1017 cm-3 in sample C and 1.4$\times$1016 cm-3 in sample D.

To interpret our photo-EPR measurements we also perform first-principles
calculations based on density functional theory (DFT) [20, 21], using the
projector-augmented wave (PAW) potentials [22] as implemented in the Vienna
Ab-initio Simulation Package (VASP) [23, 24]. We use the Heyd-Scuseria-
Ernzerhof (HSE) hybrid functional [25, *HeydJCP2006] for all of our
calculations. The energy cutoff for the plane-wave basis set is 500 eV. The
fraction of nonlocal Hartree-Fock exchange is set to 0.33 for AlN; this
results in band gaps and lattice parameters that agree with the experimental
values. Defect formation energies and thermodynamic transition levels are
calculated using the standard supercell approach [27] with 96-atom and
288-atom supercells. The lattice parameters of the supercell are held fixed
while the atomic coordinates are relaxed until the forces are below 5
meV/Angstrom. The formation energies and charge-state transition levels of
defects are determined using a single
($\frac{1}{4}$,$\frac{1}{4}$,$\frac{1}{4}$) $k$-point. Spin polarization is
included for all of our calculations. Optical absorption energies are
determined through the construction of a one-dimensional configuration
coordinate diagram using the Nonrad code using the 96 atom supercell
calculations [28]. Hyperfine parameters for the paramagnetic charge state of
each defect were calculated using a 288-atom supercell with a
(2$\times$2$\times$2) $\Gamma$-centered $k$-point grid.

The EPR spectra of sample B obtained at room temperature in the dark are shown
in Figure 1.

Figure 1:  Room temperature EPR spectrum (black solid lines) of AlN in the
dark with the magnetic field (a) parallel and (b) perpendicular to the
$c$-axis of AlN along with a fit to the spectra (blue dashed lines).

Simulations of the spectra obtained between 300 K and 4 K reveal that the HF
parameters have a weak linear dependence with increasing temperature. Our
measured HF parameters are similar to the prior EPR measurements reported for
the D5 spectrum [4, 5, 7]. Accurate measurement of the $g$-factor in the
presence of a strong hyperfine as seen for D5 is best done by using two
different frequencies as was done by Soltamov et al. [4] where they found
$g_{\parallel}$=2.002 and $g_{\perp}$=2.006. Our values obtained at 10 GHz are
$g_{\parallel}$=2.001(1) and $g_{\perp}$=2.004(1), which is in reasonable
agreement with prior measurements.

The HF parameters obtained from our measurements are listed in Table 2, along
with prior experimental reports for the D5 defect. ENDOR and ENDOR-induced EPR
performed by others have convincingly determined that the defect has axial
symmetry about the $c$-axis, and that the defect is situated on a nitrogen
site [7].

Table 2:  Hyperfine parameters that are parallel (A∥) and perpendicular (A⟂) to the $c$-axis, compared with experimental parameters reported in prior studies of AlN. For Sample B the number in [ ] is the hyperfine parameter measured at 4 K. For the three experimental references the measurement temperature is listed in ( ). The final three rows contain our first-principles calculations of the HF parameters. For each calculation, we report the magnitude of the HF parameters for the four Al ions that are nearest-neighbor to the defect site where the fourth entry is the HF parameter of the axial Al ion.  | A∥ (mT) | A⟂ (mT)
---|---|---
Experiment
Sample B 300 K [4 K] | 3.2 [4.0] | 1.5 [1.8]
Ref. 7 (40 K) | 4.0 | 1.9
Ref. 5 (1.7 K) | 3.7 | 1.5
Ref. 4 (9 K) | 4.0 | 1.9
First-principles calculations
ON | 0.9, 0.9, 20.6, 0.4 | 0.6, 0.6, 7.2, 0.2
$V_{\rm N}$ | 8.8, 4.6, 5.5, 8.6 | 7.0, 3.1, 4.2, 6.7
CN | 0.3, 0.3, 0.3, 4.0 | 0.7, 0.7, 0.7, 1.7

Calculated HF parameters for the possible candidates for D5 are also listed in
Table 2. We consider $V_{\rm N}$ and ON, since they have been reported as
possible candidates in prior EPR studies [4, 5, 7]. We also consider CN, since
our SIMS measurements indicate carbon is unintentionally incorporated (Table
1) in the AlN substrates. Prior first-principles calculations [29] have also
shown CN has low formation energies compared to either CAl or incorporation as
an interstitial.

Our calculations provide additional evidence to rule out $V_{\rm N}$ and ON as
the origin of the D5 defect. With ON, we find the HF on the axial Al is an
order of magnitude lower than the experimental value and the largest HF
associated with ON is on a basal plane Al ion, which is in contrast with the
axial anisotropy that is associated with D5. The HF parameters for $V_{\rm N}$
indicate HF interaction with all four nearest-neighbor Al dangling bonds,
which also conflicts with the observed anisotropy of D5. In contrast, the
calculated HF parameters for CN and the out-of-plane anisotropy is in
remarkably good agreement with the experimental HF parameters listed in Table
2.

In the EPR active state (C${}_{\rm N}^{0}$), the three basal plane C-Al bonds
are equivalent in length and shorter than the axial C-Al bond length. The spin
density of C${}_{\rm N}^{0}$ is localized primarily on a C $p_{z}$-orbital
that is oriented along the $c$-axis [29]. In our HF calculations, we assume C
is incorporated as 12C (i.e., the zero nuclear spin isotope of C). While the
majority of the spin density is localized on the C ion (which lacks an HF
interaction as 12C), a striking consequence of the C $p_{z}$-orbital that
constitutes the spin density of C${}_{\rm N}^{0}$ is the finite orbital
overlap of the C $p_{z}$-orbital with the orbitals of the Al ion that is along
the axial C-Al bond. This orbital overlap leads to a finite HF interaction on
the axial Al ion and the largest of the four HF parameters for C${}_{\rm
N}^{0}$ reported in Table 2 that are in agreement with experiment. There is
negligible overlap of the spin density with the three basal plane C-Al bonds,
which is consistent with the HF parameters for these three Al ions being
significantly lower compared to that of the axial Al. In reality, 1.1% of the
C is present as 13C, which has a non-zero nuclear spin. Given the overall low
concentration of 13C with respect to the total carbon incorporated in our
samples (Table 1), we expect no measurable EPR spectum due to contributions
from 13C.

Next we examine possible photoionization processes for CN to determine the
response of the EPR signal to photoexcitation. Our photo-EPR measurements
performed on sample C and sample D are illustrated in Figure 2.

Figure 2:  Steady state photo-EPR for (a) excitation and (b) quenching of the
EPR amplitude in sample C (circles) and sample D (squares) indicating the
relative number of EPR active defects as a function of photon energy. Error
bars indicate the uncertainty in comparing EPR amplitudes. The inset in (a)
illustrates the EPR spectra obtained from sample C in the dark (black), after
illumination with 4.68 eV (green) and following partial quenching with 2.01 eV
(gray)

The increase in intensity is due to photoionization that leads to C${}_{\rm
N}^{0}$, while the reduction in intensity corresponds to conversion of
C${}_{\rm N}^{0}$ to an EPR silent charge state. From Fig. 2(a), we see that
the intensity of the EPR signal begins to increase at a threshold of $\sim$ 4
eV. Fig. 2(b) shows that once the EPR signal is generated, the intensity
begins to decrease at a threshold of $\sim$ 2 eV.

The thresholds for excitation and quenching of the photo-EPR signal add
approximately to the band gap of AlN. This suggests the photo-EPR data is due
to direct photoionization of CN, rather than the capture of a carrier by a
secondary defect followed by charge transfer to CN. This interpretation is
further supported by the fact that the photo-EPR response is obtained on two
samples that were grown under different conditions and contain impurities that
differ in concentration by up to two orders of magnitude. Finally we note
that, no other EPR active defect was observed in sample C, and no other
defects with the appropriate photo-EPR response were detected in sample D.

First-principles calculations show that in addition to the (0/$-$), which is
1.88 eV above the AlN VBM, CN can also be stable in the positive charge state.
The resulting (+/0) level of CN is 1.02 eV above the VBM [29]. In principle,
photoionization processes involving either the (0/$-$) or (+/0) level levels
can excite or quench the EPR-active C${}_{\rm N}^{0}$ state. Our first-
principles calculations of the optical transitions suggest that the photo-EPR
measurements correspond to photoionization of the CN (0/$-$) level. In Figure
3(a), we illustrate the zero-phonon line and the peak optical absorption
energies for photoionization processes that involve either the (+/0) and
(0/$-$) level of CN in AlN. The peak absorption energies are determined by
invoking the Franck-Condon approximation, which is illustrated using
configuration coordinate diagrams as shown in Figure 3(b)

Figure 3:  The peak absorption energy and zero-phonon line (in parentheses)
for the CN (+/0) and (0/$-$) levels is listed alongside each arrow denoting
possible optical absorption processes. Processes that lead to an EPR active
state are denoted in green font. (b) Configuration-coordinate diagram
illustrating photoionization of electrons from the VBM to the CN (0/$-$) level
converting the EPR active charge state to an EPR silent state. The inset in
(b) illustrates the spin density of the hole introduced by the EPR active
C${}_{\rm N}^{0}$ state.

Figure 3(b) illustrates the photoionization of a carrier from the AlN VBM that
converts the EPR active C${}_{\rm N}^{0}$ to C${}_{\rm N}^{-}$. This
transition is calculated to occur at a peak absorption energy of 2.51 eV,
while the onset in the absorption process is 1.88 eV. This prediction agrees
with our observation of the photo-EPR signal quenching at $\sim$2 eV.
Similarly, we predict that photoionization of an electron to the AlN CBM from
the (EPR silent) C${}_{\rm N}^{-}$ charge state occurs with a peak absorption
energy of 4.83 eV and an onset of 4.32 eV. Again, this prediction agrees well
with our observation of the photo-excitation of the EPR signal at $\sim$4 eV.
In addition, we find that the photo-EPR cannot involve the (+/0) level of CN,
since the energies that excite and quench the EPR signal in our experiments
are incompatible with the corresponding energies that we predict from first
principles.

Having established evidence for CN in AlN, we are now in a position to comment
on optical experiments where carbon has been invoked as the origin of defect-
related spectra. In particular, several studies have connected the presence of
absorption bands at 2.6 eV and 4.7 eV as being due to carbon [12, 13, 14, 15],
and there is some debate as to whether carbon incorporates as CN [14], CAl
[12] or as a complex [15]. Given that the threshold to excite the photo-EPR
signal due to C${}_{\rm N}^{0}$ is 4 eV and the photo-EPR signal continues to
increase up to 4.68 eV, we suggest that the widely observed absorption band at
4.7 eV in AlN can be explained by photoionization of C${}_{\rm N}^{-}$,
leading to an electron in the AlN CBM.

In summary, photo-EPR measurements and first-principles calculations provide
clear evidence of carbon incorporation on the nitrogen site in AlN. The
distortion of CN along the $c$-axis leads to a finite hyperfine interaction
with the axial Al ion that is nearest neighbor to CN. This resolves the origin
of the EPR spectra in a number of prior studies on AlN where the defect giving
rise to the hyperfine interaction was thought to be a deep donor.
Photoionization of the CN (0/$-$) level at $\sim$4 eV excites the EPR signal
associated with this hyperfine interaction, while photon energies in the range
of $\sim$2 eV quench the EPR signal, which is consistent with our calculations
of the zero-phonon line and peak absorption energies for the CN (0/$-$) level.
The photo-EPR signal excited above 4 eV due to CN is also consistent with the
absorption spectrum that is peaked at 4.7 eV in AlN samples that contain
carbon.

###### Acknowledgements.

We thank Prof. Larry Halliburton for helpful discussions regarding the EPR
data. D.W and J.L.L were supported by the Office of Naval Research through the
Naval Research Laboratory’s Basic Research Program. The calculations were
supported in part by the DoD Major Shared Resource Center at AFRL. The work at
UAB was supported as part of the Ultra Materials for a Resilient Energy Grid,
an Energy Frontier Research Center funded by the U.S. Department of Energy,
Office of Science, Basic Energy Sciences under Award No. DE-SC0021230.

## References

  * Tsao  _et al._ [2018] J. Y. Tsao, S. Chowdhury, M. A. Hollis, D. Jena, N. M. Johnson, K. A. Jones, R. J. Kaplar, S. Rajan, C. G. Van de Walle, E. Bellotti, _et al._ , Ultrawide-bandgap semiconductors: research opportunities and challenges, Adv. Electron. Mater. 4, 1600501 (2018).
  * Lyons  _et al._ [2024] J. L. Lyons, D. Wickramaratne, and A. Janotti, Dopants and defects in ultra-wide bandgap semiconductors, Current Opinion in Solid State and Materials Science 30, 101148 (2024).
  * Kneissl  _et al._ [2019] M. Kneissl, T.-Y. Seong, J. Han, and H. Amano, The emergence and prospects of deep-ultraviolet light-emitting diode technologies, Nat. Photonics 13, 233 (2019).
  * Soltamov  _et al._ [2010] V. Soltamov, I. Ilyin, A. Soltamova, E. Mokhov, and P. Baranov, Identification of the deep level defects in AlN single crystals by electron paramagnetic resonance, J. Appl. Phys. 107, 113515 (2010).
  * Mason  _et al._ [1999] P. Mason, H. Przybylinska, G. Watkins, W. Choyke, and G. Slack, Optically detected electron paramagnetic resonance of AlN single crystals, Phys. Rev. B 59, 1937 (1999).
  * Soltamov  _et al._ [2011] V. Soltamov, I. Ilyin, A. Soltamova, D. Tolmachev, E. Mokhov, and P. Baranov, Identification of the deep-level defects in AlN single crystals: EPR and TL studies, Diam. Relat. Mater. 20, 1085 (2011).
  * Evans  _et al._ [2006] S. Evans, N. Giles, L. Halliburton, G. Slack, S. Schujman, and L. Schowalter, Electron paramagnetic resonance of a donor in aluminum nitride crystals, Appl. Phys. Lett. 88, 062112 (2006).
  * Son  _et al._ [2011] N. Son, A. Gali, Á. Szabó, M. Bickermann, T. Ohshima, J. Isoya, and E. Janzén, Defects at nitrogen site in electron-irradiated AlN, Appl. Phys. Lett. 98, 242116 (2011).
  * Yan  _et al._ [2014] Q. Yan, A. Janotti, M. Scheffler, and C. G. Van de Walle, Origins of optical absorption and emission lines in AlN, Appl. Phys. Lett. 105, 111104 (2014).
  * Schulz  _et al._ [2011] T. Schulz, M. Albrecht, K. Irmscher, C. Hartmann, J. Wollweber, and R. Fornari, Ultraviolet luminescence in AlN, Phys. Status Solidi (b) 248, 1513 (2011).
  * Koppe  _et al._ [2016] T. Koppe, H. Hofsäss, and U. Vetter, Overview of band-edge and defect related luminescence in aluminum nitride, J. Lumin. 178, 267 (2016).
  * Gamov  _et al._ [2021] I. Gamov, C. Hartmann, T. Straubinger, and M. Bickermann, Photochromism and influence of point defect charge states on optical absorption in aluminum nitride (AlN), J. Appl. Phys. 129, 113103 (2021).
  * Collazo  _et al._ [2012] R. Collazo, J. Xie, B. E. Gaddy, Z. Bryan, R. Kirste, M. Hoffmann, R. Dalmau, B. Moody, Y. Kumagai, T. Nagashima, _et al._ , On the origin of the 265 nm absorption band in AlN bulk crystals, Appl. Phys. Lett. 100, 191914 (2012).
  * Alden  _et al._ [2018] D. Alden, J. Harris, Z. Bryan, J. Baker, P. Reddy, S. Mita, G. Callsen, A. Hoffmann, D. Irving, R. Collazo, _et al._ , Point-defect nature of the ultraviolet absorption band in AlN, Phys. Rev. Appl. 9, 054036 (2018).
  * Irmscher  _et al._ [2013] K. Irmscher, C. Hartmann, C. Guguschev, M. Pietsch, J. Wollweber, and M. Bickermann, Identification of a tri-carbon defect and its relation to the ultraviolet absorption in aluminum nitride, J. Appl. Phys. 114, 123505 (2013).
  * Peters  _et al._ [2023] L. Peters, C. Margenfeld, J. Krügener, C. Ronning, and A. Waag, A combination of ion implantation and high-temperature annealing: The origin of the 265 nm absorption in AlN, Phys. Status Solidi (a) 220, 2200485 (2023).
  * Gerstmann  _et al._ [2001] U. Gerstmann, A. Blumenau, and H. Overhof, Transition metal defects in group-III nitrides: An ab initio calculation of hyperfine interactions and optical transitions, Phys. Rev. B 63, 075204 (2001).
  * Gordon  _et al._ [2014] L. Gordon, J. L. Lyons, A. Janotti, and C. G. Van de Walle, Hybrid functional calculations of $dx$ centers in AlN and GaN, Phys. Rev. B 89, 085204 (2014).
  * Stoll and Schweiger [2006] S. Stoll and A. Schweiger, Easyspin, a comprehensive software package for spectral simulation and analysis in EPR, Journal of magnetic resonance 178, 42 (2006).
  * Hohenberg and Kohn [1964] P. Hohenberg and W. Kohn, Inhomogeneous electron gas, Phys. Rev. 136, B864 (1964).
  * Kohn and Sham [1965] W. Kohn and L. J. Sham, Self-consistent equations including exchange and correlation effects, Phys. Rev. 140, A1133 (1965).
  * Blöchl [1994] P. E. Blöchl, Projector augmented-wave method, Phys. Rev. B 50, 17953 (1994).
  * Kresse and Furthmüller [1996] G. Kresse and J. Furthmüller, Efficient iterative schemes for ab initio total-energy calculations using a plane-wave basis set, Phys. Rev. B 54, 11169 (1996).
  * Kresse and Hafner [1994] G. Kresse and J. Hafner, Ab initio molecular-dynamics simulation of the liquid-metal–amorphous-semiconductor transition in germanium, Phys. Rev. B 49, 14251 (1994).
  * Heyd  _et al._ [2003] J. Heyd, G. Scuseria, and M. Ernzerhof, Hybrid functionals based on a screened Coulomb potential, J. Chem. Phys. 118, 8207 (2003).
  * Heyd  _et al._ [2006] J. Heyd, G. E. Scuseria, and M. Ernzerhof, Erratum: “hybrid functionals based on a screened coulomb potential” [j. chem. phys. 118, 8207 (2003)], J. Chem. Phys. 124, 219906 (2006).
  * Freysoldt  _et al._ [2014] C. Freysoldt, B. Grabowski, T. Hickel, J. Neugebauer, G. Kresse, A. Janotti, and C. G. Van de Walle, First-principles calculations for point defects in solids, Rev. Mod. Phys. 86, 253 (2014).
  * Turiansky  _et al._ [2021] M. E. Turiansky, A. Alkauskas, M. Engel, G. Kresse, D. Wickramaratne, J.-X. Shen, C. E. Dreyer, and C. G. Van de Walle, Nonrad: Computing nonradiative capture coefficients from first principles, Computer Physics Communications 267, 108056 (2021).
  * Lyons  _et al._ [2014] J. L. Lyons, A. Janotti, and C. G. Van de Walle, Effects of carbon on the electrical and optical properties of InN, GaN, and AlN, Phys. Rev. B 89, 035204 (2014).