Smoothing the Edges: Smooth Optimization for Sparse Regularization using Hadamard Overparametrization

Chris Kolb<EMAIL_ADDRESS>
Munich Center for Machine Learning (MCML),

Deptartment of Statistics, LMU Munich

80539, Munich, Germany

Christian L. Müller<EMAIL_ADDRESS>
Institute for Computational Biology, Helmholtz Munich,

Munich Center for Machine Learning (MCML),

Department of Statistics, LMU Munich

80539, Munich, Germany,

Center for Computational Mathematics, Flatiron Institute

New York, NY 10010, USA

Bernd Bischl<EMAIL_ADDRESS>
David Rügamer<EMAIL_ADDRESS>
Munich Center for Machine Learning (MCML),

Department of Statistics, LMU Munich

80539, Munich, Germany

We present a framework for smooth optimization of explicitly regularized objectives for (structured) sparsity. These non-smooth and possibly non-convex problems typically rely on solvers tailored to specific models and regularizers. In contrast, our method enables fully differentiable and approximation-free optimization and is thus compatible with the ubiquitous gradient descent paradigm in deep learning. The proposed optimization transfer comprises an overparameterization of selected parameters and a change of penalties. In the overparametrized problem, smooth surrogate regularization induces non-smooth, sparse regularization in the base parametrization. We prove that the surrogate objective is equivalent in the sense that it not only has identical global minima but also matching local minima, thereby avoiding the introduction of spurious solutions. Additionally, our theory establishes results of independent interest regarding matching local minima for arbitrary, potentially unregularized, objectives. We comprehensively review sparsity-inducing parametrizations across different
fields that are covered by our general theory, extend their scope, and propose improvements in several aspects. Numerical experiments further demonstrate the correctness and effectiveness of our approach on several sparse learning problems ranging from high-dimensional regression to sparse neural network training.

overparametrization, sparse regularization, smooth optimization, Hadamard product parametrization, surrogate optimization, gradient descent, neural networks

§ INTRODUCTION AND BACKGROUND

As a result of the proliferation of high-dimensional and unstructured data in recent years, methods for sparse (vectors) and low-rank (matrices and tensors) representations have received increasing attention in fields such as machine learning, statistics, and signal processing. Parsimonious models are commonly used to incorporate prior knowledge about the complexity of the underlying phenomenon or to obtain interpretable sparse approximations of non-sparse ground truths [Bach et al., 2012]. They are also employed to regularize otherwise intractable inverse problems [Benning and Burger, 2018] and reduce the computational burden of expensive large-scale optimization or inference, e.g.,
in deep learning (DL) models [Blalock et al., 2020, Hoefler et al., 2021]. Structured or group sparsity naturally generalizes the notion of unstructured sparsity to enable encoding structural prior information about model complexity into the optimization problem [Huang et al., 2009, Jenatton et al., 2011].

§.§ Convex and Non-Convex Sparse Regularization

[Toy Loss Landscape for Optimization Transfer]Illustration of smooth optimization transfer. Left: univariate lasso problem $\P(\beta)=(1-\frac{3}{2} \beta)^2+2|\beta|$ (red line indicates the global minimizer $\hat{\beta}$). Middle: contours of the equivalent smooth surrogate $\Q(u,v)=(1-\frac{3}{2} uv)^2+u^2+v^2$ using a Hadamard product parametrization (<ref>) with $\K(u,v)=uv=\beta$. Both global minimizers (dots) map to $\K(\hat{u},\hat{v})=\hat{\beta}$. Right: non-convex surface of higher-dimensional $\Q(u,v)$.

$\bm{\ell_0}$ and $\bm{\ell_1}$ regularization   In sparse estimation problems of a parameter vector $\bm{\beta}\in\mathbb{R}^{d}$ given a smooth objective function $\mathcal{L}:\mathbb{R}^{d} \to \mathbb{R}^{+}_{0}$, the classical optimization problem using explicit regularization is

\begin{equation*} \label{eq:standard-formulation}
\min_{\bm{\beta} \in \mathbb{R}^{d}} \mathcal{L}(\bm{\beta}) + \lambda \mathcal{R}(\bm{\beta}) \,,
\end{equation*}

with regularization or penalty function $\mathcal{R}:\mathbb{R}^{d} \to \mathbb{R}^{+}_{0}$ to $\L(\bbeta)$, whose strength is controlled by $\lambda \geq 0$.
A natural choice for the regularizer is $\mathcal{R}(\bm{\beta}) =\Vert \bm{\beta} \Vert_0$, i.e., the cardinality of the support of $\bm{\beta}$ counting its non-zero entries. However, this best-subset approach is infeasible due to its non-convex, and non-continuous NP-hard nature [Natarajan, 1995, Chen et al., 2017]. To overcome these difficulties, convex relaxations of $\ell_0$ regularization have been proposed that enable optimization via, e.g., coordinate descent or projected gradient methods [Tropp, 2006, Schmidt et al., 2007]. The tightest convex relaxation of $\Vert \bm{\beta} \Vert_0$ is given by its convex envelope $\Vert \bm{\beta} \Vert_1$, resulting in

\begin{equation} \label{eq:l1-formulation}
\min_{\bm{\beta} \in \mathbb{R}^{d}} \mathcal{L}(\bm{\beta}) + \lambda \Vert \bm{\beta} \Vert_{1} \,.
\end{equation}

This formulation is known as $\ell_{1}$ regularization today. In the context of linear models, it has been introduced as the lasso to the statistics community [Tibshirani, 1996] and as Basis Pursuit Denoising in signal processing [Chen and Donoho, 1994, Chen et al., 2001].
For convex $\L$, such as in linear regression, the well-developed machinery of convex optimization can be utilized to solve (<ref>). $\ell_1$ regularization has also been shown to have some favorable theoretical properties, such as consistent recovery of the true support of $\bm{\beta}$ under restricted conditions [Donoho and Elad, 2003, Zhao and Yu, 2006, Meinshausen and Bühlmann, 2006]. However, using $\ell_1$ regularization to achieve sparsity also comes with a disadvantage: whereas $\norm{\bbeta}_0$ is constant on the support of $\bm{\beta}$, the $\ell_1$ penalty increases linearly in the magnitude of its components. This leads to estimation bias for large parameters [Zhang and Huang, 2008] and inconsistent support recovery [Chartrand, 2007, Xu et al., 2012].
To mitigate the challenges posed by $\ell_1$ and $\ell_0$ regularization, the seminal work of Fan and Li, 2001 proposed smoothly clipped absolute deviations (SCAD), one of the earliest examples of non-convex regularizers. Another popular non-convex penalty that enables feature selection and nearly unbiased estimation is the minimax concave penalty (MCP) introduced by Zhang, 2010.

$\bm{\ell_{p,q}}$ regularization   In this work, however, we focus on a generalization of the $\ell_1$ penalty based on the $\ell_q$ quasi-norm, $\Vert \cdot \Vert_{q}$, for $0<q\leq1$. This approach was initially described by Frank and Friedman, 1993 and subsequently popularized as the bridge penalty by Fu, 1998. Non-convex bridge regularization is defined by a regularization term of the form $\mathcal{R}(\bbeta) = \Vert \bbeta \Vert_{q}^{q}$ for $0 < q < 1$. For the case of structured sparsity, $\ell_q$ regularization can be straightforwardly extended to mixed-norm $\ell_{p,q}$ regularization for $0<q<p\leq2$, studied,
e.g., in Hu et al., 2017. A number of important desirable theoretical results have been established for non-convex $\ell_q$ and $\ell_{p,q}$ regularization, such as requiring fewer linear measurements for support recovery and permitting sparser solutions compared to convex $\ell_1$ and $\ell_{2,1}$ (group-wise) regularization [Fu, 1998, Fu and Knight, 2000, Chartrand, 2007, Xu et al., 2012]. Moreover, the regularity conditions required for consistent recovery are weaker than typically required for $\ell_1$ [Chartrand and Staneva, 2008, Loh and Wainwright, 2017] or $\ell_{2,1}$ penalties [Hu et al., 2017].

Optimization using $\ell_q$ regularization, however, poses a non-smooth and non-convex
problem for $0<q<1$ and is thus difficult to solve efficiently. Ge et al., 2011 show that identification of the global minimum is strongly NP-hard.
Still, computing local minima of the non-convex regularization problem usually performs better compared to convex regularization approaches [Xu et al., 2010, Xu et al., 2012, Lyu et al., 2013, Wen et al., 2018]. A variety of optimization techniques such as the local quadratic approximation or majorization-minimization algorithms [Lange et al., 2000, Hunter and Li, 2005], and  various flavors of coordinate or subgradient descent methods have been discussed in the literature

The need for specialized optimization routines for non-smooth and non-convex regularized optimization problems
has arguably hindered the widespread use of $\ell_q$ and $\ell_{p,q}$ regularization, despite their favorable theoretical properties and the limitations of convex regularizers <cit.>.
In contrast, smooth first-order methods have become the go-to optimization tool for many researchers and practitioners, not limited to the field of DL anymore. This can be attributed to their applicability to a vast class of problems using automatic differentiation, their scalability to large data sets, and their surprising effectiveness despite using only cheaply computed gradient information.
While in practice, popular DL platforms offer implementations of $\ell_1$ regularization, this
essentially reduces to applying stochastic gradient descent (SGD) to a non-differentiable problem.
Unsurprisingly, this mismatch typically results in oscillating parameter updates, slow convergence, and a failure of parameter iterates to approach zero values (see Figure <ref>).

§.§ Our Contributions

To overcome the obstacles and complexities of using optimization routines tailored for specific non-smooth and potentially non-convex regularized problems, we apply a smooth variational form (SVF) that allows expressing the non-smooth regularizer as the constrained minimum of a smooth surrogate regularizer, where the constraint involves an overparametrization of model parameters. In our framework, we
construct a general template for exact smooth surrogate optimization of non-smooth and potentially non-convex
regularized problems. This optimization transfer is based on finding SVFs of the respective
regularizers, which entail a smooth parametrization map together with a smooth surrogate regularizer. Combined, an equivalent smooth
surrogate objective can be constructed.

Specifically, we

* provide a comprehensive
review of the loosely connected works on Hadamard parametrizations,
relating literature across DL, statistics, and optimization.

* introduce a smooth surrogate optimization framework for non-smooth and non-convex regularization of arbitrary parameters, including a matching local minima property.
While previous works often exploit properties particular to their setting, our main results (Thm. <ref> and Lemma <ref>-<ref>) are stated broadly and hold for arbitrary losses, learning models, and regularizers given our assumptions.

* apply our template method to a wide array of (group-)sparse $\ell_q$ and $\ell_{p,q}$ regularized problems, expanding the collection of sparsity-inducing parametrizations to Hadamard powers and shared parameters.

using SVFs based on Hadamard parametrizations and surrogate $\ell_2$ regularization.
We expand the collection of sparsity-inducing parametrizations discussed in the literature

using Hadamard powers and shared parameters.

* present different SVFs with variable amounts of overparametrization for the same induced regularizer, highlighting that it is not overparametrization per se inducing sparsity, but rather its effect on the curvature of the loss landscape.

* identify parametrizations with specific neural network structures, generalizing previous findings on
linear models
to modular components within arbitrary networks. This enables the integration of sparse regularization into the prevalent SGD-based optimization paradigm in DL using sparse “drop-in” replacements.

* evaluate our smooth optimization transfer approach on various sparse learning applications and demonstrate its correctness and practical feasibility.

§.§ Related Work

In recent years, parametrizations based on Hadamard products
have attracted considerable interest in several fields, including DL, statistics, signal processing, and optimization.
DL literature   In the theoretical DL community, the surge in activity can be ascribed to the correspondence of Hadamard product-based parametrizations of linear models and simple, easy-to-analyze network architectures with linear activations [Tibshirani, 2021, Dai et al., 2021], predominantly studied under the name of diagonal linear networks [Gunasekar et al., 2018, Gissin et al., 2019, Pesme et al., 2021, Li et al., 2021, Even et al., 2023, Wang and Jacot, 2023], as well as similar stylized architecture for structured sparsity [Li et al., 2023]. These networks are primarily analyzed in the context of implicit regularization effects and the representation cost of neural networks. The first phenomenon studies initialization and trajectory-based regularization effects of (S)GD without any explicit regularization term [Vaskevicius et al., 2019, Woodworth et al., 2020], whereas the latter is concerned with measuring the cost that is required for a DNN to represent particular functions in terms of norms of network weights [Dai et al., 2021, Jacot et al., 2022]. Implicit regularization through Hadamard product-based overparametrization of linear models was further extended to robust and sparse linear regression in Ma and Fattahi, 2022 using subgradient descent. In the absence of explicit regularization, Chou et al., 2023 study the implicit regularization of two variants of Hadamard parametrizations on gradient flow under vanishing initialization, obtaining improved sample complexity for compressed sensing problems. The “rich” gradient dynamics [Woodworth et al., 2020] caused by identical small initialization are further developed for overparametrized non-negative least squares problems in Chou et al., 2022. Contrasting our explicit surrogate regularization, an important shortcoming of implicit regularization approaches is that it is limited to convex $\ell_q$ norms for $q \geq 1$ for common losses such as the square loss, ruling out non-convex $\ell_q$ regularization for $q<1$ [Woodworth et al., 2020, Nacson et al., 2022].

Statistics literature   The implicit $\ell_1$ regularization effect of applying a simple Hadamard product parametrization to the parameters of a linear model under vanishing initialization and GD was studied by Zhao et al., 2022. Under the name “neuronized priors”, Shin and Liu, 2022 study similar parameter factorizations in a Bayesian modeling framework.

Signal processing literature    Li et al., 2023 recently applied the HPP to solve the tail-$\ell_1$ problem in compressed sensing. In a more general setting, Yang et al., 2022, and subsequently Parhi and Nowak, 2023, analyze the sparse functional representations learned by $\ell_2$ regularized DNNs with homogeneous activation functions from a signal processing perspective, employing a similar line of reasoning to our work to show the equivalence of group sparse $\ell_{2,1}$ and surrogate $\ell_2$ regularization using their Neural Balance Theorem. Similarly, starting with Neyshabur et al., 2015, Neyshabur et al., 2015, several works advanced the understanding of $\ell_2$ regularized networks and the inductive biases in the learned representations <cit.>.

Optimization literature   Micchelli et al., 2013 study the optimization of convex regularizers such as the $\ell_1$ penalty by smoothly approximating the absolute value using a quadratic variational formulation of the regularizer involving an additional surrogate parameter $\bm{\eta}$.
This concept is similarly discussed in Bach et al., 2012 under the umbrella term sub-quadratic norms. Formal connections between the so-called $\bm{\eta}$-trick and the Hadamard product (over)parametrizations studied in Hoff, 2017 are established for convex and lower semicontinuous proper loss functions in Poon and Peyré, 2021, who subsequently leverage Hadamard parametrizations to smooth bilevel programming [Poon and Peyré, 2023]. Recently, Ouyang et al., 2024 study smooth $\ell_1$ regularization using Hadamard parametrizations, and derive the surrogate Kurdyka-Lojasiewicz exponent at second-order stationary points from that of the original objective.
Another branch of literature in optimization that is related to our approach
is the perspective functions framework, a versatile tool for constructing proximal methods [Combettes and Müller, 2018, Combettes and Müller, 2020].

Explicit regularization and our work  We extend the literature on approximation-free, differentiable optimization for sparse regularization using a combination of overparametrization and surrogate regularization. An early connection between $\ell_1$ and an adaptive variant of $\ell_2$ regularization was first observed by Grandvalet, 1998. In statistics, the basic idea was re-discovered for a restricted problem class by Hoff, 2017, however, without noting its compatibility with simple SGD or considering additional parametrizations. Their suggested optimization routine employing alternating ridge regressions thus prevents its application beyond linear models.

Tibshirani, 2021 studies similar parametrizations in linear models and finds that they have identical global minima to certain weight-decayed network architectures (cf. Figure <ref>). Notably, a simple weight-decayed diagonal linear network with one hidden layer has the same global minimum as the lasso, which, in turn, is equivalent to applying the Hadamard product parametrization and $\ell_2$ regularization. This observation can also be implicitly inferred from the representation cost analysis of the same architecture presented in Dai et al., 2021. Building on the results of Hoff, 2017, Ziyin and Wang, 2023 propose smooth surrogate $\ell_1$ regularization for DNN weights, obtaining feature selection and network compression using SGD.

Previous works, however, exhibit limitations, including focusing only on single parametrizations (cf. Table <ref>), applying the parametrization to all model parameters instead of arbitrary subsets, or considering only linear models.

Further, we place particular emphasis on ensuring matching local minima as a crucial property to preserve structure in the overparametrized problem, which aligns with the work of Levin, 2020 and Nouiehed and Razaviyayn, 2022.
Table <ref> compares the properties of the most closely related works to ours.

1.9cmReference     2.8cmRegularization     2.5cmInduced sparse
regularizers     1.9cmMatching Local Min.     2.3cmCorresponding
NN struct.     2.7cmApplication to
arbitrary model

Grandvalet, 1998     Explicit $\ell_2$ (adaptive)     $\ell_1$                (LM)

Hoff, 2017     Explicit $\ell_2$     $\ell_{q}$ (restricted)                (AP)

Ziyin and Wang, 2023     Explicit $\ell_2$     $\ell_{1},\ell_{2,1}$        ($\ell_1$)

Tibshirani, 2021     Explicit $\ell_2$     $\ell_{q},\ell_{2,q}$ (restricted)                (LM)

Dai et al., 2021     Explicit $\ell_2$     $\ell_{q},\ell_{p,q}$ (restricted)                 (LM)

Zhao et al., 2022     Implicit (GD)     $\text{min}$-$\ell_1$-solution                (LM)

Woodworth et al., 2020     Implicit (GF)     $\text{min}$-$\ell_1$-solution                (LM)

Chou et al., 2023     Implicit (GF)     $\text{min}$-$\ell_1$-solution                (LM)

Schwarz et al., 2021     Implicit (SGD)               N/A      (AP)

Li et al., 2023     Implicit (GD/GF)     “Group Sparsity"                 (LM)

Our framework:     Explicit $\ell_2$ (weighted)      $\ell_q,\ell_{p,q}$

Overview of related works using Hadamard parametrizations for explicit and implicit sparse regularization. GD stands for gradient descent, and GF for gradient flow. In the third column, the addition (restricted) refers to a choice of $q=2/k,\,k \in \mathbb{N}$. LM indicates analyses limited to linear models while AP indicates a restrictive overparametrization of all model parameters.

Section <ref>
establishes a set of theoretical results that prove the validity of our general framework and provide a construction template for various regularizers.

Sections <ref> and <ref> apply our optimization transfer to construct equivalent smooth surrogates for convex $\ell_1$ and structured $\ell_{2,1}$ sparse regularization.

Section <ref> discusses deeper factorizations
involving more than two Hadamard factors, enabling smooth optimization of a restricted class of non-convex $\ell_q$
and $\ell_{p,q}$
regularized problems. Additionally, mitigation strategies to reduce the computational complexity of overparametrization, such as parameter sharing,
are discussed.

Section <ref> leverages the concept of Hadamard powers to broaden the expressivity of previous parametrizations, thereby lifting the aforementioned restrictions on the class of induced regularizers.

Unlike their product-based counterparts, power parametrizations enable differentiable optimization of a wider range of non-convex $\ell_q$
and $\ell_{p,q}$
regularizers despite minimal overparametrization.

Section <ref> discusses specifics regarding the practical optimization of the constructed smooth surrogates.

In Section <ref>, we showcase numerical experiments demonstrating the practical feasibility and competitiveness of our approach on a variety of model classes, ranging from sparse linear regression to (convolutional) neural network architectures.

We further illustrate the failure of subgradient descent to solve sparse regularization problems and compare against traditional implementations of convex and non-convex regularizers.

Section <ref> concludes by assessing the merits and limitations of our framework and identifying promising directions for future research.

§ SET-UP FOR TRANSFER AND THEORETICAL RESULTS

Notation  We represent vectors using bold lowercase letters and bold capital letters for matrices. We use
$\bm{\beta} \in \mathbb{R}^{d}$ to denote the parameter vector which is subject to regularization, and $\bm{\psi} \in \mathbb{R}^{d_{\psi}}$ for the remaining parameters, so that all model parameters are collected in $(\bm{\psi},\bm{\beta})$. We make this notational distinction to emphasize that our approach can be applied to arbitrary subsets of parameters of an optimization problem, irrespective of the presence of other parameters or the structure of the main objective $\L$. Thus, sparse regularization using our smooth optimization transfer framework can be applied to, e.g., specific layers of a neural network.
Further, let $\Vert \bm{\beta} \Vert_{q} \triangleq ( \sum_{j=1}^{d} | \beta_j |^{q} )^{1/q}$
denote the $\ell_q$ norm $\forall \bm{\beta} \in \mathbb{R}^{d}, q\in(0,\infty)$. Note that for $0<q<1$, only a quasi-norm is defined as the subadditivity does not hold. For $q=0$, the $\ell_0$ “norm” penalty $\Vert \bm{\beta} \Vert_{0}$
counts the number of non-zero elements in $\bm{\beta}$. Given a partition $\mathcal{G}=\{\mathcal{G}_{1},\ldots,\mathcal{G}_{L}\}$ of $[d] \triangleq \{1,\ldots,d\}$, the $\ell_{p,q}$ group (quasi-)norm is defined as $\Vert \bm{\beta} \Vert_{p, q} \triangleq(\sum_{j=1}^{L}(\sum_{i \in \mathcal{G}_{j}} \left|\beta_{i}\right|^{p})^{q / p})^{1 / q} = (\sum_{j=1}^{L} \Vert \bm{\beta}_{j} \Vert_{p}^{q})^{1 / q} \, \forall \, \bm{\beta} \in \mathbb{R}^{d},\, p,q>0$, where $\bbeta_j$
contains the components corresponding to $\Gj$. The regularization term for an $\ell_{p,q}$ penalty is given by the $q$-th power of the $\ell_{p,q}$ mixed-norm,  $\norm{\bm{\beta}}_{p,q}^{q}=\sum_{j=1}^{L} \Vert \bm{\beta}_{j} \Vert_{p}^{q}$.
Further, we use various notations to define Hadamard product-like operations, introduced in the following. Let $\odot: \mathbb{R}^{d} \times \mathbb{R}^{d} \to \Rd$ denote the classical Hadamard product, defined as $(\bm{u},\bm{v}) \mapsto (u_1v_1,\ldots,u_dv_d)^{\top}$,

and $\bigodot_{l=1}^{k} \bm{u}_{l}$ the Hadamard product of $k$ vectors, for which we also use the shorthand notation $\bm{u}_{l}^{\odot k}$. For parameter vectors with more than one index, e.g., $\bm{u}_{jl}^{\odot k}$, the Hadamard product is always taken over the second index. The self-Hadamard product $\bm{u} \odot \bm{u}$ is simply written as $\bm{u}^{2}$. A generalization of the self-Hadamard product to non-integer exponents $k>0$, i.e., element-wise raising the entries of $\bm{u}$ to the $k$-th power, is denoted as $\bm{u}^{\circ k}$. Given a partition $\mathcal{G}$ of $[d]$ into $L \leq d$ subsets, we define the group Hadamard product $\odotg$ of two vectors $\bm{u} \in \mathbb{R}^{d}$ and $\bm{\nu} \in \mathbb{R}^{L}$ as $\bm{u} \odotg \bm{\nu} \triangleq (\bm{u}_{j} \nu_{j})_{j \in \mathcal{G}}$, or more explicitly as

\begin{equation}\label{eq:ghpp-definition}
\bm{u} \odotg \bm{\nu} \triangleq  \begin{pmatrix}
\bm{u}_{1} \\ \vdots \\ \bm{u}_{L}
\end{pmatrix}  \odot \begin{pmatrix}
\nu_1 \mathds{1}_{|\mathcal{G}_1|} \\ \vdots \\ \nu_{L} \mathds{1}_{|\mathcal{G}_L|}
\end{pmatrix} \,, \nonumber
\end{equation}

where $\mathds{1}_{|\mathcal{G}_j|}$ denotes the $1$-vector of size $|\mathcal{G}_j|$. To make the distinction between vectors of size $d$ and $L$ more clear where necessary, we denote vectors in $\mathbb{R}^{d}$ as $\bm{v}$, and alternatively, use $\bm{\nu}$ for vectors in $\mathbb{R}^{L}$. In case $\bv=(\bv_1,\ldots,\bv_L)^{\top}$ is constant within groups $\Gj$, both are related as $\bm{v}_j = \nu_j \mathds{1}_{|\mathcal{G}_{j}|}$ for $j=1,\ldots,L$, and $\bu \odot \bv$ equals the group Hadamard product $\bu \odotg \bnu$.
Further, $\mathcal{B}(\bbeta,\varepsilon)\subseteq \Rd$ is used to denote an open ball with radius $\varepsilon$ centered at $\bbeta \in \Rd$, for a Euclidean space endowed with the standard topology induced by the Euclidean metric. Given a differentiable function $f:\mathbb{R}^{m} \to \mathbb{R},\, \bm{a} \mapsto f(\bm{a})$, the gradient $\nabla_{\bm{a}} f(\bm{a}) \in \mathbb{R}^{m}$  of $f$ at $\bm{a}$ contains partial derivatives $\partial f(\bm{a})/ \partial a_j$ for $j \in [m]$. The Hessian $\mathcal{H}_{f}(\bm{a})$ of $f$ at $\bm{a}$ is the $m \times m$ matrix containing second partial derivatives $(\mathcal{H}_{f}(\bm{a}))_{i j} \triangleq \partial^2 f / \partial a_i \partial a_j$.

For vector-valued differentiable maps  $\bm{f}:\mathbb{R}^{m} \to \mathbb{R}^{n}, \bm{a} \mapsto \bm{f}(\bm{a})$, the Jacobian $\mathcal{J}_{\bm{f}}(\bm{a})$ of $\bm{f}$ at $\bm{a}$ is the $n \times m$ matrix containing partial derivatives $(\mathcal{J}_{\bm{f}}(\bm{a}))_{i j} \triangleq \partial \bm{f}_{i} / \partial a_j$. Local solutions to an optimization problem over $(\bpsi,\bbeta)$ are denoted by $(\hat{\bm{\psi}},\hat{\bbeta})$. Finally, missing proofs are deferred to the appendix.

Before discussing the applications of our proposed framework to specific sparse regularizers, we first provide a number of general results on the equivalence of (regularized) optimization problems under smooth parametrization and a change of penalties, which will be applied throughout the paper. Let

\begin{equation} \label{eq:q-beginning}
\mathcal{P}:\mathbb{R}^{d_{\psi}}\times\mathbb{R}^d \to \mathbb{R}_{0}^{+},\,(\bm{\psi},\bm{\beta}) \mapsto \mathcal{L}(\bm{\psi}, \bm{\beta}) +  \lambda \cdot \mathcal{R}_{\bm{\beta}} (\bm{\beta}) %\tag{test}
\end{equation}

denote the regularized objective function in its base parametrization $(\bm{\psi}, \bm{\beta}) \in \mathbb{R}^{d_{\psi}} \times \mathbb{R}^{d}$, where $\bm{\beta}$ is an arbitrary subset of all model parameters, and $\bm{\psi}$ comprises the complementary components. Further, let  $\mathcal{L}:\mathbb{R}^{d_{\psi}} \times \mathbb{R}^{d} \to \mathbb{R}^{+}_{0}$ be a smooth and potentially non-convex
objective. Although this definition comprises a wide range of widely used loss functions, we assume a smooth $\mathcal{L}$ mainly to emphasize the transfer from a non-smooth $\mathcal{P}$ to an equivalent smooth problem that becomes amenable to smooth first-order optimization methods.[In fact, the proposed optimization transfer
can be readily extended to, e.g., neural networks with non-differentiable activations without further assumptions. It then only accounts for the non-smoothness induced by the regularizer.]
In a typical empirical risk minimization setting, $\mathcal{L}$ can be written more explicitly as $\mathcal{L}(\bm{\psi}, \bm{\beta}) = \sum_{i=1}^{n} \mathscr{L}\left(\bm{y}_{i}, f({\bm{x}_i}|\bm{\psi},\bm{\beta}) \right)$, with independently sampled data $\mathcal{D}\triangleq\left\{\left(\boldsymbol{x}_{i}, \bm{y}_{i}\right)\right\}_{i=1}^{n}$, $(\bm{x}_i,\bm{y}_i) \in\mathcal{X} \times \mathcal{Y}$. Here,
$\mathcal{X} \subseteq \mathbb{R}^{d_x}\,,\, \mathcal{Y}\subseteq \mathbb{R}^{d_y}$ denote generic feature and label spaces, $\mathscr{L}:\mathcal{Y}\times\mathbb{R}^{d_y} \to \mathbb{R}_{0}^{+}$ is an arbitrary loss contribution, and the (parametric) model $f: \mathcal{X} \to \mathbb{R}^{d_y}$ is
parametrized by $(\bpsi,\bbeta)$.

The non-smooth and potentially non-convex regularizer $\Rbeta(\bbeta)$ is defined as

\begin{equation}
\mathcal{R}_{\bm{\beta}}: \mathbb{R}^{d} \to \mathbb{R}^{+}_{0},\, \bm{\beta} \mapsto \mathcal{R}_{\bm{\beta}}(\bm{\beta})\,,
\end{equation}

with $\lambda \geq 0$ controlling the amount of regularization. To be precise, given a partition $\mathcal{G}$ of parameter indices $[d]$ into $L$ groups, we here consider regularizers $\mathcal{R}_{\bm{\beta}}(\bm{\beta})$ of the form

\begin{equation} \label{eq:set-regu-beta}
{\textstyle \mathcal{R}_{\bm{\beta}}(\bm{\beta}) \in \Big\{ \mathcal{R}: \mathbb{R}^{d} \to \mathbb{R}_0^{+}\,, \bm{\beta} \mapsto \sum_{j=1}^{L} \omega_j \norm{\bm{\beta}_j}_p^q \;\big|\; 0<q \leq p\leq2 ,\; \omega_j > 0 \; \forall \,j %\in[L]
\Big\}}\,.
\end{equation}

Note that setting $p=q$, $L=1$ and $\omega_j=1\,\forall\, j$ reduces the expression to the familiar $\ell_q$ regularizer $\Rbeta(\bbeta)=\norm{\bbeta}_q^q$. Merely setting $\omega_j=1$ results in the $\ell_{p,q}$ regularizer, whereas, e.g., $\omega_j = |\mathcal{G}_j|\in\mathbb{N}, p=2, q=1$ yields the $\ell_{2,1}$ group lasso [Yuan and Lin, 2006].

Smooth optimization transfer  To transfer the non-smooth optimization of $\mathcal{P}$ to a smooth surrogate $\mathcal{Q}$, first consider a parametrization of $\bm{\beta}$ defined by $\K(\bxi)=\bm{\beta}$ for $\bxi \in \Rdxi$.
As the parametrizations considered in this paper are based on Hadamard products and variations thereof, they can be described by the following set of assumptions:

[Parametrization map $\K$]
The parametrization map $\K:\Rdxi \to \Rd, \bxi \mapsto \bbeta$ is a smooth surjection with the following properties:

* $\K$ is block-separable, i.e., for a partition of $[d]$ into $L\leq d$ groups of size $|\Gj|, j \in [L]$, the corresponding $\bbeta_j$ are parametrized by disjoint subsets $\bxi_j$ of the entries of $\bxi$. That is, $\K$ is the Cartesian function product $\K(\bxi)=(\K_1(\bxi_1),\ldots, \K_L(\bxi_L))$ of block-wise parametrizations $\K_j(\bxi_j)=\bbeta_j$.

* All $\bbeta_j \in \mathbb{R}^{|\mathcal{G}_j|} \setminus \{\bm{0}\}$ are regular values of $\K_j(\bxi_j)$ for each $j \in [L]$, i.e., the Jacobian $\mathcal{J}_{\K_j}(\bxi_j)$ has full rank $|\mathcal{G}_j|$ for all $\bxi_j \in \K_j^{-1}(\bbeta_j)$.

* $\K_j(\bxi_j)$ is positively homogeneous of degree (here “depth”) $k>1$, i.e., $\K_j(c\, \bxi_j)=c^k\, \K_j(\bxi_j)$ for all $\bxi_j$ and $c>0$, ensuring the fibers of $\K$ are scaled versions of each other at regular values $\bbeta_j$.

* Each $\bxi_j$ is a block vector containing $k$ Hadamard factors $\bxi_{jl}, l \in [k]$, so that $\K_j(\bxi_{j1},\ldots,\bxi_{jk})$ has the zero-product property, i.e., $\bbeta_j=\bm{0}$ if and only if $\bxi_{jl}=\bm{0}$ for at least one $l \in [k]$.

Note that the degree of homogeneity $k$ mentioned in c) coincides with the number of Hadamard factors $k$ in d) for all (monomial) parametrizations that only contain Hadamard factors with unit exponents, comprising all parametrizations considered here except those employing parameter sharing or Hadamard powers.
Moreover, we define a smooth and strongly convex surrogate regularization function
$\mathcal{R}_{\bm{\xi}}: \Rdxi \to \mathbb{R}^{+}_{0}, \bm{\xi} \mapsto \mathcal{R}_{\bm{\xi}}(\bm{\xi})$.
Throughout this work, each surrogate regularizer
is taken to be a weighted sum of $\ell_2$ penalties of components of $\bm{\xi}$, i.e., is of the form

\begin{equation}\label{eq:set-regu-xi}
{\textstyle \mathcal{R}_{\bm{\xi}}(\bm{\xi}) \in \Big\{ \mathcal{R}: \mathbb{R}^{d_{\bm{\xi}}} \to \mathbb{R}_0^{+},\; \bxi \mapsto \sum_{j=1}^{\dxi} \tilde{\omega}_j \; \xi_j^2 \;\big|\; \tilde{\omega}_j > 0 \; \forall \,j %\in[\dxi]
\Big\}}\,.
\end{equation}

Together, these define our proposed optimization transfer approach to construct an equivalent smooth surrogate $\Q(\bpsi,\bxi)$ from the non-smooth objective $\P(\bpsi,\bbeta)$:

We define a smooth optimization transfer for an objective $\P(\bpsi,\bbeta)=\L(\bpsi,\bbeta)+\lambda \Rbeta(\bbeta)$ as in (<ref>), with non-smooth regularizer $\mathcal{R}_{\bm{\beta}}(\bbeta)$ as in (<ref>), as the tuple $(\Rbeta,\K,\Rxi)$, where $\K(\bxi)$ is a smooth and surjective parametrization of $\bbeta \in \Rd$, and $\Rxi(\bxi)$ is a smooth surrogate penalty term imposed on $\bxi \in \Rdxi$, as defined in (<ref>). The smooth surrogate $\mathcal{Q}$ can then be constructed from $(\Rbeta,\K,\Rxi)$ by first applying the parametrization $\bbeta=\K(\bxi)$ to obtain the “lifted” objective $\P(\bpsi,\K(\bxi))$, and further substituting $\mathcal{R}_{\bm{\xi}}(\bm{\xi})$ for $\mathcal{R}_{\bm{\beta}}(\mathcal{K}(\bm{\xi}))$:

\begin{align} \label{eq:g-beginning}
\mathcal{Q}:\mathbb{R}^{d_{\psi}}\times \Rdxi \to \mathbb{R}_{0}^{+},\,(\bm{\psi},\bm{\xi}) \mapsto \mathcal{L}(\bm{\psi}, \mathcal{K}(\bm{\xi})) +  \lambda \cdot \mathcal{R}_{\bm{\xi}} (\bm{\xi}) \,.
\end{align}

The next definition explicitly states our notion of equivalence between $\P$ and $\Q$:

We say the two optimization problems
$$\underset{\bm{\psi},\,\bm{\beta}}{\text{minimize}}\; \mathcal{P}(\bm{\psi},\bm{\beta})\quad\; \text{and}\;\quad \underset{\bm{\psi},\,\bm{\xi}}{\text{minimize}}\; \mathcal{Q}(\bm{\psi},\bm{\xi})\,,$$
as defined in (<ref>) and (<ref>), are equivalent if the following conditions hold:

* $\underset{\bm{\psi},\,\bm{\beta}}{\inf}\; \mathcal{P}(\bm{\psi},\bm{\beta}) = \underset{\bm{\psi},\,\bm{\xi}}{\inf}\, \mathcal{Q}(\bm{\psi},\bm{\xi})$, i.e., their globally optimal values coincide.

* If $(\hat{\bm{\psi}},\hat{\bm{\beta}})$ is a local minimizer of $\mathcal{P}(\bm{\psi},\bm{\beta})$, then there is a local minimizer $(\hat{\bm{\psi}},\hat{\bm{\xi}})$ of $\mathcal{Q}(\bm{\psi},\bm{\xi})$ with $\hat{\bm{\xi}}\in \mathcal{K}^{-1}(\hat{\bm{\beta}})$ and $\mathcal{Q}(\hat{\bm{\psi}}, \hat{\bm{\xi}}) = \mathcal{P}(\hat{\bm{\psi}}, \hat{\bm{\beta}})$.

* If $(\hat{\bm{\psi}},\hat{\bm{\xi}})$ is a local minimizer of $\mathcal{Q}(\bm{\psi},\bm{\xi})$, then $(\hat{\bm{\psi}},\hat{\bm{\beta}})$ with $\hat{\bm{\beta}}=\mathcal{K}(\hat{\bm{\xi}})$ is a local minimizer of $\mathcal{P}(\bm{\psi},\bm{\beta})$ and $\mathcal{Q}(\hat{\bm{\psi}}, \hat{\bm{\xi}}) = \mathcal{P}(\hat{\bm{\psi}}, \hat{\bm{\beta}})$.

Equivalence of local minima is particularly important for non-convex regularization, encompassed by the second and third conditions, as finding global minima in non-convex optimization is challenging and for the most part intractable. Moreover, in non-convex regularization, local minima have been observed to generalize similarly or even better than global minima on test data [Chartrand and Yin, 2008, Chartrand, 2007, Olsson et al., 2017].

This so-called matching of local minima [Levin, 2020] ensures that the transfer from the non-smooth objective $\P$ to a smooth objective $\Q$ preserves such properties. By focusing only on global minima, important information about the structure of problem structure
is neglected. Importantly, we do not

introduce spurious local minima in $\mathcal{Q}$, which would
artificially increase the difficulty of the optimization problem.
Through the matching property, we can further use the surjection $\K(\bxi)$ to reconstruct all (local) minimizers of $\mathcal{P}$ from local minimizers of $\mathcal{Q}$ as $\K(\hbxi)=\hbbeta$. To guarantee this matching of local minima property for $\P(\bpsi,\bbeta)$ under the parametrization $\P(\bpsi,\K(\bxi))$, local openness of the parametrization mapping $\K(\bxi)$ at all local minimizers $\hat{\bxi}$ of $\P(\bpsi,\K(\bxi))$ is a crucial property [Nouiehed and Razaviyayn, 2022]. Levin et al., 2024 show that it is both a necessary and sufficient condition for the preservation of local minima under smooth parametrization.[Local openness is closely related to, but distinct from the notion of continuity, which is defined as
$\forall\, \varepsilon>0 \, \exists \, \delta>0:\,\K(\mathcal{B(\bxi)},\delta) \subseteq \mathcal{B}(\K(\bxi),\varepsilon)$ using the same notation. ]

A mapping $\mathcal{K}: \Rdxi \to \mathbb{R}^{d},\, \bm{\xi} \mapsto \K(\bxi)$ is locally open at $\bxi$ if for every $\varepsilon>0$ we can find $\delta>0$ such that $\mathcal{B}(\K(\bxi), \delta) \subseteq \K(\mathcal{B}(\bxi, \varepsilon))$. Further, the map $\K$ is called globally open if it is locally open at all $\bxi \in \Rdxi$.

General theoretical results
Using the function characterizations encapsulated in Definition <ref>, we can now prove the following results. Note that these hold for any continuous, potentially unregularized objective $\P(\bpsi,\bbeta)$ under reparametrization:

If $(\hat{\bpsi},\hat{\bbeta})$ is a local minimizer of $\P(\bpsi,\bbeta)$, and $\K(\bxi)$ is a continuous surjection, then all $(\hat{\bpsi},\hat{\bxi})$ such that $\hat{\bxi}\in\K^{-1}(\hat{\bbeta})$ are local minimizers of $\P(\bpsi,\K(\bxi))$ with $\P(\hat{\bpsi},\hat{\bbeta})=\P(\hat{\bpsi},\K(\hat{\bxi}))$.

If $(\hat{\bpsi},\hat{\bxi})$ is a local minimizer of $\P(\bpsi,\K(\bxi))$, and the continuous surjection $\K(\bxi)$ is locally open at $\hbxi$, then $(\hat{\bpsi},\K(\hat{\bxi}))=(\hbpsi,\hbbeta)$ is a local minimizer of $\P(\bpsi,\bbeta)$ with $\P(\hat{\bpsi},\hat{\bbeta})=\P(\hat{\bpsi},\K(\hat{\bxi}))$.

Their proofs are given in Appendices <ref> and <ref>. Together, both results show that the set of local minima of $\P(\bpsi,\bbeta)$ and $\P(\bpsi,\K(\bxi))$ are equal
if $\K(\bxi)$ is locally open at all local minimizers of $\P(\bpsi,\K(\bxi))$, and the local minimizers are related via $(\hbpsi,\K(\hbxi))=(\hbpsi,\hbbeta)$. Still, for non-smooth regularizers, smoothly parametrizing $\bbeta$ will not result in a smooth optimization problem. However, the results using local openness of the map $\K(\bxi)$ can be applied to guarantee matching local minima under smooth and surjective parametrizations in general problems, e.g., for parametrizations used in the implicit regularization literature.

In our smooth optimization transfer approach, however, we further replace the parametrized regularizer $\Rbeta(\K(\bxi))$ by the surrogate penalty $\Rxi(\bxi)$ to obtain the smooth surrogate $\Q(\bpsi,\bxi)$. The smooth surrogate penalty $\Rxi$ and the non-smooth regularizer $\Rbeta$ are related through an SVF, defined as follows:

A smooth variational form

is an expression of a function $\Rbeta(\bbeta)$ as the minimum of a smooth surrogate $\Rxi(\bxi)$ over a feasible set given by the fiber $\K^{-1}(\bbeta)$ of a
surjective parametrization map $\K(\bxi)$ at $\bbeta$,

\begin{equation}\label{eq:svg}\Rbeta(\bbeta)=\min_{\bxi:\K(\bxi)=\bbeta}\Rxi(\bxi)\quad \forall \bbeta \in \Rd\,.
\end{equation}

We further require stability of the solutions $\hbxi(\bbeta)$ to the SVF with respect to the constraint parameter $\bbeta$, i.e., continuous dependence of the minimizers $\hbxi \in \argmin_{\bxi:\K(\bxi)=\bbeta}\Rxi(\bxi)$ on $\bbeta$, formalized through upper hemicontinuity of the set-valued solution mapping:

A set-valued map $\hbxi:\Rd \rightrightarrows \Rdxi,\,\bbeta \mapsto \hbxi(\bbeta)$ is said to be upper hemicontinuous (u.h.c.) at $\bbeta \in \Rd$, if $\forall\,\varepsilon>0\,\exists\,\delta>0:\,\hbxi(\mathcal{B}(\bbeta,\delta)) \subseteq \mathcal{B}(\hbxi(\bbeta),\varepsilon)$. Equivalently, for all $\tbbeta \in \mathcal{B}(\bbeta,\delta)$, it holds that all $\tbxi \in \hbxi(\tbbeta)$ belong to $\mathcal{B}(\hbxi(\bbeta),\varepsilon)$.
Note that an $\varepsilon$-ball $\mathcal{B}(\hbxi(\bbeta),\varepsilon)$ around a set $\hbxi(\bbeta) \subset \Rdxi$ is defined as $\bigcup_{\bxi \in \hbxi(\bbeta)} \mathcal{B}(\bxi,\varepsilon)$.

This allows us to formulate the assumptions of our optimization transfer approach regarding the SVF. Note that finding the appropriate SVF is non-trivial and will be derived for each presented regularizer $\Rbeta$ in the respective section.

[Smooth variational form with continuous solution]

* The minimum of the surrogate penalty $\Rxi(\bxi)$ over the
the fiber of the smooth surjection $\K(\bxi)$ at $\bbeta$, is given by
$\min_{\bxi:\K(\bxi)=\bbeta}\Rxi(\bxi) = \Rbeta(\bbeta)\quad \forall \bbeta \in \Rd.$

Thus, $\Rxi(\bxi)$ and $\K(\bxi)$ define a smooth variational form for the non-smooth regularizer $\Rbeta(\bbeta)$ according in Definition <ref>.

* The smooth surrogate penalty $\Rxi(\bxi)$ majorizes the parametrized non-smooth regularizer $\Rbeta(\K(\bxi))$, i.e.,  $\Rxi(\bxi)\geq\Rbeta(\K(\bxi))\forall\bxi \in \Rdxi$.

* The set-valued solution map $\hbxi(\bbeta):\Rd\rightrightarrows\Rdxi,\,\bbeta \mapsto \underset{\bxi:\K(\bxi)=\bbeta}{\argmin} \Rxi(\bxi)$ is u.h.c.

Instead of requiring local openness, as previously for smooth parametrizations without a change of regularizers, we use the upper hemicontinuity of the solution map $\hbxi(\bbeta)$ in Assumption <ref>, a property that is easily obtained as a by-product in the construction of our smooth variational forms. For details on set-valued analysis, we refer to Aubin and Frankowska, 2009. Together with the majorization property, we can establish a matching local minima property between $\P(\bpsi,\bbeta)$ and $\Q(\bpsi,\bxi)$.

If $(\hbpsi,\hbbeta)$ is a local minimizer of $\P(\bpsi,\bbeta)$,
then all $(\hbpsi,\hbxi)$ such that $\hbxi \in \argmin_{\bxi:\K(\bxi)=\hbbeta} \Rxi(\bxi)$ are local minimizers of $\Q(\bpsi,\bxi)$ with $\Q(\hbpsi,\hbxi)=\P(\hbpsi,\hbbeta)$ under Assumptions <ref> and <ref>.

If $(\hbpsi,\hbxi)$ is a local minimizer of $\Q(\bpsi,\bxi)$,
then $(\hbpsi,\K(\hbxi))=(\hbpsi,\hbbeta)$ is a local minimizer of $\P(\bpsi,\bbeta)$ with $\Q(\hbpsi,\hbxi)=\P(\hbpsi,\hbbeta)$ under Assumptions <ref> and <ref>.

In the proof of Lemma <ref>, it is also established that for all local minimizers $(\hbpsi,\hbxi)$ of $\Q(\bpsi,\bxi)$, $\hbxi$ must also minimize the SVF over the fiber $\K^{-1}(\K(\hbxi))$. Figure <ref> provides some intuition behind the preceding results assuming no additional parameters $\bpsi$.

It illustrates the relationship between a local minimizer $\hbxi$ of $\Q(\bxi)$ and the corresponding local minimizer $\K(\hbxi)=\hbbeta$ of $\P(\bbeta)$. Note that at points around $\hbxi$ that are in the image of $\hbxi(\bbeta)$ (dashed green), we have equality of $\Q(\hbxi(\bbeta))$ and $\P(\bbeta)$.
By Lemma <ref>, if $\hbbeta$ is a local minimizer of $\P(\bbeta)$, then any $\hbxi \in \K^{-1}(\hbbeta)$ (red curve) is a local minimizer of the non-smooth overparametrized $\P(\K(\bxi))$. But only those $\hbxi(\hbbeta)\in\argmin_{\bxi:\K(\bxi)=\hbbeta}\Rxi(\bxi)\subset \K^{-1}(\hbbeta)$ (red dot at vertex)
are also local minimizers of $\Q(\bxi)$ due to the majorization property $\P(\K(\bxi))\leq\Q(\bxi)\forall \bxi \in \Rdxi$ combined with $\Q(\hbxi)=\P(\K(\hbxi))$. Conversely, if $\hbxi$ is a local minimizer of $\Q(\bxi)$, then by continuity of the solution map $\hbxi(\bbeta)$ at $\K(\hbxi)=\hbbeta$, if there existed $\tbbeta\in\mathcal{B}(\hbbeta,\delta)$ such that $\P(\tbbeta)<\P(\hbbeta)$, this would imply existence of $\tbxi\in\mathcal{B}(\hbxi,\varepsilon)$ with $\Q(\tbxi)<\Q(\hbxi)$, contradicting that $\hbxi$ is a local minimizer of $\Q(\bxi)$. Figure <ref> shows a specific choice of functions for $\K$ and $\Rxi$. The previous results let us now state our main result:

[Schematic illustration of smooth optimization transfer.

(0,0) circle (3cm);

(8,0) circle (1.5cm);

[red] (0,0) circle (3pt);

[blue] (0.32,-0.33) circle (3pt);

[red] (-1.7,1) circle (3pt);

[blue] (-0.9,-1.2) circle (3pt);

[red] (8,0) circle (3pt);

[blue] (7.5,-0.65) circle (3pt);

at (0,-3.5) $\mathcal{B}(\textcolor{red}{\hat{\bm{\xi}}}, \varepsilon)$;

at (8,-3.5) $\mathcal{B}(\textcolor{red}{\hat{\bm{\beta}}}, \delta)$;

[red] at (-0.7,-0.15) $\hat{\bm{\xi}}$;

[blue] at (0.32,-0.89) $\tilde{\bm{\xi}}$;

[red] at (8.5,0) $\hat{\bm{\beta}}$;

[blue] at (8,-0.65) $\tilde{\bm{\beta}}$;

[red] at (3.6,1.4) $\mathcal{K}(\hat{\bm{\xi}})$;

[red] at (3.6,1.4) $\mathcal{K}(\hat{\bm{\xi}})$;

[blue] at (3.6,0.2) $\mathcal{K}(\tilde{\bm{\xi}})$;

[red] at (-3.4,1.5) $\mathcal{K}^{-1}(\hat{\bm{\beta}})$;

[blue] at (-3.2,-1.85) $\mathcal{K}^{-1}(\tilde{\bm{\beta}})$;

[colordk] at (3.7,-1.15) $\hat{\bm{\xi}}(\textcolor{blue}{\tilde{\bm{\beta}}})$;

[colordk] at (-1.5,2.5) $\hat{\bm{\xi}}(\textcolor{black}{\bm{\beta}}) \textcolor{black}{\in \text{arg min}_{\bm{\xi}: \mathcal{K}(\bm{\xi})=\bm{\beta}} \mathcal{R}_{\bm{\xi}}(\bm{\xi})}$;

[red] plot[domain=-1.95:1.95] (-1*cosh()+1, 0.4*sinh());

[blue] plot[domain=-1.93:1.93] (-1.1*cosh()+1.47, 0.4*sinh()-0.4);

[colordk, dashed] (-2.1, 2.1) – (2.1, -2.1);

[->, red, dashed, bend left=30] (0,0) to (7.8,0);

[->, blue, dashed, bend left=30] (0.42,-0.28) to (7.3,-0.5);

[->, red, dashed, bend left=30] (-1.7,1) to (7.8,0.2);

[->, colordk, dashed, bend left=30] (7.4,-0.65) to (0.6,-0.4);

[->, blue, dashed, bend right=30] (-0.9,-1.2) to (7.5,-0.85);

[Contours of HPP in (<ref>) and surrogate $\ell_2$ penalty.

(-9, -9) rectangle (9, 9);

(-9, -9) rectangle (9, 9);

[fill=color6] (0,0) circle (12);
[fill=color5] (0,0) circle (13);
[fill=color4] (0,0) circle (9.5);
[fill=color3] (0,0) circle (7.9);
[fill=color2] (0,0) circle (6.2);
[fill=color1] (0,0) circle (4.5);
[fill=color0] (0,0) circle (3);

[darkgray] (-9, -9) rectangle (9, 9);

[thick,->,darkgray] (-9, 0) – (10, 0) node[below]$u$;

[thick,->,darkgray] (0, -9) – (0, 10) node[left] $v$;

[red, line width=1.3mm, domain=-9:-0.-0.2, samples=100, smooth] plot (,4.5/);
[red, line width=1.3mm, domain=0.2:9, samples=100, smooth] plot (,4.5/);

[blue, line width=1.3mm, domain=-9:-0.-0.2, samples=100, smooth] plot (,10.125/);
[blue, line width=1.3mm, domain=0.2:9, samples=100, smooth] plot (,10.125/);

[red] (-2.1,-2.1) circle (7pt);

[red] (2.1,2.1) circle (7pt);

[blue] (-3.2,-3.2) circle (7pt);

[blue] (3.2,3.2) circle (7pt);

[colordk, dashed, line width=1mm, dash pattern=on 8pt off 8pt] (-9.1, -9.1) – (9.1, 9.1);

[colordk, dashed, line width=1mm, dash pattern=on 8pt off 8pt] (-9.1, 9.1) – (9.1, -9.1);

[black] (0,0) circle (6pt);

[red] at (-1.8,-0.8) 3$\hat{\bm{\xi}}$;
[blue] at (-3.5,-4.75) 3$\tilde{\bm{\xi}}$;
[colordk] at (4.5,-3.85) 2.4
$\hat{\bm{\xi}}(\textcolor{black}{\bm{\beta}\textcolor{colordk}{)} \textcolor{black}{\in \underset{\bm{\xi}:\mathcal{K}(\bm{\xi})=\bm{\beta}}{\text{argmin}}} \mathcal{R}_{\bm{\xi}}(\bm{\xi})}

at (0, -9.5) 10080$\bm{u}$;
at (-9.5, 0) 10080$\bm{v}$;
at (0, 9.5) 10080$\hspace{0.4cm}$;
at (9.6, 0) 10080$\hspace{0.4cm}$;

Relationship between local minimizer $\hbxi$ of $\Q$, the induced minimizer $\K(\hbxi)=\hbbeta$ of $\P$, and the cont. solution mapping $\hbxi(\bbeta)$ of the SVF.
Left: solid curves show two fibers $\K^{-1}(\hbbeta)$ (red) and $\K^{-1}(\tbbeta)$ (blue). The solution map $\hbxi(\bbeta)$ (dashed green) maps to minimizers of the SVF for varying $\bbeta$, where
$\Q$ equals $\P$.

Right: concrete example showing scalar parametrization $\beta_j=\K(u_j,v_j)=u_j v_j$, and surrogate $\ell_2$ regularization $\Rxi(u_j,v_j)=u_j^2+v_j^2$. Each branch of $\K^{-1}(\beta_j)$ has a unique minimal-norm point (vertices).
The $\ell_2$ penalty there is $2|u_j v_j|=2|\beta_j|$, inducing $\ell_1$ regularization.

Let the non-smooth objective $\mathcal{P}(\bpsi,\bbeta)$ and its smooth surrogate $\mathcal{Q}(\bpsi,\bxi)$ be defined as in Equations (<ref>) and (<ref>). Under Assumptions <ref> and <ref>, the optimization problems

\begin{align}
\underset{\bm{\psi},\,\bm{\beta}}{\text{minimize}}\;\P(\bpsi,\bbeta) &\triangleq \L(\bpsi,\bbeta)+\lambda \Rbeta(\bbeta)\,\,\, \text{and} \,\,\, \underset{\bm{\psi},\,\bxi}{\text{minimize}}\;\Q(\bpsi,\bxi) &\triangleq \L(\bpsi,\K(\bxi))+\lambda \Rxi(\bxi)    \nonumber
\end{align}

are equivalent according to Definition <ref>.

For the first point of Definition <ref>, we show that the infima of both $\P(\bpsi,\bbeta)$ and $\Q(\bpsi,\bxi)$ coincide. Because $\L(\bpsi,\K(\bxi))$ is constant on the fiber of $\K$ at $\bbeta=\K(\bxi)$, we can pull in the infimum and re-state it in terms of $\bbeta$:

\begin{align}
\inf_{\bm{\psi}, \bm{\xi}} \mathcal{Q}(\bm{\psi}, \bm{\xi}) = \inf_{\bm{\psi}, \bm{\xi}} \big\{ \mathcal{L}(\bm{\psi}, \mathcal{K}(\bm{\xi})) +  \lambda \cdot \mathcal{R}_{\bm{\xi}} (\bm{\xi})
\big\}
= \inf_{\bm{\psi},\bm{\beta}}  \big\{ \mathcal{L}(\bm{\psi}, \bm{\beta}) +  \lambda \inf_{\bm{\xi}: \mathcal{K}(\bm{\xi})=\bm{\beta}} \{\mathcal{R}_{\bm{\xi}} (\bm{\xi}) \} \big\} \nonumber
\end{align}

By Assumption <ref>, we have $\inf_{\bxi:\K(\bxi)=\bbeta}\Rxi(\bxi)=\min_{\bxi:\K(\bxi)=\bbeta}\Rxi(\bxi)=\Rbeta(\bbeta)$, and thus

\begin{equation}
\inf_{\bm{\psi}, \bm{\xi}} \mathcal{Q}(\bm{\psi}, \bm{\xi}) =  \inf_{\bm{\psi}, \bm{\beta}} \left\{ \mathcal{L}(\bm{\psi}, \bm{\beta}) +  \lambda \mathcal{R}_{\bm{\beta}}(\bm{\beta}) \right\} = \inf_{\bm{\psi}, \bm{\beta}} \mathcal{P}(\bm{\psi}, \bm{\beta})\,. \nonumber
\end{equation}

This shows the first point. For the second and third points of Definition <ref>, we can apply Lemma <ref> together with Lemma <ref> under Assumptions <ref> and <ref> to obtain the required matching of local minima with corresponding minimizers.

From Theorem <ref> it follows that there is a surjective mapping from the set of local minimizers of $\Q$ to the set of local minimizers of $\P$, obtained by restricting the domain of the parametrization $\mathcal{K}$ to the set of local minimizers of $\Q$. Table <ref> shows an (incomplete) summary of the different parametrizations $\mathcal{K}(\bm{\xi})$ of $\bm{\beta}$ that can be represented in our framework, together with the sparse regularization terms $\mathcal{R}_{\bm{\beta}}$ that are induced by applying the smooth and convex regularizers $\mathcal{R}_{\bm{\xi}}$ to the surrogate parameters $\bm{\xi}$.

1cAbbreviation     1c$\mathcal{K}(\cdot)=\bm{\beta}$     1c$\mathcal{R}_{\bm{\xi}}$     1c$\mathcal{R}_{\bm{\beta}}$     1cType
HPP        $\bm{u}\odot\bm{v}$      $\Vert \bm{u} \Vert_{2}^{2} + \Vert \bm{v} \Vert_{2}^{2}$     $2\Vert \bm{\beta} \Vert_1$     $\ell_1$

HDP        $\bm{\gamma}^2-\bm{\delta}^2$      $\Vert \bm{\gamma} \Vert_{2}^{2} + \Vert \bm{\delta} \Vert_{2}^{2}$      $\Vert \bm{\beta} \Vert_1$      $\ell_1$

GHPP      $\bm{u}\odotg\bm{\nu}$       $\sum_{j=1}^{L} (\Vert \bm{u}_j \Vert_{2}^{2} + \nu_j^2)$      $2\Vert\bm{\beta}\Vert_{2,1}$      $\ell_{2,1}$

Adj. GHPP       $\bm{u}\odotg\bm{\nu}$     $\sum_{j=1}^{L} (\Vert \bm{u}_j \Vert_{2}^{2} +|\mathcal{G}_j| \nu_j^2)$     $2\sum_{j=1}^{L} \sqrt{|\mathcal{G}_j|} \Vert \bm{\beta}_j \Vert_2$      $\ell_{2,1}$
5l$k \in \mathbb{N},\; k_1 \in \mathbb{N},\; k_2\triangleq k-k_1 \in \mathbb{N}:$

$\text{HPP}_{k}$      $\bigodot_{l=1}^{k} \bm{u}_{l}$     $\sum_{l=1}^{k} \Vert \bm{u}_{l} \Vert_{2}^{2}$      $k \Vert \bm{\beta} \Vert_{2/k}^{2/k}$      $\ell_{2/k}$

$\text{GHPP}_{k}$     $\bm{u} \odotg \bm{\nu}_{r}^{\odot(k-1)}$     $\sum_{j=1}^{L} \Vert \bm{u}_j \Vert_{2}^{2} + \sum_{r=1}^{k-1} \nu_{jr}^2$      $k \Vert \bm{\beta} \Vert_{2,2/k}^{2/k}$      $\ell_{2,2/k}$

$\text{GHPP}_{k_1,k}$      $\bm{\mu}_{t}^{\odot  k_1} \odotg \bm{\nu}_{r}^{\odot  k_2}$      $\sum_{t=1}^{k_1} \Vert \bm{\mu}_{t}\Vert_{2}^{2}+\sum_{r=1}^{k_2} \Vert \bm{\nu}_{r} \Vert_{2}^{2}$      $k \Vert \bm{\beta} \Vert_{2/k_1,2/k}^{2/k}$      $\ell_{2/k_1,2/k}$

$\text{HDP}_{k}$     $\bm{u}_{l}^{\odot  k} - \bm{v}_{l}^{\odot  k}$      $\sum_{l=1}^{k} \Vert \bm{u}_{l} \Vert_{2}^{2} + \Vert \bm{v}_{l} \Vert_{2}^{2}$      $k\Vert \bm{\beta} \Vert_{2/k}^{2/k}$      $\ell_{2/k}$

$\text{HPP}_{k}^{shared}$     $\bm{u} \odot \bm{v}^{k-1}$      $\Vert \bm{u} \Vert_{2}^{2} + (k-1) \Vert \bm{v} \Vert_{2}^{2}$      $k \Vert \bm{\beta} \Vert_{2/k}^{2/k}$      $\ell_{2/k}$

$\text{HDP}_{k}^{shared}$     $\bm{u}^k - \bm{v}^k$      $\Vert \bm{u} \Vert_{2}^{2} + \Vert \bm{v} \Vert_{2}^{2}$      $\Vert \bm{\beta} \Vert_{2/k}^{2/k}$       $\ell_{2/k}$
5l$k \in \mathbb{R}_{>1},\; k_1 \in \mathbb{R}_{>1},\; k_2\triangleq k-k_1 \in \mathbb{R}_{>0}:$

$\text{HPowP}_{k}$     $\bm{u} \odot |\bm{v}|^{\circ (k-1)}$      $\Vert \bm{u} \Vert_{2}^{2} + (k-1) \Vert \bm{v} \Vert_{2}^{2}$      $k \Vert \bm{\beta} \Vert_{2/k}^{2/k}$     $\ell_{2/k}$

Powerprop.     $\bm{v} \odot |\bm{v}|^{\circ (k-1)}$     $\Vert \bm{v} \Vert_{2}^{2}$      $\Vert \bm{\beta} \Vert_{2/k}^{2/k}$      $\ell_{2/k}$

$\text{GHPowP}_{k}$     $\bm{u} \odotg |\bm{\nu}|^{\circ (k-1)}$     $\Vert \bm{u} \Vert_{2}^{2} + (k-1) \Vert \bm{\nu} \Vert_{2}^{2}$     $k \Vert \bm{\beta} \Vert_{2,2/k}^{2/k}$     $\ell_{2,2/k}$

$\text{GHPowP}_{k_1,k}$     $(\bm{\mu} \odot |\bm{\mu}|^{\circ (k_1-1)}) \odotg |\bm{\nu}|^{\circ k_2}$     $k_1 \Vert \bm{\mu} \Vert_{2}^{2} + k_2 \Vert \bm{\nu} \Vert_{2}^{2}$     $\Vert \bm{\beta} \Vert_{2/k_1, 2/k}^{2/k}$     $\ell_{2/k_1,2/k}$

Overview over induced regularizers $\mathcal{R}_{\bm{\beta}}$ obtained by parametrizing $\bm{\beta}$ through $\mathcal{K}(\bm{\xi})$ and adding a smooth and convex penalty $\mathcal{R}_{\bm{\xi}}$.
The letter “H" abbreviates “Hadamard", the letter “G" abbreviates “Group", “PP" abbreviates “Product Parametrization", “DP" abbreviates “Difference Parametrization", and “PowP" stands for “Power Parametrization". Novel parametrizations in blue.

§ SMOOTH $\ELL_1$ REGULARIZATION USING HADAMARD PRODUCTS

In this section, we introduce two smooth surrogate approaches for sparsity-inducing $\ell_1$ regularization and provide some intuition on the underlying geometry.

§.§ Hadamard Product Parametrization

We first present a canonical example of our optimization transfer framework based on the so-called Hadamard product parametrization [Hoff, 2017]. This approach enables smooth optimization of $\ell_1$ regularized objectives by applying an overparametrization $\bbeta=\bu\odot\bv$ and imposing $\ell_2$ regularization on the surrogate parameters.
As the prototype case of our framework, this connection between $\ell_1$ and $\ell_2$ regularization under reparametrization
will be briefly re-derived in the following.
Assume a non-smooth $\ell_1$ regularized objective $\P$ with $\Rbeta(\bbeta)=2\norm{\bbeta}_1$ and consider the following overparametrized smooth surrogate $\Q$:

\begin{align}
&{\textstyle \mathcal{P}:\mathbb{R}^{d_{\psi}}\times\mathbb{R}^d \to \mathbb{R}_{0}^{+},\,(\bm{\psi},\bm{\beta}) \mapsto \mathcal{L}(\bm{\psi}, \bm{\beta}) + 2 \lambda \|\bm{\beta}\|_{1} = %\sum_{i=1}^{n} \mathscr{L}\left(y_{i}, f(\bm{x}_i|{\bm{\psi},\bm{\beta}}) \right)
\mathcal{L}(\bm{\psi}, \bm{\beta})
+ 2\lambda \sum_{j=1}^{d}\left|\beta_{j}\right| } \,, \label{eq:q-abstract-intext}\\
&{\textstyle \mathcal{Q}:\mathbb{R}^{d_{\psi}}\times\mathbb{R}^d\times\mathbb{R}^d \to \mathbb{R}^{+}_{0},\,(\bm{\psi},\bm{u}, \bm{v}) \mapsto \mathcal{L}(\bm{\psi}, \bm{u}\odot\bm{v}) + \lambda\sum_{j=1}^{d}\big(u_j^2+v_j^2\big) } \label{eq:g-abstract-intext}\,. %\\
%&\hspace{5.5cm} %=\sum_{i=1}^{n} \mathscr{L}\left(y_{i}, f(\bm{x}_i|{\bpsi,\bu\odot\bv})\right)
%=\mathcal{L}(\bm{\psi}, \bm{u}\odot\bm{v})
%+\lambda \sum_{j=1}^{d}\left(u_j^2+v_j^2\right) \,. \nonumber
\end{align}

In (<ref>), the HPP map is defined as

\begin{equation} \label{eq:hpp-def}
\mathcal{K}:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}^{d}, (\bm{u}, \bm{v})\mapsto \bm{u} \odot \bm{v} = \bm{\beta} \,,
\end{equation}

while the surrogate penalty is the plain $\ell_2$ regularizer $\Rxi(\bu,\bv)=\norm{\bu}_2^2+\norm{\bv}_2^2$ with $\bxi=(\bu,\bv)^{\top}$. Our goal is to show that the minimization of (<ref>) and (<ref>) is equivalent according to Definition <ref>. In our smooth optimization transfer framework, the main assumption of Theorem <ref> requires that the HPP $\bbeta=\bu\odot\bv$ and the surrogate regularization $\Rxi(\bu,\bv)=\Vert \bm{u} \Vert_{2}^{2} + \Vert \bm{v} \Vert_{2}^{2}$ together define an SVF for $\Rbeta(\bbeta)=2\norm{\bbeta}_1$ (cf. Definition <ref>). The inequality of arithmetic and geometric means (AM-GM) provides a simple but powerful tool for the construction of SVFs using $\ell_2$ regularization as the surrogate penalty and is repeatedly applied throughout the paper. The AM-GM inequality states that, given a list of $n \in \mathbb{N}$ non-negative numbers $x_i,\,i=1,\ldots,n$, it holds that $\frac{x_1 + \ldots + x_n}{n} \geq \sqrt[n]{x_1 \cdots x_n}$ with equality if and only if $x_1 = \ldots = x_n$.

Given a list of $n \in \mathbb{N}$ non-negative numbers $x_i,\,i=1,\ldots,n$, it holds that

\begin{equation} \label{eq:am-gm-plain}
\frac{x_1 + \ldots + x_n}{n} \geq \sqrt[n]{x_1 \cdots x_n} \nonumber
\end{equation}

with equality if and only if $x_1 = \ldots = x_n$.

In the case of the HPP, it allows us to determine the minimum of the surrogate penalty $\Rxi$ under the constraint $\bm{u}\odot\bm{v}=\bbeta$ for any $\bbeta\in\mathbb{R}^{d}$.

Given the parametrization map $\K(\bu,\bv)=\bu\odot\bv$, the minimum of  surrogate $\ell_2$ regularization $\Rxi(\bu,\bv)=\norm{\bu}_2^2+\norm{\bv}_2^2$ subject to $\bu\odot\bv=\bbeta$ constitutes an SVF for $\Rbeta(\bbeta) = 2 \norm{\bbeta}_1$ in (<ref>) and is given by

$\min_{\bm{u},\bm{v}: \bu\odot\bv=\bbeta} \quad \Vert \bm{u} \Vert_{2}^{2} + \Vert \bm{v} \Vert_{2}^{2} = 2\norm{\bbeta}_1\; \,\, \forall \bbeta \in \mathbb{R}^{d}$.

Because the HPP defines element-wise multiplication, we can minimize $u_j^2 + v_j^2$ such that $u_j v_j = \beta_j$ for some $\beta_j \in \mathbb{R}$ and $j=1,\ldots,d$. Using the AM-GM inequality for $n=2$ and the non-negative numbers $u_j^2$ and $v_j^2$, we obtain

\frac{u_j^2 + v_j^2}{2} \geq \sqrt{u_j^2 v_j^2} = \sqrt{(u_j v_j)^2} = \sqrt{\beta_j^2} =  |\beta_j| \,,

which reduces to equality if and only if $u_j^2 = v_j^2$, yielding a minimum value of $u_j^2 + v_j^2 = 2 |\beta_j|$. Repeating this procedure for all $j=1,\ldots,d$ shows that the constrained minimum of the surrogate penalty is indeed equal to $2 \Vert \bm{\beta} \Vert_1$ for all $\bbeta\in\Rd$.

The optimality conditions $u_j^2=v_j^2=|\beta_j|$ further ensure that we can derive continuous solutions $(\hat{u}_j,\hat{v}_j)$ as functions of $\beta_j=u_j v_j$. Analytically,  $(\hat{u}_j,\hat{v}_j)$ are of the form

\begin{equation}
\underset{(u_j, v_j): u_j v_j = \beta_j}{\argmin} u_j^2+v_j^2 =
\begin{cases}
\left(\sqrt{|\beta_j|},\sqrt{|\beta_j|}\right) \;\text{and}\;\left(-\sqrt{|\beta_j|},-\sqrt{|\beta_j|}\right) & \text{for $\beta_j > 0$} \\
(0,0) & \text{for $\beta_j=0$} \\
\left(\sqrt{|\beta_j|},-\sqrt{|\beta_j|}\right) \;\text{and}\; \left(-\sqrt{|\beta_j|},\sqrt{|\beta_j|}\right) & \text{for $\beta_j < 0$} \nonumber \, .
\end{cases}
\end{equation}

Further, we can determine the number of equivalent solutions in the surrogate problem, corresponding to a specific solution in the original problem, using the AM-GM inequality. Due to this duplicity for each $j=1,\ldots,d$, there are a total of $2^s$ equivalent local minimizers $(\hat{\bm{\psi}}, \hat{\bm{u}}, \hat{\bm{v}})$ of $\mathcal{Q}$ for each local minimizer $(\hat{\bm{\psi}}, \hat{\bm{\beta}})$ of $\mathcal{P}$, where $s=||\hat{\bbeta}||_0$.

Moreover, we can establish the stability of a solution mapping in a more general setting for solutions that are characterized by necessary optimality conditions similar to the above, obtained from applying the AM-GM inequality to the squared surrogate parameters $u_j^2$ and $v_j^2$ for $j\in [d]$.

Let $\hbxi(\bbeta):\Rd \rightrightarrows \Rdxi,\,\bbeta \mapsto \argmin_{\bxi:\K(\bxi)=\bbeta}\Rxi(\bxi)$, be a set-valued solution mapping, where the components of $\bbeta$ can be separated into $j=1,\ldots,L \leq d$ groups with independent corresponding solution parameters. Within each group vector $\bbeta_j$, the solution parameter vectors in $\hbxi_j(\bbeta_j)$ can be further grouped into factors $\hbxi_{jl}$ for $l=1,\ldots,k$. Assume we are given necessary optimality conditions $\hbxi_j(\bbeta_j)\subseteq \{\hbxi_j:\,\Vert \hbxi_{j1} \Vert_2^2 = \ldots = \Vert \hbxi_{jk} \Vert_2^2 = T(\bbeta_j)\}$ for all $j = 1, \ldots, L$, where $T(\bbeta_j)$ is a continuous scalar-valued function that is $0$ if and only if $\bbeta_j=0$ and strictly increasing in $\Vert\bbeta_j\Vert_2$. Then the solution map is upper hemicontinuous at all $\bbeta \in \Rd$.

Note that for the simple HPP, we have $L=d$ and $k=2$, so that the optimality conditions simplify to $u_j^2=v_j^2=T(\beta_j)$ for $j=1,\ldots,d$, where $T(\beta_j)=|\beta_j|$.

The optimization of $\P$ in (<ref>) is equivalent to the optimization of the smooth surrogate $\Q$ in (<ref>) by Definition <ref>, and solutions to the base problem can be constructed as $(\hbpsi,\hat{\bbeta})=(\hbpsi,\hat{\bu}\odot\hat{\bv})$.

The result directly follows by combining Lemma <ref> with Theorem <ref> and observing that $\K$ conforms to the requirements on a parametrization map.

For brevity, this proof will be omitted from now. Inspired by the implicitly regularized elastic net Zhao et al., 2022, we propose the following explicitly regularized smooth variant:

(Smooth elastic net formulation via HPP)
We can readily extend the HPP optimization transfer for $\ell_1$ regularization to the Elastic Net penalty $\mathcal{R}_{\bm{\beta}}(\bm{\beta})\triangleq (1-\alpha)\norm{\bm{\beta}}_1 + \alpha \norm{\bm{\beta}}_2^2$,  $\alpha\in(0,1)$, as introduced in Zou and Hastie, 2005. To do this, we merely redefine $\tilde{\L}(\bpsi,\bbeta) \triangleq \L(\bpsi,\bbeta)+\lambda\alpha \norm{\bbeta}_2^2$ and $\lambda\Tilde{\mathcal{R}}_{\bbeta}(\bbeta) \triangleq \lambda(1-\alpha)\norm{\bbeta}_1$. Applying the HPP, we minimize
$$\tilde{\L}(\bpsi, \bm{u} \odot \bm{v})+\frac{\lambda}{2}\Tilde{\mathcal{R}}_{\bxi}(\bm{u},\bm{v}) = \L(\bpsi,\bm{u}\odot\bm{v})+\lambda\alpha \norm{\bm{u}\odot\bm{v}}_2^2 + \frac{\lambda (1-\alpha)}{2}(\norm{\bm{u}}_2^2 + \norm{\bm{v}}_2^2)$$
over $(\bpsi, \bm{u},\bm{v})$ instead of $(\bpsi,\bbeta)$.
Solutions to the Elastic Net-regularized problem can be reconstructed after optimization of the smooth surrogate as $(\hat{\bpsi},\hat{\bbeta})=(\hat{\bpsi},\hat{\bm{u}}\odot\hat{\bm{v}})$.

Further, for general smoothly parametrized objectives $\P(\bpsi,\K(\bu,\bv))$ using the HPP, one requirement for equivalence to $\P(\bpsi,\bbeta)$ by Lemma <ref> is that the parametrization $\K$ is locally open at the local minimizers $(\hat{\bu},\hat{\bv})\in\Rd \times \Rd$ of $\P(\bpsi,\K(\bu,\bv))$. In fact, the Hadamard product of two $d$-dimensional real-valued vectors is a (uniformly) open map everywhere [Balcerzak et al., 2016], meaning that under $\K$, the image of any open ball around $(\bu,\bv)$ in $\Rd \times \Rd$ contains an open ball around $(\bu\odot\bv)$ in $\Rd$ for all $(\bu,\bv)\in\Rd \times \Rd$ (cf. Def. <ref>).

§.§ The Hadamard Difference Parametrization

An alternative smooth optimization transfer approach for $\ell_1$ regularization is based on the Hadamard difference parametrization (HDP), which is defined as

\begin{equation}\label{eq:hdp-def}
\mathcal{K}:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}^{d},\, (\bm{\gamma}, \bm{\delta})\mapsto \bm{\gamma} \odot \bm{\gamma} - \bm{\delta} \odot \bm{\delta} = \bm{\beta} \,.
\end{equation}

This variant of the HPP is often employed in studying the implicit regularization effects of GD in linear neural networks and is sometimes referred to as an “unbiased" diagonal network of depth $2$ [Woodworth et al., 2020].
This description is used because the HDP allows for a balanced non-zero initialization of $(\bm{\gamma},\bm{\delta})$ with weights of equal magnitude, e.g., $(\bm{\gamma}_0,\bm{\delta}_0)=(\alpha\mathds{1}_d,\alpha\mathds{1}_d)$ for some small constant $\alpha>0$, that results in a zero initialization of $\bbeta$. In contrast, for the HPP, a zero initialization of $\bbeta$ either requires an unbalanced initialization $\bu_0\neq\bv_0$ or setting $(\bu_0,\bv_0)=(\bm{0},\bm{0})$, which initializes the optimization process exactly at a saddle point, resulting in GD to get stuck as gradient updates are zero for all iterations. This can be circumvented using the HDP, facilitating an easier theoretical analysis by enabling a balanced zero initialization <cit.>.[On the other hand, Even et al., 2023 show that using the HPP with initialization $(\bu_0,\bv_0)=(\sqrt{2}\alpha\mathds{1}_d,\bm{0})$ yields identical optimization trajectories to the HDP initialization described above.] In our framework, applying the HDP and imposing explicit surrogate $\ell_2$ regularization on $\bm{\gamma}$ and $\bm{\delta}$ corresponds to $\ell_1$ regularization of $\bbeta$, albeit without the scaling factor of $2$ present in the HPP. To establish a connection between the HDP and the HPP, let $\bm{\gamma} = \frac{\bm{u}+\bm{v}}{2}$ and $\bm{\delta} = \frac{\bm{v}-\bm{u}}{2}$, or equivalently, $\bm{u} = \bm{\gamma} - \bm{\delta}$ and $\bm{v} = \bm{\gamma} + \bm{\delta}$. Then it is easy to confirm that $\bm{\gamma} \odot \bm{\gamma} - \bm{\delta} \odot \bm{\delta} = \bm{u} \odot \bm{v}$.

For an objective $\P$ with $\ell_1$ regularization of $\bbeta$, we can construct a smooth surrogate $\Q$ applying the HDP and surrogate $\ell_2$ regularization. Both objectives can be written as

\begin{align}
&{\textstyle \mathcal{P}(\bm{\psi}, \bm{\beta}) = \mathcal{L}(\bm{\psi}, \bm{\beta}) + \lambda \|\bm{\beta}\|_{1} =
%\sum_{i=1}^{n} \mathscr{L}\left(y_{i}, f(\bm{x}_i|{\bm{\psi},\bm{\beta}}) \right)
\mathcal{L}(\bm{\psi}, \bm{\beta})
+ \lambda \sum_{j=1}^{d}\left|\beta_{j}\right| }\,, \label{eq:optim_q_diff} \\
&{\textstyle \mathcal{Q}(\bm{\psi}, \bm{\gamma}, \bm{\delta}) =  \mathcal{L}(\bm{\psi},\bm{\gamma}^2 - \bm{\delta}^2) + \lambda (\Vert \bm{\gamma} \Vert_{2}^{2} + \Vert \bm{\delta} \Vert_{2}^{2}) =
%\sum_{i=1}^{n} \mathscr{L}\left(y_{i}, f(\bm{x}_i|{\bm{\psi},\bm{\gamma}^2 - \bm{\delta}^2})\right)
\mathcal{L}(\bm{\psi},\bm{\gamma}^2 - \bm{\delta}^2)
+\lambda \sum_{j=1}^{d}\big(\gamma_{j}^{2}+\delta_{j}^{2}\big) }. \label{eq:optim_g_diff}
\end{align}

To show equivalence of the smooth surrogate, we first establish that $\K$ and $\Rxi(\bm{\gamma},\bm{\delta})=\Vert \bm{\gamma} \Vert_{2}^{2} + \Vert \bm{\delta} \Vert_{2}^{2}$ together define an SVF for $\Rbeta(\bbeta)=\norm{\bbeta}_1$.
Given the parametrization map $\K(\bm{\gamma},\bm{\delta})=\bm{\gamma}\odot\bm{\gamma}-\bm{\delta}\odot\bm{\delta}$ as defined in Equation (<ref>), the minimum of the surrogate $\ell_2$ regularization $\Rxi(\bm{\gamma},\bm{\delta}))=\norm{\bm{\gamma}}_2^2+\norm{\bm{\delta}}_2^2$ subject to $\bm{\gamma}\odot\bm{\gamma}-\bm{\delta}\odot\bm{\delta}=\bbeta$ constitutes an SVF for $\Rbeta(\bbeta)=\norm{\bbeta}_1$ in (<ref>) and is given by

\begin{equation} \label{eq:S_hdp-def}
\min_{\bm{\gamma}, \bm{\delta}: \bm{\gamma}^2 - \bm{\delta}^2 = \bm{\beta}} \Vert \bm{\gamma} \Vert_{2}^{2} + \Vert \bm{\delta} \Vert_{2}^{2} \; = \Vert \bm{\beta} \Vert_{1} \quad \forall \bbeta \in \Rd\,.
\end{equation}

For each $\beta_j$ in $\bbeta$, either $\gamma_j^2$ or $\delta_j^2$ must equal zero at the minimum, depending on the sign of $\beta_j$, with the square of the second parameter being equal to $|\beta_j|$. The minimizers $(\hat{\gamma}_j,\hat{\delta}_j)$ hence form a continuous set-valued function of $\beta_j$.

Optimization of $\P$ (<ref>) is equivalent to optimization of the smooth surrogate $\Q$ (<ref>), and solutions to the $\P$ can be constructed as $(\hbpsi,\hat{\bm{\beta}})=(\hbpsi,\hat{\bm{\gamma}}^2 -\hat{\bm{\delta}}^2)$.

For the preservation of local minima in general, potentially unregularized objectives $\P(\bpsi,\bbeta)$ under a smooth parametrization using the HDP, Lemma <ref> again requires local openness of the HDP at local minimizers $(\hat{\gamma},\hat{\delta})$ of $\P(\bpsi,\K(\bm{\gamma},\bm{\delta}))$. Recall that rotating a point $(u,v)\in\mathbb{R}^2$ by $45^{\circ}$ clockwise about the origin defines the transformation $(\gamma,\delta)\triangleq(\frac{u+v}{\sqrt{2}},\frac{v-u}{\sqrt{2}})$. Evaluating the HDP at the rotated point yields $\gamma^2-\delta^2=2uv$, showing that the HDP constitutes a rotation of the HPP scaled by a factor of $2$, with both actions preserving the openness. Details on the difference between the HPP and HDP can be found in Appendix <ref>.

§.§ Intuition and Examples

Correspondence to diagonal linear networks

[GHPP (<ref>)]

[Deep Diagonal Linear Network Structures]Diagonal linear networks corresponding to different parametrizations of a linear predictor: a) HPP ($\ell_1$),  b) HDP ($\ell_1$),  c) Network corresponding to a structure-inducing parametrization (GHPP for $\ell_{2,1}$, cf. <ref>) with grouping layer. Left nodes are inputs and right-most node the output.

The HPP $\bm{\beta} = \bm{u} \odot \bm{v}$ and HDP $\bm{\beta} = \bm{\gamma} \odot \bm{\gamma} - \bm{\delta} \odot \bm{\delta}$ parametrizations reveal close connections to diagonal linear networks and linear regression [Woodworth et al., 2020, Tibshirani, 2021]. Assuming a simple linear model $f(\bm{x}_i | \bm{\beta}) = \bm{x}_{i}^{\top}\bm{\beta}$ with no additional parameters $\bpsi$, applying the respective parametrization induces a network architecture with linear activations and no bias terms, which is equivalent to the $\ell_1$ regularized linear regression under smooth $\ell_2$ regularization of the weights. Figure <ref> shows two such linear networks, with the diagonal network corresponding to the HPP on the left, and the diagonal network corresponding to the HDP in the middle. This correspondence, however, is not limited to overparametrized linear models. For example, we can “stretch out" a network architecture by inserting additional diagonal layers at certain locations, promoting localized sparse representations. More generally, we can overparametrize any layer of a DNN by replacing its weights $\bbeta$ by $\K(\bxi)$. Imposing suitable surrogate regularization on the weights $\bxi$ of the parametrized layer then induces sparse regularization of the original layer in the base parametrization.

Geometric intuition
A graphical analysis of our optimization transfer approach for $\ell_1$ regularization using the HPP provides additional insights into the underlying geometry. Figure <ref> illustrates why the minimum of the surrogate $\ell_2$ penalty $\mathcal{R}_{\bm{\xi}}(\bm{u}, \bm{v})=\Vert \bm{u} \Vert_{2}^{2} + \Vert \bm{v} \Vert_{2}^{2}$ over $\{(\bm{u}, \bm{v}):\bm{u} \odot \bm{v} = \bm{\beta}\}$ equals $2\Vert\bm{\beta}\Vert_{1}$.

The setting in Figure <ref> shows the HPP $\mathcal{K}(\bm{u}, \bm{v})=\bm{u}\odot\bm{v}$ (blue/green), the majorizing surrogate $\ell_2$ penalty (orange), as well as the feasible set defined by the fiber $\K^{-1}(\bbeta)$ (black hyperbola). In this example, we set $d=1$ and fix $\beta=10$. Alternatively, we can interpret the plot as an illustration for only a single entry $\beta_j=10$, $j\in [d]$. The shape of $\K(u_j,v_j)=u_jv_j$ is a hyperbolic paraboloid, and the fiber $\K^{-1}(\beta_j)\subset\mathbb{R}\times \mathbb{R}$ for $\beta_j=10$ is obtained by intersecting $\mathcal{K}$ with the horizontal plane $\beta_j=10$. The geometric shape of the resulting set is a rectangular hyperbola defined by $u_j(v_j)=\frac{\beta_j}{v_j}$. This forms an unbounded feasible set
in the constrained minimization problem stated in Lemma <ref>.
Since the surrogate regularizer $\mathcal{R}_{\bm{\xi}}(\bm{u}, \bm{v})$ defines an elliptic paraboloid for each $j\in[d]$, the constrained minimization problem is solved by searching the entry-wise feasible sets with respect to the smallest surrogate penalty, i.e., the smallest distance to the center of the paraboloid at level $\beta_j$,  $(0,0,\beta_j)$.

For a hyperbola defined by $u_j(v_j)=\frac{\beta_j}{v_j}, \beta_j>0$,

this is achieved at the vertices $(\sqrt{\beta_j}, \sqrt{\beta_j})$ and $(-\sqrt{\beta_j}, -\sqrt{\beta_j})$, with a minimal distance of $\sqrt{2\beta_j}$. Similarly, for
$\beta_j<0$, minimal distance of $\sqrt{2|\beta_j|}$ is attained at $(-\sqrt{|\beta_j|}, \sqrt{|\beta_j|})$ and $(\sqrt{|\beta_j|}, -\sqrt{|\beta_j|})$. For $\beta_j=0$, the fiber $\K^{-1}(0)$ contains all points on the coordinate axes, with 0 minimal distance at $(0,0)$.

The majorization property is visualized in Figure <ref>. We further demonstrate how the proposed optimization transfer to an equivalent smooth surrogate transforms the loss landscape using a simple toy objective in Figure <ref> and a more detailed visualization in Figure <ref>.

Moreover, the surrogate $\mathcal{R}_{\bm{\xi}}(\bm{u}, \bm{v})=\Vert \bm{u} \Vert_{2}^{2} + \Vert \bm{v} \Vert_{2}^{2}$ is a majorant of the overparametrized $\ell_1$ regularizer $\mathcal{R}_{\bm{\beta}}(\mathcal{K}(\bm{u},\bm{v}))=2\Vert\bm{u}\odot\bm{v}\Vert_{1}$, with equality of both regularizers achieved at the two vertices of the hyperbolas defined by the fibers $\K^{-1}(\beta_j)$ for all non-zero values of $\beta_j$.

[Optim. Transfer (HPP)]

[Majorization of $\ell_1$ via surrogate $\ell_2$ penalty (HPP)]

a)  Illustration of $\ell_1$ optimization transfer using HPP and surrogate $\ell_2$ regularization on a scalar $\beta_j=10$ (lower plane). The hyperbolic paraboloid (blue/green) shows the parametrization $\K(u_j,v_j)=u_jv_j$ and the elliptic paraboloid (orange) the $\ell_2$ surrogate.
The fiber $\K^{-1}(10)$ defines a hyperbola (black), whose two vertices
achieve minimal a min. $\ell_2$ penalty of $2|10|=20$ (upper plane) over $\K^{-1}(10)$. b)  Majorization of
overparametrized $\ell_1$ term $2|u_jv_j|$ (blue/green) through $\ell_2$ penalty. The $\ell_2$
(orange) is tightly “hugged" by the $\ell_1$ term. The difference of both regularizers attains zero at perpendicular lines intersecting at the origin, illustrating the u.h.c. of the SVF solution map.

§ HADAMARD GROUP LASSO FOR STRUCTURED SPARSITY

In many applications, we have additional a priori structural information on the parameters, e.g., that certain gene pathways can only be jointly relevant or that a set of dummy-coded features representing a categorical variable should either be included in the model or fully selected out. To obtain structured sparsity, we make use of parametrization maps “tying together" groups of parameters through shared factors, with the property that adding smooth $\ell_2$ regularization on the surrogate parameters induces an $\ell_{2,1}$ (group lasso) penalty $2 \sum_{j=1}^{L} \Vert \bm{\beta}_{j} \Vert_{2}$ in the base parametrization $\bbeta$.

Set-up for structured sparsity regularization
Let $[d]%=\{1,\ldots,d\}
$ denote the index set corresponding to the entries of $\bm{\beta}\in\mathbb{R}^{d}$, and define $\mathcal{G}_j = \big\{{j}_{1},\ldots, {j}_{|\mathcal{G}_{j}|}\big\} \subseteq [d]$ to be the subsets of indices corresponding to groups $j=1,\ldots,L$. Let $\mathcal{G} = \{\mathcal{G}_1, \ldots, \mathcal{G}_{L}\}$ form a partition of $[d]$, i.e. $\cup_{j=1}^{L} \mathcal{G}_j= \{1,\ldots,d\}$ and $\mathcal{G}_i \cap \mathcal{G}_j = \emptyset$ for $i \neq j$, so that $|\mathcal{G}_1|+\ldots+|\mathcal{G}_L|=d$. The parameter vector $\bm{\beta}$ contains the group-wise vectors $\bbeta_j$, i.e., $\bm{\beta} = \left(\bm{\beta}_{1},\ldots, \bm{\beta}_{L}\right)^{\top}$, where $\bbeta_j=\big(\beta_{j_1,\ldots,\beta_{j_{|\Gj|}}}\big)^{\top} \in \mathbb{R}^{|\mathcal{G}_j|}$ for $j \in [L]$.

§.§ Group Hadamard Product Parametrization

For the group Hadamard product parametrization (GHPP), we again use the parametrization structure $\bm{\beta} = \bm{u} \odot \bm{v}$, but now with the elements of $\bm{v}$ (and thus also $\bbeta$) constrained to reflect the group membership. Noting that $\Rd = \mathbb{R}^{|\mathcal{G}_1|+\ldots+|\mathcal{G}_L|}$, the Hadamard factors are

\begin{align}\label{eq:hadgroup-reparam-defs}
\bm{u} = \left( \bm{u}_{1},\ldots,\bm{u}_{L} \right)^{\top} \in \mathbb{R}^{d},\,\,\bm{v} = \left( \bm{v}_{1},\ldots,\bm{v}_{L} \right)^{\top} =
\begin{pmatrix}
\nu_1 \mathds{1}_{|\mathcal{G}_1|} \\ \vdots \\ \nu_{L} \mathds{1}_{|\mathcal{G}_L|}
\end{pmatrix}  \in \Rd\,\;. \nonumber
\end{align}

Then we have $\bbeta_j=\bu_j \odot \bv_j = \nu_j \cdot (u_{{j}_{1}},\ldots,u_{{j}_{|\mathcal{G}_j|}})^{\top} \in \mathbb{R}^{|\Gj|}$ for $j \in [L]$.

Note that in this parametrization,
the second Hadamard factor $\bm{v}$ is a $d$-dimensional vector containing values $\nu_{1}, \ldots, \nu_{L}$, where each $\nu_{j}$ is repeated $|\mathcal{G}_j|$ times in $\bv$. Comparing this to the Hadamard factor $\bm{v} = (v_1, \ldots, v_d)^{\top}$ in the HPP, the $d$ distinct entries of $\bm{v}$ are replaced by entries that are constant within groups $\mathcal{G}_{1}, \ldots, \mathcal{G}_L$, thereby “tying” together the parameters in each $\Gj$. The first Hadamard factor $\bu$ remains unconstrained as in the HPP, i.e., $\bm{u}=(u_1,\ldots, u_d)^{\top}\in\Rd$.

Letting $\bnu \in \mathbb{R}^{L}$ denote $(\nu_{1}, \ldots, \nu_{L})^{\top}$, the GHPP map is defined as:

\begin{equation}\label{eq:ghpp-reparam-mapping}
\mathcal{K}: \mathbb{R}^d \times \mathbb{R}^{L} \to \mathbb{R}^{d}, (\bm{u},\bm{\nu}) \mapsto  \begin{pmatrix}
\bm{u}_{1} \\ \vdots \\ \bm{u}_{L}
\end{pmatrix}  \odot \begin{pmatrix}
\nu_1 \mathds{1}_{|\mathcal{G}_1|} \\ \vdots \\ \nu_{L} \mathds{1}_{|\mathcal{G}_L|}
\end{pmatrix}  = \bm{u} \odotg \bm{\nu} = \begin{pmatrix}
\bm{\beta}_{1} \\ \vdots \\ \bm{\beta}_{L}
\end{pmatrix}  = \bm{\beta} \,,
\end{equation}

where we use the notation $\bm{u} \odotg \bm{\nu} \triangleq (\bm{u}_{j} \nu_{j})_{j \in \mathcal{G}}$. Given an objective $\P$ with non-smooth regularization $\Rbeta(\bbeta)=2\norm{\bbeta}_{2,1}$, defining the surrogate regularization as $\Rxi(\bu,\bnu)\triangleq\norm{\bu}_2^2+\norm{\bnu}_2^2$ provides a smooth optimization transfer $(\Rbeta,\K,\Rxi)$, from which we construct the smooth surrogate $\Q$:

\begin{align}
&{\textstyle \mathcal{P}(\bm{\psi}, \bm{\beta}) = \mathcal{L}(\bm{\psi}, \bm{\beta}) + 2 \lambda \Vert \bm{\beta}\Vert_{2,1} =
%\sum_{i=1}^{n} \mathscr{L}\left(y_{i}, f(\bm{x}_i|{\bm{\psi},\bm{\beta}}) \right)
\mathcal{L}(\bm{\psi}, \bm{\beta})
+ 2 \lambda \sum_{j=1}^{L} \Vert \bm{\beta}_{j} \Vert_{2} } \, , \label{eq:optim_q_group} \\
&{\textstyle \mathcal{Q}(\bm{\psi}, \bm{u}, \bm{v}) =  \mathcal{L}(\bm{\psi},\bm{u} \odot \bm{v}) + \lambda (\Vert \bm{u} \Vert_{2}^{2} + \Vert \bm{\nu} \Vert_{2}^{2}) =
%\sum_{i=1}^{n} \mathscr{L}\left(y_{i}, f(\bm{x}_i|{\bm{\psi},\bm{u} \odot \bm{v}})\right)
\mathcal{L}(\bm{\psi},\bm{u} \odot \bm{v})
+\lambda \sum_{j=1}^{L}\big(\Vert \bm{u}_{j} \Vert_{2}^{2} +\nu_{j}^{2}\big) }\,. \label{eq:optim_g_group}
\end{align}

The functions $\K$ and $\Rxi$ are chosen so that we obtain an SVF for $\Rbeta$:

Given the parametrization map $\K(\bu,\bnu)=\bu \odotg \bnu$, the minimum of the surrogate $\ell_2$ regularization $\Rxi(\bu,\bnu)=\norm{\bu}_2^2+\norm{\bnu}_2^2$ subject to $\K(\bu,\bnu)=\bbeta$ constitutes an SVF for $\Rbeta(\bbeta)$ in (<ref>) and is

\begin{equation} \label{eq:S_ghpp-def}
\min_{\bm{u}_{j}, \nu_j: \bm{\beta}_{j} = \nu_j \bm{u}_{j} } {\textstyle  \sum_{j=1}^{L} \Vert \bm{u}_{j} \Vert_{2}^{2} +\nu_{j}^{2}  = 2 \sum_{j=1}^{L} \Vert \bm{\beta}_{j} \Vert_{2} } \quad \forall \bbeta \in \mathbb{R}^{d}\,,
\end{equation}

According to Lemma <ref>, the optimality conditions $\Vert \bm{u}_{j} \Vert_{2}^{2} = \nu_{j}^{2} = \Vert \bm{\beta}_{j} \Vert_{2}$ of the AM-GM inequality in the proof allow us to derive the minimizers $(\hat{\bu}_j,\hat{\nu}_j)$ as an upper hemicontinuous function of $\bbeta_j$ for all $\bbeta_j\in\mathbb{R}^{|\G_j|}$:

\begin{equation}\label{eq:minimizers-ghpp}
%\argmin_{\substack{(\bu_j,\nu_j):\\ \bm{\beta}_{j} = \nu_j \bm{u}_{j}}}
%\min_{\substack{\bm{U},\bm{V}\\ \bm{U}\bm{V}^{\top}=\bm{X}}}
%\underset{(\bu_j,\nu_j): \bm{\beta}_{j} = \nu_j \bm{u}_{j}}{\argmin}
\arg\hspace{-0.05cm}\min_{\hspace{-0.4cm}\substack{(\bu_j,\nu_j):\\ \bm{\beta}_{j} = \nu_j \bm{u}_{j}}}
\Vert \bm{u}_{j} \Vert_{2}^{2} + \nu_{j}^{2} =
\begin{cases}
\pm \left(\bbeta_j/\sqrt{\Vert \bm{\beta}_{j} \Vert_{2}}, \sqrt{\Vert \bm{\beta}_{j} \Vert_{2}}\right) %\land \left(-\bbeta_j/\sqrt{\Vert \bm{\beta}_{j} \Vert_{2}}, -\sqrt{\Vert \bm{\beta}_{j} \Vert_{2}}\right)
, & \hspace{-0.25cm}\text{$\norm{\bbeta_j}_2 > 0$} \\
(\bm{0},0), & \hspace{-0.25cm}\text{$\norm{\bbeta_j}_2=0$} \\
%(0,\sqrt{\Vert \bm{\beta}_{j} \Vert_{2}})\;\text{and}\;(0,-\sqrt{\Vert \bm{\beta}_{j} \Vert_{2}}) & \hspace{-2.45cm}\text{for $\beta_{j_k}=0$ and $\norm{\bbeta_j}_2>0$} \\
%\left(|\beta_{{j}_{k}}|/\sqrt{\Vert \bm{\beta}_{j} \Vert_{2}}, -\sqrt{\Vert \bm{\beta}_{j} \Vert_{2}}\right)\;\text{and}\;\left(-|\beta_{{j}_{k}}|/\sqrt{\Vert \bm{\beta}_{j} \Vert_{2}}, \sqrt{\Vert \bm{\beta}_{j} \Vert_{2}}\right) & \text{for $\beta_j < 0$}
\end{cases}
\end{equation}

The tuple $(\Rbeta,\K,\Rxi)$ is thus a valid optimization transfer for $\ell_{2,1}$ group sparsity:

The optimization of $\P$ in (<ref>) is equivalent to the optimization of the smooth surrogate $\Q$ in (<ref>) by Definition <ref>, and solutions to the base problem can be obtained as $(\hbpsi,\hat{\bbeta})=(\hbpsi,\hat{\bu}\odotg\hat{\bnu})$.

Note that there are only two equivalent minimizers for each $\bbeta_j$ given $\norm{\bbeta_j}_2>0$, as the sign of $\hat{\nu}_j$ uniquely determines the sign of all $\hat{u}_{j_i}$ in $\hat{\bu}_j$ for $i=1,\ldots,|\G_j|$. Thus, for each minimizer $(\hat{\bpsi},\hat{\bbeta})$ of $\P$, there will be $2^{s}$ equivalent corresponding solutions $(\hat{\bpsi},\hat{\bu},\hat{\bnu})$ to $\Q$, where $s$ is the number of groups $\G_j$ with $\Vert\hat{\bbeta}_j\Vert_2>0$.

For linear predictors, structure-inducing overparametrization was also studied in Tibshirani, 2021 and Dai et al., 2021, however, without proving the matching local minima property or going beyond linearity.
Similar to the HPP approach to smooth $\ell_1$ regularization, the GHPP corresponds to a particular network structure with linear activations and a grouping layer when applied to a linear model, as shown in Figure <ref>. The $\ell_2$ regularized network then corresponds to a linear model with an $\ell_{2,1}$ penalty.

Considering the preservation of local minima in a general objective $\P(\bpsi,\bbeta)$ under smooth parametrization of $\bbeta$ using the GHPP, local openness of $\K$ at the local solutions to $\P(\bpsi,\K(\bxi))$ is a crucial requirement for Lemma <ref>. This assumption, however, is not straightforward for the GHPP. While the Banach open mapping theorem states that every continuous linear surjection between Banach spaces is globally open, it is known that this openness principle can not be extended to bilinear continuous surjections [Horowitz, 1975, Balcerzak et al., 2013]. A widely used counterexample of a bilinear continuous surjection that is not open everywhere is given, e.g., in <cit.>, corresponding to the GHPP for $L=1$ and $d=2$. Therefore, as opposed to the HPP, the GHPP is not globally open in general. To establish matching local minima, we thus need to ensure that local solutions $(\hat{\bu},\hat{\bnu})$ to $\P(\bpsi,\K(\bu,\bnu))$ are indeed points of local openness:

The parametrization map defined by $\K:\Rd \times \mathbb{R}^{L},\,(\bu,\bnu)\mapsto \bu \odotg \bnu$ is locally open at $(\bu,\bnu)$, with $\bu=(\bu_1,\ldots,\bu_L)^{\top}$ and $\bnu=(\nu_1,\ldots,\nu_L)^{\top}$,  if the $(\bu_j,\nu_j)$ are such that $\nu_j=0$ implies $\norm{\bu_j}_2=0$ for all $j\in[L]$.

Note that all minimizers of $\Q(\bu,\bnu)$ are of the form stated in (<ref>), i.e., either $(\hat{\bu}_j,\hat{\nu}_j)=(\bm{0},0)$, or the $(\hat{\bu}_j,\hat{\nu}_j)$ are such that $\norm{\hat{\bu}_j}_2>0$ and $|\hat{\nu}_j|>0$ for all $j\in[L]$. Then, Lemma <ref> shows that $\K(\bu,\bnu)$ is locally open at all local solutions to $\Q(\bu,\bnu)$.

§.§ Adjusting the GHPP for Variable Group Sizes

The well-known group lasso, initially proposed by Yuan and Lin, 2006,
does not employ plain $\ell_{2,1}$ regularization, but includes additional weights accounting for the variable group sizes $|\mathcal{G}_j|,j\in [L]$. With this modification, we can define the non-smooth penalty as $\mathcal{R}_{\bm{\beta}}(\bm{\beta})\triangleq\sum_{j=1}^{L} \sqrt{|\mathcal{G}_j|}\norm{\bm{\beta}_j}_2$. Interestingly, this regularizer can be obtained as a simple extension to the previous approach by introducing a scaling factor in the surrogate penalty. The derivation is deferred to Appendix <ref>. This results in the following smooth objective $\Q$ and corresponding equivalent group lasso regularized objective $\P$:

\begin{align}
&{\textstyle \mathcal{P}(\bm{\psi}, \bm{\beta}) = \mathcal{L}(\bm{\psi}, \bm{\beta}) + 2 \lambda  \sum_{j=1}^{L} \sqrt{|\mathcal{G}_j|} \Vert \bm{\beta}_{j} \Vert_{2} }\,, \label{eq:p-adj-ghpp}\\
&{\textstyle \mathcal{Q}(\bm{\psi}, \bm{u}, \bm{\nu}) =  \mathcal{L}(\bm{\psi},\bm{u} \odotg \bm{\nu}) + \lambda \sum_{j=1}^{L}\big(\Vert \bm{u}_{j} \Vert_{2}^{2} + |\mathcal{G}_j| \nu_{j}^{2}\big) }. \label{eq:q-adj-ghpp}
\end{align}

§ GOING DEEPER: NON-CONVEX REGULARIZATION WITH HADAMARD PRODUCT PARAMETRIZATIONS OF DEPTH K

The Hadamard product parametrizations factorizing $\bbeta$ using two factors $\bu,\bv$ can be naturally extended to deeper factorizations of depth $k>2,\,k \in \mathbb{N}$. For a suitable surrogate penalty, these parametrizations induce (a restricted class) of non-convex $\ell_q$  and $\ell_{p,q}$ regularizers for $0<q<1$  and $0< q < p\leq 2$ in the base parametrization $\bbeta$.

§.§ Hadamard Product Parametrization of Depth k

First, consider a multilinear extension of the bilinear HPP termed the $\text{HPP}_k$,

\begin{equation}\label{eq:hppk}
{\textstyle \mathcal{K}:\prod_{l=1}^{k} \mathbb{R}^{d} \to \mathbb{R}^{d}, (\bm{u}_1,\ldots,\bm{u}_{k}) \mapsto \bigodot_{l=1}^{k} \bm{u}_{l} = \bm{\beta} \,,}
\end{equation}

where $\prod_{l=1}^{k} \mathbb{R}^{d}$ denotes the $k$th Cartesian power of $\mathbb{R}^{d}$ and $k>2$. The depth two case recovers the simple HPP (<ref>). Each $\beta_j,\, j\in [d]$, is parametrized as the product $\prod_{l=1}^{k} u_{jl}$, where each factor $u_{jl}$ is taken from a different $\bu_l$. Further, we define $\Rxi(\bu_1,\ldots,\bu_k)\triangleq\sum_{l=1}^{k}\norm{\bu_l}_2^2$. Then, minimizing $\Rxi(\bu_1,\ldots,\bu_k)$ subject to the constraint imposed by the parametrization map $\K$ yields an SVF for non-convex $\ell_{q}$ regularization with $q=2/k$:

Given the parametrization map $\K(\bu_1,\ldots,\bu_k)=\bu_{l}^{\odot k}$, the minimum surrogate $\ell_2$ regularizer $\Rxi(\bu_1,\ldots,\bu_k)=\sum_{l=1}^{k}\norm{\bu_l}_2^2$ subject to $\K(\bu_1,\ldots,\bu_k)=\bbeta$ constitutes an SVF for $\Rbeta(\bbeta)\triangleq k \norm{\bbeta}_{2/k}^{2/k}$ and is given by

$\min_{\bm{u}_{l}: \bbeta=\bm{u}_{l}^{\odot  k}} {\textstyle \sum_{l=1}^{k}} \Vert \bm{u}_l \Vert_{2}^{2} = k \Vert \bm{\beta} \Vert_{2/k}^{2/k} \,\, \forall \bbeta \in \mathbb{R}^{d}$.

A visualization of the $\text{HPP}_k$ for $k=3$ can be found in Appendix <ref>, illustrating the shape of the fibers of $\K$ and the majorization of the non-smooth $\ell_{2/3}$ penalty by the smooth surrogate $\ell_2$ penalty.
Given an objective $\P$ with smooth $\L$ and non-convex $\ell_{2/k}$ regularization $\Rbeta(\bbeta)$, applying the optimization transfer defined by $(\Rbeta,\K,\Rxi)$ yields the corresponding $\Q$:

\begin{align}
&{\textstyle \mathcal{P}(\bm{\psi}, \bm{\beta}) = \mathcal{L}(\bm{\psi}, \bm{\beta}) + \lambda k \|\bm{\beta}\|_{2/k}^{2/k} =  %\sum_{i=1}^{n} \mathscr{L}\left(y_{i}, f(\bm{x}_i|{\bm{\psi},\bm{\beta}}) \right)
\mathcal{L}(\bm{\psi}, \bm{\beta})
+ \lambda k \sum_{j=1}^{d}\left|\beta_{j}\right|^{2/k} }\,, \label{eq:optim_q_HPC} \\
&\hspace{-0.2cm}{\textstyle \mathcal{Q}(\bm{\psi}, \bm{u}_1,\ldots,\bm{u}_{k}) =  \mathcal{L}\big(\bm{\psi}, \bm{u}_{l}^{\odot  k}\big) + \lambda \sum_{l=1}^{k} \Vert \bm{u}_{l} \Vert_{2}^{2} =
%\sum_{i=1}^{n} \mathscr{L}\left(y_{i}, f\left(\bm{x}_i \bigl\vert {\bm{\psi}, \bm{u}_{l}^{\odot  k}}\right)\right)
\mathcal{L}\big(\bm{\psi}, \bm{u}_{l}^{\odot  k}\big)
+ \lambda \sum_{j=1}^{d} \sum_{l=1}^{k} u_{jl}^{2} }\,. \label{eq:optim_g_HPC}
\end{align}

The optimality conditions of the AM-GM inequality ensure upper hemicontinuity of the solution map in Lemma <ref> by Lemma <ref>, implying equivalence of $\P$ and $\Q$ using Thm. <ref>:

The optimization of $\P$ (<ref>) is equivalent to optimization of the smooth surrogate $\Q$ (<ref>) by Def. <ref>, and solutions to $\P$ can be constructed as $(\hbpsi,\hat{\bm{\beta}}) = (\hbpsi,\hat{\bm{u}}_{l}^{\odot  k})$.

Extending the HPP, the $\text{HPP}_k$ also corresponds to a horizontally “stretched" diagonal network structure with increased depth, as shown in Figure <ref>. The relation of parametrization and corresponding network structure for linear models was also studied in simpler settings and without proof of our general result [Tibshirani, 2021, Dai et al., 2021]. Besides these works in explicit regularization, a strand of literature in DL uses diagonal linear networks to study the implicit regularization of GD [Gunasekar et al., 2018, Gissin et al., 2019, Woodworth et al., 2020, Moroshko et al., 2020, Li et al., 2021].

[Deep Diagonal Linear Network Structures]Deep diagonal linear networks corresponding to different parametrizations of a linear predictor set-up. a) HPP (for $\ell_{2/k}$),  b) $\text{GHPP}_k$ (for $\ell_{2,2/k}$),  c) $\text{GHPP}_{k_1,k_1+k_2}$ (for $\ell_{2/k_1,2/(k_1+k_2)})$. The depth up to and including the grouping layer is $k_1$, followed by $k_2=k-k_1$ more diagonal layers. Nodes on the left represent input features and the single node on the right the output.

Regarding applications of the $\text{HPP}_k$ to general objectives $\P(\bpsi,\bbeta)$ without surrogate regularization, we can establish the global openness of the $k$-linear surjection $\K$:

The map $\mathcal{K}:\prod_{l=1}^{k} \mathbb{R}^{d} \to \mathbb{R}^{d}, (\bm{u}_1,\ldots,\bm{u}_{k}) \mapsto \bigodot_{l=1}^{k} \bm{u}_{l}$ is globally open.

Consequently, applying Lemma <ref>, smoothly parametrizing any continuous objective using the $\text{HPP}_k$
preserves the local minima of $\P$.

§.§ Group Hadamard Product Parametrizations of Depth k

The smooth optimization transfer for $\ell_{2,1}$ regularized problems can be naturally extended to structured sparsity with non-convex $\ell_{2,2/k}$ regularization. We start with the same set-up as in Section <ref>, but now consider deeper factorizations of $\bm{\beta}$. Recall that the GHPP is defined as $\K(\bu,\bnu)=\bu \odotg \bnu=\bbeta$.
Further factorizing the grouping parameter $\bnu$ into $k-1$ Hadamard factors, i.e., $\bnu=\bigodot_{r=1}^{k-1}\bnu_{r}$, defines the $\text{GHPP}_k$ map:

\begin{align} \label{eq:ghpp-k}
\hspace{-0.2cm}\mathcal{K}:\,\mathbb{R}^{d} \times \prod_{r=1}^{k-1} \mathbb{R}^{L} \to \mathbb{R}^{d}, (\bm{u}, \bm{\nu}_1,\ldots,\bm{\nu}_{k-1}) \mapsto  \bm{u} \odotg  \bnu_{r}^{\odot(k-1)}=
{\footnotesize \begin{pmatrix}
\bm{u}_{1} \\ \vdots \\ \bm{u}_{L}
\end{pmatrix}  \odot \begin{pmatrix}
\mathds{1}_{|\mathcal{G}_1|} \prod_{r=1}^{k-1} \nu_{1r} \\ \vdots \\ \mathds{1}_{|\mathcal{G}_L|} \prod_{r=1}^{k-1} \nu_{Lr}
\end{pmatrix}}
%= \begin{pmatrix}
%\bm{\beta}_{1} \\ \vdots \\ \bm{\beta}_{L}
%= \bm{\beta} . \nonumber
\end{align}

Equivalently, the parametrization on the group level reads $\bbeta_j=\bu_j \prod_{r=1}^{k-1}\nu_{jr}$, where $\bbeta_j,\bu_j\in\mathbb{R}^{|\G_j|}$ and $\nu_{jr}\in\mathbb{R}$, for $j=1,\ldots,L$ and $r=1,\ldots,k-1$. Applying plain $\ell_2$ regularization under this parametrization, i.e., $\Rxi(\bu, \bnu_1, \ldots, \bnu_{k-1})\triangleq\norm{\bu}_2^2+\sum_{r=1}^{k-1}\norm{\bnu_r}_2^2$, induces the non-smooth and non-convex regularizer $\Rbeta(\bbeta)=k\norm{\bbeta}_{2,2/k}^{2/k}$ for structured sparsity in the base parametrization. To show this, we first prove that the minimum $\ell_2$ penalty under the parametrization map constraint equals $\Rbeta$:
Given the parametrization map $\K(\bu,\bnu_1,\ldots,\bnu_{k-1})=\bu \odotg \bnu_{r}^{\odot (k-1)}$, the minimum of the surrogate $\ell_2$ regularizer $\Rxi(\bu, \bnu_1, \ldots, \bnu_{k-1})\triangleq\norm{\bu}_2^2+\sum_{r=1}^{k-1}\norm{\bnu_r}_2^2$ subject to $\K(\bu,\bnu_1\ldots,\bnu_{k-1})=\bbeta$ constitutes the following SVF for $\Rbeta(\bbeta)\triangleq k \norm{\bbeta}_{2,2/k}^{2/k}$:

\begin{equation} \label{eq:S_ghppk-def}
\min_{\substack{\bm{u}, \bm{\nu}_{1}, \ldots, \bm{\nu}_{k-1}:\\ \bm{\beta} = \bm{u}\odotg \bnu_{r}^{\odot (k-1)}}}
%\min_{\bm{u}, \bm{\nu}_{2}, \ldots, \bm{\nu}_{k}: \bm{\beta} = \bm{u}\odot \bm{v}_{r}^{\odot k}}
\textstyle\sum_{j=1}^{L} \Big( \Vert \bm{u}_{{j}} \Vert_{2}^{2} + \textstyle\sum_{r=1}^{k-1}  \nu_{jr}^{2} \Big)  =  k \Vert \bm{\beta} \Vert_{2, 2/k}^{2/k}\quad\forall\bbeta\in\Rd \,.
\end{equation}

For an objective $\P(\bpsi,\bbeta)$ with non-convex $\ell_{2,2/k}$ regularization,

\begin{equation}
{\textstyle \mathcal{P}(\bm{\psi}, \bm{\beta}) = \mathcal{L}(\bm{\psi}, \bm{\beta}) + \lambda k \|\bm{\beta}\|_{2,2/k}^{2/k} = \L(\bpsi,\bbeta)+\lambda k \sum_{j=1}^{L}\norm{\bbeta_j}_2^{2/k} }\,, \label{eq:optim_q_HGPC}
\end{equation}

the smooth surrogate $\Q$ obtained from the tuple $(\Rbeta,\K,\Rxi)$ is given by

\begin{equation}
{\textstyle \mathcal{Q}(\bm{\psi}, \bm{u}, \bm{\nu}_{1},\ldots,\bm{\nu}_{k-1}) =  \mathcal{L}\big(\bm{\psi}, \bm{u} \odotg \bm{\nu}_{r}^{\odot (k-1)} \big) + \lambda \sum_{j=1}^{L} \Big(\Vert \bm{u}_{{j}} \Vert_{2}^{2} + \sum_{r=1}^{k-1}  \nu_{jr}^{2}\Big) }  \,. \label{eq:optim_g_HGPC}
\end{equation}

By Lemma <ref>, the optimality conditions obtained in the proof of Lemma <ref> imply an upper hemicontinuous solution map as a function of $\bbeta$, so that we can state:

The optimization of $\P$ in (<ref>) is equivalent to the optimization of the smooth surrogate $\Q$ in (<ref>) by Definition <ref>, and solutions to $\P$ can be constructed as $(\hbpsi,\hat{\bm{\beta}}) = (\hbpsi,\hat{\bm{u}} \odotg  \hat{\bnu_{r}}^{\odot (k-1)})$.

We can think of the parametrization $\K$ as a composition involving the GHPP and the $\text{HPP}_{k-1}$ for $\bnu$ to gain insights into the network architecture corresponding to a linear model overparametrized by $\K$. Compared to the depth-two network matching the GHPP in Figure <ref>, the network for the $\text{GHPP}_k$ shown in Figure <ref> adds $k-1$ diagonal layers after the initial layer, corresponding to the additional deeper factorization of $\bnu$ in the $\text{GHPP}_k$. In the previously mentioned less general setting, Tibshirani, 2021 first discovered that optimizing a network as in Figure <ref> with weight decay induces an objective with the same global minimum as an $\ell_{2,2/k}$ regularized linear model.

Regarding the preservation of local minima when applying the $\text{GHPP}_k$ to a general objective $\P(\bpsi,\bbeta)$ without surrogate regularization, we can use the compositional nature of the $\text{GHPP}_k$ to obtain points of local openness, as required by Lemma <ref>:

The parametrization mapping $\K(\bu,\bnu_1,\ldots,\bnu_{k-1}) = \bu \odotg \bnu_r^{\odot (k-1)}$ (<ref>) is locally open at $(\bm{u}, \bm{\nu}_1,\ldots,\bm{\nu}_{k-1})$ whenever the GHPP (<ref>) is locally open at $(\bu,\bnu_r^{\odot (k-1)})$.

Besides the proof in Appendix <ref>, conditions for the local openness of the GHPP are stated in Lemma <ref>.
Note that the optimality conditions in the proof of Lemma <ref> thus also imply the local openness of $\K$ at all local minimizers of $\Q$.

§.§ Generalizing the GHPP to Mixed $\ell_{p,q}$ Quasi-Norms

We can extend the principle behind the construction of the $\text{GHPP}_k$, i.e., starting with the $\text{GHPP}$ and factorizing the $\bnu$ parameter, to deeper parametrizations factorizing both $\bu$ and $\bnu$ simultaneously into $k_1$ and $k_2$ Hadamard factors. In the following, we establish that smooth $\ell_2$ regularization of the resulting surrogate parameters induces non-convex $\ell_{p,q}$ mixed-norm regularization in the base parametrization, with $(p,q)\in\{(2/k_1,2/(k_1+k_2)):k_1,k_2 \in \mathbb{N}\}$. We start with the same structured parameter set-up as in Section <ref>, partitioning the components of $\bbeta$ into $L$ groups. Consider the GHPP map given by $\bm{\beta} = \bm{u} \odotg \bnu$, with $\bm{u}=\left( \bm{u}_{1},\ldots,\bm{u}_{L} \right)^{\top}$ and $\bnu=\left( \nu_{1},\ldots,\nu_{L} \right)^{\top}$, together comprising $L$ pairs of group-wise parameters $(\bm{u}_{{j}},\nu_{{j}})$. Factorizing each $\bm{u}_{{j}}$ into a product of $k_1$ Hadamard factors $\bm{\mu}_{jt}$, $t=1,\ldots,k_1$, and each $\nu_j$ into a product of $k_2$ scalar factors $\nu_{jr}$, $r=1,\ldots,k_2$, we can define the following surjective parametrization mapping $\mathcal{K}$ termed the $\text{GHPP}_{k_1,k_1+k_2}$:

\begin{align}\label{eq:ghppk1k-def}
\mathcal{K}\,:\, \textstyle\prod_{t=1}^{k_1} \mathbb{R}^{d} \times \textstyle\prod_{r=1}^{k_2} \mathbb{R}^{L} \to &\mathbb{R}^{d},\; (\bm{\mu}_{1}, \ldots, \bm{\mu}_{k_1}, \bm{\nu}_1,\ldots,\bm{\nu}_{k_2}) \mapsto  \bm{\mu}_{t}^{\odot  k_1} \odotg \bnu_{r}^{\odot  k_2}  \\
\bm{\mu}_{1t}^{\odot  k_1} \\ \vdots \\ \bm{\mu}_{Lt}^{\odot  k_1}
\end{pmatrix}  \odot \begin{pmatrix}
\mathds{1}_{|\mathcal{G}_1|} \prod_{r=1}^{k_2} \nu_{1r} \\ \vdots \\ \mathds{1}_{|\mathcal{G}_L|} \prod_{r=1}^{k_2} \nu_{Lr}
\end{pmatrix} = \begin{pmatrix}
\bm{\beta}_{1} \\ \vdots \\ \bm{\beta}_{L}
\end{pmatrix} = \bm{\beta} \,, \nonumber
\end{align}

where $\bm{\mu}_{t} \triangleq (\bm{\mu}_{1t}, \ldots, \bm{\mu}_{Lt})^{\top} \in \mathbb{R}^{d}$ and $\bm{\nu}_{r} \triangleq (\nu_{1r},\ldots, \nu_{Lr})^{\top} \in \mathbb{R}^{L}$. Note that each $\bm{\mu}_{jt}$ is the $t$th factor of the $j$th parameter group with entries $(\mu_{{j}_{1}t}, \ldots, \mu_{{j}_{|\mathcal{G}_j|}t})^{\top}\in\mathbb{R}^{|\G_j|}$. On the group level, the parametrization reads $\bbeta_j=\bu_j \nu_j = (\bigodot_{t=1}^{k_1} \bm{\mu}_{jt}) \prod_{r=1}^{k_2}\nu_{jr}=\bm{\mu}_{jt}^{\odot k_1}\prod_{r=1}^{k_2}\nu_{jr}$, for $j\in[L]$. Further, let $k \triangleq k_1+k_2$ denote the total factorization depth. To derive the non-convex group-sparse regularizer for $\bbeta$ induced through $\ell_2$ regularization of $\bm{\mu}_{jt},\nu_{jr}$ for  $j\in[L],t\in[k_1],r\in[k_2]$, a simple generalization of the AM-GM inequality is required.

Defining the surrogate penalty $\Rxi$ as plain $\ell_2$ regularization, we can show that $\Rxi$ and $\K$ induce an SVF for mixed-norm $\ell_{p,q}$ regularization.

Given a parametrization $\K(\bm{\mu}_{1},\ldots,\bm{\mu}_{k_1},\bnu_1,\ldots,\bnu_{k_2})=\bm{\mu}_{t}^{\odot  k_1} \odotg \bnu_{r}^{\odot  k_2}$, the minimum surrogate $\ell_2$ regularization $\Rxi(\bm{\mu}_{1}, \ldots, \bm{\mu}_{k_1} \bnu_1, \ldots, \bnu_{k_2} ) \triangleq \sum_{t=1}^{k_1}\norm{\bm{\mu}_{t}}_2^2+\sum_{r=1}^{k_2}\norm{\bnu_r}_2^2$ subject to $\K(\bm{\mu}_{1},\ldots,\bm{\mu}_{k_1},\bnu_1,\ldots,\bnu_{k_2})=\bbeta$ constitutes an SVF for $\Rbeta(\bbeta)\triangleq k \norm{\bbeta}_{2/k_1,2/k}^{2/k}$ and is given by

\begin{equation} \label{eq:S_ghppk1k-def}
\min_{\substack{\bm{\mu}_{1}, \ldots, \bm{\mu}_{k_1}, \bnu_1, \ldots, \bnu_{k_2}:\\
\bbeta = \bm{\mu}_{t}^{\odot  k_1} \odotg  \bnu_{r}^{\odot  k_2}}} \,\, {\textstyle \sum_{j=1}^{L} \Big(\sum_{t=1}^{k_1} \Vert \bm{\mu}_{jt} \Vert_{2}^{2} + \sum_{r=1}^{k_2}  \nu_{jr}^{2} \Big)}  =  k \Vert \bm{\beta} \Vert_{2/k_1, 2/k}^{2/k} \quad\forall\bbeta\in\Rd \,.
\vspace{-0.15cm}
\end{equation}

Note that by Lemma <ref>, the optimality conditions in the proof above ensure upper hemicontinuity of the solution map to the SVF. Assuming an objective $\P(\bpsi,\bbeta)$ with non-convex $\ell_{2/{k_1},2/k}$ regularizer $\Rbeta(\bbeta)$, the optimization transfer $(\Rbeta,\K,\Rxi)$ defines the following equivalent smooth surrogate $\Q$:

\begin{align}
%\min_{\bm{\psi}, \bm{\beta}}\,
&{\small \mathcal{P}(\bm{\psi}, \bm{\beta}) = \mathcal{L}(\bm{\psi}, \bm{\beta}) + \lambda k \|\bm{\beta}\|_{2/k_1,2/k}^{2/k} = \L(\bpsi,\bbeta) + \lambda k \sum_{j=1}^{L}\norm{\bbeta_j}_{2/k_1}^{2/k} } \,, \label{eq:optim_q_GHGPC}\\
%\min_{\bm{\psi}, \bm{\mu}_{ k_1}, \bm{\nu}_{ k_2}}
&{\small \mathcal{Q}(\bm{\psi}, \bm{\mu}_{1},\ldots,\bm{\mu}_{k_1},\bnu_1,\ldots,\bnu_{k_2}) =  \mathcal{L}\big(\bm{\psi}, \bm{\mu}_{t}^{\odot  k_1} \odotg \bnu_{r}^{\odot  k_2} \big) + \lambda {\footnotesize \sum_{j=1}^{L} \Big( \sum_{t=1}^{k_1} \Vert \bm{\mu}_{jt} \Vert_{2}^{2} + \sum_{r=1}^{k_2}  \nu_{jr}^{2} \Big)}  \,.}\label{eq:optim_g_GHGPC}
\end{align}

The objective $\P$ in (<ref>) is equivalent to the smooth surrogate $\Q$ in (<ref>) by Definition <ref>, and solutions to $\mathcal{P}$ can be constructed as $(\hbpsi,\hat{\bm{\beta}}) = (\hbpsi,\hat{\bm{\mu}}_{t}^{\odot  k_1} \odotg  \hat{\bnu}_{r}^{\odot  k_2}) = \big(\hbpsi,\big( \bigodot_{t=1}^{k_1} \hat{\bm{\mu}}_{t} \big) \odotg \big(\bigodot_{r=1}^{k_2} \hat{\bnu}_{r}\big)\big)$, with $\bnu_{r}$ and $\bm{\mu}_{t}$ defined as in (<ref>) ff.

Figure <ref> shows an exemplary network architecture corresponding to the $\text{GHPP}_{k_1,k_1+k_2}$ applied to an LM [Dai et al., 2021]. The architecture also provides an intuitive visualization of mixed-norm regularization for structured sparsity as a whole. While the depth of the first block of diagonal layers, factorizing $\bu$ into $k_1$ Hadamard factors $\bm{\mu}_t$, determines the induced within-group norm, the depth of the group-wise constant parameters in $\bnu$ into $k_2$ Hadamard factors determines the induced between-group norm.

§.§ Parametrizations with Parameter Sharing

Parameter or weight sharing enables interesting modifications of the previously presented parametrizations, as the parameter redundancy caused by overparametrization
can be greatly reduced by allowing for shared parameters between the Hadamard factors. Parameter sharing can be defined as identifying two or more parameters of an objective function as a single parameter, i.e., interpreting them as identical. For example, the group structure-inducing GHPP, $\K(\bu,\bnu) = \bu \odotg \bnu$, is essentially the HPP $\K(\bu,\bv)=\bu \odot \bv$, but with shared parameters $\bv_j = \nu_j \mathds{1}_{|\G_j|}$ within groups $j \in [L]$, collapsed into the scalar $\nu_j$.
Despite requiring many fewer additional parameters, these parametrizations still define a valid SVF $\Rbeta$ like their fully overparametrized counterparts.

Deep HPP with shared parameters
Consider the parametrization map for the $\text{HPP}_k$, defined as $\K(\bu_1,\ldots,\bu_k)=\bigodot_{l=1}^{k}\bu_l$. By introducing parameter sharing between $(k-1)$ Hadamard factors, i.e., replacing the Hadamard product of $k-1$ separate factors with a self-Hadamard product, we retain enough freedom to ensure surjectivity of the parametrization.
We use $\bu\in\Rd$ to denote the first Hadamard factor, and $\bv^{k-1}\in\Rd$ for the other factors that are collapsed into a single shared vector $\bv \in \Rd$. The following defines the $\text{HPP}_{k}^{shared}$

\begin{equation}\label{eq:hppk-shared}
\hspace{-0.1cm}\mathcal{K}:\mathbb{R}^{d} \times \mathbb{R}^{d} \to \mathbb{R}^{d}, (\bm{u}, \bm{v}) \mapsto \bm{u} \odot \left( \bm{v} \odot \cdots \odot \bm{v} \right) = \bm{u} \odot {\textstyle (\bigodot_{l=1}^{k-1}} \bm{v})  = \bm{u} \odot \bm{v}^{k-1} = \bm{\beta} \,.
\end{equation}

The suitable surrogate penalty $\Rxi$ to obtain an SVF is a re-weighted $\ell_2$ penalty accounting for the increased contribution of the shared parameter to the parametrization.
More precisely, the shared parameter $\bv$ is counted $(k-1)$ times, providing the appropriate re-weighting for $\Rxi$ to define an SVF for non-convex $\ell_{2/k}$ regularization:

Given the parametrization $\K(\bu,\bv)=\bm{u} \odot \bm{v}^{k-1}$, the minimum surrogate $\ell_2$ regularization $\Rxi(\bu,\bv) \triangleq \norm{\bu}_2^2+(k-1)\norm{\bv}_2^2$ subject to $\K(\bu,\bv)=\bbeta$ constitutes an SVF for $\Rbeta(\bbeta)\triangleq k \norm{\bbeta}_{2/k}^{2/k}$, i.e.,

$\min_{\bm{u}, \bm{v}: \bm{u} \odot \bm{v}^{k-1} = \bm{\beta}}  \Vert \bm{u} \Vert_{2}^{2} + (k-1) \Vert \bm{v}  \Vert_{2}^{2} = k \Vert \bm{\beta} \Vert_{2/k}^{2/k}  \,\,\forall\bbeta\in\Rd\,$.

However, despite constituting a valid SVF with less overparametrization, parameter sharing breaks the balance and symmetry in the parametrization, with unclear consequences for the optimization.
Yet, we can relate the GD optimization dynamics for the $\text{HPP}_{k}^{shared}$ to its fully overparametrized counterpart $\text{HPP}_k$ under identical initialization of the to-be-shared parameters. Using a rescaled learning rate for the shared factors, we derive identical updates for both variants, as detailed in Appendix <ref>.

Moreover, initializing all $k$ Hadamard factors of the $\text{HPP}_k$ identically prohibits them from changing their sign over the iterations for sufficiently small step sizes, since the gradient updates vanish as the reconstructed coefficients $\beta_j$ approach zero. This can be exploited to solve non-negative least squares using [Gissin et al., 2019, Chou et al., 2022].

HDP of depth k without and with shared weights
Similar to how the HPP can be generalized to the deeper parametrization $\text{HPP}_k$, the HDP from <ref> can be generalized to deeper variants inducing  $\ell_{2/k}$ regularization in the base parametrization under $\ell_2$ regularization of the surrogate parameters. Chou et al., 2023 mention this fully-overparametrized generalization of the HDP, here named $\text{HDP}_k$:

$\mathcal{K}:\prod_{l=1}^{2k}\mathbb{R}^{d} \to \mathbb{R}^{d}, (\bm{u}_1, \ldots, \bm{u}_{k}, \bm{v}_1, \ldots,\bm{v}_{k}) \mapsto   %\bigodot_{l=1}^{k} \bu_l - \bigodot_{l=1}^{k} \bv_l =
\bm{u}_{l}^{\odot k} - \bm{v}_{l}^{\odot k}
= \bm{\beta} $.

In their analysis of gradient dynamics they restrict themselves to the case of identical initialization, effectively giving rise to the following parametrization termed the $\text{HDP}_{k}^{shared}$, incorporating parameter sharing between the $\bm{u}_l$ for $l\in [k]$ and the $\bm{v}_l$ for $l \in [k]$:

$\mathcal{K}: \mathbb{R}^{d} \times \mathbb{R}^{d} \to \mathbb{R}^{d}, (\bm{u},\bm{v}) \mapsto %\bigodot_{l=1}^{k} \bm{u} - \bigodot_{l=1}^{k} \bm{v} =
\bm{u}^{k} - \bm{v}^{k} = \bm{\beta}$.

In DL, these parametrizations are widely applied in the DL implicit regularization literature to obtain simple-to-analyze depth-$k$ networks that exhibit rich optimization and implicit regularization dynamics <cit.>.

§ HADAMARD POWERS:  NON-INTEGER FACTORIZATION DEPTHS FOR UNRESTRICTED $\ELL_Q$ AND $\ELL_{P,Q}$ REGULARIZATION

The parametrizations based on (group) Hadamard products can induce $\ell_q$ and $\ell_{p,q}$ regularization under surrogate $\ell_2$ regularization for the restricted class $q\in\{2/k|k\in\mathbb{N}\}$ and $(p,q)\in\{(2/k_1,2/(k_1+k_2)|k_1,k_2\in\mathbb{N}\}$. Extending Hadamard product-based parametrizations to Hadamard powers
permits a more flexible choice of the induced regularizer, allowing selection of the previously restricted $p$ and $q$ arbitrarily from $q \in (0,1]$ and $0<q < p \leq 2$. Thus, smooth optimization for non-convex sparse regularization can be achieved using our framework for any feasible real-valued choices of $q$ and $p$, extending previous results to non-integer factorization depths.

§.§ Hadamard Power Parametrization

To construct a parametrization that induces $\ell_{q}$ regularization of $\bm{\beta}$ under (slightly modified) $\ell_2$ regularization of the surrogate parameters for any $q\in (0,1]$, we extend the notion of self-Hadamard products to Hadamard powers. For powers $v_j^k$ with positive, real-valued exponents $k$ to be well-defined, we require positivity of the base $v_j$, e.g., by designing parametrizations of the form $\beta_j = u_j |v_j|^{k-1}$.

The resulting $\text{HPowP}_k$ map is

\begin{equation} \label{eq:hpowp}
\mathcal{K}: \mathbb{R}^{d} \times \mathbb{R}^{d} \to \mathbb{R}^{d}, (\bm{u}, \bm{v}) \mapsto  \bm{u} \odot |\bm{v}|^{\circ (k-1)} = \bm{\beta} \,,
\end{equation}

where $|\bm{v}|^{\circ(k-1)}$ denotes element-wise raising the $|v_j|$ to the $(k-1)$-th power, with $k>1$. This generalizes the self-Hadamard product $\bigodot_{l=1}^{k-1} \bm{v} = \bm{v}^{k-1}$, defined for $k\in\mathbb{N}$, to real-valued positive exponents, with $\circ(k-1)$ denoting non-integer exponents.

Given the parametrization $\K(\bu,\bv)=\bm{u} \odot |\bm{v}|^{\circ(k-1)}$, the minimum surrogate $\ell_2$ regularization $\Rxi(\bu,\bv) \triangleq \norm{\bu}_2^2+(k-1)\norm{\bv}_2^2$ subject to $\K(\bu,\bv)=\bbeta$ constitutes an SVF for $\Rbeta(\bbeta)\triangleq k \norm{\bbeta}_{2/k}^{2/k}$, i.e.,

$\min_{\bm{u}, \bm{v}: \bm{u} \odot |\bm{v}|^{\circ(k-1)} = \bm{\beta}} \Vert \bm{u} \Vert_{2}^{2} + (k-1) \Vert \bm{v}  \Vert_{2}^{2} = k \Vert \bm{\beta} \Vert_{2/k}^{2/k}  \,\forall\bbeta\in\Rd$.

Note that the sign of the constrained minimizer $\hat{u}_j$ is uniquely determined by the sign of $\beta_j$ due to the positivity of $|\hat{v}_j|^{k-1}$. By the optimality conditions, the squared coefficients $u_j^2$ and $|v_j|^2$ must equal $|\beta_j|^{2/k}$ at the minimum, so that by Lemma <ref>, the set-valued solution map is upper hemicontinuous and Assumption <ref> is satisfied. Thus, for any $(k-1) \in \mathbb{R}^{+}$, given an $\ell_{2/k}$ regularized base objective $\P(\bpsi,\bbeta)$,

\begin{equation}
%\min_{\bm{\psi}, \bm{\beta}}
\mathcal{P}(\bm{\psi}, \bm{\beta}) = \mathcal{L}(\bm{\psi}, \bm{\beta}) + \lambda k \|\bm{\beta}\|_{2/k}^{2/k} %=  \sum_{i=1}^{n} \mathscr{L}\left(y_{i}, f(\bm{x}_i|{\bm{\psi},\bm{\beta}}) \right) + \lambda k \sum_{j=1}^{d}\left|\beta_{j}\right|^{2/k}
\label{eq:optim_q_WAMGM} \,,
\end{equation}

we can construct an equivalent differentiable $\Q(\bpsi,\bu,\bv)$ from the tuple $(\Rbeta,\K,\Rxi)$:

\begin{align}\label{eq:optim_g_WAMGM}
\mathcal{Q}(\bm{\psi}, \bm{u},\bm{v}) &=  \mathcal{L}\big(\bm{\psi}, \bm{u} \odot |\bm{v}|^{\circ(k-1)}\big) + \lambda \left( \Vert \bm{u} \Vert_{2}^{2} + (k-1) \Vert \bm{v} \Vert_{2}^{2} \right)\,. %\\
%&=  \sum_{i=1}^{n} \mathscr{L}\left(y_{i}, f(\bm{x}_i|{\bm{\psi}, \bm{u}\odot|\bm{v}|^{\circ(k-1)}})\right) + \lambda \sum_{j=1}^{d} u_j^2 + (k-1) |v_j|^2\
\end{align}

The optimization of $\P$ in (<ref>) is equivalent to the optimization of the smooth surrogate $\Q$ in (<ref>) by Definition <ref>, and solutions to $\mathcal{P}$ can be constructed as $(\hbpsi,\hat{\bm{\beta}}) = (\hbpsi,\hbu \odot |\hbv|^{\circ(k-1)})$.

Note that similar to (<ref>), we modify the usual $\ell_2$ regularization by multiplying each of the $|v_j|^2$ by $(k-1)$ to reflect the imbalance of $\bm{u}$ and $\bm{v}$ in the parametrization $\bm{\beta} = \bm{u} \odot |\bm{v}|^{\circ(k-1)}$.

§.§ Invertible Reparametrization with Hadamard Powers

In Schwarz et al., 2021, a differentiable sparsity-promoting parametrization termed Powerpropagation was introduced, aligning with discussions of related approaches in mathematical optimization [Ramlau and Zarzer, 2012]. The underlying motivation is to artificially increase the curvature of the loss landscape, which induces optimization- and initialization-dependent “rich get richer" dynamics for sparse training of DNNs: the key idea is that applying a power parametrization makes the gradient with respect to the surrogate parameters critically depend on their current values
(cf. Figure <ref>).

Intuitively, this promotes the accumulation of weights either close to or far away from zero, however, Schwarz et al., 2021 did not realize the induced sparse regularization in the base parametrization under explicit $\ell_2$ regularization. Being bijective, Powerpropagation is not an over- but rather a reparametrization given by

\begin{equation} \label{eq:powerprop-param}
\mathcal{K}: \mathbb{R}^{d} \to \mathbb{R}^{d}, \bm{v} \mapsto  \bm{v} \odot |\bm{v}|^{\circ (k-1)} = \bm{\beta} \,.
\end{equation}

For this parametrization, the feasible set of the problem $\min_{\bm{v}: \bm{v} \odot |\bm{v}|^{\circ(k-1)} = \bm{\beta}}\Vert \bm{v} \Vert_{2}^{2}$ is a singleton containing $\hat{\bm{v}}$ such that $\hat{v}_j = \sqrt[k]{|\beta_j|}$ for $\beta_j \geq 0$ and $\hat{v}_j = -\sqrt[k]{|\beta_j|}$ for $\beta_j<0$, $j=1,\ldots,d$. Hence, $\Vert \hbv \Vert_{2}^{2}$ contains $d$ summands $\hat{v}_j^2 = |\beta_j|^{2/k}$, and we conclude $\min_{\bm{v}: \bm{v} \odot |\bm{v}|^{\circ(k-1)} = \bm{\beta}}\Vert \bm{v} \Vert_{2}^{2} = \Vert \bm{\beta} \Vert_{2/k}^{2/k}$.

Since the solution map is continuous in $\bbeta$, Assumption <ref> holds. Thus, for an $\ell_{2/k}$ regularized objective $\P(\bpsi,\bbeta)$ with real-valued $k>1$, we can construct an equivalent smooth $\Q(\bpsi,\bv)$ as follows:

\begin{align}
%\min_{\bm{\psi}, \bm{\beta}}
\mathcal{P}(\bm{\psi}, \bm{\beta}) &= \mathcal{L}(\bm{\psi}, \bm{\beta}) + \lambda  \|\bm{\beta}\|_{2/k}^{2/k} %=  \sum_{i=1}^{n} \mathscr{L}\left(y_{i}, f(\bm{x}_i|{\bm{\psi},\bm{\beta}}) \right) + \lambda  \sum_{j=1}^{d}\left|\beta_{j}\right|^{2/k}\,
, \label{eq:optim_q_bijective} \\
%\min_{\bm{\psi}, \bm{v}}
\mathcal{Q}(\bm{\psi},\bm{v}) &=  \mathcal{L}\big(\bm{\psi}, \bm{v} \odot |\bm{v}|^{\circ(k-1)}\big) + \lambda \Vert \bm{v} \Vert_{2}^{2}% =  \sum_{i=1}^{n} \mathscr{L}\left(y_{i}, f\left(\bm{x}_i \Big| {\bm{\psi}, \bm{v}\odot|\bm{v}|^{\circ(k-1)}}\right)\right) + \lambda \sum_{j=1}^{d} v_j^2
\,.  \label{eq:optim_g_bijective}
\end{align}

The optimization of $\P$ in (<ref>) is equivalent to the optimization of the smooth surrogate $\Q$ in (<ref>) by Definition <ref>, and solutions to $\mathcal{P}$ can be constructed as $(\hbpsi,\hat{\bm{\beta}}) = (\hbpsi,\hbv \odot |\hbv|^{\circ(k-1)})$.

This result shows that it is the functional shape of the parametrization and its warping effect on the loss surface that induces sparsity, not overparametrization per se.

§.§ Hadamard Group Powers (GHPowP)

We can naturally extend the Hadamard power parametrization presented in <ref> to structured sparsity, thereby obtaining a more flexible choice of the hyperparameters $p$ and $q$ in $\ell_{p,q}$ regularization. The following two subsections are structured analogously to their Hadamard product-based counterparts discussed in Section <ref>. As before, we consider the parameter vector with group structure $\bm{\beta} = \left(\bm{\beta}_{1},\ldots,\bm{\beta}_{L}\right)^{\top}$. Consider the following parametrization mapping, named the $\text{GHPowP}_k$,

\begin{equation} \label{eq:reparam-had-group-powers}
\mathcal{K}: \mathbb{R}^{d} \times \mathbb{R}^{L} \to \mathbb{R}^{d}, (\bm{u}, \bm{\nu}) \mapsto  \bm{u} \odotg |\bnu|^{\circ (k-1)} = \begin{pmatrix}
\bm{u}_{1} \\ \vdots \\ \bm{u}_{L}
\end{pmatrix}  \odot \begin{pmatrix}
|\nu_1|^{k-1} \mathds{1}_{|\mathcal{G}_1|} \\ \vdots \\ |\nu_{L}|^{k-1} \mathds{1}_{|\mathcal{G}_L|}
\end{pmatrix}  = \bm{\beta} \,.}
\end{equation}

On the group level, we have $\bm{\beta}_{{j}} = |\nu_{j}|^{k-1} (u_{j_1},\ldots,u_{j_{|\G_j|}})^{\top}\, \forall j\in [L]$, where $\bm{u} = \left(\bm{u}_{{1}}, \ldots, \bm{u}_{{L}} \right)^{\top}$ and $\bm{\nu} = (\nu_{1},\ldots, \nu_{L})^{\top}$. Now, define $\mathcal{R}_{\bm{\beta}}(\bm{\beta}) \triangleq k \Vert \bm{\beta} \Vert_{2,2/k}^{2/k}$ and $\mathcal{R}_{\bm{\xi}}(\bu,\bnu) \triangleq \Vert \bm{u} \Vert_{2}^{2} + (k-1) \Vert \bm{\nu} \Vert_{2}^{2}$.

Given the parametrization map $\K(\bu,\bnu)=\bm{u} \odotg |\bnu|^{\circ(k-1)}$, the minimum of the surrogate $\ell_2$ regularizer $\Rxi(\bu,\bnu) \triangleq \norm{\bu}_2^2+(k-1)\norm{\bnu}_2^2$ subject to $\K(\bu,\bnu)=\bbeta$ constitutes an SVF for $\Rbeta(\bbeta)\triangleq k \norm{\bbeta}_{2,2/k}^{2/k}$ and is given by

\begin{equation} \label{eq:S_ghpowp}
\min_{\bm{u}, \bm{\nu}: \bm{u} \odotg |\bnu|^{\circ(k-1)} = \bm{\beta}} \Vert \bm{u} \Vert_{2}^{2} + (k-1) \Vert \bm{\nu} \Vert_{2}^{2} = k \Vert \bm{\beta} \Vert_{2,2/k}^{2/k} \quad\forall\bbeta\in\Rd \,.
\end{equation}

Using  Lemma <ref>, the optimality conditions provided in the proof ensure upper hemicontinuity of the solution map. Therefore, Assumption <ref> holds and we can construct an equivalent smooth surrogate $\Q$ to an $\ell_{2,2/k}$ regularized base objective $\P(\bpsi,\bbeta)$ for any $k>1$:

\begin{align}
%\min_{\bm{\psi}, \bm{\beta}}
&\mathcal{P}(\bm{\psi}, \bm{\beta}) = \mathcal{L}(\bm{\psi}, \bm{\beta}) + \lambda k \|\bm{\beta}\|_{2,2/k}^{2/k} %= \sum_{i=1}^{n} \mathscr{L}\left(y_{i}, f(\bm{x}_i|{\bm{\psi},\bm{\beta}}) \right) + \lambda k \sum_{j=1}^{L}\Vert \bm{\beta}_{{j}}\Vert_{2}^{2/k}
, \label{eq:optim_q_had-group-power} \\
%\min_{\bm{\psi}, \bm{u}, \bm{\nu}}
&\mathcal{Q}(\bm{\psi}, \bm{u},\bm{\nu}) =  \mathcal{L}\big(\bm{\psi}, \bm{u} \odotg |\bnu|^{\circ(k-1)}\big) + \lambda \big( \Vert \bm{u} \Vert_{2}^{2} + (k-1) \Vert \bm{\nu} \Vert_{2}^{2} \big). \label{eq:optim_g_had-group-power}  %\\
%&\hspace{1.6cm}=\sum_{i=1}^{n} \mathscr{L}\left(y_{i}, f\left(\bm{x}_i \Bigl\vert {\bm{\psi}, \bm{u}\odotg |\bnu|^{\circ(k-1)}}\right)\right) + \lambda \sum_{j=1}^{L} \Vert \bm{u}_{{j}} \Vert_{2}^{2} + (k-1) |\nu_j|^2 \,,  \nonumber
\end{align}

The optimization of $\P$ in  (<ref>) is equivalent to the optimization of $\Q$ in (<ref>) by Def. <ref>, and solutions to $\mathcal{P}$ can be constructed as $(\hbpsi,\hat{\bm{\beta}}) = (\hbpsi,\hbu \odotg |\hbnu|^{\circ(k-1)})$.

§.§ Mixed Norm Regularization with Hadamard Group Powers

Analogous to the previous subsection, we can further apply Hadamard powers to induce $\ell_{p,q}$ mixed-norm regularization for arbitrary feasible values $0<q < p \leq 2$. As a starting point, we again revisit the structured group set-up $\bm{\beta}=\left(\bm{\beta}_{1},\ldots, \bm{\beta}_{L}\right)^{\top}$. However, to allow for non-integer factorization depths, a more complex nested power parametrization
is required and constructed in the following.
Consider the parametrization $\bm{\beta} = \bm{u} \odotg |\bnu|^{\circ k_2}$, $k_2>0$, with $\bm{u} = \left( \bm{u}_{1},\ldots,\bm{u}_{L} \right)^{\top} \in \Rd$ and $\bm{\nu}=(\nu_{1},\ldots,\nu_{L})^{\top} \in \mathbb{R}^{L}$, corresponding to parametrization (<ref>).
Additionally, the auxiliary parameter $\bu$ is parametrized using an invertible pre-composition, i.e., $\bu=\bm{\mu} \odot |\bm{\mu}|^{\circ(k_1-1)}$ with $k_1>0$ and surrogate parameters $\bm{\mu} = (\bm{\mu}_{1}, \ldots, \bm{\mu}_{L})^{\top} \in \mathbb{R}^{|\mathcal{G}_1|+\ldots+|\mathcal{G}_L|} = \mathbb{R}^{d}$. We can then define the $\text{GHPowP}_{k_1,k_1+k_2}$ as

\begin{align} \label{eq:reparam-had-lpq-powers}
\mathcal{K}: \mathbb{R}^{d} \times \mathbb{R}^{L} \to \mathbb{R}^{d},\,&(\bm{\mu}, \bm{\nu}) \mapsto \bm{\mu} \odot |\bm{\mu}|^{\circ(k_1-1)} \odotg |\bnu|^{\circ k_2}
%    \bm{u}_{1} \\ \vdots \\ \bm{u}_{L}
%  \end{pmatrix}  \odot \begin{pmatrix}
%    |\bm{v}_{1}|^{\circ k_2} \\ \vdots \\ |\bm{v}_{L}|^{\circ k_2}
%  \end{pmatrix}
= {\footnotesize \begin{pmatrix}
\bm{\mu}_{1} \odot |\bm{\mu}_{1}|^{\circ (k_1-1)} \\ \vdots \\ \bm{\mu}_{L} \odot |\bm{\mu}_{L}|^{\circ (k_1-1)}
\end{pmatrix}  \odot \begin{pmatrix}
|\nu_1|^{k_2}\mathds{1}_{|\mathcal{G}_1|} \\ \vdots \\ |\nu_{L}|^{k_2}\mathds{1}_{|\mathcal{G}_L|} \\
\end{pmatrix}}, \nonumber
%= \begin{pmatrix}(
%\bm{\beta}_{1} \\ \vdots \\ \bm{\beta}_{L}
%\end{pmatrix} \\
%= \bm{\beta} \,,
\end{align}

or equivalently on the group level, $\bm{\beta}_{{j}} = \bu_j |\nu_j|^{k_2} = \bm{\mu}_{j} \odot |\bm{\mu}_{j}|^{\circ (k_1-1)} \cdot |\nu_{j}|^{k_2}$ for groups $j \in [L]$. The parametrization of $\bm{u}_{{j}}$ via $\bm{\mu}_{j}$ is bijective, so that for each $u_{j_i}, i=1,\ldots,|\mathcal{G}_{j}|$ in $\bm{u}_{{j}}$, it holds $\mu_{j_i} = \text{sign}(u_{j_i})\cdot |u_{j_i}|^{1/k_1}$. Thus, we can express the squared Euclidean norm of $\bm{\mu}_{j}$ as

\begin{equation}
\Vert \bm{\mu}_{j} \Vert_{2}^{2} = \sum_{i \in \mathcal{G}_{j}} \mu_{j_i}^{2} = \sum_{i \in \mathcal{G}_{j}} |u_{j_i}|^{2/k_1} = \Vert \bm{u}_{{j}} \Vert_{2/k_1}^{2/k_1} \,. \nonumber
\end{equation}

Letting $k\triangleq k_1+k_2$, we define the non-convex base regularizer as $\mathcal{R}_{\bm{\beta}}(\bm{\beta}) \triangleq k \Vert \bm{\beta} \Vert_{2/k_1,2/k}^{2/k}$ and the surrogate as $\mathcal{R}_{\bm{\xi}}(\bm{\mu},\bnu) \triangleq k_1 \Vert \bm{\mu} \Vert_{2}^{2} + k_2 \Vert \bm{\nu} \Vert_{2}^{2}$. Together, $\K$ and $\Rxi$ form an SVF for $\Rbeta$:

For a parametrization $\K(\bu,\bnu)=\bm{\mu} \odot |\bm{\mu}|^{\circ(k_1-1)} \odotg |\bnu|^{\circ k_2}$, the minimum of the surrogate $\ell_2$ regularizer $\Rxi(\bu,\bnu) \triangleq k_1 \Vert \bm{\mu} \Vert_{2}^{2} + k_2 \Vert \bm{\nu} \Vert_{2}^{2}$ subject to $\K(\bu,\bnu)=\bbeta$ constitutes an SVF for $\Rbeta(\bbeta)\triangleq k \norm{\bbeta}_{2/k_1,2/k}^{2/k}$ and is given by

\begin{equation} \label{eq:S_ghpowpk1}
\min_{\substack{\bm{\mu}, \bm{\nu}: \bm{\mu}\odot|\bm{\mu}|^{\circ(k_1-1)} \odotg |\bnu|^{\circ k_2} = \bm{\beta}}}  k_1 \Vert \bm{\mu} \Vert_{2}^{2} + k_2 \Vert \bm{\nu} \Vert_{2}^{2}  = k \Vert \bm{\beta} \Vert_{2/k_1,2/k}^{2/k} \quad\forall\bbeta\in\Rd \,,
\end{equation}

The optimality conditions obtained in the proof of this result further ensure Assumption <ref> holds by establishing upper hemicontinuity of the set-valued solution map of the SVF according to Lemma <ref>. Given an $\ell_{2/k_1,2/k}$ regularized objective $\P(\bpsi,\bbeta)$, we can construct a surrogate $\Q(\bpsi,\bm{\mu},\bnu)$ from the tuple $(\Rbeta,\K,\Rxi)$:

\begin{align}
%\min_{\bm{\psi}, \bm{\beta}}
&\mathcal{P}(\bm{\psi}, \bm{\beta}) = \mathcal{L}(\bm{\psi}, \bm{\beta}) + \lambda k \|\bm{\beta}\|_{2/k_1,2/k}^{2/k}, \label{eq:optim_q_had-lpq-power} %=  \sum_{i=1}^{n} \mathscr{L}\left(y_{i}, f(\bm{x}_i|{\bm{\psi},\bm{\beta}}) \right) + \lambda k \sum_{j=1}^{L}\Vert \bm{\beta}_{{j}}\Vert_{2/k_1}^{2/k}
\\
%\min_{\bm{\psi}, \bm{\mu}, \bm{\nu}}
&\mathcal{Q}(\bm{\psi}, \bm{\mu},\bm{\nu}) =  \mathcal{L}\big(\bm{\psi}, (\bm{\mu} \odot |\bm{\mu}|^{\circ (k_1-1)}) \odotg |\bnu|^{\circ k_2}\big) + \lambda \left( k_1 \Vert \bm{\mu} \Vert_{2}^{2} + k_2 \Vert \bm{\nu} \Vert_{2}^{2} \right). \label{eq:optim_g_had-lpq-power} %\\
%&=  \sum_{i=1}^{n} \mathscr{L}\left(y_{i}, f\left(\bm{x}_i \bigl\vert {\bm{\psi}, (\bm{\mu} \odot |\bm{\mu}|^{\circ (k_1-1)}) \odotg |\bnu|^{\circ k_2}}\right)\right) + \lambda \sum_{j=1}^{L} k_1\Vert \bm{\mu}_{j} \Vert_{2}^{2} + k_2 |\nu_j|^2 \,.  \nonumber
\end{align}

The optimization of $\P(\bpsi,\bbeta)$ in (<ref>) is equivalent to the optimization of the smooth surrogate $\Q(\bpsi,\bu, \bnu)$ in (<ref>) for any $k_1,k_2\in\mathbb{R}^{+}$ according to Definition <ref>, and solutions to $\mathcal{P}$ can be constructed from solutions to $\mathcal{Q}$ as $(\hbpsi,\hat{\bm{\beta}}) = (\hbpsi,\bm{\mu} \odot |\bm{\mu}|^{\circ (k_1-1)} \odotg |\hbnu|^{\circ k_2})$.

§ OPTIMIZATION DETAILS

In this section, we discuss optimization details of our smooth optimization transfer approach and provide some guidance regarding practical implementations.

Iterative optimization using (S)GD
A considerable body of literature has established desirable convergence properties of (S)GD that hold in overparametrized non-convex settings, such as provably almost always escaping (strict) saddle points under random initialization and mild regularity conditions [Lee et al., 2016, Lee et al., 2019]. For full-batch GD, however, Du et al., 2017 show that it might take exponentially long to escape saddle points. This can be reduced to polynomial time in the presence of sufficient perturbation in the gradient updates [Ge et al., 2015, Jin et al., 2017], emphasizing the benefit of SGD in efficiently optimizing non-convex problems.
The effect of applying a smooth parametrization on the optimization landscape is not only to transfer the problem to a more curved space, but it also impacts the optimization geometry of (S)GD in a way that has been termed the “rich get richer" effect in the literature. This effect hinges on the multiplicative structure of the parametrizations $\K$, leading to additional multiplicative dependence of the gradient updates of one Hadamard factor on the current parameter values of the remaining factors parametrizing the same base parameter.
This also shows in the gradient of the smooth surrogate (<ref>) where the product-structured Jacobian $\mathcal{J}_{\K(\bxi)}(\bxi)$ essentially acts as a parameter-dependent preconditioner leading to adaptive step sizes and momentum [Arora et al., 2019].

Besides overparametrization, our approach also imposes differentiable surrogate regularization, inducing additional regularizing effects that differentiate our approach from the mere (unpenalized) overparametrization in implicit regularization. In contrast, our method does not require impractically small initializations to induce regularization [Woodworth et al., 2020, Zhao et al., 2022, Vaskevicius et al., 2019] because the actual solutions of the regularized smooth surrogate reflect the induced sparse regularization, regardless of how this solution is reached. Likewise, early stopping is not strictly required as in implicit regularization [Li et al., 2021], since the equivalence holds on the solution level independent of some optimization trajectory window.

Critical points

Due to the results obtained in Lemma <ref> and Lemma <ref>, any local minimum of the surrogate optimization problem corresponds to a local minimum in the base parametrization. As a result, if the base optimization problem $\P(\bpsi,\bbeta)$
is convex, e.g., for a convex $\L(\bpsi,\bbeta)$ with $\ell_1$ or $\ell_{2,1}$ regularization, every local minimum of the surrogate problem $\Q(\bpsi,\bxi)$ is necessarily global. For non-convex base problems, our approach ensures no spurious minima are created in the optimization transfer.

However, such a matching property does not necessarily hold for critical points of the surrogate $\Q$, owed to the zero-product property of the parametrizations $\K$. Without loss of generality, consider a non-smooth regularized objective $\P(\bbeta)=\L(\bbeta)+\lambda \Rbeta(\bbeta)$ with smooth loss $\L(\bbeta)$ and no additional unregularized parameters $\bpsi$. Applying the proposed smooth optimization transfer, we construct the surrogate $\Q(\bxi)=\L(\K(\bxi))+\lambda \Rxi(\bxi)$ using a smooth parametrization $\K(\bxi)$ and further imposing surrogate $\ell_2$ regularization on $\bxi$. The gradient of $\Q$ with respect to $\bm{\xi}$ is then given by

\begin{equation} \label{eq:gradient-intext}
\nabla_{\bxi} \Q(\bm{\xi}) = \mathcal{J}_{\mathcal{K}(\bm{\xi})}^{\top}(\bxi) \nabla_{\K} \mathcal{L}(\mathcal{K}(\bm{\xi})) + \lambda \nabla_{\bxi} \mathcal{R}_{\bm{\xi}}(\bxi)\,,
\end{equation}