ADMM for Structured Fractional Minimization

## Abstract

Abstract We consider a class of structured fractional minimization problems, where the numerator includes a differentiable function, a simple nonconvex nonsmooth function, a concave nonsmooth function, and a convex nonsmooth function composed with a linear operator, while the denominator is a continuous function that is either weakly convex or has a weakly convex square root. These problems are widespread and span numerous essential applications in machine learning and data science. Existing methods are mainly based on subgradient methods and smoothing proximal gradient methods, which may suffer from slow convergence and numerical stability issues. In this paper, we introduce FADMM , the first Alternating Direction Method of Multipliers tailored for this class of problems. FADMM decouples the original problem into linearized proximal subproblems, featuring two variants: one using Dinkelbach’s parametric method ( FADMM-D ) and the other using the quadratic transform method ( FADMM-Q ). By introducing a novel Lyapunov function, we establish that FADMM converges to ϵ italic-ϵ \epsilon -approximate critical points of the problem within an oracle complexity of 𝒪 ​ ( 1 / ϵ 3 ) 𝒪 1 superscript italic-ϵ 3 \mathcal{O}(1/\epsilon^{3}) . Our experiments on synthetic and real-world data for sparse Fisher discriminant analysis, robust Sharpe ratio minimization, and robust sparse recovery demonstrate the effectiveness of our approach.

## 1 Introduction

This paper focuses on the following class of nonconvex and nonsmooth fractional minimization problem (where ‘$\triangleq$’ denotes definition):

$$ $\displaystyle\min_{\mathbf{x}}\,F(\mathbf{x})\triangleq\frac{u(\mathbf{x})}{d(\mathbf{x})},~{}\text{where}~{}u(\mathbf{x})\triangleq f(\mathbf{x})+\delta(\mathbf{x})-g(\mathbf{x})+h(\mathbf{A}\mathbf{x}).$ (1) $$

Here, $\mathbf{x}\in\mathbb{R}^{n}$ and $\mathbf{A}\in\mathbb{R}^{m\times n}$. We impose the following assumptions on Problem ([1](#S1.E1)). (i) The function $f(\mathbf{x})$ is differentiable and possibly nonconvex. (ii) The function $\delta(\mathbf{x})$ is possibly nonconvex, nonsmooth, and non-Lipschitz. (iii) Both functions $g(\mathbf{x})$ and $h(\mathbf{x})$ are convex and possibly nonsmooth. (iv) Both functions $\delta(\mathbf{x})$ and $h(\mathbf{y})$ are simple, such that their proximal operators can be computed efficiently and exactly. (v) The function $d(\mathbf{x})$ is Lipschitz continuous, and either $d(\mathbf{x})$ itself or its square root, $d(\mathbf{x})^{1/2}$, is weakly convex. (vi) To ensure Problem ([1](#S1.E1)) is well-defined, we assume that all functions $g(\mathbf{x})$, $\delta(\mathbf{x})$, $h(\mathbf{y})$, and $d(\mathbf{x})$ are proper and lower semicontinuous, $u(\mathbf{x})\geq 0$, and $d(\mathbf{x})\geq 0$ for all $\mathbf{x}$ and $\mathbf{y}$.

Problem ([1](#S1.E1)) serves as a fundamental optimization framework in various machine learning and data science models, such as sparse Fisher discriminant analysis Bishop & Nasrabadi (), (robust) Sharpe ratio maximization Chen et al. (), robust sparse recovery Yuan (); Yang & Zhang (), limited-angle CT reconstruction Wang et al. (), AUC maximization Wang et al. (), and signal-to-noise ratio maximization Shen & Yu (; ). An alternative formulation of Problem ([1](#S1.E1)) can be obtained by replacing the maximization with the minimization, as explored in the fractional optimization literature Stancu-Minasian (); Schaible (). Although these two formulations are generally distinct, the corresponding algorithmic developments can readily adapt to either formulation.

### 1.1 Motivating Applications

Many models in machine learning and data science can be formulated as Problem ([1](#S1.E1)). We present the sparse Fisher discriminant analysis application below, with additional applications, including robust Sharpe ratio maximization and robust sparse recovery, detailed in Appendix [B](#A2).

$\bullet$ Sparse Fisher Discriminant Analysis (Sparse FDA). Given observations from two distinct classes, let $\bm{\mu}_{(i)}\in\mathbb{R}^{n}$ and $\bm{\Sigma}_{(i)}\in\mathbb{R}^{n\times n}$ represent the mean vector and covariance matrix of class $i$ ($i=1$ or $2$), respectively. Classical FDA Bishop & Nasrabadi (); Xu & Li () aims to find an orthogonal subspace $\mathbf{X}\in\Omega$ with $\Omega\triangleq\{\mathbf{X}\,|\,\mathbf{X}^{\mathsf{T}}\mathbf{X}=\mathbf{I}_{r}\}$, that maximizes the between-class variance relative to the within-class variance. This leads to the following optimization problem: $\min_{\mathbf{X}\in\Omega}\,{\operatorname{tr}(\mathbf{X}^{\mathsf{T}}(\bm{\Sigma}_{(1)}+\bm{\Sigma}_{(2)})\mathbf{X})}/{\operatorname{tr}(\mathbf{X}^{\mathsf{T}}((\bm{\mu}_{(1)}-\bm{\mu}_{(2)})(\bm{\mu}_{(1)}-\bm{\mu}_{(2)})^{\mathsf{T}})\mathbf{X})}$. Inducing sparsity in the solution helps mitigate overfitting and enhances the interpretability of the model in high-dimensional data analysis Journée et al. (). We consider the following Difference-of-Convex (DC) model Gotoh et al. (); Bi et al. () for learning sparse orthogonal loadings for FDA:

$$ $\displaystyle\min_{\mathbf{X}\in\mathbb{R}^{n\times r}}~{}\frac{\operatorname{tr}(\mathbf{X}^{\mathsf{T}}\mathbf{C}\mathbf{X})+\rho(\|\mathbf{X}\|_{1}-\|\mathbf{X}\|_{[k]})}{\operatorname{tr}(\mathbf{X}^{\mathsf{T}}\mathbf{D}\mathbf{X})},~{}\operatorname{s.t.}\mathbf{X}\in\Omega,$ (2) $$

where $\mathbf{D}\triangleq(\bm{\mu}_{(1)}-\bm{\mu}_{(2)})(\bm{\mu}_{(1)}-\bm{\mu}_{(2)})^{\mathsf{T}}$, $\mathbf{C}=\bm{\Sigma}_{(1)}+\bm{\Sigma}_{(2)}$, and $\|\mathbf{X}\|_{[k]}$ is the $\ell_{1}$ norm of the $k$ largest (in magnitude) elements of the matrix $\mathbf{X}$. A notable advantage of this model is that when $\rho$ is sufficient large, $\|\mathbf{X}\|_{[k]}$ closely approximates $\|\mathbf{X}\|_{1}$, resulting in a solution $\mathbf{X}$ with $k$-sparsity. We define $\iota_{\Omega}(\mathbf{X})$ as the indicator function of the set $\Omega$. Problem ([2](#S1.E2)) coincides with Problem ([1](#S1.E1)) with $\mathbf{x}=\operatorname{vec}(\mathbf{X})$, $f(\mathbf{x})=\operatorname{tr}(\mathbf{X}^{\mathsf{T}}\mathbf{C}\mathbf{X})$, $\delta(\mathbf{x})=\iota_{\Omega}(\mathbf{X})$, $g(\mathbf{x})=\rho\|\mathbf{X}\|_{[k]}$, $\mathbf{A}=\mathbf{I}$, $h(\mathbf{A}\mathbf{x})=\|\mathbf{X}\|_{1}$, and $d(\mathbf{x})=\operatorname{tr}(\mathbf{X}^{\mathsf{T}}\mathbf{D}\mathbf{X})$. Importantly, both $d(\mathbf{x})$ and $d(\mathbf{x})^{1/2}$ are $W_{d}$-weakly convex with $W_{d}=0$.

### 1.2 Contributions and Organizations

The contributions of this paper are threefold. (i) We propose FADMM, a new ADMM tailored for nonsmooth composite fractional minimization problems. This method includes two specialized variants: FADMM based on Dinkelbach’s parametric method (FADMM-D) and FADMM based on the quadratic transform method (FADMM-Q). (ii) We establish that both FADMM-D and FADMM-Q algorithms converge to an $\epsilon$-critical point with a computational complexity of $\mathcal{O}(1/\epsilon^{3})$. This is the first report of iteration complexity results for estimating approximate stationary points for this class of fractional programs. (iii) We conducted experiments on sparse FDA, robust Sharpe ratio maximization, and robust sparse recovery to demonstrate the effectiveness of our approach.

The rest of the paper is organized as follows: Section [2](#S2) reviews related work. Section [3](#S3) presents technical preliminaries. Section [4](#S4) details the proposed algorithm. Section [5](#S5) discusses global convergence. Section [6](#S6) addresses iteration complexity. Section [7](#S7) provides some experiment results, and Section [8](#S8) concludes the paper.

## 2 Related Work

We review some nonconvex optimization algorithms that are related to solve the fractional program in Problem ([1](#alg1)).

$\bullet$ Algorithms in Limited Scenarios. Existing fractional minimization algorithms primarily address a special instance of Problem ([1](#alg1)) that $\min_{\mathbf{x}}\,F(\mathbf{x})\triangleq u(\mathbf{x})/d(\mathbf{x})$, where $u(\mathbf{x})\triangleq f(\mathbf{x})+\delta(\mathbf{x})$. (i) Dinkelbach’s Parametric Algorithm (DPA) Dinkelbach () is a classical approach. The fractional program has an optimal solution $\bar{\mathbf{x}}$ if and only if $\bar{\mathbf{x}}$ is an optimal solution to the problem $\min_{\mathbf{x}}u(\mathbf{x})-\bar{\lambda}d(\mathbf{x})$, where $\bar{\lambda}=F(\bar{\mathbf{x}})$. Since the optimal value $\bar{\lambda}$ is generally unknown, iterative methods are used. DPA generates a sequence $\{\mathbf{x}^{t}\}$ as: $\mathbf{x}^{t+1}=\arg\min_{\mathbf{x}}\ u(\mathbf{x})-\lambda^{t}d(\mathbf{x})$, with $\lambda^{t}$ updated as $\lambda^{t}=F(\mathbf{x}^{t})$. (ii) The Quadratic Transform Algorithm (QTA) Zhou & Yang (); Shen & Yu (; ) reformulates the problem as: $\min_{\mathbf{x}}-d(\mathbf{x})/u(\mathbf{x})\Leftrightarrow\min_{\mathbf{x},\alpha}\alpha^{2}u(\mathbf{x})-2\alpha d(\mathbf{x})^{1/2}$. QTA generates a sequence $\{\mathbf{x}^{t}\}$ as: $\mathbf{x}^{t+1}=\arg\min_{\mathbf{x}}(\alpha^{t})^{2}u(\mathbf{x})-2\alpha^{t}d(\mathbf{x})^{1/2}$, with $\alpha^{t}$ updated as $\alpha^{t}=d(\mathbf{x}^{t})^{1/2}\cdot u(\mathbf{x}^{t})^{-1}$. This method is particularly suited for solving multiple-ratio fractional programs. (iii) Linearized variants of DPA and QTA Li & Zhang (); Boţ et al. () address the high computational cost of solving nonconvex subproblems in DPA and QTA. They employ full splitting paradigms and achieve fast convergence by performing a single iteration of splitting algorithms at each step, efficiently avoiding inner loops to solve complex nonconvex problems. The proposed ADMM algorithm is built on linearized DPA and QTA to solve the subproblems.

$\bullet$ General Algorithms for Solving Problem ([1](#alg1)). (i) Subgradient Projection Methods (SPM) Li et al. () offer a simple, natural approach to solving Problem ([1](#S1.E1)). SPM iteratively updates the solution by moving in the negative subgradient direction and projecting onto the feasible set: $\mathbf{x}^{t+1}=\mathcal{P}_{\Omega}(\mathbf{x}^{t}-\eta^{t}\mathbf{g}^{t})$, where $\mathbf{g}^{t}\in\partial F(\mathbf{x}^{t})$, $\Omega$ is the constraint set, and $\eta^{t}$ is a diminishing step size. However, as $\mathbf{g}^{t}$ is not unique, these methods often suffer from slower convergence and numerical instability. (ii) Smoothing Proximal Gradient Methods (SPGM) Beck & Rosset (); Yuan (); Bian & Chen (); Böhm & Wright () combine gradient-based optimization with smoothing techniques to handle nonsmooth terms in the objective function. By approximating nonsmooth components with smooth ones, SPGM enables more efficient updates via the proximal gradient method, achieving convergence for complex nonsmooth problems. In fact, the proposed FADMM algorithm reduces to SPGM when the multiplier is set to zero in all iterations. Our FADMM achieves faster convergence and better numerical stability than both SPM and SPGM.

$\bullet$ Other Fractional Minimization Algorithms. (i) Charnes-Cooper transform algorithm converts an original linear-fractional programming problem to a standard linear programming problem Charnes & Cooper (). Using the transformation $\mathbf{y}=\frac{\mathbf{x}}{d(\mathbf{x})}$, $t=\frac{1}{d(\mathbf{x})}$, Problem ([1](#S1.E1)) can be reformulated as: $\min_{t,\mathbf{y}}tu(\mathbf{y}/t),~{}s.t.~{}td(\mathbf{y}/t)=1$. (ii) Coordinate descent algorithms Yuan () iteratively solve one-dimensional subproblems globally and are guaranteed to converge to stronger coordinate-wise stationary points for a specific class of fractional programs. (iii) Inertial proximal block coordinate methods Boţ et al. (), based on the quadratic transform, have been proposed to address a class of nonsmooth sum-of-ratios minimization problems.

$\bullet$ ADMM for Nonconvex Optimization. The Alternating Direction Method of Multipliers (ADMM) is a powerful optimization technique that addresses complex problems by breaking them down into simpler, more manageable subproblems, which are then solved iteratively to achieve convergence. The standard ADMM was first introduced in Gabay & Mercier (), with complexity analysis for convex settings conducted in He & Yuan (); Monteiro & Svaiter (). Motivated by research on the convergence analysis of nonconvex ADMM Li & Pong (); Hong et al. (); Boţ et al. (); Boţ & Nguyen (); Yuan (), we propose applying ADMM to solve structured fractional minimization problems. To the best of our knowledge, this is the first instance of ADMM being used to address fractional programs, and our goal is to study both the theoretical iteration complexity required to reach an approximate stationary point and the empirical performance of the method.

## 3 Technical Preliminaries

This section presents technical preliminaries on basic assumptions, stationary points, and Nesterov’s smoothing techniques. Notations, additional technical preliminaries, and relevant lemmas are provided in Appendix Section [A](#A1).

### 3.1 Basic Assumptions and Stationary Points

We impose the following assumptions on Problem ([1](#S1.E1)) throughout this paper.

###### Assumption 3.1 .

There exists a universal positive constant $\overline{\rm{x}}$ such that $\|\mathbf{x}\|\leq\overline{\rm{x}}$ for all $\mathbf{x}\in\operatorname{dom}(F)$.

###### Assumption 3.2 .

The function $f(\cdot)$ is $L_{f}$-smooth such that $\|\nabla f(\mathbf{x})-\nabla f(\mathbf{x}^{\prime})\|\leq L_{f}\|\mathbf{x}-\mathbf{x}^{\prime}\|$ holds for all $\mathbf{x},\mathbf{x}^{\prime}\in\mathbb{R}^{n}$. This implies that: $|f(\mathbf{x})-f(\mathbf{x}^{\prime})-\langle\nabla f(\mathbf{x}^{\prime}),\mathbf{x}-\mathbf{x}^{\prime}\rangle|\leq\tfrac{L_{f}}{2}\|\mathbf{x}-\mathbf{x}^{\prime}\|_{2}^{2}$ (cf. Lemma 1.2.3 in Nesterov ()).

###### Assumption 3.3 .

Let $\mu>0$, $\mathbf{x}^{\prime}\in\mathbb{R}^{n}$, and $\mathbf{y}^{\prime}\in\mathbb{R}^{m}$. Both proximal operators, $\operatorname{\operatorname{Prox}}(\mathbf{y}^{\prime};h,\mu)\triangleq\arg\min_{\mathbf{y}}\tfrac{1}{2\mu}\|\mathbf{y}-\mathbf{y}^{\prime}\|_{2}^{2}+h(\mathbf{y})$ and $\operatorname{\operatorname{Prox}}(\mathbf{x}^{\prime};\delta,\mu)\triangleq\arg\min_{\mathbf{x}}\tfrac{1}{2\mu}\|\mathbf{x}-\mathbf{x}^{\prime}\|_{2}^{2}+\delta(\mathbf{x})$, can be computed efficiently and exactly.

###### Assumption 3.4 .

The function $d(\mathbf{x})$ is $C_{d}$-Lipschitz continuous with $C_{d}\geq 0$, and meets one of the following conditions for some $W_{d}\geq 0$: (a) $d(\mathbf{x})$ is $W_{d}$-weakly convex. (b) $\sqrt{d(\mathbf{x})}$ is $W_{d}$-weakly convex.

###### Remark 3.5 .

(i) Assumption [3.1](#S3.Thmtheorem1) is fulfilled by setting $\delta(\mathbf{x})=\iota_{\Omega}(\mathbf{x})$, where $\Omega$ is a compact set. (ii) Assumption [3.2](#S3.Thmtheorem2) is commonly used in the convergence analysis of nonconvex algorithms. (iii) (iv) Assumption [3.3](#S3.Thmtheorem3) is mild and is satisfied by our applications. Appendix [G](#A7) details the computation of proximal operators.

We now introduce the definition of stationary points for Problem ([1](#S1.E1)). A straightforward option is the Fréchet stationary point Rockafellar & Wets. (); Mordukhovich (). Recall that a solution $\ddot{\mathbf{x}}$ is a Fréchet stationary point of Problem ([1](#S1.E1)) if: $\mathbf{0}\in\widehat{\partial}F(\ddot{\mathbf{x}})=\widehat{\partial}((f+\delta-g+h\circ A)/{d})(\ddot{\mathbf{x}})$. However, computing a Fréchet stationary point is challenging for general nonconvex nonsmooth programs. Following the work of Li et al. (); Li & Zhang (); Boţ et al. (; ); Yuan (), we adopt a weaker notion of optimality, namely critical points (or limiting lifted stationary points), defined as follows:

###### Definition 3.6 .

(Critical Point) A solution $\dot{\mathbf{x}}\in\operatorname{dom}(F)$ is a critical point of Problem ([1](#S1.E1)) if: $\mathbf{0}\in\partial\delta(\dot{\mathbf{x}})+\nabla f(\dot{\mathbf{x}})-\partial g(\dot{\mathbf{x}})+\mathbf{A}^{\mathsf{T}}\partial h(\mathbf{A}\dot{\mathbf{x}})-F(\dot{\mathbf{x}})\partial d(\dot{\mathbf{x}})$.

###### Remark 3.7 .

Using Lemma [A.1](#A1.Thmtheorem1) in Appendix [A.2](#A1.SS2), we obtain that $\widehat{\partial}F(\mathbf{x})\in g(\mathbf{x})^{-2}\{\partial\delta(\mathbf{x})+\nabla f(\mathbf{x})-\partial g(\mathbf{x})+\mathbf{A}^{\mathsf{T}}\partial h(\mathbf{A}\mathbf{x})-F(\mathbf{x})\partial d(\mathbf{x})\}$ for any $\mathbf{x}$. According to Definition [3.6](#S3.Thmtheorem6), $\mathbf{0}\in\widehat{\partial}F(\ddot{\mathbf{x}})$ implies that $\ddot{\mathbf{x}}$ is a critical point of Problem [1](#S1.E1), while the converse is generally not true. However, under certain mild conditions discussed in Boţ et al. (; ), Definition [3.6](#S3.Thmtheorem6) aligns with the standard Fréchet stationary point that $\mathbf{0}\in\widehat{\partial}F(\dot{\mathbf{x}})$.

###### Assumption 3.1 .

###### Assumption 3.2 .

###### Assumption 3.3 .

###### Assumption 3.4 .

###### Remark 3.5 .

###### Definition 3.6 .

###### Remark 3.7 .

### 3.2 Nesterov’s Smoothing Technique

The nonsmooth nature of the function $h(\mathbf{y})$ presents challenges for the algorithm design and theoretical analysis. To address this, we approximate $h(\mathbf{y})$ with a smooth function $h_{\mu}(\mathbf{y})$ using Nesterov’s smoothing technique Nesterov (; ); Devolder et al. (), which relies on the conjugate function of $h(\mathbf{y})$. We introduce the following useful definition in this context.

###### Definition 3.8 .

For a proper, convex, and lower semicontinuous function $h(\mathbf{y}):\mathbb{R}^{m}\mapsto\mathbb{R}$, the Nesterov’s smoothing function for $h(\mathbf{y})$ with a parameter $\mu\in(0,\infty)$ is defined as: $h_{\mu}(\mathbf{y})=\max_{\mathbf{v}}\langle\mathbf{y},\mathbf{v}\rangle-h^{*}(\mathbf{v})-\tfrac{\mu}{2}\|\mathbf{v}\|_{2}^{2}$.

We outline some key properties of Nesterov’s smoothing function.

###### Lemma 3.9 .

(Proof in Appendix [C.1](#A3.SS1)) Assume that $h(\mathbf{y})$ is $C_{h}$-Lipschitz continuous. We let $\mu>0$, and $0<\mu_{2}\leq\mu_{1}$. We have the following results: (a) The function $h_{\mu}(\mathbf{y})$ is $(1/\mu)$-smooth and convex, with its gradient given by $\nabla h_{\mu}(\mathbf{y})=\arg\max_{\mathbf{v}}\,\{\langle\mathbf{y},\mathbf{v}\rangle-h^{*}(\mathbf{v})-\tfrac{\mu}{2}\|\mathbf{v}\|_{2}^{2}\}$, it holds that $\nabla h_{\mu}(\mathbf{y})=\frac{1}{\mu}(\mathbf{y}-\operatorname{\operatorname{Prox}}(\mathbf{y};h,\mu))$. (b) $0<h(\mathbf{y})-h_{\mu}(\mathbf{y})\leq\tfrac{\mu}{2}C_{h}^{2}$. (c) The function $h_{\mu}(\mathbf{y})$ is $C_{h}$-Lipschitz continuous. (d) $h_{\mu}(\mathbf{y})=\tfrac{1}{2\mu}\|\mathbf{y}-\dot{\mathbf{y}}\|_{2}^{2}+h(\dot{\mathbf{y}})$, where $\dot{\mathbf{y}}=\operatorname{\operatorname{Prox}}(\mathbf{y};h,\mu)$. (e) $0\leq h_{\mu_{2}}(\mathbf{y})-h_{\mu_{1}}(\mathbf{y})\leq\tfrac{\mu_{1}-\mu_{2}}{2}C_{h}^{2}$. (f) $\|\nabla h_{\mu_{2}}(\mathbf{y})-\nabla h_{\mu_{1}}(\mathbf{y})\|\leq(\tfrac{\mu_{1}}{\mu_{2}}-1)C_{h}$.

###### Lemma 3.10 .

(Proof in Section [C.2](#A3.SS2)) Assume that $h(\mathbf{y})$ is $C_{h}$-Lipschitz continuous. Let $\mathbf{b}\in\mathbb{R}^{m}$, and $\beta,\mu>0$. Consider $\bar{\mathbf{y}}\in\arg\min_{\mathbf{y}}h_{\mu}(\mathbf{y})+\tfrac{1}{2}\beta\|\mathbf{y}-\mathbf{b}\|_{2}^{2}\triangleq\operatorname{\operatorname{Prox}}(\mathbf{b};h_{\mu},1/\beta)$. We have: (a) $\bar{\mathbf{y}}=\tfrac{\check{\mathbf{y}}+\beta\mu\mathbf{b}}{1+\beta\mu}$, where $\check{\mathbf{y}}\triangleq\operatorname{\operatorname{Prox}}(\mathbf{b};h,\mu+1/\beta)$. (b) $\beta(\mathbf{b}-\bar{\mathbf{y}})\in\partial h(\check{\mathbf{y}})$. (c) $\|\bar{\mathbf{y}}-\check{\mathbf{y}}\|\leq\mu C_{h}$.

###### Remark 3.11 .

(i) Lemmas [3.9](#S3.Thmtheorem9) and [3.10](#S3.Thmtheorem10) represent novel contributions of this paper and play an essential role in the analysis of the proposed FADMM algorithm. (ii) Lemma [3.10](#S3.Thmtheorem10) shows how to compute the proximal operator $\operatorname{\operatorname{Prox}}(\mathbf{b};h_{\mu},1/\beta)$ from $\operatorname{\operatorname{Prox}}(\mathbf{b};h,1/\beta^{\prime})$ for some $\beta,\beta^{\prime}>0$ and $\mathbf{b}\in\mathbb{R}^{m}$.

###### Definition 3.8 .

###### Lemma 3.9 .

###### Lemma 3.10 .

###### Remark 3.11 .

## 4 The Proposed FADMM Algorithm

This section presents the proposed FADMM Algorithm for solving Problem ([1](#S1.E1)), featuring two variants: one based on Dinkelbach’s parametric method (FADMM-D) Dinkelbach () and the other on the quadratic transform method (FADMM-Q) Zhou & Yang (); Shen & Yu (). Notably, FADMM-D and FADMM-Q target different problem structures: FADMM-D is designed for Assumption [3.4](#S3.Thmtheorem4)(a), while FADMM-Q is suited for Assumption [3.4](#S3.Thmtheorem4)(b), with potential extensions to multi-ratio fractional programs Boţ et al. ().

We first introduce a new variable $\mathbf{y}\in\mathbb{R}^{m}$ and reformulate Problem ([1](#S1.E1)) as: $\min_{\mathbf{x},\mathbf{y}}\{f(\mathbf{x})+\delta(\mathbf{x})-g(\mathbf{x})+h_{\mu}(\mathbf{y})\}/d(\mathbf{x}),\ \mathbf{A}\mathbf{x}=\mathbf{y}$, where $h_{\mu}(\mathbf{y})$ is the Nesterov’s smoothing function of $h(\mathbf{y})$, with $\mu\rightarrow 0$ as the smoothing parameter. Notably, similar smoothing techniques have been used in the design of augmented Lagrangian methods Zeng et al. (), ADMM Li et al. (); Yuan (), and minimax optimization Zhang et al. (). From this problem, we define two functions, referred to as modified augmented Lagrangian functions, as follows:

$$ $\displaystyle\mathcal{L}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)$ $\displaystyle\,\triangleq\,\tfrac{\mathcal{U}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)}{d(\mathbf{x})},$ (3) $\displaystyle\mathcal{K}(\alpha,\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)$ $\displaystyle\,\triangleq\,-2\alpha\sqrt{d(\mathbf{x})}+\alpha^{2}\mathcal{U}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu),$ (4) $$

where

$$ $\displaystyle\mathcal{U}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)\triangleq\underbrace{f(\mathbf{x})+\langle\mathbf{A}\mathbf{x}-\mathbf{y},\mathbf{z}\rangle+\tfrac{\beta}{2}\|\mathbf{A}\mathbf{x}-\mathbf{y}\|_{2}^{2}}_{\triangleq\,\mathcal{S}(\mathbf{x},\mathbf{y};\mathbf{z};\beta)}+\delta(\mathbf{x})-g(\mathbf{x})+h_{\mu}(\mathbf{y}).$ (5) $$

Here, $\beta$ is the penalty parameter and $\mathbf{z}$ is the dual variable for the linear constraint. In brief, FADMM updates the primal variables sequentially, keeping the others fixed, and updates the dual variables via gradient ascent on the dual problem. It iteratively generates a sequence $\{\mathbf{x}^{t},\mathbf{y}^{t},\mathbf{z}^{t},\lambda^{t},\beta^{t},\mu^{t}\}_{t=0}^{\infty}$ or $\{\alpha^{t},\mathbf{x}^{t},\mathbf{y}^{t},\mathbf{z}^{t},\beta^{t},\mu^{t}\}_{t=0}^{\infty}$, where $\beta^{t}=\beta^{0}(1+\xi t^{p})$, $\mu^{t}=\frac{\chi}{\beta^{t}}$, and $\{\beta^{0},\xi,p,\chi\}$ are fixed constants.

Majorization Minimization (MM). MM is an effective optimization strategy to minimize complex functions and is a widely used to develop practical optimization algorithms Mairal (); Razaviyayn et al. (). This technique iteratively constructs a majorization function that upper-bounds the objective, enabling efficient optimization and gradual reduction of the objective function. We define $s(\mathbf{x})\triangleq\SS(\mathbf{x},\mathbf{y}^{t},\mathbf{z}^{t};\beta^{t})$, where $t$ is known from context. Given that $s(\mathbf{x})$ is $(L_{f}+\beta^{t}\|\mathbf{A}\|_{2}^{2})$-smooth, $g(\mathbf{x})$ is convex, and both $d(\mathbf{x})$ or $\sqrt{d(\mathbf{x})}$ are $W_{d}$-weakly convex, we construct the majorization functions for the four functions as follows.

- (a)
$s(\mathbf{x})\leq\mathcal{U}^{t}(\mathbf{x};\mathbf{x}^{t})\triangleq s(\mathbf{x}^{t})+\langle\mathbf{x}-\mathbf{x}^{t},\nabla s(\mathbf{x}^{t})\rangle+\tfrac{1}{2}(L_{f}+\beta^{t}\|\mathbf{A}\|_{2}^{2})\|\mathbf{x}-\mathbf{x}^{t}\|_{2}^{2}$.
- (b)
$-g(\mathbf{x})\leq\mathcal{R}(\mathbf{x};\mathbf{x}^{t})\triangleq-g(\mathbf{x}^{t})-\langle\mathbf{x}-\mathbf{x}^{t},\bm{\xi}\rangle$, $\forall\bm{\xi}\in\partial g(\mathbf{x}^{t})$.
- (c)
$-d(\mathbf{x})\leq\dot{\mathcal{V}}(\mathbf{x};\mathbf{x}^{t})\triangleq-d(\mathbf{x}^{t})-\langle\mathbf{x}-\mathbf{x}^{t},\bm{\xi}\rangle+\tfrac{W_{d}}{2}\|\mathbf{x}-\mathbf{x}^{t}\|_{2}^{2}$, $\forall\bm{\xi}\in\partial d(\mathbf{x}^{t})$.
- (d)
$-\sqrt{d(\mathbf{x})}\leq\ddot{\mathcal{V}}(\mathbf{x};\mathbf{x}^{t})\triangleq-\sqrt{d(\mathbf{x}^{t})}-\langle\mathbf{x}-\mathbf{x}^{t},\bm{\xi}\rangle+\tfrac{W_{d}}{2}\|\mathbf{x}-\mathbf{x}^{t}\|_{2}^{2}$, $\forall\bm{\xi}\in\partial\sqrt{d(\mathbf{x}^{t})}$.

$\bullet$ FADMM-D Algorithm. Based on Equation ([3](#S4.E3)), FADMM-D alternately updates the primal variables $\{\mathbf{x},\mathbf{y}\}$ and the dual variable $\mathbf{z}$. (i) To update the variable $\mathbf{x}$, we approximately solve Dinkelbach’s parametric subproblem as follows: $\mathbf{x}^{t+1}\approx\arg\min_{\mathbf{x}}\dot{\mathcal{W}}^{t}(\mathbf{x})\triangleq s(\mathbf{x})+\delta(\mathbf{x})-g(\mathbf{x})-\lambda^{t}d(\mathbf{x})$, where $\lambda^{t}=\mathcal{L}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$. However, this problem is challenging in general. We apply MM methods and consider the following problem:

$$ $\displaystyle\textstyle\min_{\mathbf{x}}\dot{\mathcal{M}}^{t}(\mathbf{x};\mathbf{x}^{t},\lambda^{t})\triangleq\delta(\mathbf{x})+\mathcal{U}^{t}(\mathbf{x};\mathbf{x}^{t})+\mathcal{R}(\mathbf{x};\mathbf{x}^{t})+\lambda^{t}\dot{\mathcal{V}}(\mathbf{x};\mathbf{x}^{t})+\tfrac{\theta-1}{2}\ell(\beta^{t})\|\mathbf{x}-\mathbf{x}^{t}\|_{2}^{2},$ (6) $$

where $\ell(\beta^{t})\triangleq L_{f}+\beta^{t}\|\mathbf{A}\|_{2}^{2}+\lambda^{t}W_{d}$, and $\theta>1$. One can verify that $\dot{\mathcal{M}}^{t}(\mathbf{x};\mathbf{x}^{t},\lambda^{t})$ is a majorization function, satisfying $\dot{\mathcal{W}}^{t}(\mathbf{x})\leq\dot{\mathcal{M}}^{t}(\mathbf{x};\mathbf{x}^{t},\lambda^{t})$ and $\dot{\mathcal{W}}^{t}(\mathbf{x}^{t})=\dot{\mathcal{M}}^{t}(\mathbf{x}^{t};\mathbf{x}^{t},\lambda^{t})$ for all $\mathbf{x}$ and $\mathbf{x}^{t}$. Problem ([6](#S4.E6)) reduces to the computation of a proximal operator for the function $\delta(\mathbf{x})$, yielding $\mathbf{x}^{t+1}\in\arg\min_{\mathbf{x}}\dot{\mathcal{M}}^{t}(\mathbf{x};\mathbf{x}^{t},\lambda^{t})=\operatorname{\operatorname{Prox}}(\mathbf{x}^{\prime};\delta,\theta\ell(\beta^{t}))$, where $\mathbf{x}^{\prime}=\mathbf{x}^{t}-\mathbf{g}/(\theta\ell(\beta^{t}))$, and $\mathbf{g}\in\nabla s(\mathbf{x}^{t})-\partial g(\mathbf{x}^{t})-\lambda^{t}\partial d(\mathbf{x}^{t})$. (ii) When minimizing the modified augmented Lagrangian function in Equation ([3](#S4.E3)) over $\mathbf{y}$, the problem reduces to solving: $\mathbf{y}^{t+1}\in\arg\min_{\mathbf{y}}h_{\mu^{t}}(\mathbf{y})+\tfrac{1}{2}\beta^{t}\|\mathbf{y}-\mathbf{b}^{t}\|_{2}^{2}$, where $\mathbf{b}^{t}\triangleq\mathbf{y}^{t}-\nabla_{\mathbf{y}}\mathcal{S}(\mathbf{x}^{t+1},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t})/\beta^{t}$. (iii) We adjust the dual variable $\mathbf{z}$ using the standard gradient ascent update rule in ADMM.

$\bullet$ FADMM-Q Algorithm. Based on Equation ([4](#S4.E4)), FADMM-Q alternates between updating the primal variables $\{\alpha,\mathbf{x},\mathbf{y}\}$ and the dual variable $\mathbf{z}$. (i) To update the variable $\alpha$, we set the gradient of $\mathcal{K}(\alpha,\mathbf{x},\mathbf{y};\mathbf{z};\beta)$ w.r.t. $\alpha$ to zero, resulting in the update rule: $\alpha^{t+1}=\sqrt{d(\mathbf{x}^{t})}/\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$. (ii) To update the variable $\mathbf{x}$, we approximately solve the following problem: $\mathbf{x}^{t+1}\approx\arg\min_{\mathbf{x}}\ddot{\mathcal{W}}^{t}(\mathbf{x})\triangleq s(\mathbf{x})+\delta(\mathbf{x})-g(\mathbf{x})-\tfrac{2}{\alpha^{t+1}}\sqrt{d(\mathbf{x})}$. To tackle this challenging problem, we employ MM methods and formulate the following problem:

$$ $\displaystyle\min_{\mathbf{x}}\ddot{\mathcal{M}}^{t}(\mathbf{x};\mathbf{x}^{t},\alpha^{t+1})\triangleq\delta(\mathbf{x})+\mathcal{U}^{t}(\mathbf{x};\mathbf{x}^{t})+\mathcal{R}(\mathbf{x};\mathbf{x}^{t})+\tfrac{2}{\alpha^{t+1}}\ddot{\mathcal{V}}(\mathbf{x};\mathbf{x}^{t})+\tfrac{\theta-1}{2}\ell(\beta^{t})\|\mathbf{x}-\mathbf{x}^{t}\|_{2}^{2},$ (7) $$

where $\ell(\beta^{t})\triangleq L_{f}+\beta^{t}\|\mathbf{A}\|_{2}^{2}+\tfrac{2}{\alpha^{t+1}}W_{d}$, and $\theta>1$. One can show that $\ddot{\mathcal{W}}^{t}(\mathbf{x})\leq\ddot{\mathcal{M}}^{t}(\mathbf{x};\mathbf{x}^{t},\alpha^{t+1})$ and $\ddot{\mathcal{W}}^{t}(\mathbf{x}^{t})\leq\ddot{\mathcal{M}}^{t}(\mathbf{x}^{t};\mathbf{x}^{t},\alpha^{t+1})$ for all $\mathbf{x}$ and $\mathbf{x}^{t}$. Problem ([7](#S4.E7)) can be efficiently and effectively solved, as it reduces to the computation of a proximal operator for the function $\delta(\mathbf{x})$, yielding $\mathbf{x}^{t+1}\in\arg\min_{\mathbf{x}}\ddot{\mathcal{M}}^{t}(\mathbf{x};\mathbf{x}^{t},\alpha^{t+1})=\operatorname{\operatorname{Prox}}(\mathbf{x}^{\prime};\delta,\theta\ell(\beta^{t}))$, where $\mathbf{x}^{\prime}=\mathbf{x}^{t}-\mathbf{g}/(\theta\ell(\beta^{t}))$ and $\mathbf{g}\in\nabla s(\mathbf{x}^{t})-\partial g(\mathbf{x}^{t})-\tfrac{2}{\alpha^{t+1}}\partial\sqrt{d(\mathbf{x}^{t})}$. (iii) We use the same strategy as in FADMM-D to update the primal variable $\mathbf{y}$ and the dual variable $\mathbf{z}$.

Figure: Algorithm 1 FADMM: The Proposed ADMM using Dinkelbach’s Parametric Method or the Quadratic Transform Method for Solving Problem ([1](#S1.E1)).

We summarize FADMM-D and FADMM-Q in Algorithm [1](#alg1), and provide the following remarks.

###### Remark 4.1 .

(i) The $\mathbf{y}$-subproblem in Step (S5) of Algorithm [1](#alg1) can be solved by invoking Lemma [3.10](#S3.Thmtheorem10). (ii) The introduction of the strongly convex term $\tfrac{\theta-1}{2}\ell(\beta^{t})\|\mathbf{x}-\mathbf{x}^{t}\|_{2}^{2}$ with $\theta>1$ as in Problems ([6](#S4.E6)) and ([7](#S4.E7)) is crucial to our analysis. (iii) By minimizing $\mathcal{K}(\alpha,\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)$ and setting its gradient w.r.t. $\alpha$ to zero, we obtain $\alpha^{*}=\mathcal{U}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)/d(\mathbf{x})$, which leads to $\mathcal{L}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)=-1/\mathcal{K}(\alpha^{*},\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)$. Thus, Formulations ([3](#S4.E3)) and ([4](#S4.E4)) are equivalent in a certain sense.

###### Remark 4.1 .

## 5 Global Convergence

This section establishes the global convergence of both FADMM-D and FADMM-Q. We begin with an initial theoretical analysis applicable to both algorithms, followed by a detailed, separate analysis for each.

### 5.1 Initial Theoretical Analysis

First, we impose the following condition on Algorithm [1](#alg1).

###### Assumption 5.1 .

Let $\{\mathbf{x}^{t}\}_{t=0}^{\infty}$ be generated by Algorithm [1](#alg1). For all $t$, there exist constants $\{\underline{\rm{d}},\overline{\rm{d}}\}$ such that $0<\underline{\rm{d}}\leq d(\mathbf{x}^{t})\leq\overline{\rm{d}}$, and constants $\{\underline{\rm{F}},\overline{\rm{F}}\}$ such that $0<\underline{\rm{F}}\leq F(\mathbf{x}^{t})\leq\overline{\rm{F}}$.

###### Remark 5.2 .

(i) The existence of the upper bounds $\overline{\rm{d}}$ and $\overline{\rm{F}}$ is guaranteed by the boundedness of $\mathbf{x}$ and the continuity of the functions $d(\mathbf{x})$ and $F(\mathbf{x})$ within their respective effective domains. (ii) The lower bound condition $\underline{\rm{d}}>0$ is mild and widely utilized in the literature Li & Zhang (); Yuan (); Boţ et al. (). (iii) The lower bound condition $\underline{\rm{F}}>0$ is reasonable; otherwise, it suffices to solve the non-fractional problem: $\min_{\mathbf{x}}u(\mathbf{x})$.

Second, we provide first-order optimality conditions for the solution $\mathbf{y}^{t+1}$.

###### Lemma 5.3 .

(Proof in Appendix [D.1](#A4.SS1), First-Order Optimality Conditions) For all $t\geq 0$, we have: $\mathbf{z}^{t+1}=\nabla h_{\mu^{t}}(\mathbf{y}^{t+1})\in\partial h(\check{\mathbf{y}}^{t+1})$.

Third, using the subsequent lemma, we establish an upper bound for the term $\|\mathbf{z}^{t+1}-\mathbf{z}^{t}\|_{2}^{2}$.

###### Lemma 5.4 .

(Proof in Section [D.2](#A4.SS2), Controlling Dual using Primal) For all $t\geq 1$, we have: $\|\mathbf{z}^{t+1}-\mathbf{z}^{t}\|_{2}^{2}\leq 2\tfrac{(\beta^{t})^{2}}{\chi^{2}}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}+2C_{h}^{2}(\tfrac{6}{t}-\tfrac{6}{t+1})$.

Fourth, we show that the solution $\{\mathbf{x}^{t},\mathbf{y}^{t},\mathbf{z}^{t}\}$ is always bounded for all $t\geq 0$.

###### Lemma 5.5 .

(Proof in Appendix [D.3](#A4.SS3)) Let $t\geq 0$. There exists universal constants $\{\overline{\rm{x}},\overline{\rm{y}},\overline{\rm{z}}\}$ such that $\|\mathbf{x}^{t}\|\leq\overline{\rm{x}}$, $\|\mathbf{z}^{t}\|\leq\overline{\rm{z}}$, and $\|\mathbf{y}^{t}\|\leq\overline{\rm{y}}$.

Fifth, the subsequent lemma establishes bounds for the term $\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t},\mathbf{z}^{t},\beta^{t})$.

###### Lemma 5.6 .

(Proof in Appendix [D.4](#A4.SS4)) For all $t\geq 1$, we have: $\underline{\rm{F}}\underline{\rm{d}}-\underline{\rm{v}}/\beta^{t}\leq\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})\leq\overline{\rm{F}}\overline{\rm{d}}+\overline{\rm{v}}/\beta^{t}$, where $\underline{\rm{v}}\triangleq 8\overline{\rm{z}}^{2}+\tfrac{1}{2}\chi\overline{\rm{z}}^{2}$ and $\overline{\rm{v}}\triangleq 24\overline{\rm{z}}^{2}$.

Given Lemma [5.6](#S5.Thmtheorem6), we make the following additional assumption.

###### Assumption 5.7 .

Assume $\Delta\triangleq\beta^{0}-\underline{\rm{v}}/(\underline{\rm{F}}\underline{\rm{d}})>0$.

###### Remark 5.8 .

(i) By Assumption [5.7](#S5.Thmtheorem7), we have $\beta^{t}\geq\beta^{0}>\underline{\rm{v}}/(\underline{\rm{F}}\underline{\rm{d}})$, ensuring $\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})>0$ and $\lambda^{t}>0$ for both FADMM-D and FADMM-Q for all $t\geq 1$. These inequalities are crucial to our analysis (see Inequalities ([31](#A5.E31)), ([38](#A5.E38))). (ii) Assumption [5.7](#S5.Thmtheorem7) is automatically satisfied when $t$ is sufficiently large due to increasing penalty update rules. In practice, $\beta^{0}=1$ can be used.

Finally, we demonstrate some critical properties for the parameters $\{\beta^{t},\lambda^{t},\alpha^{t},\ell(\beta^{t})\}$.

###### Lemma 5.9 .

(Proof in Appendix [D.5](#A4.SS5)) Let $t\geq 1$. For both FADMM-D and FADMM-Q, we have: (a) $\beta^{t}\leq\beta^{t+1}\leq(1+\xi)\beta^{t}$. (b) There exist constants $\{\overline{\lambda},\underline{\lambda}\}$ such that $0<\underline{\lambda}\leq\lambda^{t}\leq\overline{\lambda}$, and constants $\{\underline{\alpha},\overline{\alpha}\}$ such that $0<\underline{\alpha}\leq\alpha^{t}\leq\overline{\alpha}$. (c) There exist positive constants $\{\underline{\ell},\overline{\ell}\}$ such that $\beta^{t}\underline{\ell}\leq\ell(\beta^{t})\leq\beta^{t}\overline{\ell}$.

###### Assumption 5.1 .

###### Remark 5.2 .

###### Lemma 5.3 .

###### Lemma 5.4 .

###### Lemma 5.5 .

###### Lemma 5.6 .

###### Assumption 5.7 .

###### Remark 5.8 .

###### Lemma 5.9 .

### 5.2 Analysis for FADMM-D

This subsection provides the convergence analysis of FADMM-D.

We define $\varepsilon_{x}\triangleq{\underline{\ell}(\theta-1)}/{(2\overline{\rm{d}})}>0$, $\varepsilon_{y}\triangleq\{1-{4(1+\xi)}/\chi^{2}\}/(2\overline{\rm{d}})>0$, and $\varepsilon_{z}\triangleq\xi/(2\overline{\rm{d}})>0$. We define $\mathbb{L}^{t}\triangleq\mathcal{L}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$, $\mathbb{T}^{t}=12(1+\xi)C_{h}^{2}/(\beta^{0}\underline{\rm{d}}t)$, and $\mathbb{U}^{t}\triangleq C_{h}^{2}\mu^{t}/(2\underline{\rm{d}})$.

We first present two useful lemmas regarding the decrease of the variables $\{\mathbf{x}\}$ and $\{\mathbf{y},\mathbf{z},\beta,\mu\}$.

###### Lemma 5.10 .

(Proof in Section [E.1](#A5.SS1), Decrease on the Function $\mathcal{L}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)$ w.r.t. $\mathbf{x}$) For all $t\geq 1$, we have: $\varepsilon_{x}\beta^{t}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}+\mathcal{L}(\mathbf{x}^{t+1},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})\leq\mathcal{L}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$.

###### Lemma 5.11 .

(Proof in Section [E.2](#A5.SS2), Decrease on the Function $\mathcal{L}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)$ w.r.t. $\{\mathbf{y},\mathbf{z},\beta,\mu\}$) For all $t\geq 1$, we have: $\varepsilon_{y}\beta^{t}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}+\varepsilon_{z}\beta^{t}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|_{2}^{2}+\mathcal{L}(\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t+1};\beta^{t+1},\mu^{t+1})-\mathcal{L}(\mathbf{x}^{t+1},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})\leq\mathbb{U}^{t}+\mathbb{T}^{t}-\mathbb{U}^{t+1}-\mathbb{T}^{t+1}$.

The following lemma demonstrates a decrease property on a potential function.

###### Lemma 5.12 .

(Proof in Section [E.3](#A5.SS3), Decrease on a Potential Function) We let $t\geq 1$. We define $\mathcal{E}^{t}\triangleq\beta^{t}\{\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}+\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}+\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|_{2}^{2}\}$. We define the potential function as $\mathbb{P}^{t}\triangleq\mathbb{L}^{t}+\mathbb{T}^{t}+\mathbb{U}^{t}$. We have: (a) There exists a univeral positive constant $\underline{\mathbb{P}}$ such that $\mathbb{P}^{t}\geq\underline{\mathbb{P}}$. (b) It holds that $\min(\varepsilon_{x},\varepsilon_{y},\varepsilon_{z})\mathcal{E}^{t}\leq\mathbb{P}^{t}-\mathbb{P}^{t+1}$.

The following theorem establishes the global convergence of FADMM-D.

###### Theorem 5.13 .

(Proof in Section [E.4](#A5.SS4), Global Convergence) We let $t\geq 1$. We define $\mathcal{E}_{+}^{t}\triangleq\beta^{t}\{\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|+\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|+\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|\}$. We have: $\tfrac{1}{T}\sum_{t=1}^{T}\mathcal{E}_{+}^{t}\leq\mathcal{O}(T^{(p-1)/2})$. In other words, there exists an index $\bar{t}$ with $1\leq\bar{t}\leq T$ such that $\mathcal{E}_{+}^{\bar{t}}\leq\mathcal{O}(T^{(p-1)/2})$.

###### Remark 5.14 .

(i) With the choice $p\in(0,1)$, Theorem ([5.13](#S5.Thmtheorem13)) implies that $\mathcal{E}_{+}^{t}$ converges to 0 in the ergodic sense. (ii) The convergence $\mathcal{E}_{+}^{t}\rightarrow 0$ is significantly stronger than the convergence $\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|+\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|+\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|\rightarrow 0$ as $\{\beta^{t}\}_{t=1}^{\infty}$ is increasing.

###### Lemma 5.10 .

###### Lemma 5.11 .

###### Lemma 5.12 .

###### Theorem 5.13 .

###### Remark 5.14 .

### 5.3 Analysis for FADMM-Q

This subsection presents the convergence analysis of FADMM-Q.

We define $\varepsilon_{x}\triangleq\tfrac{1}{2}\underline{\alpha}^{2}\underline{\ell}(\theta-1)>0$, $\varepsilon_{y}\triangleq\tfrac{1}{2}\underline{\alpha}^{2}\{1-4(1+\xi)/(\chi^{2})\}$, and $\varepsilon_{z}\triangleq\tfrac{1}{2}\xi\underline{\alpha}^{2}>0$. We define $\mathbb{K}^{t}\triangleq\mathcal{K}(\alpha^{t},\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$, and $\mathbb{T}^{t}=12\overline{\alpha}^{2}(1+\xi)C_{h}^{2}/(\beta^{0}t)$, and $\mathbb{U}^{t}\triangleq\tfrac{1}{2}\overline{\alpha}^{2}C_{h}^{2}\mu^{t}$.

The following two lemmas establish the decrease of the variables $\{\lambda,\mathbf{x}\}$ and $\{\mathbf{y},\mathbf{z},\beta,\mu\}$.

###### Lemma 5.15 .

(Proof in Section [E.5](#A5.SS5), Decrease on the Function $\mathcal{K}(\lambda,\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)$ w.r.t. $\lambda$ and $\mathbf{x}$) For all $t\geq 1$, we have: $\mathcal{K}(\lambda^{t+1},\mathbf{x}^{t+1},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})+\varepsilon_{x}\beta^{t}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}\leq\mathcal{K}(\lambda^{t},\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$.

###### Lemma 5.16 .

(Proof in Section [E.6](#A5.SS6), Decrease on the Function $\mathcal{K}(\lambda,\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)$ w.r.t. $\{\mathbf{y},\mathbf{z},\beta,\mu\}$) For all $t\geq 1$, we have: $\varepsilon_{y}\beta^{t}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}+\varepsilon_{z}\beta^{t}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|_{2}^{2}+\mathcal{K}(\lambda^{t+1},\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t+1};\beta^{t+1},\mu^{t+1})-\mathcal{K}(\lambda^{t+1},\mathbf{x}^{t+1},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})\leq\mathbb{U}^{t}+\mathbb{T}^{t}-\mathbb{U}^{t+1}-\mathbb{T}^{t+1}$.

The following lemma shows a decrease property on a potential function.

###### Lemma 5.17 .

(Proof in Section [E.7](#A5.SS7), Decrease on a Potential Function) We let $t\geq 1$. We define $\mathcal{E}^{t}\triangleq\beta^{t}\{\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}+\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}+\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|_{2}^{2}\}$. We define the potential function as $\mathbb{P}^{t}\triangleq\mathbb{K}^{t}+\mathbb{T}^{t}+\mathbb{U}^{t}$. We have: (a) There exists a univeral positive constant $\underline{\mathbb{P}}$ such that $\mathbb{P}^{t}\geq\underline{\mathbb{P}}$. (b) It holds that $\min(\varepsilon_{x},\varepsilon_{y},\varepsilon_{z})\mathcal{E}^{t}\leq\mathbb{P}^{t}-\mathbb{P}^{t+1}$.

The following theorem establishes the global convergence of FADMM-Q.

###### Theorem 5.18 .

(Proof in Section [E.8](#A5.SS8), Global Convergence) We let $t\geq 1$. We define $\mathcal{E}_{+}^{t}\triangleq\beta^{t}\{\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|+\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|+\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|\}$. We have: $\tfrac{1}{T}\sum_{t=1}^{T}\mathcal{E}_{+}^{t}\leq\mathcal{O}(T^{(p-1)/2})$. In other words, there exists an index $\bar{t}$ with $1\leq\bar{t}\leq T$ such that $\mathcal{E}_{+}^{\bar{t}}\leq\mathcal{O}(T^{(p-1)/2})$.

###### Remark 5.19 .

Theorem [5.18](#S5.Thmtheorem18) is analogous to Theorem [5.13](#S5.Thmtheorem13), with $\mathcal{E}_{+}^{\bar{t}}$ converging to 0 in the ergodic sense.

###### Lemma 5.15 .

###### Lemma 5.16 .

###### Lemma 5.17 .

###### Theorem 5.18 .

###### Remark 5.19 .

## 6 Iteration Complexity

This section examines the iteration complexity of FADMM for converging to critical points.

First, we introduce the notion of approximate critical points for the problem ([1](#S1.E1)), which will play an important role in our analysis.

###### Definition 6.1 .

($\epsilon$-Critical Point) A solution $(\bar{\mathbf{x}}^{+},\bar{\mathbf{x}},\bar{\mathbf{y}}^{+},\bar{\mathbf{y}},\bar{\mathbf{z}}^{+},\bar{\mathbf{z}})$ is a critical point of Problem ([1](#S1.E1)) if: $\operatorname{Crit}(\bar{\mathbf{x}}^{+},\bar{\mathbf{x}},\bar{\mathbf{y}}^{+},\bar{\mathbf{y}},\bar{\mathbf{z}}^{+},\bar{\mathbf{z}})\leq\epsilon$, where $\operatorname{Crit}(\mathbf{x}^{+},\mathbf{x},\mathbf{y}^{+},\mathbf{y},\mathbf{z}^{+},\mathbf{z})\triangleq\|\mathbf{x}^{+}-\mathbf{x}\|+\|\mathbf{y}^{+}-\mathbf{y}\|+\|\mathbf{z}^{+}-\mathbf{z}\|+\|\mathbf{A}\mathbf{x}^{+}-\mathbf{y}^{+}\|+\|\partial h(\mathbf{y}^{+})-\mathbf{z}^{+}\|+\|\partial\delta(\mathbf{x}^{+})+\nabla f(\mathbf{x}^{+})-\partial g(\mathbf{x})+\mathbf{A}^{\mathsf{T}}\mathbf{z}^{+}-\varphi(\mathbf{x},\mathbf{y})\partial d(\mathbf{x})\|$, and $\varphi(\mathbf{x},\mathbf{y})=\{f(\mathbf{x})+\delta(\mathbf{x})-g(\mathbf{x})+h(\mathbf{y})\}/d(\mathbf{x})$.

###### Remark 6.2 .

(a) If $\epsilon=0$, Definition [6.1](#S6.Thmtheorem1) simplifies to the (exact) critical point as described in Definition [3.6](#S3.Thmtheorem6). (b) The study in Boţ et al. () introduces a notation of approximate limiting subdifferential to define the $\epsilon$-critical point, whereas we simply employ consecutive iterations for its definition.

Finally, we establish the iteration complexity of FADMM as follows.

###### Theorem 6.3 .

(Proof in Section [F.1](#A6.SS1), Iteration Complexity for Both FADMM-D and FADMM-Q) We define $\mathcal{W}^{t}\triangleq\{\mathbf{x}^{t+1},\mathbf{x}^{t},\breve{\mathbf{y}}^{t+1},\mathbf{y}^{t},\mathbf{z}^{t+1},\mathbf{z}^{t}\}$. Let the sequence $\{\mathcal{W}^{t}\}_{t=0}^{T}$ be generated by FADMM-D or FADMM-Q. If $p\in(0,1)$, we have: $\operatorname{Crit}(\mathcal{W}^{t})\leq\mathcal{O}(T^{-p})+\mathcal{O}(T^{(p-1)/2})$. In particular, with the choice $p=1/3$, we have $\operatorname{Crit}(\mathcal{W}^{t})\leq\mathcal{O}(T^{-1/3})$. In other words, there exists $1\leq\bar{t}\leq T$ such that: $\operatorname{Crit}(\mathcal{W}^{t})\leq\epsilon$, provided that $T\geq\mathcal{O}(\tfrac{1}{\epsilon^{3}})$.

###### Remark 6.4 .

(i) To our knowledge, Theorem [6.3](#S6.Thmtheorem3) is the first complexity result for ADMM applied to this class of fractional programs, and it matches the iteration bound of smoothing proximal gradient methods Beck & Rosset (); Böhm & Wright (). (ii) The point $\{\mathbf{x}^{t+1},\mathbf{x}^{t},\breve{\mathbf{y}}^{t+1},\mathbf{y}^{t},\mathbf{z}^{t+1},\mathbf{z}^{t}\}$ rather than the point $\{\mathbf{x}^{t+1},\mathbf{x}^{t},\mathbf{y}^{t+1},\mathbf{y}^{t},\mathbf{z}^{t+1},\mathbf{z}^{t}\}$ serves as an approximate critical point of Problem ([1](#alg1)) in Theorem [6.3](#S6.Thmtheorem3).

###### Definition 6.1 .

###### Remark 6.2 .

###### Theorem 6.3 .

###### Remark 6.4 .

## 7 Experiments

This section evaluates the effectiveness of FADMM-D and FADMM-Q on sparse FDA. Additioanl experiments on robust Sharpe ratio minimization, and robust sparse recovery, please refer to Appendix Section [H](#A8).

$\blacktriangleright$ Compared Methods. We compare FADMM-D and FADMM-Q with two state-of-the-art general-purpose algorithms that solve Problem ([1](#S1.E1)) (i) the Subgradient Projection Method (SPM) Li et al. (), (ii) the Smoothing Proximal Gradient Method (SPGM) Beck & Rosset (); Yuan (); Bian & Chen (); Böhm & Wright (). Notably, when $\mathbf{z}^{t}=\mathbf{0}$ and $\mu^{t}=0$ for all $t$ in Algorithm [1](#alg1), FADMM-D and FADMM-Q reduce to two SPGM variants, SPGM-D and SPGM-Q.

$\blacktriangleright$ Experimental Settings. For both SPGM and FADMM, we consider the default parameter settings $(\xi,\theta,p,\chi)=(1,1.01,1/3,2\sqrt{1+\xi}+10^{-5})$. For SPM, we use the default diminishing step size $\eta^{t}=1/\beta^{t}$, where $\beta^{t}$ is the same penalty parameter as in SPGM and FADMM. For all algorithm, we initialize $(\mathbf{x}^{0},\mathbf{y}^{0},\mathbf{z}^{0})$ using the standard Gaussian distribution. All methods are implemented in MATLAB on an Intel 2.6 GHz CPU with 64 GB RAM. We incorporate a set of 8 datasets into our experiments, comprising both randomly generated and publicly available real-world data. Appendix Section D describes how to generate the data used in the experiments. We compare objective values for all methods after running $t$ seconds with $t$ = 20. We provide our code in the supplemental material.

$\blacktriangleright$ Experimental Results on Sparse FDA. We consider solving Problem ([2](#S1.E2)) using the following parameters $r=20$, $k=0.1\times n\times r$, and $\rho\in\{10,100,1000\}$. For all methods, we set $\beta^{0}=100\rho$. The experimental results depicted in Figure [1](#S7.F1) offer the following insights: (i) SGM tends to be less efficient in comparison to other methods. This is primarily because, in the case of a sparse solution, the subdifferential set of the objective function is large and provides a poor approximation of the (negative) descent direction. (ii) SPGM-D and SPGM-Q, utilizing a variable smoothing strategy, generally demonstrates better performance than SGM. (iii) The proposed FADMM-D and FADMM-Q generally exhibit similar performance, both achieving the lowest objective function values among all the methods examined. This supports the widely accepted view that primal-dual methods are generally more robust and faster than primal-only methods.

Figure: (a) madelon-2000-500
Refer to caption: /html/2411.07496/assets/x1.png

Figure: (a) madelon-2000-500
Refer to caption: /html/2411.07496/assets/x9.png

Figure: (a) madelon-2000-500
Refer to caption: /html/2411.07496/assets/x17.png

## 8 Conclusions

In this paper, we introduce FADMM, the first ADMM algorithm designed to solve general structured fractional minimization problems. Our approach integrates Nesterov’s smoothing technique into the algorithm’s updates to guarantee convergence. We present two specific variants of FADMM: one based on Dinkelbach’s parametric method (FADMM-D) and the other on the quadratic transform method (FADMM-Q). Additionally, we establish the iteration complexity of FADMM for convergence to approximate critical points. Finally, we validate the effectiveness of our methods through experimental results.

## Appendix A Notations, Technical Preliminaries, and Relevant Lemmas

### A.1 Notations

In this paper, lowercase boldface letters signify vectors, while uppercase letters denote real-valued matrices. The following notations are utilized throughout this paper.

- •
$[n]$: $\{1,2,...,n\}$
- •
$\|\mathbf{x}\|$: Euclidean norm: $\|\mathbf{x}\|=\|\mathbf{x}\|_{2}=\sqrt{\langle\mathbf{x},\mathbf{x}\rangle}$
- •
$\mathbf{X}^{\mathsf{T}}$ : the transpose of the matrix $\mathbf{X}$
- •
$\operatorname{vec}(\mathbf{X})$ : the vector formed by stacking the column vectors of $\mathbf{X}$ with $\operatorname{vec}(\mathbf{X})\in\mathbb{R}^{nr\times 1}$
- •
$\operatorname{mat}(\mathbf{x})$ : convert $\mathbf{x}\in\mathbb{R}^{nr\times 1}$ into a matrix with $\operatorname{mat}(\operatorname{vec}(\mathbf{X}))=\mathbf{X}$ with $\operatorname{mat}(\mathbf{x})\in\mathbb{R}^{n\times r}$
- •
$\mathbf{0}_{n,r}$ : a zero matrix of size $n\times r$; the subscript is omitted sometimes
- •
$\mathbf{I}_{r}$: identity matrix with $\mathbf{I}_{r}\in\mathbb{R}^{r\times r}$
- •
$\mathbf{X}\succeq\mathbf{0}\,(\text{or}\,\succ\mathbf{0})$ : matrix $\mathbf{X}$ is symmetric positive semidefinite (or definite)
- •
$\|\mathbf{X}\|_{\mathsf{F}}$ : Frobenius norm: $(\sum_{ij}{\mathbf{X}_{ij}^{2}})^{1/2}$
- •
$\partial f(\mathbf{x})$ : limiting subdifferential of $f(\mathbf{x})$ at $\mathbf{x}$
- •
$\iota_{\Omega}(\mathbf{x})$ : the indicator function of a set $\Omega$ with $\iota_{\Omega}(\mathbf{x})=0$ if $\mathbf{\mathbf{x}}\in\Omega$ and otherwise $+\infty$
- •
$\operatorname{tr}(\mathbf{A})$ : Sum of the elements on the main diagonal $\mathbf{A}$ with $\operatorname{tr}(\mathbf{A})=\sum_{i}\mathbf{A}_{i,i}$
- •
$\langle\mathbf{X},\mathbf{Y}\rangle$ : Euclidean inner product, i.e., $\langle\mathbf{X},\mathbf{Y}\rangle=\sum_{ij}{\mathbf{X}_{ij}\mathbf{Y}_{ij}}$
- •
$\|\mathbf{X}\|$ : Operator/Spectral norm: the largest singular value of $\mathbf{X}$
- •
$\text{dist}(\Xi,\Xi^{\prime})$ : the distance between two sets with $\text{dist}(\Xi,\Xi^{\prime})\triangleq\inf_{\mathbf{x}\in\Xi,\mathbf{x}^{\prime}\in\Xi^{\prime}}\|\mathbf{x}-\mathbf{x}^{\prime}\|$
- •
$\|\partial F(\mathbf{x})\|$: $\|\partial F(\mathbf{x})\|=\inf_{\mathbf{z}\in\partial F(\mathbf{x})}\|\mathbf{z}\|_{\mathsf{F}}={\rm{dist}}(\mathbf{0},\partial F(\mathbf{x}))$.
- •
$\|\mathbf{X}\|_{[k]}$: $\ell_{1}$ norm of the $k$ largest (in magnitude) elements of the matrix $\mathbf{X}$
- •
$\mathbf{x}_{i}$: the $i$-th element of vector $\mathbf{x}$
- •
$\mathbf{X}_{i,j}$ or $\mathbf{X}_{ij}$ : the ($i^{\text{th}}$, $j^{\text{th}}$) element of matrix $\mathbf{X}$
- •
$\mathcal{P}_{\Omega}(\mathbf{X}^{\prime})$ : Orthogonal projection of $\mathbf{X}^{\prime}$ with $\mathcal{P}_{\Omega}(\mathbf{X}^{\prime})=\arg\min_{\mathbf{X}\in\Omega}\|\mathbf{X}^{\prime}-\mathbf{X}\|_{\mathsf{F}}^{2}$

### A.2 Technical Preliminaries on Nonsmooth Nonconvex Optimization

We present various techniques in convex analysis, nonsmooth analysis, and nonconvex analysis Mordukhovich et al. (); Mordukhovich (); Rockafellar & Wets. (); Bertsekas (), encompassing conjugate functions, weakly convex functions, the Fréchet subdifferential, limiting subdifferential, and rules for sum and quotient in the Fréchet subdifferential context.

For any extended real-valued (not necessarily convex) function $f:{\mathbb{R}}^{n}\rightarrow(-\infty,+\infty]$, we denote by $\operatorname{dom}(f):=\{\mathbf{x}\in\mathbb{R}^{n}:f(\mathbf{x})<+\infty\}$ its effective domain. The function $f(\mathbf{x})$ is proper if $\operatorname{dom}(f)\neq\emptyset$. The function $f(\mathbf{x})$ is lower-semicontinuous at some point $\dot{\mathbf{x}}\in\mathbb{R}^{n}$ if $\lim\inf_{\mathbf{x}\rightarrow\dot{\mathbf{x}}}f(\mathbf{x})\geq f(\dot{\mathbf{x}})$.

$\bullet$ Conjugate Functions. For a proper, convex, lower semicontinuous function $h(\mathbf{y}):\mathbb{R}^{m}\mapsto\mathbb{R}$, we denote the (Fenchel) conjugate function of $h(\mathbf{y})$ as $h^{*}(\mathbf{y})\triangleq\sup_{\mathbf{v}\in\operatorname{dom}(h)}\left\{\mathbf{y}^{\mathsf{T}}\mathbf{v}-h(\mathbf{v})\right\}$, and it follows that $h^{**}(\mathbf{y})=h(\mathbf{y})=\sup_{\mathbf{v}\in\operatorname{dom}(h^{*})}\left\{\mathbf{y}^{\mathsf{T}}\mathbf{v}-h^{*}(\mathbf{v})\right\}$, where $h^{**}(\mathbf{y})$ is called the biconjugate function. For any $\mu>0$, we have that $(\mu h)^{*}(\mathbf{y})=\sup_{\mathbf{x}\in\operatorname{dom}(h)}\left\{\langle\mathbf{y},\mathbf{x}\rangle-\mu h(\mathbf{x})\right\}=\mu h^{*}(\tfrac{\mathbf{y}}{\mu})$. For any $\mathbf{x},\mathbf{y}\in\mathbb{R}^{n}$, the following statements are equivalent (see Rockafellar & Wets. (), Proposition 11.3): $\langle\mathbf{x},\mathbf{y}\rangle=h(\mathbf{x})+h^{*}(\mathbf{y})$ $\Leftrightarrow$ $\mathbf{y}\in\partial h(\mathbf{x})$ $\Leftrightarrow$ $\mathbf{x}\in\partial h^{*}(\mathbf{y})$. The conjugate of the support function of a closed convex set $\Omega$ is its indicator function, i.e., $h(\mathbf{y})=\sup_{\mathbf{v}\in\Omega}\,\langle\mathbf{v},\mathbf{y}\rangle$, and $h^{*}(\mathbf{v})=\iota_{\Omega}(\mathbf{v})$. Typical nonsmooth functions for $h(\mathbf{y})$ include $\{\|\mathbf{y}\|_{1},\|\max(0,\mathbf{y})\|_{1},\|\mathbf{y}\|_{\infty}\}$, with their respective conjugate functions $h^{*}(\mathbf{y})$ being $\{\iota_{[-1,1]^{m}}(\mathbf{y}),\,\iota_{[0,1]^{m}}(\mathbf{y}),\,\iota_{\|\mathbf{y}\|_{1}\leq 1}(\mathbf{y})\}$.

$\bullet$ Weakly Convex Functions. The function $d(\mathbf{x})$ is weakly convex if a constant $W_{d}\geq 0$ exists, making $d(\mathbf{x})+\tfrac{W_{d}}{2}\|\mathbf{x}\|_{2}^{2}$ convex, with the smallest such $W_{d}$ known as the modulus of weak convexity. Weakly convex functions constitute a diverse class of functions which covers convex functions, differentiable functions whose gradient is Lipschitz continuous, as well as compositions of convex, Lipschitz-continuous functions with $C^{1}$-smooth mappings that have Lipschitz continuous Jacobians Drusvyatskiy & Paquette ().

$\bullet$ Fréchet Subdifferential and Limiting (Fréchet) Subdifferential. The Fréchet subdifferential of $F$ at $\ddot{\mathbf{x}}\in\text{dom}(F)$, denoted as $\widehat{\partial}F(\ddot{\mathbf{x}})$, is defined as

$$ $\widehat{\partial}{F}(\ddot{\mathbf{x}})\triangleq\left\{\mathbf{v}\in\mathbb{R}^{n}:\lim_{\mathbf{x}\rightarrow\ddot{\mathbf{x}}}\inf_{\mathbf{x}\neq\ddot{\mathbf{x}}}\frac{{F}(\mathbf{x})-{F}(\ddot{\mathbf{x}})-\langle\mathbf{v},\mathbf{x}-\ddot{\mathbf{x}}\rangle}{\|\mathbf{x}-\ddot{\mathbf{x}}\|}\geq 0\right\}.$ $$

The limiting subdifferential of ${F}(\mathbf{x})$ at $\dot{\mathbf{x}}\in\text{dom}({F})$, denoted as $\partial F(\dot{\mathbf{x}})$, is defined as

$$ $\partial{F}(\dot{\mathbf{x}})\triangleq\left\{\mathbf{v}\in\mathbb{R}^{n}:\exists\mathbf{x}^{k}\rightarrow\dot{\mathbf{x}},{F}(\mathbf{x}^{k})\rightarrow{F}(\dot{\mathbf{x}}),\mathbf{v}^{k}\in\widehat{\partial}{F}(\mathbf{x}^{k})\rightarrow\mathbf{v},\forall k\right\}.$ $$

It is straightforward to verify that $\widehat{\partial}{F}(\mathbf{x})\subseteq\partial{F}(\mathbf{x})$, $\widehat{\partial}(\alpha F)(x)=\alpha\widehat{\partial}F(x)$ and $\partial(\alpha F)(x)=\alpha\partial F(x)$ hold for any $x\in\operatorname{dom}(F)$ and $\alpha>0$. Additionally, if $F(\cdot)$ is differentiable at $\mathbf{x}$, then $\widehat{\partial}{F}(\mathbf{x})=\partial{F}(\mathbf{x})=\{\nabla F(\mathbf{x})\}$ with $\nabla F(\mathbf{x})$ being the gradient of $F(\cdot)$ at $\mathbf{x}$; when $F(\cdot)$ is convex, $\widehat{\partial}{F}(\mathbf{x})$ and $\partial{F}(\mathbf{x})$ reduce to the classical subdifferential for convex functions, i.e., $\widehat{\partial}{F}(\mathbf{x})=\partial{F}(\mathbf{x})=\{\mathbf{v}\in\mathbf{R}^{n}:F(\mathbf{z})-F(\mathbf{x})-\langle\mathbf{v},\mathbf{z}-\mathbf{x}\rangle\geq 0,\forall\mathbf{z}\in\mathbb{R}^{n}\}$.

$\bullet$ Sum and Quotient Rules for the Fréchet Subdifferential. First, we examine sum rules for the Fréchet subdifferential. Let $\varphi_{1},\,\varphi_{2}:\mathbb{R}^{n}\to(-\infty,+\infty]$ be proper, closed functions, and let $\mathbf{x}\in\operatorname{dom}(\varphi_{1})\cap\operatorname{dom}(\varphi_{2})$. Then, $\widehat{\partial}\varphi_{1}(\mathbf{x})+\widehat{\partial}\varphi_{2}(\mathbf{x})\subseteq\widehat{\partial}(\varphi_{1}+\varphi_{2})(\mathbf{x})$, where equality holds if $\varphi_{1}$ or $\varphi_{2}$ is differentiable at $x$ (See Corollary 10.9 in Rockafellar & Wets. ()). Moreover, $\partial(\varphi_{1}+\varphi_{2})(\mathbf{x})\subseteq\partial\varphi_{1}(\mathbf{x})+\partial\varphi_{2}(\mathbf{x})$ holds when $\varphi_{1}$ or $\varphi_{2}$ is locally Lipschitz continuous at $\mathbf{x}$, and it holds with equality when $\varphi_{1}$ or $\varphi_{2}$ is continuously differentiable at $\mathbf{x}$ (See Exercise 10.10 in Rockafellar & Wets. ()).

We review the quotient rules for the Fréchet subdifferential. The concept of calmness Rockafellar & Wets. () plays an important role in our analysis. A proper function $g:\mathbb{R}^{n}\rightarrow(-\infty,+\infty]$ is said to be calm at $\mathbf{x}\in\operatorname{dom}(g)$ if there exist $\varepsilon>0$ and $\kappa>0$ such that $|g(\mathbf{x})-g(\mathbf{x}^{\prime})|\leq\kappa\|\mathbf{x}-\mathbf{x}^{\prime}\|$ for all $\mathbf{x}^{\prime}\in\mathcal{B}(\mathbf{x},\varepsilon)\triangleq\{\mathbf{z}\in\mathbb{R}^{n}:\|\mathbf{z}-\mathbf{x}\|<\varepsilon\}$. Many convex functions, including Lipschitz continuous functions, satisfy the calmness condition.

We define $\varphi:\mathbb{R}^{n}\mapsto(-\infty,+\infty]$ at $\mathbf{x}\in\mathbb{R}^{n}$ as:

$$ $\varphi(\mathbf{x}):=\begin{cases}\frac{\varphi_{1}(\mathbf{x})}{\varphi_{2}(\mathbf{x})},&\text{ if $\mathbf{x}\in\operatorname{dom}(\varphi_{1})$ and $\varphi_{2}(\mathbf{x})\neq 0$,}\\ +\infty,&\text{else.}\end{cases}$ $$

The following lemma concerns the quotient rules for the Fréchet subdifferential.

###### Lemma A.1 .

Li & Zhang (); Li et al. (); Boţ et al. (). Let $\varphi_{1}:\mathbb{R}^{n}\rightarrow(-\infty,+\infty]$ and $\varphi_{2}:\mathbb{R}^{n}\rightarrow\mathbb{\mathbb{R}}$ be two functions which are finite at $\mathbf{x}$ with $\varphi_{2}(\mathbf{x})>0$. We denote $\alpha_{1}:=\varphi_{1}(\mathbf{x})$ and $\alpha_{2}:=\varphi_{2}(\mathbf{x})$. Suppose that $\varphi_{1}$ is closed and continuous at $\mathbf{x}$ relative to
$\operatorname{dom}(\varphi_{1})$, that $\varphi_{2}$ is calm at $\mathbf{x}$. We have the following results:

- (a)
It holds that: $\widehat{\partial}\varphi({\mathbf{x}})=\tfrac{1}{\alpha_{2}^{2}}\{{\widehat{\partial}}(\alpha_{2}\varphi_{1}-\alpha_{1}\varphi_{2})({\mathbf{x}})\}$.
- (b)
If $\varphi_{2}({\mathbf{x}})$ is differentiable at $\mathbf{x}$, then $\widehat{\partial}\varphi({\mathbf{x}})=\tfrac{1}{\alpha_{2}^{2}}\{\alpha_{2}\widehat{\partial}\varphi_{1}({\mathbf{x}})-\alpha_{1}\nabla\varphi_{2}({\mathbf{x}})\}$.
- (c)
If $\alpha_{1}\geq 0$ and $\varphi_{2}(\mathbf{x})$ is convex, then $\widehat{\partial}\varphi(\mathbf{x})\subseteq\tfrac{1}{\alpha_{2}^{2}}\{\widehat{\partial}(\alpha_{2}\varphi_{1})(\mathbf{x})-\alpha_{1}{\widehat{\partial}}\varphi_{2}(\mathbf{x})\}\subseteq\tfrac{1}{\alpha_{2}}\{\partial(\varphi_{1})(\mathbf{x})-\tfrac{\alpha_{1}}{\alpha_{2}}{\partial}\varphi_{2}(\mathbf{x})\}$.

###### Lemma A.1 .

### A.3 Relevant Lemmas

We present some useful lemmas that will be used subsequently.

###### Lemma A.2 .

(Extended Moreau Decomposition) Assume $h(\mathbf{y})$ is convex. For any $\mu>0$ and $\mathbf{b}\in\mathbb{R}^{m}$, we define $\operatorname{\operatorname{Prox}}(\mathbf{b};h,\mu)\triangleq\arg\min_{\mathbf{y}}h(\mathbf{y})+\frac{1}{2\mu}\|\mathbf{b}-\mathbf{y}\|_{2}^{2}$. It holds that: $\mathbf{b}=\operatorname{\operatorname{Prox}}(\mathbf{b};h,\mu)+\mu\operatorname{\operatorname{Prox}}(\tfrac{\mathbf{b}}{\mu};h^{*},\tfrac{1}{\mu})$.

###### Proof.

The conclusion of this lemma can be found in Nesterov (); Parikh et al. (). For completeness, we present the proof.

We define $\bar{\mathbf{y}}\triangleq\operatorname{\operatorname{Prox}}(\mathbf{b};h,\mu)$. We derive:

$$ $\displaystyle\mathbf{b}-\bar{\mathbf{y}}\in\partial(\mu h)(\bar{\mathbf{y}})$ $\displaystyle\overset{\text{\char 172}}{\Leftrightarrow}$ $\displaystyle\bar{\mathbf{y}}\in\partial((\mu h)^{*})(\mathbf{b}-\bar{\mathbf{y}})$ $\displaystyle\Leftrightarrow$ $\displaystyle\mathbf{b}-(\mathbf{b}-\bar{\mathbf{y}})\in\partial((\mu h)^{*})(\mathbf{b}-\bar{\mathbf{y}})$ $\displaystyle\Leftrightarrow$ $\displaystyle\mathbf{b}-\bar{\mathbf{y}}=\operatorname{\operatorname{Prox}}(\mathbf{b};(\mu h)^{*},1)$ $\displaystyle\overset{\text{\char 173}}{\Leftrightarrow}$ $\displaystyle\mathbf{b}=\operatorname{\operatorname{Prox}}(\mathbf{b};h,\mu)+\mu\operatorname{\operatorname{Prox}}(\tfrac{\mathbf{b}}{\mu};h^{*},\tfrac{1}{\mu}),$ $$

where step ① uses the definition of the conjugate function, and the property of the subdifferential that $\mathbf{v}\in\partial h(\mathbf{y})\Leftrightarrow\mathbf{y}\in\partial h^{*}(\mathbf{v})$; step ② uses the following derivations that: $\arg\min_{\mathbf{y}}(\mu h)^{*}(\mathbf{y})+\tfrac{1}{2}\|\mathbf{y}-\mathbf{b}\|_{2}^{2}=\arg\min_{\mathbf{y}}\mu h^{*}(\mathbf{y}/\mu)+\tfrac{1}{2}\|\mathbf{y}-\mathbf{b}\|_{2}^{2}=\mu\arg\min_{\mathbf{y}^{\prime}}h^{*}(\mathbf{y}^{\prime})+\tfrac{\mu}{2}\|\mathbf{y}^{\prime}-\mathbf{b}/\mu\|_{2}^{2}=\mu\operatorname{\operatorname{Prox}}(\tfrac{\mathbf{b}}{\mu};h^{*},\tfrac{1}{\mu})$.

∎

###### Lemma A.3 .

Let $\beta^{t}\triangleq\beta^{0}(1+\xi t^{p})$ and $\mu^{t}\propto\tfrac{1}{\beta^{t}}$, where $\beta^{0}\geq 0$ and $\xi\in(0,1)$. For any integer $t\geq 1$, we have: $(\tfrac{\mu^{t-1}}{\mu^{t}}-1)^{2}\leq\tfrac{6}{t}-\tfrac{6}{t+1}$.

###### Proof.

We define $h(t)\triangleq t^{p}$, where $p\in(0,1)$.

Given the concavity of $h(t)$, it follows that: $h(y)-h(x)\leq\langle y-x,\nabla h(x)\rangle$. Letting $x=t-1$ and $y=t$, for all $t>1$, we have:

$$ $\displaystyle t^{p}-(t-1)^{p}\leq p(t-1)^{p-1}.$ (8) $$

Part (a). When $t=1$, we have: $(\tfrac{\mu^{t-1}}{\mu^{t}}-1)^{2}-(\tfrac{6}{t}-\tfrac{6}{t+1})=(\tfrac{\beta^{1}}{\beta^{0}}-1)^{2}-3=\xi^{2}-3\leq-2<0$.

Part (b). When $t\geq 2$, we derive:

$$ $\displaystyle\textstyle(\tfrac{\mu^{t-1}}{\mu^{t}}-1)^{2}~{}$ $\displaystyle\overset{\text{\char 172}}{=}~{}\textstyle(\tfrac{\beta^{t}}{\beta^{t-1}}-1)^{2}~{}\overset{\text{\char 173}}{=}~{}\textstyle(\tfrac{1+\xi t^{p}}{1+\xi(t-1)^{p}}-1)^{2}~{}\overset{\text{\char 174}}{\leq}~{}\textstyle(\tfrac{t^{p}}{(t-1)^{p}}-1)^{2}$ $\displaystyle=~{}(\tfrac{t^{p}-(t-1)^{p}}{(t-1)^{p}})^{2}~{}\overset{\text{\char 175}}{\leq}~{}\textstyle((t-1)^{p-1-p})^{2}=\frac{1}{(t-1)^{2}}~{}\overset{\text{\char 176}}{\leq}~{}\textstyle\tfrac{6}{t}-\tfrac{6}{t+1},$ $$

where step ① uses $\mu^{t}\propto\tfrac{1}{\beta^{t}}$; step ② uses $\beta^{t}=\beta^{0}(1+\xi t^{p})$; step ③ uses $1<\tfrac{1+\xi t^{p}}{1+\xi(t-1)^{p}}\leq\tfrac{\xi t^{p}}{\xi(t-1)^{p}}$; step ④ uses Inequality ([8](#A1.E8)) and $p\leq 1$; step ⑤ uses $\frac{1}{(t-1)^{2}}\leq\tfrac{6}{t}-\tfrac{6}{t+1}$ for any integer $t\geq 2$.

∎

###### Lemma A.4 .

For all $t\geq 1$, $p\in(0,1)$. It holds that: $-1\leq(t+1)^{p}-t^{p}-2p(t+1)^{p-1}\leq 0$.

###### Proof.

We assume $t\geq 1$ and $p\in(0,1)$.

First, consider the function $h(t)=t^{p}$. We have $\nabla h(t)=pt^{p-1}$ and $\nabla^{2}h(t)=p(p-1)t^{p-2}<0$. Therefore, $h(t)$ is concave. For all $x>0$ and $y>0$, we have: $h(x)-h(y)\geq\langle x-y,\nabla h(x)\rangle$. Letting $x=t$ and $y=t+1$, we have:

$$ $\displaystyle t^{p}-(t+1)^{p}\geq-pt^{p-1}$ (9) $$

Letting $x=t+1$ and $y=t$, we have:

$$ $\displaystyle(t+1)^{p}-t^{p}\geq p(t+1)^{p-1}$ (10) $$

Second, we shown that $t^{p-1}\leq 2(t+1)^{p-1}$. Given $t\geq 1$, we have: $\frac{t+1}{t}\leq 2$, leading to $(\frac{t+1}{t})^{p-1}\geq 2^{p-1}\geq\frac{1}{2}$. We obtain:

$$ $\displaystyle t^{p-1}\leq 2(t+1)^{p-1}.$ (11) $$

Part (a). We now prove the upper bound. We derive: $(t+1)^{p}-t^{p}-2p(t+1)^{(p-1)}\overset{\text{\char 172}}{\leq}pt^{p-1}-2p(t+1)^{(p-1)}\overset{\text{\char 173}}{\leq}0$, where step ① uses Inequality ([9](#A1.E9)); step ② uses Inequality ([11](#A1.E11)).

Part (b). We now focus on the lower bound. We obtain: $(t+1)^{p}-t^{p}-2p(t+1)^{p-1}\overset{\text{\char 172}}{\geq}p(t+1)^{p-1}-2p(t+1)^{p-1}=-p(t+1)^{p-1}\overset{\text{\char 173}}{\geq}-p\overset{\text{\char 174}}{\geq}-1$, where step ① uses Inequality ([10](#A1.E10)); step ② uses $(t+1)^{p-1}\leq 1$; step ③ uses $p\leq 1$.

∎

###### Lemma A.5 .

For all $t\geq 1$, $p\in(0,1)$. It holds that: $(1-p)T^{1-p}\leq\sum_{t=1}^{T}\tfrac{1}{t^{p}}\leq\tfrac{T^{1-p}}{1-p}$.

###### Proof.

We let $t\geq 1$, $p\in(0,1)$, and $q\in(0,1)$. We define $h(t)\triangleq\tfrac{1}{q}(t+1)^{q}-\tfrac{1}{q}-qt^{q}$.

First, we prove that $h(1)=\tfrac{1}{q}2^{q}-\tfrac{1}{q}-q\geq 0$. We let $f(q)=2^{q}-1-q^{2}$. We have $\nabla f(q)=\ln(2)2^{q}-2q$ and $\nabla^{2}f(q)=\ln(2)^{2}2^{q}-2\leq\ln(2)^{2}2-2<0$. Therefore, $f(q)$ is concave. The global minimum lies in the boundary point. We have $h(1)\geq\frac{1}{q}\min(f(1),f(0))=\frac{1}{q}\min(2^{0}-1-0^{2},2^{1}-1-1^{2})=\frac{0}{q}=0$. Therefore, we have:

$$ $\displaystyle h(1)=\tfrac{1}{q}2^{q}-\tfrac{1}{q}-q\geq 0.$ (12) $$

Second, we prove that $h(t)\geq 0$. We have: $\nabla h(t)=(t+1)^{q-1}-qt^{q-1}\geq t^{q-1}-qt^{q-1}=(1-q)t^{q-1}\geq 0$. Therefore, the function $h(t)$ is increasing. We further obtain:

$$ $\displaystyle h(t)\triangleq\tfrac{1}{q}(t+1)^{q}-\tfrac{1}{q}-qt^{q}\geq h(1)$ $\displaystyle\overset{\text{\char 172}}{\geq}$ $\displaystyle 0,$ (13) $$

where step ① uses Inequality ([12](#A1.E12)).

Third, we define $h(t)=t^{-p}$. Using the integral test for convergence (^1^11[https://en.wikipedia.org/wiki/Integral_test_for_convergence](https://en.wikipedia.org/wiki/Integral_test_for_convergence)), we have:

$$ $\displaystyle\textstyle\int_{1}^{T+1}h(x)dx\leq\sum_{t=1}^{T}h(t)\leq h(1)+\int_{1}^{T}h(x)dx.$ $$

Part (a). We define $g(x)=\frac{1}{1-p}x^{1-p}$. We derive: $\sum_{t=1}^{T}t^{-p}\leq\textstyle g(1)+\int_{1}^{T}x^{-p}dx\overset{\text{\char 172}}{=}\textstyle 1+g(T)-g(1)=1+\tfrac{1}{1-p}(T)^{1-p}-\tfrac{1}{1-p}\overset{\text{\char 173}}{=}\tfrac{T^{(1-p)}-p}{1-p}<\tfrac{T^{(1-p)}}{1-p}$, where step ① uses $\nabla g(x)=x^{-p}$; step ② uses Inequality ([13](#A1.E13)) with $q=1-p$ and $t=T$.

Part (b). We derive: $\sum_{t=1}^{T}t^{-p}\geq\textstyle\sum_{t=1}^{T}\int_{t}^{t+1}x^{-p}dx=\int_{1}^{T+1}x^{-p}dx\overset{\text{\char 172}}{\geq}\textstyle g(T+1)-g(1)=\tfrac{1}{1-p}(T+1)^{1-p}-\tfrac{1}{1-p}\overset{\text{\char 173}}{\geq}(1-p)T^{1-p}$, where step ① uses $\nabla g(x)=x^{-p}$; step ② uses Inequality ([13](#A1.E13)) with $q=1-p$ and $t=T$.

∎

###### Lemma A.2 .

###### Proof.

###### Lemma A.3 .

###### Proof.

###### Lemma A.4 .

###### Proof.

###### Lemma A.5 .

###### Proof.

## Appendix B Additional Motivating Applications

$\bullet$ Robust Sharpe Ratio Maximization (Robust SRM). Recall that the standard SRM, which operates without data uncertainty and is commom in finance, can be formulated as: $\max_{\mathbf{x}\in\Omega}\frac{\mathbf{d}^{\top}\mathbf{x}-r}{\mathbf{x}^{\top}\mathbf{C}\mathbf{x}}$, where $\mathbf{C}\succeq 0$ is the risk covariance matrix, $\mathbf{d}\in\mathbb{R}^{n}$ are the expected returns, $r\in\mathbb{R}$ is the risk-free rate, and $\Omega\triangleq\{\mathbf{x}\,|\,\mathbf{x}\geq\mathbf{0},\mathbf{x}^{\top}\mathbf{1}=1\}$ ensures valid portfolio weights (see Chen et al. (); Boţ et al. ()). In contrast, the robust SRM, designed to handle scenario data uncertainty, is defined by: $\min_{\mathbf{x}\in\Omega}\frac{\max_{i=1}^{m}\{\mathbf{b}_{i}-(\mathbf{D}\mathbf{x})_{i}\}}{\max_{i=1}^{p}\mathbf{x}^{\mathsf{T}}\mathbf{C}_{(i)}\mathbf{x}}$, where each $\mathbf{C}_{(i)}\in\mathbb{R}^{n\times n}\succeq\mathbf{0}$, $\mathbf{b}\in\mathbb{R}^{m}$, and $\mathbf{D}\in\mathbb{R}^{m\times n}$. The corresponding equivalent optimization problem is formulated as:

$$ $\displaystyle\min_{\mathbf{x}\in\mathbb{R}^{n}}\frac{\max(0,\max(\mathbf{b}-\mathbf{D}\mathbf{x}))}{\max_{i=1}^{p}\mathbf{x}^{\mathsf{T}}\mathbf{C}_{(i)}\mathbf{x}},\operatorname{s.t.}\mathbf{x}\in\Omega.$ (14) $$

We use $\max(0,\max(\mathbf{b}-\mathbf{D}\mathbf{x}))$ instead of simply $\max(\mathbf{b}-\mathbf{D}\mathbf{x})$ to explicitly enforce nonnegativity in the numerator for all $\mathbf{x}\in\Omega$. Problem ([14](#A2.E14)) corresponds to Problem ([1](#S1.E1)) with $f(\mathbf{x})=g(\mathbf{x})=0$, $\delta(\mathbf{x})=\iota_{\Omega}(\mathbf{x})$, $\mathbf{A}=-\mathbf{D}$, $h(\mathbf{y})=\max(0,\max(\mathbf{y}+\mathbf{b}))$, and $d(\mathbf{x})=\max_{i=1}^{p}\mathbf{x}^{\mathsf{T}}\mathbf{C}_{(i)}\mathbf{x}$. Notably, both $d(\mathbf{x})$ and $d(\mathbf{x})^{1/2}$ are $W_{d}$-weakly convex with $W_{d}=0$.

$\bullet$ Robust Sparse Recovery. It is a signal processing technique, which can effectively acquire
and reconstruct the signal by finding the solution of the
underdetermined linear system. Given a design matrix $\mathbf{A}\in\mathbb{R}^{m\times n}$ and an observation vector $\mathbf{b}\in\mathbb{R}^{m}$, robust sparse recovery
can be formulated as the following fractional optimization problem
Li & Zhang (); Yang & Zhang (); Yuan ():

$$ $\displaystyle\min_{\mathbf{x}\in\mathbb{R}^{n}}\frac{\rho_{1}\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_{1}+\rho_{2}\|\mathbf{x}\|_{1}}{\|\mathbf{x}\|_{[k]}},\operatorname{s.t.}\mathbf{x}\in\Omega,$ (15) $$

where $\Omega\triangleq\{\mathbf{x}\,|\,\|\mathbf{x}\|_{\infty}\leq\rho_{0}\}$, and $\rho_{0},\rho_{1},\rho_{2}$ are positive constants provided by the users. Problem ([15](#A2.E15)) coincides with Problem ([1](#S1.E1)) with $f(\mathbf{x})=g(\mathbf{x})=0$, $\delta(\mathbf{x})=\iota_{\Omega}(\mathbf{x})+\rho_{2}\|\mathbf{x}\|_{1}$, $h(\mathbf{y})=\|\mathbf{y}-\mathbf{b}\|_{1}$, and $d(\mathbf{x})=\|\mathbf{x}\|_{[k]}$. Importantly, $d(\mathbf{x})$ is $W_{d}$-weakly convex with $W_{d}=0$.

## Appendix C Proofs for Section 3

### C.1 Proof of Lemma 3.9

###### Proof.

For any $\mathbf{y}\in\mathbb{R}^{,}$, we define $h_{\mu}(\mathbf{y})\triangleq\max_{\mathbf{v}}\,\langle\mathbf{y},\mathbf{v}\rangle-h^{*}(\mathbf{v})-\tfrac{\mu}{2}\|\mathbf{v}\|_{2}^{2}$. Since $\mu>0$ and $\tfrac{\mu}{2}\|\mathbf{v}\|_{2}^{2}$ is $\mu$-strongly
convex, the maximization problem has a unique solution and thus the subgradient set is a single set Nesterov (); Devolder et al. (), i.e., $\partial h_{\mu}(\mathbf{y})=\nabla h_{\mu}(\mathbf{y})=\arg\max_{\mathbf{v}}\,\{\langle\mathbf{y},\mathbf{v}\rangle-h^{*}(\mathbf{v})-\tfrac{\mu}{2}\|\mathbf{v}\|_{2}^{2}\}$.

Part (a). We now prove that $h_{\mu}(\mathbf{y})$ is $(1/\mu)$-smooth. For any $\mathbf{y}_{1},\mathbf{y}_{2}\in\mathbb{R}^{m}$, we define $\mathbf{v}_{1}=\arg\max_{\mathbf{v}}\{\langle\mathbf{y}_{1},\mathbf{v}\rangle-h^{*}(\mathbf{v})-\tfrac{\mu}{2}\|\mathbf{v}\|_{2}^{2}\}$, and $\mathbf{v}_{2}=\arg\max_{\mathbf{v}}\{\langle\mathbf{y}_{2},\mathbf{v}\rangle-h^{*}(\mathbf{v})-\tfrac{\mu}{2}\|\mathbf{v}\|_{2}^{2}\}$. We have:

$$ $\displaystyle\|\mathbf{y}_{1}-\mathbf{y}_{2}\|\|\mathbf{v}_{1}-\mathbf{v}_{2}\|\overset{\text{\char 172}}{\geq}$ $\displaystyle~{}\langle\mathbf{y}_{1}-\mathbf{y}_{2},\mathbf{v}_{1}-\mathbf{v}_{2}\rangle$ $\displaystyle\overset{\text{\char 173}}{=}$ $\displaystyle~{}\mu\langle\mathbf{v}_{1}-\mathbf{v}_{2},\mathbf{v}_{1}-\mathbf{v}_{2}\rangle+\langle\partial h^{*}(\mathbf{v}_{1})-\partial h^{*}(\mathbf{v}_{2}),\mathbf{v}_{1}-\mathbf{v}_{2}\rangle$ $\displaystyle\overset{\text{\char 174}}{\geq}$ $\displaystyle~{}\mu\|\mathbf{v}_{2}-\mathbf{v}_{1}\|_{2}^{2}+0,$ $$

where step ① uses the Cauchy-Schwarz Inequality; step ② uses the optimality of $\mathbf{v}_{1}$ that $\mathbf{y}_{1}-\partial h^{*}(\mathbf{v}_{1})-\mu\mathbf{v}_{1}=\mathbf{0}$ and the optimality of $\mathbf{v}_{2}$ that $\mathbf{y}_{2}-\partial h^{*}(\mathbf{v}_{2})-\mu\mathbf{v}_{2}=\mathbf{0}$; step ③ uses the monotonicity of subdifferentials for the convex function $h^{*}(\mathbf{v})$. Dividing both sides by $\|\mathbf{v}_{1}-\mathbf{v}_{2}\|$, we have: $\frac{\|\mathbf{v}_{2}-\mathbf{v}_{1}\|}{\|\mathbf{y}_{1}-\mathbf{y}_{2}\|}\leq\tfrac{1}{\mu}$, which implies that the function $h_{\mu}(\mathbf{y})$ is ($1/\mu$)-smooth.

We now prove that the function $h_{\mu}(\mathbf{y})$ is convex. For any $\mathbf{y}_{1},\mathbf{y}_{2}\in\mathbb{R}^{m}$ and $\mu>0$, we define $\mathbf{u}_{1}=\arg\max_{\mathbf{u}}\{\langle\mathbf{y}_{1},\mathbf{u}\rangle-h^{*}(\mathbf{u})-\tfrac{\mu}{2}\|\mathbf{u}\|_{2}^{2}\}$, and $\mathbf{u}_{2}=\arg\max_{\mathbf{u}}\{\langle\mathbf{y}_{2},\mathbf{u}\rangle-h^{*}(\mathbf{u})-\tfrac{\mu}{2}\|\mathbf{u}\|_{2}^{2}\}$. We have:

$$ $\displaystyle h_{\mu}(\mathbf{y}_{1})-h_{\mu}(\mathbf{y}_{2})\overset{\text{\char 172}}{=}$ $\displaystyle~{}h_{\mu}(\mathbf{y}_{1})-\{\langle\mathbf{y}_{2},\mathbf{u}_{2}\rangle-h^{*}(\mathbf{u}_{2})-\tfrac{\mu}{2}\|\mathbf{u}_{2}\|_{2}^{2}\}$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}h_{\mu}(\mathbf{y}_{1})-\{\langle\mathbf{y}_{2},\mathbf{u}_{1}\rangle-h^{*}(\mathbf{u}_{1})-\tfrac{\mu}{2}\|\mathbf{u}_{1}\|_{2}^{2}\}$ $\displaystyle\overset{\text{\char 174}}{=}$ $\displaystyle~{}\{\langle\mathbf{y}_{1},\mathbf{u}_{1}\rangle-h^{*}(\mathbf{u}_{1})-\tfrac{\mu}{2}\|\mathbf{u}_{1}\|_{2}^{2}\}-\{\langle\mathbf{y}_{2},\mathbf{u}_{1}\rangle-h^{*}(\mathbf{u}_{1})-\tfrac{\mu}{2}\|\mathbf{u}_{1}\|_{2}^{2}\}$ $\displaystyle\overset{}{=}$ $\displaystyle~{}\langle\mathbf{u}_{1},\mathbf{y}_{1}-\mathbf{y}_{2}\rangle,$ $$

where step ① uses the definition of $h_{\mu}(\mathbf{y}_{2})$ and $\mathbf{u}_{2}$; step ② uses the optimality of $\mathbf{u}_{2}$; step ③ uses the definition of $h_{\mu}(\mathbf{y}_{1})$.

Part (b). For any $\mathbf{y}\in\mathbb{R}^{m}$ and $\mu>0$, we define $h_{\mu}(\mathbf{y})\triangleq\max_{\mathbf{v}}\,\langle\mathbf{y},\mathbf{v}\rangle-h^{*}(\mathbf{v})-\tfrac{\mu}{2}\|\mathbf{v}\|_{2}^{2}$, $\mathbf{u}_{1}\triangleq\arg\max_{\mathbf{u}}\{\langle\mathbf{y},\mathbf{u}\rangle-h^{*}(\mathbf{u})\}$, and $\mathbf{u}_{2}\triangleq\arg\max_{\mathbf{u}}\{\langle\mathbf{y},\mathbf{u}\rangle-h^{*}(\mathbf{u})-\tfrac{\mu}{2}\|\mathbf{u}\|_{2}^{2}\}$.

b-i). We now prove that $0<h(\mathbf{y})-h_{\mu}(\mathbf{y})$. We have:

$$ $\displaystyle h_{\mu}(\mathbf{y})=$ $\displaystyle~{}\max_{\mathbf{v}}\{\mathbf{v}^{\mathsf{T}}\mathbf{y}-h^{*}(\mathbf{v})-\tfrac{\mu}{2}\|\mathbf{v}\|_{2}^{2}\}$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}\max_{\mathbf{v}}\{\mathbf{v}^{\mathsf{T}}\mathbf{y}-h^{*}(\mathbf{v})\}+\max_{\mathbf{v}}\{-\tfrac{\mu}{2}\|\mathbf{v}\|_{2}^{2}\}$ $\displaystyle\overset{\text{\char 173}}{=}$ $\displaystyle~{}h(\mathbf{y}),$ $$

where step ① uses a general property of the maximum function when applied to the sum of two functions; step ② uses the definition of $h(\mathbf{y})=\max_{\mathbf{v}}\{\mathbf{v}^{\mathsf{T}}\mathbf{y}-h^{*}(\mathbf{v})\}$ and the fact that $\max_{\mathbf{v}}\{-\tfrac{\mu}{2}\|\mathbf{v}\|_{2}^{2}\}=0$.

b-ii). We now prove that $h(\mathbf{y})-h_{\mu}(\mathbf{y})\leq\tfrac{\mu}{2}C_{h}^{2}$. We have:

$$ $\displaystyle h(\mathbf{y})-h_{\mu}(\mathbf{y})\overset{\text{\char 172}}{=}$ $\displaystyle~{}\{\langle\mathbf{y},\mathbf{u}_{1}\rangle-h^{*}(\mathbf{u}_{1})\}-h_{\mu}(\mathbf{y})$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}\{\langle\mathbf{y},\mathbf{u}_{1}\rangle-h^{*}(\mathbf{u}_{1})\}-\{\langle\mathbf{y},\mathbf{u}_{1}\rangle-h^{*}(\mathbf{u}_{1})-\tfrac{\mu}{2}\|\mathbf{u}_{1}\|_{2}^{2}\}$ $\displaystyle\overset{}{=}$ $\displaystyle~{}\tfrac{\mu}{2}\|\mathbf{u}_{2}\|_{2}^{2}=\tfrac{\mu}{2}\|\nabla h_{\mu}(\mathbf{y})\|_{2}^{2}$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}\tfrac{\mu}{2}C_{h}^{2},$ $$

where step ① uses the definition of $h(\mathbf{y})$: $h(\mathbf{y})=\{\langle\mathbf{y},\mathbf{u}_{1}\rangle-h^{*}(\mathbf{u}_{1})\}$; step ② uses the definition of $h_{\mu}(\mathbf{y})$ and the optimality of $\mathbf{u}_{2}$: $h_{\mu}(\mathbf{y})=\{\langle\mathbf{y},\mathbf{u}_{2}\rangle-h^{*}(\mathbf{u}_{2})-\tfrac{\mu}{2}\|\mathbf{u}_{2}\|_{2}^{2}\}\geq\{\langle\mathbf{y},\mathbf{u}_{1}\rangle-h^{*}(\mathbf{u}_{1})-\tfrac{\mu}{2}\|\mathbf{u}_{1}\|_{2}^{2}\}$; step ③ uses Claim (b) of this lemma.

Part (c). We now prove that the function $h_{\mu}(\mathbf{y})$ is $C_{h}$-Lipschitz continuous. For any $\mathbf{y}\in\mathbb{R}^{m}$ and $\mu>0$, we define $h_{\mu}(\mathbf{y})\triangleq\max_{\mathbf{v}}\,\langle\mathbf{y},\mathbf{v}\rangle-h^{*}(\mathbf{v})-\tfrac{\mu}{2}\|\mathbf{v}\|_{2}^{2}$. We have:

$$ $\displaystyle\nabla h_{\mu}(\mathbf{y})\textstyle\overset{\text{\char 172}}{=}$ $\displaystyle~{}\textstyle\arg\max_{\mathbf{v}}\{\langle\mathbf{y},\mathbf{v}\rangle-h^{*}(\mathbf{v})-\tfrac{\mu}{2}\|\mathbf{v}\|_{2}^{2}\}$ $\displaystyle\overset{}{=}$ $\displaystyle~{}\textstyle\arg\min_{\mathbf{v}}\{h^{*}(\mathbf{v})+\tfrac{\mu}{2}\|\mathbf{v}-\mathbf{y}/\mu\|_{2}^{2}\}$ $\displaystyle\overset{\text{\char 173}}{=}$ $\displaystyle~{}\textstyle\operatorname{\operatorname{Prox}}(\tfrac{\mathbf{y}}{\mu};h^{*},1/\mu)$ $\displaystyle\overset{\text{\char 174}}{=}$ $\displaystyle~{}\textstyle\tfrac{1}{\mu}(\mathbf{y}-\operatorname{\operatorname{Prox}}(\mathbf{y};h,\mu))$ (16) $\displaystyle\overset{\text{\char 175}}{\in}$ $\displaystyle~{}\textstyle\partial h(\operatorname{\operatorname{Prox}}(\mathbf{y};h,\mu)),$ (17) $$

where step ① uses the fact that the function $h_{\mu}(\mathbf{y})$ is smooth and its gradient can be computed as: $\nabla h_{\mu}(\mathbf{y})=\arg\max_{\mathbf{v}}\{\langle\mathbf{y},\mathbf{v}\rangle-h^{*}(\mathbf{v})-\tfrac{\mu}{2}\|\mathbf{v}\|_{2}^{2}\}$; step ② uses the definition of $\operatorname{\operatorname{Prox}}(\mathbf{b};h,\mu)\triangleq\arg\min_{\mathbf{y}}h(\mathbf{y})+\frac{1}{2\mu}\|\mathbf{b}-\mathbf{y}\|_{2}^{2}$; step ③ uses the extended Moreau decomposition property as shown in Lemma [A.2](#A1.Thmtheorem2); step ④ uses the optimality of $\operatorname{\operatorname{Prox}}(\mathbf{y};h,\mu)$ that $\mathbf{0}\in\partial h(\operatorname{\operatorname{Prox}}(\mathbf{y};h,\mu))+\tfrac{1}{\mu}(\operatorname{\operatorname{Prox}}(\mathbf{y};h,\mu)-\mathbf{y})$. Using Equation ([17](#A3.E17)), we directly conclude that $\nabla h_{\mu}(\mathbf{y})$ is $C_{h}$-Lipschitz continuous with $\|\nabla h_{\mu}(\mathbf{y})\|\leq C_{h}$.

Part (d). We show how to compute $h_{\mu}(\mathbf{y})$. For any $\mathbf{y}\in\mathbb{R}^{m}$ and $\mu>0$, we define $h_{\mu}(\mathbf{y})\triangleq\max_{\mathbf{v}}\,\langle\mathbf{y},\mathbf{v}\rangle-h^{*}(\mathbf{v})-\tfrac{\mu}{2}\|\mathbf{v}\|_{2}^{2}$, and $\bar{\mathbf{v}}=\arg\max_{\mathbf{v}}\,\{\langle\mathbf{y},\mathbf{v}\rangle-h^{*}(\mathbf{v})-\tfrac{\mu}{2}\|\mathbf{v}\|_{2}^{2}\}$. We have:

$$ $\displaystyle\mathbf{y}-\mu\bar{\mathbf{v}}\in\partial h^{*}(\bar{\mathbf{v}})~{}~{}~{}\overset{\text{\char 172}}{\Leftrightarrow}~{}~{}~{}\langle\mathbf{y}-\mu\bar{\mathbf{v}},\bar{\mathbf{v}}\rangle=h^{*}(\bar{\mathbf{v}})+h(\mathbf{y}-\mu\bar{\mathbf{v}}).$ (18) $$

where step ① uses the equivalence relation: $\langle\tilde{\mathbf{x}},\tilde{\mathbf{y}}\rangle=h(\tilde{\mathbf{x}})+h^{*}(\tilde{\mathbf{y}})$ $\Leftrightarrow$ $\tilde{\mathbf{y}}\in\partial h(\tilde{\mathbf{x}})$ $\Leftrightarrow$ $\tilde{\mathbf{x}}\in\partial h^{*}(\tilde{\mathbf{y}})$ for all $\tilde{\mathbf{x}}$ and $\tilde{\mathbf{y}}$, as stated in Proposition 11.3 of Rockafellar & Wets. (). Therefore, we have:

$$ $\displaystyle h_{\mu}(\mathbf{y})$ $\displaystyle\overset{\text{\char 172}}{=}$ $\displaystyle\langle\mathbf{y},\bar{\mathbf{v}}\rangle-h^{*}(\bar{\mathbf{v}})-\tfrac{\mu}{2}\|\bar{\mathbf{v}}\|_{2}^{2}$ $\displaystyle\overset{\text{\char 173}}{=}$ $\displaystyle\langle\mathbf{y},\bar{\mathbf{v}}\rangle-\langle\mathbf{y}-\mu\bar{\mathbf{v}},\bar{\mathbf{v}}\rangle-h(\mathbf{y}-\mu\bar{\mathbf{v}})-\tfrac{\mu}{2}\|\bar{\mathbf{v}}\|_{2}^{2}$ $\displaystyle\overset{\text{\char 174}}{=}$ $\displaystyle\langle\mathbf{y},\bar{\mathbf{v}}\rangle-\langle\mathbf{y}-\mu\bar{\mathbf{v}},\bar{\mathbf{v}}\rangle+h(\operatorname{\operatorname{Prox}}(\mathbf{y};h,\mu))-\tfrac{\mu}{2}\|\bar{\mathbf{v}}\|_{2}^{2}$ $\displaystyle\overset{}{=}$ $\displaystyle h(\operatorname{\operatorname{Prox}}(\mathbf{y};h,\mu))+\tfrac{\mu}{2}\|\tfrac{1}{\mu}(\mathbf{y}-\operatorname{\operatorname{Prox}}(\mathbf{y};h,\mu))\|_{2}^{2},$ $$

where step ① uses the definition of $h_{\mu}(\mathbf{y})$; step ② uses Equation ([18](#A3.E18)) that $h^{*}(\bar{\mathbf{v}})=\langle\mathbf{y}-\mu\bar{\mathbf{v}},\bar{\mathbf{v}}\rangle-h(\mathbf{y}-\mu\bar{\mathbf{v}})$; step ③ uses $\bar{\mathbf{v}}=\frac{1}{\mu}(\mathbf{y}-\operatorname{\operatorname{Prox}}(\mathbf{y};h,\mu))$, as shown in Equation ([16](#A3.E16)).

Part (e). For any $\mathbf{y}\in\mathbb{R}^{m}$ and $\mu_{1},\mu_{2}>0$ with $\mu_{2}\leq\mu_{1}$, we define $\mathbf{u}_{1}=\arg\max_{\mathbf{u}}\{\langle\mathbf{y},\mathbf{u}\rangle-h^{*}(\mathbf{u})-\tfrac{\mu_{1}}{2}\|\mathbf{u}\|_{2}^{2}\}$, and $\mathbf{u}_{2}=\arg\max_{\mathbf{u}}\{\langle\mathbf{y},\mathbf{u}\rangle-h^{*}(\mathbf{u})-\tfrac{\mu_{2}}{2}\|\mathbf{u}\|_{2}^{2}\}$.

e-i). We now prove that $0\leq h_{\mu_{2}}(\mathbf{y})-h_{\mu_{1}}(\mathbf{y})$ for all $0<\mu_{2}\leq\mu_{1}$. We have:

$$ $\displaystyle~{}h_{\mu_{1}}(\mathbf{y})-h_{\mu_{2}}(\mathbf{y})$ $\displaystyle\overset{\text{\char 172}}{=}$ $\displaystyle~{}\{\langle\mathbf{y},\mathbf{u}_{1}\rangle-h^{*}(\mathbf{u}_{1})-\tfrac{\mu_{1}}{2}\|\mathbf{u}_{1}\|_{2}^{2}\}-h_{\mu_{2}}(\mathbf{y})$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}\{\langle\mathbf{y},\mathbf{u}_{1}\rangle-h^{*}(\mathbf{u}_{1})-\tfrac{\mu_{1}}{2}\|\mathbf{u}_{1}\|_{2}^{2}\}-\{\langle\mathbf{y},\mathbf{u}_{1}\rangle-h^{*}(\mathbf{u}_{1})-\tfrac{\mu_{2}}{2}\|\mathbf{u}_{1}\|_{2}^{2}\}$ $\displaystyle\overset{}{=}$ $\displaystyle~{}\tfrac{\mu_{2}-\mu_{1}}{2}\|\mathbf{u}_{1}\|_{2}^{2}$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}0,$ $$

where step ① uses the definition of $h_{\mu_{1}}(\mathbf{y})$: $h_{\mu_{1}}(\mathbf{y})=\{\langle\mathbf{y},\mathbf{u}_{1}\rangle-h^{*}(\mathbf{u}_{1})-\tfrac{\mu_{1}}{2}\|\mathbf{u}_{1}\|_{2}^{2}\}$; step ② uses the definition of $h_{\mu_{2}}(\mathbf{y})$ and the optimality of $\mathbf{u}_{2}$: $h_{\mu_{2}}(\mathbf{y})=\{\langle\mathbf{y},\mathbf{u}_{2}\rangle-h^{*}(\mathbf{u}_{2})-\tfrac{\mu_{2}}{2}\|\mathbf{u}_{2}\|_{2}^{2}\}\geq\{\langle\mathbf{y},\mathbf{u}_{1}\rangle-h^{*}(\mathbf{u}_{1})-\tfrac{\mu_{2}}{2}\|\mathbf{u}_{1}\|_{2}^{2}\}$; step ③ uses $\mu_{2}\leq\mu_{1}$.

e-ii). We now prove that $h_{\mu_{2}}(\mathbf{y})-h_{\mu_{1}}(\mathbf{y})\leq\tfrac{\mu_{1}-\mu_{2}}{2}C_{h}^{2}$ for all $0<\mu_{2}\leq\mu_{1}$. We have:

$$ $\displaystyle~{}h_{\mu_{2}}(\mathbf{y})-h_{\mu_{1}}(\mathbf{y})$ $\displaystyle\overset{\text{\char 172}}{=}$ $\displaystyle~{}\{\langle\mathbf{y},\mathbf{u}_{2}\rangle-h^{*}(\mathbf{u}_{2})-\tfrac{\mu_{2}}{2}\|\mathbf{u}_{2}\|_{2}^{2}\}-h_{\mu_{1}}(\mathbf{y})$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}\{\langle\mathbf{y},\mathbf{u}_{2}\rangle-h^{*}(\mathbf{u}_{2})-\tfrac{\mu_{2}}{2}\|\mathbf{u}_{2}\|_{2}^{2}\}-\{\langle\mathbf{y},\mathbf{u}_{2}\rangle-h^{*}(\mathbf{u}_{2})-\tfrac{\mu_{1}}{2}\|\mathbf{u}_{2}\|_{2}^{2}\}$ $\displaystyle\overset{}{=}$ $\displaystyle~{}\tfrac{\mu_{1}-\mu_{2}}{2}\|\mathbf{u}_{2}\|_{2}^{2}=\tfrac{\mu_{1}-\mu_{2}}{2}\|\nabla h_{\mu_{2}}(\mathbf{y})\|_{2}^{2}$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}\tfrac{\mu_{1}-\mu_{2}}{2}C_{h}^{2},$ $$

where step ① uses the definition of $h_{\mu_{2}}(\mathbf{y})$: $h_{\mu_{2}}(\mathbf{y})=\{\langle\mathbf{y},\mathbf{u}_{2}\rangle-h^{*}(\mathbf{u}_{2})-\tfrac{\mu_{2}}{2}\|\mathbf{u}_{2}\|_{2}^{2}\}$; step ② uses the definition of $h_{\mu_{1}}(\mathbf{y})$ and the optimality of $\mathbf{u}_{1}$: $h_{\mu_{1}}(\mathbf{y})=\{\langle\mathbf{y},\mathbf{u}_{1}\rangle-h^{*}(\mathbf{u}_{1})-\tfrac{\mu_{1}}{2}\|\mathbf{u}_{1}\|_{2}^{2}\}\geq\{\langle\mathbf{y},\mathbf{u}_{2}\rangle-h^{*}(\mathbf{u}_{2})-\tfrac{\mu_{1}}{2}\|\mathbf{u}_{2}\|_{2}^{2}\}$; step ③ uses Claim (b) of this lemma.

Part (f). We now prove that $\|\nabla h_{\mu_{2}}(\mathbf{y})-\nabla h_{\mu_{1}}(\mathbf{y})\|\leq(\tfrac{\mu_{1}}{\mu_{2}}-1)C_{h}$ for all $0<\mu_{2}\leq\mu_{1}$. Using Equality ([16](#A3.E16)), we have:

$$ $\displaystyle\nabla h_{\mu}(\mathbf{y})=\tfrac{1}{\mu}(\mathbf{y}-\operatorname{\operatorname{Prox}}(\mathbf{y};h,\mu)).$ $$

We now examine the following mapping $\mathcal{H}(\upsilon)\triangleq\upsilon(\mathbf{y}-\operatorname{\operatorname{Prox}}(\mathbf{y};h,1/\upsilon))$. We derive:

$$ $\displaystyle\lim_{\delta\rightarrow 0}\tfrac{\mathcal{H}(\upsilon+\delta)-\mathcal{H}(\upsilon)}{\delta}=$ $\displaystyle~{}\lim_{\delta\rightarrow 0}\tfrac{(\upsilon+\delta)(\mathbf{y}-\operatorname{\operatorname{Prox}}(\mathbf{y};h,1/(\upsilon+\delta)))-\upsilon(\mathbf{y}-\operatorname{\operatorname{Prox}}(\mathbf{y};h,1/\upsilon))}{\delta}$ $\displaystyle=$ $\displaystyle~{}\lim_{\delta\rightarrow 0}\tfrac{\delta\mathbf{y}-(\upsilon+\delta)\operatorname{\operatorname{Prox}}(\mathbf{y};h,1/\upsilon)+\upsilon\operatorname{\operatorname{Prox}}(\mathbf{y};h,1/\upsilon)}{\delta}$ $\displaystyle=$ $\displaystyle~{}\mathbf{y}-\operatorname{\operatorname{Prox}}(\mathbf{y};h,1/\upsilon).$ $$

Therefore, the first-order derivative of the mapping $\mathcal{H}(\upsilon)$ w.r.t. $\upsilon$ always exists and can be computed as: $\nabla_{\upsilon}\mathcal{H}(\upsilon)=\mathbf{y}-\operatorname{\operatorname{Prox}}(\mathbf{y};h,1/\upsilon)$, resulting in:

$$ $\displaystyle\forall\upsilon,\upsilon^{\prime}>0,\tfrac{\|\mathcal{H}(\upsilon)-\mathcal{H}(\upsilon^{\prime})\|}{|\upsilon-\upsilon^{\prime}|}\leq\|\mathbf{y}-\operatorname{\operatorname{Prox}}(\mathbf{y};h,1/\upsilon)\|.$ $$

Letting $\upsilon=1/\mu_{1}$ and $\upsilon^{\prime}=1/\mu_{2}$, we derive:

$$ $\displaystyle\tfrac{\|\nabla h_{\mu_{1}}(\mathbf{y})-\nabla h_{\mu_{2}}(\mathbf{y})\|}{|1/\mu_{1}-1/\mu_{2}|}\leq$ $\displaystyle~{}\|\mathbf{y}-\operatorname{\operatorname{Prox}}(\mathbf{y};h,\mu_{1})\|$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}\mu_{1}\|\partial h(\operatorname{\operatorname{Prox}}(\mathbf{y};h,\mu_{1}))\|$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}\mu_{1}C_{h},$ $$

where step ① uses the optimality of $\operatorname{\operatorname{Prox}}(\mathbf{y};h,\mu_{1})$ that $\mathbf{0}\in\partial h(\operatorname{\operatorname{Prox}}(\mathbf{y};h,\mu_{1}))+\frac{1}{\mu_{1}}(\operatorname{\operatorname{Prox}}(\mathbf{y};h,\mu_{1})-\mathbf{y})$ for all $\mu_{1}$; step ② uses the Lipschitz continuity of $h(\cdot)$. We further obtain:

$$ $\displaystyle\|\nabla h_{\mu_{1}}(\mathbf{x})-\nabla h_{\mu_{2}}(\mathbf{x})\|\leq|\tfrac{1}{\mu_{1}}-\tfrac{1}{\mu_{2}}|\cdot\mu_{1}C_{h}=(\tfrac{\mu_{1}}{\mu_{2}}-1)C_{h}.$ $$

∎

###### Proof.

### C.2 Proof of Lemma 3.10

###### Proof.

Consider the strongly convex minimization problem: $\bar{\mathbf{y}}=\arg\min_{\mathbf{y}}h_{\mu}(\mathbf{y})+\tfrac{1}{2}\beta\|\mathbf{y}-\mathbf{b}\|_{2}^{2}$, which can be equivalently repressed as:

$$ $\displaystyle(\bar{\mathbf{y}},\bar{\mathbf{v}})=\arg\min_{\mathbf{y}}\max_{\mathbf{v}}\,\{\mathbf{y}^{\mathsf{T}}\mathbf{v}-h^{*}(\mathbf{v})-\tfrac{\mu}{2}\|\mathbf{v}\|_{2}^{2}+\tfrac{\beta}{2}\|\mathbf{y}-\mathbf{b}\|_{2}^{2}\}.$ $$

Using the optimality of the variables $\{\bar{\mathbf{y}},\bar{\mathbf{v}}\}$, we have:

$$ $\displaystyle\bar{\mathbf{y}}=$ $\displaystyle~{}\mathbf{b}-\tfrac{1}{\beta}\bar{\mathbf{v}},$ (19) $\displaystyle\mathbf{0}=$ $\displaystyle~{}-\partial h^{*}(\bar{\mathbf{v}})-\mu\bar{\mathbf{v}}+\bar{\mathbf{y}}.$ (20) $$

Plugging Equation ([19](#A3.E19)) into Equation ([20](#A3.E20)) to eliminate $\bar{\mathbf{y}}$ yields:

$$ $\displaystyle\mathbf{0}=-\partial h^{*}(\bar{\mathbf{v}})-\mu\bar{\mathbf{v}}+\mathbf{b}-\tfrac{1}{\beta}\bar{\mathbf{v}}.$ (21) $$

Second, we derive the following equalities:

$$ $\displaystyle\bar{\mathbf{v}}\overset{\text{\char 172}}{=}$ $\displaystyle~{}\arg\max_{\mathbf{v}}-h^{*}(\mathbf{v})+\langle\mathbf{v},\mathbf{b}\rangle-\tfrac{\mu}{2}\|\mathbf{v}\|_{2}^{2}-\tfrac{1}{2\beta}\|\mathbf{v}\|_{2}^{2}$ (22) $\displaystyle\overset{}{=}$ $\displaystyle~{}\arg\min_{\mathbf{v}}h^{*}(\mathbf{v})-\langle\mathbf{v},\mathbf{b}\rangle+\tfrac{1}{2}(\mu+\tfrac{1}{\beta})\|\mathbf{v}\|_{2}^{2}$ $\displaystyle\overset{}{=}$ $\displaystyle~{}\arg\min_{\mathbf{v}}h^{*}(\mathbf{v})+\tfrac{1}{2}(\mu+\tfrac{1}{\beta})\|\mathbf{v}-\mathbf{b}/(\mu+\tfrac{1}{\beta})\|_{2}^{2}$ $\displaystyle\overset{\text{\char 173}}{=}$ $\displaystyle~{}\operatorname{\operatorname{Prox}}(\tfrac{\mathbf{b}}{\mu+1/\beta});h^{*},\tfrac{1}{\mu+1/\beta})$ $\displaystyle\overset{\text{\char 174}}{=}$ $\displaystyle~{}\tfrac{1}{\mu+1/\beta}\cdot(\mathbf{b}-\operatorname{\operatorname{Prox}}(\mathbf{b};h,\mu+\tfrac{1}{\beta}))$ (23) $\displaystyle\overset{\text{\char 175}}{\in}$ $\displaystyle~{}\partial h(\operatorname{\operatorname{Prox}}(\mathbf{b};h,\mu+\tfrac{1}{\beta})),$ (24) $$

where step ① uses the fact that Equation ([21](#A3.E21)) is the necessary and sufficient first-order optimality condition for Problem ([22](#A3.E22)); step ② uses the definition of $\operatorname{\operatorname{Prox}}(\cdot;\cdot,\cdot)$; step ③ uses the extended Moreau decomposition that $\mathbf{a}=\operatorname{\operatorname{Prox}}(\mathbf{a};h,\mu)+\mu\operatorname{\operatorname{Prox}}(\tfrac{\mathbf{a}}{\mu};h^{*},1/\mu)$ for all $\mu>0$ and $\mathbf{a}$, as shown in Lemma [A.2](#A1.Thmtheorem2); step ④ uses the following necessary and sufficient first-order optimality condition for $\operatorname{\operatorname{Prox}}(\mathbf{b};h,\mu+\tfrac{1}{\beta})$:

$$ $\displaystyle\tfrac{1}{\mu+1/\beta}\cdot\{\mathbf{b}-\operatorname{\operatorname{Prox}}(\mathbf{b};h,\mu+\tfrac{1}{\beta})\}\in\partial h(\operatorname{\operatorname{Prox}}(\mathbf{b};h,\mu+\tfrac{1}{\beta})).$ $$

Part (a). Combining Equation ([23](#A3.E23)) with Equation ([19](#A3.E19)) to eliminate $\bar{\mathbf{v}}$, we have:

$$ $\displaystyle\bar{\mathbf{y}}$ $\displaystyle=$ $\displaystyle\mathbf{b}-\tfrac{1}{\beta}\cdot\tfrac{1}{\mu+{1}/{\beta}}\cdot\{\mathbf{b}-\operatorname{\operatorname{Prox}}(\mathbf{b};h,\mu+1/\beta)\}$ $\displaystyle=$ $\displaystyle\mathbf{b}-\tfrac{1}{\mu\beta+1}\cdot\{\mathbf{b}-\operatorname{\operatorname{Prox}}(\mathbf{b};h,\mu+1/\beta)\}.$ $$

Part (b). We define $\check{\mathbf{y}}\triangleq\operatorname{\operatorname{Prox}}(\mathbf{b};h,\mu+1/\beta)$. We have:

$$ $\displaystyle\beta(\mathbf{b}-\bar{\mathbf{y}})\overset{\text{\char 172}}{=}$ $\displaystyle~{}\tfrac{\beta}{\mu\beta+1}\cdot\{\mathbf{b}-\operatorname{\operatorname{Prox}}(\mathbf{b};h,\mu+1/\beta)\}$ $\displaystyle\overset{\text{\char 173}}{=}$ $\displaystyle~{}\tfrac{1}{\mu+1/\beta}\cdot\{\mathbf{b}-\check{\mathbf{y}}\}\overset{\text{\char 174}}{=}\bar{\mathbf{v}}\overset{\text{\char 175}}{\in}\partial h(\check{\mathbf{y}}),$ (25) $$

where step ① uses Claim (a) of this lemma; step ② uses the definition of $\check{\mathbf{y}}$; step ③ uses Equality ([23](#A3.E23)); step ④ uses Equality ([24](#A3.E24)) that $\bar{\mathbf{v}}\in\partial h(\check{\mathbf{y}})$.

Part (c). We now prove that $\|\bar{\mathbf{y}}-\check{\mathbf{y}}\|\leq\mu C_{h}$. We derive:

$$ $\displaystyle\|\bar{\mathbf{y}}-\check{\mathbf{y}}\|\overset{\text{\char 172}}{=}$ $\displaystyle~{}\|\mathbf{b}-\tfrac{1}{\beta\mu+1}\cdot(\mathbf{b}-\check{\mathbf{y}})-\check{\mathbf{y}}\|$ $\displaystyle\overset{}{=}$ $\displaystyle~{}\tfrac{\beta\mu}{1+\beta\mu}\|\check{\mathbf{y}}-\mathbf{b}\|$ $\displaystyle\overset{\text{\char 173}}{=}$ $\displaystyle~{}\tfrac{\beta\mu}{1+\beta\mu}(\mu+1/\beta)\|\partial h(\check{\mathbf{y}})\|$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}\tfrac{\beta\mu}{1+\beta\mu}(\mu+1/\beta)C_{h}=\mu C_{h},$ $$

where step ① uses Claim (a) of this lemma that $\bar{\mathbf{y}}=\mathbf{b}-\tfrac{1}{\beta\mu+1}\cdot\{\mathbf{b}-\check{\mathbf{y}}\}$; step ② uses Equality ([C.2](#A3.Ex58)) that $\mathbf{b}-\check{\mathbf{y}}\in(\mu+1/\beta)\partial h(\check{\mathbf{y}})$; step ③ uses the fact that $h(\mathbf{y})$ is $C_{h}$-Lipschitz continuous.

∎

###### Proof.

## Appendix D Proofs for Section 4

### D.1 Proof of Lemma 5.3

###### Proof.

Part (a). We now show that $\mathbf{z}^{t+1}=\nabla h_{\mu^{t}}(\mathbf{y}^{t+1})$. For any $t\geq 0$, we have:

$$ $\displaystyle\textstyle\mathbf{0}\overset{\text{\char 172}}{=}$ $\displaystyle~{}\textstyle\nabla h_{\mu^{t}}(\mathbf{y}^{t+1})+\beta^{t}(\mathbf{y}^{t+1}-\mathbf{y}^{t})+\nabla_{\mathbf{y}}\mathcal{S}(\mathbf{x}^{t+1},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t})$ $\displaystyle\overset{\text{\char 173}}{=}$ $\displaystyle~{}\textstyle\nabla h_{\mu^{t}}(\mathbf{y}^{t+1})+\beta^{t}(\mathbf{y}^{t+1}-\mathbf{y}^{t})+\beta^{t}(\mathbf{y}^{t}-\mathbf{A}\mathbf{x}^{t+1})-\mathbf{z}^{t}$ $\displaystyle\overset{\text{\char 174}}{=}$ $\displaystyle~{}\textstyle\nabla h_{\mu^{t}}(\mathbf{y}^{t+1})-\mathbf{z}^{t+1},$ $$

where step ① uses the optimality condition for $\mathbf{y}^{t+1}$; step ② uses $\nabla_{\mathbf{y}}\mathcal{S}(\mathbf{x}^{t+1},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t})=\beta^{t}(\mathbf{y}-\mathbf{A}\mathbf{x}^{t+1})-\mathbf{z}^{t}$; step ③ uses $\mathbf{z}^{t+1}-\mathbf{z}^{t}=\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1})$.

Part (b). We now show that $\nabla h_{\mu^{t}}(\mathbf{y}^{t+1})\in\partial h(\check{\mathbf{y}}^{t+1})$. For any $t\geq 0$, we have:

$$ $\displaystyle\partial h(\breve{\mathbf{y}}^{t+1})\overset{\text{\char 172}}{\ni}$ $\displaystyle~{}\beta^{t}(\mathbf{b}^{t}-\mathbf{y}^{t+1})$ $\displaystyle\overset{\text{\char 173}}{=}$ $\displaystyle~{}\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}+\mathbf{z}^{t}/\beta^{t}-\mathbf{y}^{t+1})$ $\displaystyle\overset{\text{\char 174}}{=}$ $\displaystyle~{}\mathbf{z}^{t+1},$ $$

where step ① uses Claim (b) of Lemma [3.10](#S3.Thmtheorem10); step ② uses $\mathbf{b}^{t}=\mathbf{y}^{t}-\nabla_{\mathbf{y}}\mathcal{S}(\mathbf{x}^{t+1},\mathbf{y}^{t};z^{t};\beta^{t})/\beta^{t}=\mathbf{y}^{t}-[\beta^{t}(\mathbf{y}^{t}-\mathbf{A}\mathbf{x}^{t+1})-\mathbf{z}^{t}]/\beta^{t}=\mathbf{A}\mathbf{x}^{t+1}+\mathbf{z}^{t}/\beta^{t}$; step ③ uses $\mathbf{z}^{t+1}-\mathbf{z}^{t}=\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1})$.

∎

###### Proof.

### D.2 Proof of Lemma 5.4

###### Proof.

Since $t$ can be arbitrary, for any $t\geq 1$, we have from Lemma [5.3](#S5.Thmtheorem3):

$$ $\displaystyle\textstyle\mathbf{0}=$ $\displaystyle~{}\textstyle\nabla h_{\mu^{t}}(\mathbf{y}^{t+1})-\mathbf{z}^{t+1},$ $\displaystyle\textstyle\mathbf{0}=$ $\displaystyle~{}\textstyle\nabla h_{\mu^{t-1}}(\mathbf{y}^{t})-\mathbf{z}^{t}.$ $$

Combining the two equalities above, we have, for any $t\geq 1$:

$$ $\displaystyle\mathbf{z}^{t+1}-\mathbf{z}^{t}=\nabla h_{\mu^{t}}(\mathbf{y}^{t+1})-\nabla h_{\mu^{t-1}}(\mathbf{y}^{t}).$ $$

This further leads to the following inequalities:

$$ $\displaystyle\|\mathbf{z}^{t+1}-\mathbf{z}^{t}\|_{2}^{2}=$ $\displaystyle~{}\|\nabla h_{\mu^{t}}(\mathbf{y}^{t+1})-\nabla h_{\mu^{t-1}}(\mathbf{y}^{t})\|_{2}^{2}$ $\displaystyle=$ $\displaystyle~{}\|\nabla h_{\mu^{t}}(\mathbf{y}^{t+1})-\nabla h_{\mu^{t}}(\mathbf{y}^{t})+\nabla h_{\mu^{t}}(\mathbf{y}^{t})-\nabla h_{\mu^{t-1}}(\mathbf{y}^{t})\|_{2}^{2}$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}2\|\nabla h_{\mu^{t}}(\mathbf{y}^{t+1})-\nabla h_{\mu^{t}}(\mathbf{y}^{t})\|_{2}^{2}+2\|\nabla h_{\mu^{t}}(\mathbf{y}^{t})-\nabla h_{\mu^{t-1}}(\mathbf{y}^{t})\|_{2}^{2}$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}2\|\tfrac{1}{\mu^{t}}(\mathbf{y}^{t+1}-\mathbf{y}^{t})\|_{2}^{2}+2(\tfrac{\mu^{t-1}}{\mu^{t}}-1)^{2}C_{h}^{2}$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}2\tfrac{(\beta^{t})^{2}}{\chi^{2}}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}+2C_{h}^{2}(\tfrac{6}{t}-\tfrac{6}{t+1}),$ $$

where step ① uses $\|\mathbf{a}+\mathbf{b}\|_{2}^{2}\leq 2\|\mathbf{a}\|_{2}^{2}+2\|\mathbf{a}\|_{2}^{2}$; step ② uses $\tfrac{1}{\mu^{t}}$-smoothness of $h_{\mu^{t}}(\mathbf{y})$ for all $\mathbf{y}$, and Claim (f) of Lemma [3.9](#S3.Thmtheorem9) that $\|\nabla h_{\mu_{1}}(\mathbf{y})-\nabla h_{\mu_{2}}(\mathbf{y})\|\leq(\frac{\mu_{1}}{\mu_{2}}-1)C_{h}$ for all $0<\mu_{2}<\mu_{1}$; step ③ uses $\mu^{t}=\tfrac{\chi}{\beta^{t}}$ and Lemma [A.3](#A1.Thmtheorem3) that $(\tfrac{\mu^{t-1}}{\mu^{t}}-1)^{2}\leq\tfrac{6}{t}-\tfrac{6}{t+1}$ for any integer $t\geq 1$.

∎

###### Proof.

### D.3 Proof of Lemma 5.5

###### Proof.

We define $\overline{\rm{z}}\triangleq\max(\|\mathbf{z}^{0}\|,C_{h})$, and $\overline{\rm{y}}\triangleq\max(\|\mathbf{y}^{0}\|,\tfrac{2}{\beta^{0}}\overline{\rm{z}}+\|\mathbf{A}\|\overline{\rm{x}})$.

Part (a). The conclusion $\|\mathbf{x}^{t}\|\leq\overline{\rm{x}}$ directly follows by assumption.

Part (b). We now show that $\|\mathbf{z}^{t}\|\leq\overline{\rm{z}}$. Using Claim (a) of Lemma [5.3](#S5.Thmtheorem3), we have $\forall t\geq 0,\,\mathbf{z}^{t+1}=\nabla h_{\mu^{t}}(\mathbf{y}^{t+1})$. This leads to $\forall t\geq 1,\,\|\mathbf{z}^{t}\|\leq\|\nabla h_{\mu^{t-1}}(\mathbf{y}^{t})\|\leq C_{h}$. Therefore, it holds that $\forall t\geq 0,\,\|\mathbf{z}^{t}\|\leq\max(\|\mathbf{z}^{0}\|,C_{h})\triangleq\overline{\rm{z}}$.

Part (c). We now show that $\|\mathbf{y}^{t}\|\leq\overline{\rm{y}}$. For all $t\geq 0$, we have:

$$ $\displaystyle\|\mathbf{y}^{t+1}\|\overset{\text{\char 172}}{=}$ $\displaystyle~{}\|\tfrac{1}{\beta^{t}}(\mathbf{z}^{t+1}-\mathbf{z}^{t})-\mathbf{A}\mathbf{x}^{t+1}\|$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}\tfrac{1}{\beta^{0}}(\|\mathbf{z}^{t+1}\|+\|\mathbf{z}^{t}\|)+\|\mathbf{A}\|\|\mathbf{x}^{t+1}\|$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}\tfrac{2}{\beta^{0}}\overline{\rm{z}}+\|\mathbf{A}\|\overline{\rm{x}},$ $$

where step ① uses $\mathbf{z}^{t+1}=\mathbf{z}^{t}+\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1})$; step ② uses the triangle inequality, the norm inequality, and $\beta^{0}\leq\beta^{t}$; step ③ uses the boundedness of $\mathbf{z}^{t}$ and $\mathbf{x}^{t}$. Therefore, it holds that $\forall t\geq 0,\,\|\mathbf{y}^{t}\|\leq\max(\|\mathbf{y}^{0}\|,\tfrac{2}{\beta^{0}}\overline{\rm{z}}+\|\mathbf{A}\|\overline{\rm{x}})\triangleq\overline{\rm{y}}$.

∎

###### Proof.

### D.4 Proof of Lemma 5.6

###### Proof.

We define $\mathcal{U}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)\triangleq\delta(\mathbf{x})+f(\mathbf{x})-g(\mathbf{x})+h_{\mu}(\mathbf{y})+\langle\mathbf{A}\mathbf{x}-\mathbf{y},\mathbf{z}\rangle+\frac{\beta}{2}\|\mathbf{A}\mathbf{x}-\mathbf{y}\|_{2}^{2}$.

We define $\underline{\rm{v}}\triangleq 8\overline{\rm{z}}^{2}+\tfrac{1}{2}\chi\overline{\rm{z}}^{2}$, and $\overline{\rm{v}}\triangleq 16\overline{\rm{z}}^{2}$.

First, given $h(\mathbf{y})$ is convex, for all $\mathbf{y},\mathbf{y}^{\prime}\in\mathbb{R}^{m}$, we have:

$$ $\displaystyle h(\mathbf{y}^{\prime})-h(\mathbf{y})\leq\langle\partial h(\mathbf{y}^{\prime}),\mathbf{y}^{\prime}-\mathbf{y}\rangle.$ (26) $$

Second, for any $\mathbf{y}\in\mathbb{R}^{m}$ and $t\geq 1$, we have:

$$ $\displaystyle\langle\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t},\mathbf{z}^{t}-\partial h(\mathbf{y})\rangle\overset{\text{\char 172}}{=}$ $\displaystyle~{}\tfrac{1}{\beta^{t-1}}\langle\mathbf{z}^{t}-\mathbf{z}^{t-1},\mathbf{z}^{t}-\partial h(\mathbf{y})\rangle$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}\tfrac{2}{\beta^{t}}\|\mathbf{z}^{t}-\mathbf{z}^{t-1}\|\cdot\|\mathbf{z}^{t}-\partial h(\mathbf{y})\|$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}\tfrac{2}{\beta^{t}}\cdot 2\overline{\rm{z}}\cdot(\overline{\rm{z}}+\|\partial h(\mathbf{y})\|)$ $\displaystyle\overset{\text{\char 175}}{\leq}$ $\displaystyle~{}\tfrac{2}{\beta^{t}}\cdot 2\overline{\rm{z}}\cdot 2\overline{\rm{z}},$ (27) $$

where step ① uses the $\mathbf{z}^{t+1}-\mathbf{z}^{t}=\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1})$; step ② uses the norm inequality and $\beta^{t}\leq 2\beta^{t-1}$; step ③ uses $\|\mathbf{z}^{t}\|\leq\overline{\rm{z}}$ and $\|\nabla h_{\mu^{t}}(\mathbf{y})\|\leq C_{h}\leq\overline{\rm{z}}$, as shown in Lemma [D.3](#A4.SS3).

Third, for any $t\geq 1$, we have:

$$ $\displaystyle\tfrac{\beta^{t}}{2}\|\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}\|_{2}^{2}\overset{\text{\char 172}}{=}$ $\displaystyle~{}\beta^{t}\|\tfrac{1}{\beta^{t-1}}(\mathbf{z}^{t}-\mathbf{z}^{t-1})\|_{2}^{2}$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}\beta^{t}\tfrac{2}{(\beta^{t})^{2}}\|\mathbf{z}^{t}-\mathbf{z}^{t-1}\|_{2}^{2}$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}\tfrac{2}{\beta^{t}}\|\mathbf{z}^{t}-\mathbf{z}^{t-1}\|_{2}^{2}$ $\displaystyle\overset{\text{\char 175}}{\leq}$ $\displaystyle~{}\tfrac{2}{\beta^{t}}(2\|\mathbf{z}^{t}\|_{2}^{2}+2\|\mathbf{z}^{t-1}\|_{2}^{2})$ $\displaystyle\overset{\text{\char 176}}{\leq}$ $\displaystyle~{}\tfrac{8}{\beta^{t}}\overline{\rm{z}}^{2},$ (28) $$

where step ① uses the $\mathbf{z}^{t+1}-\mathbf{z}^{t}=\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1})$; step ② uses $\beta^{t}\leq 2\beta^{t-1}$; step ③ uses $\beta^{t}\geq\beta^{0}$ for all $t\geq 0$; step ④ uses $\|\mathbf{a}+\mathbf{b}\|_{2}^{2}\leq 2\|\mathbf{a}\|_{2}^{2}+2\|\mathbf{b}\|_{2}^{2}$; step ⑤ uses $\|\mathbf{z}^{t}\|\leq\overline{\rm{z}}$.

Part (a). We now derive the lower bound for any $t\geq 1$, as follows:

$$ $\displaystyle\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})\overset{}{\triangleq}$ $\displaystyle~{}f(\mathbf{x}^{t})+\delta(\mathbf{x}^{t})-g(\mathbf{x}^{t})+\langle\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t},\mathbf{z}^{t}\rangle+\tfrac{\beta^{t}}{2}\|\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}\|_{2}^{2}+h_{\mu^{t}}(\mathbf{y}^{t})$ $\displaystyle\overset{\text{\char 172}}{\geq}$ $\displaystyle~{}\underline{\rm{F}}\cdot d(\mathbf{x}^{t})-h(\mathbf{A}\mathbf{x}^{t})+\langle\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t},\mathbf{z}^{t}\rangle+\tfrac{\beta^{t}}{2}\|\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}\|_{2}^{2}+h_{\mu^{t}}(\mathbf{y}^{t})$ $\displaystyle\overset{\text{\char 173}}{\geq}$ $\displaystyle~{}\underline{\rm{F}}\cdot d(\mathbf{x}^{t})+h(\mathbf{y}^{t})-h(\mathbf{A}\mathbf{x}^{t})+\langle\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t},\mathbf{z}^{t}\rangle+\{h_{\mu^{t}}(\mathbf{y}^{t})-h(\mathbf{y}^{t})\}$ $\displaystyle\overset{\text{\char 174}}{\geq}$ $\displaystyle~{}\underline{\rm{F}}\cdot d(\mathbf{x}^{t})+\langle\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t},\mathbf{z}^{t}-\partial h(\mathbf{A}\mathbf{x}^{t})\rangle-\tfrac{\mu^{t}}{2}C_{h}^{2}$ $\displaystyle\overset{\text{\char 175}}{\geq}$ $\displaystyle~{}\underline{\rm{F}}\cdot d(\mathbf{x}^{t})-\tfrac{8\overline{\rm{z}}^{2}}{\beta^{t}}-\tfrac{\chi\overline{\rm{z}}^{2}}{2\beta^{t}}$ $\displaystyle\overset{\text{\char 176}}{=}$ $\displaystyle~{}\underline{\rm{F}}\cdot d(\mathbf{x}^{t})-\tfrac{\underline{\rm{v}}}{\beta^{t}},$ $$

where step ① uses $F(\mathbf{x}^{t})\triangleq\tfrac{f(\mathbf{x}^{t})+\delta(\mathbf{x}^{t})-g(\mathbf{x}^{t})+h(\mathbf{A}\mathbf{x}^{t})}{d(\mathbf{x}^{t})}\geq\underline{\rm{F}}$; step ② uses $\tfrac{\beta^{t}}{2}\|\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}\|_{2}^{2}\geq 0$; step ③ uses Inequality ([26](#A4.E26)) with $\mathbf{y}=\mathbf{y}^{t}$ and $\mathbf{y}^{\prime}=\mathbf{A}\mathbf{x}^{t}$, and the fact that $h(\mathbf{y})\leq h_{\mu}(\mathbf{y})+\tfrac{\mu}{2}C_{h}^{2}$ (see Claim (b) of Lemma [3.9](#S3.Thmtheorem9)); step ④ uses Inequality ([D.4](#A4.Ex80)), $\mu^{t}=\tfrac{\chi}{\beta^{t}}$, and $C_{h}\leq\overline{\rm{z}}$; step ⑤ uses the definition of $\underline{\rm{v}}$.

Part (b). We now derive the upper bound for any $t\geq 1$, as follows:

$$ $\displaystyle\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})\overset{}{\triangleq}$ $\displaystyle~{}f(\mathbf{x}^{t})+\delta(\mathbf{x}^{t})-g(\mathbf{x}^{t})+\langle\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t},\mathbf{z}^{t}\rangle+\tfrac{\beta^{t}}{2}\|\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}\|_{2}^{2}+h_{\mu^{t}}(\mathbf{y}^{t})$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}\overline{\rm{F}}d(\mathbf{x}^{t})-h(\mathbf{A}\mathbf{x}^{t})+\langle\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t},\mathbf{z}^{t}\rangle+\tfrac{\beta^{t}}{2}\|\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}\|_{2}^{2}+h_{\mu^{t}}(\mathbf{y}^{t})$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}\overline{\rm{F}}\cdot\overline{\rm{d}}-h(\mathbf{A}\mathbf{x}^{t})+\langle\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t},\mathbf{z}^{t}\rangle+\tfrac{\beta^{t}}{2}\|\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}\|_{2}^{2}+h(\mathbf{y}^{t})$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}\overline{\rm{F}}\cdot\overline{\rm{d}}+\langle\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t},\mathbf{z}^{t}-\partial h(\mathbf{y}^{t})\rangle+\tfrac{\beta^{t}}{2}\|\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}\|_{2}^{2}$ $\displaystyle\overset{\text{\char 175}}{\leq}$ $\displaystyle~{}\overline{\rm{F}}\cdot\overline{\rm{d}}+\tfrac{(8+8)\overline{\rm{z}}^{2}}{\beta^{t}}$ $\displaystyle\overset{}{\leq}$ $\displaystyle~{}\overline{\rm{F}}\cdot\overline{\rm{d}}+\tfrac{\overline{\rm{v}}}{\beta^{t}},$ $$

where step ① uses $F(\mathbf{x}^{t})\triangleq\tfrac{f(\mathbf{x}^{t})+\delta(\mathbf{x}^{t})-g(\mathbf{x}^{t})+h(\mathbf{A}\mathbf{x}^{t})}{d(\mathbf{x}^{t})}\leq\overline{\rm{F}}$; step ② uses $d(\mathbf{x}^{t})\leq\overline{\rm{d}}$, and $h_{\mu}(\mathbf{y})\leq h(\mathbf{y})$ for all $\mathbf{y}$ and $\mu$; step ③ uses Inequality ([26](#A4.E26)) with $\mathbf{y}=\mathbf{A}\mathbf{x}^{t}$ and $\mathbf{y}^{\prime}=\mathbf{y}^{t}$; step ④ uses Inequalities ([D.4](#A4.Ex80)) and ([28](#A4.E28)).
∎

###### Proof.

### D.5 Proof of Lemma 5.9

###### Proof.

Part (a). For any $t\geq 0$, we have:

$$ $\displaystyle\tfrac{\beta^{t+1}}{\beta^{t}}=\tfrac{1+\xi(t+1)^{p}}{1+\xi t^{p}}\overset{\text{\char 172}}{\leq}\tfrac{1+\xi(t^{p}+1)}{1+\xi t^{p}}\overset{\text{\char 173}}{\leq}1+\xi,$ (29) $$

where step ① uses the fact that $(t+1)^{p}\leq t^{p}+1^{p}$ for all $p\in(0,1)$ and $t\geq 0$; step ② uses the fact that $\tfrac{a+\xi}{a}\leq 1+\xi$ for all $a\geq 1$ and $\xi\geq 0$.

Part (b). For all $t\geq 1$, we derive the upper bound and lower bound for $\lambda^{t}$:

$$ $\displaystyle\textstyle\lambda^{t}\triangleq$ $\displaystyle\textstyle~{}\tfrac{\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})}{d(\mathbf{x}^{t})}\leq\textstyle\tfrac{\overline{\rm{F}}\overline{\rm{d}}+\overline{\rm{v}}/\beta^{t}}{\underline{\rm{d}}}\leq\tfrac{\overline{\rm{F}}\overline{\rm{d}}+\overline{\rm{v}}/\beta^{0}}{\underline{\rm{d}}}\triangleq\overline{\lambda}.$ $\displaystyle\textstyle\lambda^{t}\triangleq$ $\displaystyle\textstyle~{}\tfrac{\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})}{d(\mathbf{x}^{t})}\geq\tfrac{\underline{\rm{F}}\underline{\rm{d}}-\underline{\rm{v}}/\beta^{t}}{\overline{\rm{d}}}\geq\tfrac{\underline{\rm{F}}\underline{\rm{d}}-\underline{\rm{v}}/\beta^{0}}{\overline{\rm{d}}}\triangleq\underline{\lambda}.$ $$

For all $t\geq 0$, we derive the upper bound and lower bound for $\alpha^{t+1}$:

$$ $\displaystyle\alpha^{t+1}\triangleq$ $\displaystyle~{}\tfrac{\sqrt{d(\mathbf{x}^{t})}}{\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})}\leq\tfrac{\sqrt{\overline{\rm{d}}}}{\underline{\rm{F}}\underline{\rm{d}}-{\underline{\rm{v}}}/{\beta^{t}}}\leq\tfrac{\sqrt{\overline{\rm{d}}}}{\underline{\rm{F}}\underline{\rm{d}}-{\underline{\rm{v}}}/{\beta^{0}}}\triangleq\overline{\alpha}.$ $\displaystyle\textstyle\alpha^{t+1}\triangleq$ $\displaystyle~{}\tfrac{\sqrt{d(\mathbf{x}^{t})}}{\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})}\geq\tfrac{\sqrt{\underline{\rm{d}}}}{\overline{\rm{F}}\overline{\rm{d}}+{\overline{\rm{v}}}/{\beta^{t}}}\geq\tfrac{\sqrt{\underline{\rm{d}}}}{\overline{\rm{F}}\overline{\rm{d}}+{\overline{\rm{v}}}/{\beta^{0}}}\triangleq\underline{\alpha}.$ $$

Part (c). We first focus on FADMM-D with $\ell(\beta^{t})\triangleq L_{f}+\beta^{t}\|\mathbf{A}\|_{2}^{2}+\lambda^{t}W_{d}$. For all $t\geq 1$, we have:

$$ $\displaystyle\ell(\beta^{t})\geq$ $\displaystyle~{}\beta^{t}\|\mathbf{A}\|_{2}^{2}.$ $\displaystyle\ell(\beta^{t})\leq$ $\displaystyle~{}\tfrac{\beta^{t}L_{f}}{\beta^{0}}+\beta^{t}\|\mathbf{A}\|_{2}^{2}+\tfrac{\beta^{t}}{\beta^{0}}\overline{\lambda}W_{d}.$ $$

We now focus on FADMM-Q with $\ell(\beta^{t})\triangleq L_{f}+\beta^{t}\|\mathbf{A}\|_{2}^{2}+(2/\alpha^{t})W_{d}$. For all $t\geq 1$, we have:

$$ $\displaystyle\ell(\beta^{t})\geq$ $\displaystyle~{}\beta^{t}\|\mathbf{A}\|_{2}^{2}.$ $\displaystyle\ell(\beta^{t})\leq$ $\displaystyle~{}\tfrac{\beta^{t}L_{f}}{\beta^{0}}+\beta^{t}\|\mathbf{A}\|_{2}^{2}+\tfrac{\beta^{t}}{\beta^{0}}\tfrac{2}{\underline{\alpha}}W_{d}.$ $$

∎

###### Proof.

## Appendix E Proofs for Section 5

### E.1 Proof of Lemma 5.10

###### Proof.

We define $\SS(\mathbf{x},\mathbf{y};\mathbf{z};\beta)\triangleq f(\mathbf{x})+\langle\mathbf{A}\mathbf{x}-\mathbf{y},\mathbf{z}\rangle+\frac{\beta}{2}\|\mathbf{A}\mathbf{x}-\mathbf{y}\|_{2}^{2}$.

We define $s(\mathbf{x})\triangleq\SS(\mathbf{x},\mathbf{y}^{t},\mathbf{z}^{t};\beta^{t})$, where $t$ is known from context.

We define $\mathcal{L}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)\triangleq\tfrac{1}{d(\mathbf{x})}\cdot\mathcal{U}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)$.

We define $\mathcal{U}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)\triangleq\SS(\mathbf{x},\mathbf{y};\mathbf{z};\beta)+\delta(\mathbf{x})-g(\mathbf{x})+h_{\mu}(\mathbf{y})$.

We define $\ell(\beta^{t})\triangleq L_{f}+\beta^{t}\|\mathbf{A}\|_{2}^{2}+\lambda^{t}W_{d}$, where $\lambda^{t}=\tfrac{\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})}{d(\mathbf{x}^{t})}$.

We define $\varepsilon_{x}\triangleq{(\theta-1)\underline{\ell}}/{(2\overline{\rm{d}})}>0$.

Initially, using the optimality condition of $\mathbf{x}^{t+1}\in\arg\min_{\mathbf{x}}\dot{\mathcal{M}}^{t}(\mathbf{x};\mathbf{x}^{t},\lambda^{t})$, we have: $\dot{\mathcal{M}}^{t}(\mathbf{x}^{t+1};\mathbf{x}^{t},\lambda^{t})\leq\dot{\mathcal{M}}^{t}(\mathbf{x}^{t};\mathbf{x}^{t},\lambda^{t})$. This leads to $\langle\mathbf{x}^{t+1}-\mathbf{x}^{t},\nabla s(\mathbf{x}^{t})-\partial g(\mathbf{x}^{t})-\lambda^{t}\partial d(\mathbf{x}^{t})\rangle+\tfrac{\theta\ell(\beta^{t})}{2}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}+\delta(\mathbf{x}^{t+1})\leq 0+0+\delta(\mathbf{x}^{t})$. Rearranging terms yields:

$$ $\displaystyle~{}\delta(\mathbf{x}^{t+1})-\delta(\mathbf{x}^{t})+\tfrac{\theta\ell(\beta^{t})}{2}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}$ $\displaystyle\overset{}{\leq}$ $\displaystyle~{}\langle\mathbf{x}^{t}-\mathbf{x}^{t+1},\nabla s(\mathbf{x}^{t})-\partial g(\mathbf{x}^{t})-\lambda^{t}\partial d(\mathbf{x}^{t})\rangle$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}s(\mathbf{x}^{t})-s(\mathbf{x}^{t+1})+\tfrac{L_{f}+\beta^{t}\|\mathbf{A}\|_{2}^{2}}{2}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}+g(\mathbf{x}^{t+1})-g(\mathbf{x}^{t})$ $\displaystyle~{}+\lambda^{t}(d(\mathbf{x}^{t+1})-d(\mathbf{x}^{t}))+\lambda^{t}\tfrac{W_{d}}{2}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}$ $\displaystyle\overset{\text{\char 173}}{=}$ $\displaystyle~{}s(\mathbf{x}^{t})-s(\mathbf{x}^{t+1})+\tfrac{\ell(\beta^{t})}{2}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}+g(\mathbf{x}^{t+1})-g(\mathbf{x}^{t})+\lambda^{t}(d(\mathbf{x}^{t+1})-d(\mathbf{x}^{t})),$ (30) $$

where step ① uses the facts that the function $s(\mathbf{x})$ is $(L_{f}+\beta^{t}\|\mathbf{A}\|_{2}^{2})$-smooth w.r.t. $\mathbf{x}$, $\lambda^{t}>0$, $g(\mathbf{x})$ is convex, and $d(\mathbf{x})$ is $W_{d}$-weakly convex, yielding the following inequalities:

$$ $\displaystyle s(\mathbf{x}^{t+1})-s(\mathbf{x}^{t})\leq$ $\displaystyle~{}\langle\mathbf{x}^{t+1}-\mathbf{x}^{t},\nabla s(\mathbf{x}^{t})\rangle+\tfrac{L_{f}+\beta^{t}\|\mathbf{A}\|_{2}^{2}}{2}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2},$ $\displaystyle g(\mathbf{x}^{t})-g(\mathbf{x}^{t+1})\leq$ $\displaystyle~{}\langle\partial g(\mathbf{x}^{t}),\mathbf{x}^{t}-\mathbf{x}^{t+1}\rangle,$ $\displaystyle\lambda^{t}d(\mathbf{x}^{t})-\lambda^{t}d(\mathbf{x}^{t+1})\leq$ $\displaystyle~{}\lambda^{t}\langle\partial d(\mathbf{x}^{t}),\mathbf{x}^{t}-\mathbf{x}^{t+1}\rangle+\lambda^{t}\tfrac{W_{d}}{2}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2};$ (31) $$

step ② uses the definition of $\ell(\beta^{t})=L_{f}+\beta^{t}\|\mathbf{A}\|_{2}^{2}+\lambda^{t}W_{d}$.

We further derive:

$$ $\displaystyle~{}\mathcal{L}(\mathbf{x}^{t+1},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})-\mathcal{L}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$ $\displaystyle\overset{\text{\char 172}}{=}$ $\displaystyle~{}\textstyle\tfrac{1}{d(\mathbf{x}^{t+1})}\{h_{\mu^{t}}(\mathbf{y}^{t})+\delta(\mathbf{x}^{t+1})+s(\mathbf{x}^{t+1})-g(\mathbf{x}^{t+1})\}-\lambda^{t}$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}\textstyle\tfrac{1}{d(\mathbf{x}^{t+1})}\{h_{\mu^{t}}(\mathbf{y}^{t})+\delta(\mathbf{x}^{t})-g(\mathbf{x}^{t})+\tfrac{\ell(\beta^{t})(1-\theta)}{2}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}+s(\mathbf{x}^{t})-\lambda^{t}d(\mathbf{x}^{t})\}+\lambda^{t}-\lambda^{t}$ $\displaystyle\overset{\text{\char 174}}{=}$ $\displaystyle~{}\textstyle\tfrac{1}{d(\mathbf{x}^{t+1})}\{h_{\mu^{t}}(\mathbf{y}^{t})+\delta(\mathbf{x}^{t})-g(\mathbf{x}^{t})+\tfrac{\ell(\beta^{t})(1-\theta)}{2}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}-\{\delta(\mathbf{x}^{t})-g(\mathbf{x}^{t})+h_{\mu^{t}}(\mathbf{y}^{t})\}\}$ $\displaystyle\overset{}{=}$ $\displaystyle~{}\tfrac{1}{d(\mathbf{x}^{t+1})}\tfrac{\ell(\beta^{t})(1-\theta)}{2}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}$ $\displaystyle\overset{\text{\char 175}}{\leq}$ $\displaystyle~{}\tfrac{\ell(\beta^{t})\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}}{2\overline{\rm{d}}}\cdot\{1-\theta\}$ $\displaystyle\overset{\text{\char 176}}{\leq}$ $\displaystyle~{}-\varepsilon_{x}\beta^{t}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2},$ $$

where step ① uses the definition of $\mathcal{L}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})=\lambda^{t}$; step ② uses Inequality ([E.1](#A5.Ex107)); step ③ uses $\lambda^{t}d(\mathbf{x}^{t})-s(\mathbf{x}^{t})=\delta(\mathbf{x}^{t})-g(\mathbf{x}^{t})+h_{\mu^{t}}(\mathbf{y}^{t})$; step ④ uses $d(\mathbf{x})\leq\overline{\rm{d}}$ and $\theta>1$; step ⑤ uses the definition of $\varepsilon_{x}\triangleq{(\theta-1)\underline{\ell}}/{(2\overline{\rm{d}})}>0$.

∎

###### Proof.

### E.2 Proof of Lemma 5.11

###### Proof.

We define $\mathcal{L}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)\triangleq\tfrac{1}{d(\mathbf{x})}\cdot\{f(\mathbf{x})-g(\mathbf{x})+h_{\mu}(\mathbf{y})+\langle\mathbf{A}\mathbf{x}-\mathbf{y},\mathbf{z}\rangle+\frac{\beta}{2}\|\mathbf{A}\mathbf{x}-\mathbf{y}\|_{2}^{2}\}$.

We define $\mathbb{T}^{t}\triangleq 12(1+\xi)C_{h}^{2}/(\beta^{0}\underline{\rm{d}}t)$, and $\mathbb{T}^{t}\triangleq C^{2}_{h}\mu^{t}/(2\underline{\rm{d}})$.

We define $\varepsilon_{z}\triangleq\xi/(2\overline{\rm{d}})$, and $\varepsilon_{y}\triangleq\{1-4(1+\xi)/\chi^{2}\}/(2\overline{\rm{d}})$.

First, we focus on a decrease for the function $\mathcal{L}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)$ w.r.t. $\mathbf{y}$. We have:

$$ $\displaystyle~{}\mathcal{L}(\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t};\beta^{t},\mu^{t})-\mathcal{L}(\mathbf{x}^{t+1},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$ $\displaystyle\overset{\text{\char 172}}{=}$ $\displaystyle~{}\tfrac{1}{d(\mathbf{x}^{t+1})}\{\langle\mathbf{y}^{t}-\mathbf{y}^{t+1},\mathbf{z}^{t}\rangle+\tfrac{\beta^{t}}{2}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|_{2}^{2}-\tfrac{\beta^{t}}{2}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}+h_{\mu^{t}}(\mathbf{y}^{t+1})-h_{\mu^{t}}(\mathbf{y}^{t})\}$ $\displaystyle\overset{\text{\char 173}}{=}$ $\displaystyle~{}\tfrac{1}{d(\mathbf{x}^{t+1})}\{\langle\mathbf{y}^{t}-\mathbf{y}^{t+1},\mathbf{z}^{t}+\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1})\rangle+h_{\mu^{t}}(\mathbf{y}^{t+1})-h_{\mu^{t}}(\mathbf{y}^{t})-\tfrac{\beta^{t}}{2}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}\}$ $\displaystyle\overset{\text{\char 174}}{=}$ $\displaystyle~{}\tfrac{1}{d(\mathbf{x}^{t+1})}\{\langle\mathbf{y}^{t}-\mathbf{y}^{t+1},\mathbf{z}^{t+1}\rangle+h_{\mu^{t}}(\mathbf{y}^{t+1})-h_{\mu^{t}}(\mathbf{y}^{t})-\tfrac{\beta^{t}}{2}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}\}$ $\displaystyle\overset{\text{\char 175}}{\leq}$ $\displaystyle~{}\tfrac{1}{d(\mathbf{x}^{t+1})}\{\langle\mathbf{y}^{t}-\mathbf{y}^{t+1},\mathbf{z}^{t+1}-\nabla h_{\mu^{t}}(\mathbf{y}^{t+1})\rangle-\tfrac{\beta^{t}}{2}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}\}$ $\displaystyle\overset{\text{\char 176}}{=}$ $\displaystyle~{}\tfrac{-\beta^{t}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}}{2d(\mathbf{x}^{t+1})},$ (32) $$

where step ① uses the definition of $\mathcal{L}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)$; step ② uses the Pythagoras relation that $\frac{1}{2}\|\mathbf{a}-\mathbf{c}\|_{2}^{2}-\frac{1}{2}\|\mathbf{b}-\mathbf{c}\|_{2}^{2}=-\frac{1}{2}\|\mathbf{a}-\mathbf{b}\|_{2}^{2}+\langle\mathbf{a}-\mathbf{c},\mathbf{a}-\mathbf{b}\rangle$; step ③ uses $\mathbf{z}^{t+1}-\mathbf{z}^{t}=\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1})$; step ④ uses the convexity of $h_{\mu^{t}}(\cdot)$; step ⑤ uses the optimality for $\mathbf{y}^{t+1}$ as in Claim (a) of Lemma [5.3](#S5.Thmtheorem3) that: $\nabla h_{\mu^{t}}(\mathbf{y}^{t+1})=\mathbf{z}^{t+1}$.

Second, we focus on a decrease for the function $\mathcal{L}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)$ w.r.t. $\{\mathbf{z},\beta\}$. We have:

$$ $\displaystyle~{}\tfrac{\xi}{2\overline{\rm{d}}}\tfrac{1}{\beta}\|\mathbf{z}^{t+1}-\mathbf{z}^{t}\|_{2}^{2}+\mathcal{L}(\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t+1};\beta^{t+1},\mu^{t})-\mathcal{L}(\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t};\beta^{t},\mu^{t})$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}\tfrac{\xi}{2d(\mathbf{x}^{t+1})}\tfrac{1}{\beta^{t}}\|\mathbf{z}^{t+1}-\mathbf{z}^{t}\|_{2}^{2}+\{\mathcal{L}(\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t+1};\beta^{t},\mu^{t})-\mathcal{L}(\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t};\beta^{t},\mu^{t})\}$ $\displaystyle~{}+\{\mathcal{L}(\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t+1};\beta^{t+1},\mu^{t})-\mathcal{L}(\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t+1};\beta^{t},\mu^{t})\}$ $\displaystyle\overset{\text{\char 173}}{=}$ $\displaystyle~{}\tfrac{1}{d(\mathbf{x}^{t+1})}\cdot\{\tfrac{\xi}{2\beta^{t}}\|\mathbf{z}^{t+1}-\mathbf{z}^{t}\|_{2}^{2}+\langle\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1},\mathbf{z}^{t+1}-\mathbf{z}^{t}\rangle+\tfrac{(\beta^{t+1}-\beta^{t})\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|_{2}^{2}}{2}\}$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}\tfrac{1}{d(\mathbf{x}^{t+1})}\cdot\{\tfrac{\xi}{2\beta^{t}}\|\mathbf{z}^{t+1}-\mathbf{z}^{t}\|_{2}^{2}+\tfrac{\|\mathbf{z}^{t+1}-\mathbf{z}^{t}\|_{2}^{2}}{\beta^{t}}+\tfrac{(\beta^{t}(1+\xi)-\beta^{t})\|\mathbf{z}^{t+1}-\mathbf{z}^{t}\|_{2}^{2}}{2(\beta^{t})^{2}}\}$ $\displaystyle\overset{}{=}$ $\displaystyle~{}\tfrac{1}{d(\mathbf{x}^{t+1})}(\tfrac{\xi}{2}+1+\tfrac{\xi}{2})\tfrac{1}{\beta^{t}}\|\mathbf{z}^{t+1}-\mathbf{z}^{t}\|_{2}^{2}$ $\displaystyle\overset{\text{\char 175}}{\leq}$ $\displaystyle~{}\tfrac{1}{d(\mathbf{x}^{t+1})}\tfrac{1+\xi}{\beta^{t}}\{\tfrac{2(\beta^{t})^{2}}{\chi^{2}}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}+12C_{h}^{2}(\tfrac{1}{t}-\tfrac{1}{t+1})\}$ $\displaystyle\overset{\text{\char 177}}{\leq}$ $\displaystyle~{}\{\tfrac{1}{d(\mathbf{x}^{t+1})}\tfrac{2(1+\xi)}{\chi^{2}}\beta^{t}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}\}+\tfrac{12(1+\xi)C_{h}^{2}}{\beta^{0}\underline{\rm{d}}}(\tfrac{1}{t}-\tfrac{1}{t+1}),$ (33) $$

where step ① uses $d(\mathbf{x}^{t+1})\leq\overline{\rm{d}}$; step ② uses the definition of $\mathcal{L}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)$; step ③ uses $\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1})=\mathbf{z}^{t+1}-\mathbf{z}^{t}$ and $\beta^{t+1}\leq\beta^{t}(1+\xi)$; step ④ uses Claim (b) of Lemma [5.4](#S5.Thmtheorem4); step ⑤ uses Lemma [5.4](#S5.Thmtheorem4); step ⑥ uses $d(\mathbf{x}^{t+1})\geq\underline{\rm{d}}$, and $\beta^{t}\geq\beta^{0}$.

Third, we focus on a decrease for the function $\mathcal{L}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)$ w.r.t. $\mu$. We have:

$$ $\displaystyle~{}\mathcal{L}(\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t+1};\beta^{t+1},\mu^{t+1})-\mathcal{L}(\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t+1};\beta^{t+1},\mu^{t})$ $\displaystyle=$ $\displaystyle~{}\tfrac{1}{d(\mathbf{x}^{t+1})}\{h_{\mu^{t+1}}(\mathbf{y}^{t+1})-h_{\mu^{t}}(\mathbf{y}^{t+1})\}$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}\tfrac{1}{2d(\mathbf{x}^{t+1})}(\mu^{t}-\mu^{t+1})\cdot C^{2}_{h}$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}\tfrac{1}{2\underline{\rm{d}}}(\mu^{t}-\mu^{t+1})\cdot C^{2}_{h},$ (34) $$

where step ① uses Claim (e) of Lemma [3.9](#S3.Thmtheorem9); step ② uses $d(\mathbf{x}^{t})\geq\underline{\rm{d}}$.

Adding Inequalities ([32](#A5.E32)), ([E.2](#A5.Ex125)), and ([E.2](#A5.Ex132)), we have:

$$ $\displaystyle~{}\mathcal{L}(\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t+1};\beta^{t+1},\mu^{t+1})-\mathcal{L}(\mathbf{x}^{t+1},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})+\mathbb{T}^{t+1}+\mathbb{U}^{t+1}-\mathbb{T}^{t}-\mathbb{U}^{t}$ $\displaystyle\leq$ $\displaystyle~{}-\varepsilon_{z}\beta^{t}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|_{2}^{2}-\tfrac{1}{2d(\mathbf{x}^{t+1})}\cdot\beta^{t}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}\cdot\{1-\tfrac{4(1+\xi)}{\chi^{2}}\}$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}-\varepsilon_{z}\beta^{t}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|_{2}^{2}-\beta^{t}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}\cdot\varepsilon_{y},$ $$

where step ① uses the definition of $\varepsilon_{y}\triangleq\{1-4(1+\xi)/\chi^{2}\}/(2\overline{\rm{d}})$.

∎

###### Proof.

### E.3 Proof of Lemma 5.12

###### Proof.

We define $\mathbb{L}^{t}\triangleq\mathcal{L}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$, and $\mathbb{T}^{t}=12(1+\xi)C_{h}^{2}/(\beta^{0}\underline{\rm{d}}t)$, and $\mathbb{U}^{t}=C_{h}^{2}\mu^{t}/(2\underline{\rm{d}})$.

We define $\mathbb{P}^{t}\triangleq\mathbb{L}^{t}+\mathbb{T}^{t}+\mathbb{U}^{t}$.

Part (a). We derive the following inequalities:

$$ $\displaystyle\textstyle\mathbb{P}^{t}\overset{}{\triangleq}$ $\displaystyle~{}\textstyle\mathbb{L}^{t}+\mathbb{T}^{t}+\mathbb{U}^{t}$ $\displaystyle\overset{\text{\char 172}}{\geq}$ $\displaystyle~{}\textstyle\mathcal{L}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})+0$ $\displaystyle\overset{\text{\char 173}}{\geq}$ $\displaystyle~{}\textstyle\tfrac{\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})}{d(\mathbf{x}^{t})}$ $\displaystyle\overset{\text{\char 174}}{\geq}$ $\displaystyle~{}\textstyle\tfrac{\underline{\rm{F}}\underline{\rm{d}}-\underline{\rm{v}}/\beta^{t}}{\overline{\rm{d}}}$ $\displaystyle\overset{\text{\char 175}}{\geq}$ $\displaystyle~{}\textstyle\tfrac{\underline{\rm{F}}\underline{\rm{d}}-\underline{\rm{v}}/\beta^{0}}{\overline{\rm{d}}}\triangleq\underline{\mathbb{P}},$ $$

where step ① uses $\mathbb{T}^{t}\geq 0$ and $\mathbb{U}^{t}\geq 0$; step ② uses the definition of $\mathcal{L}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$; step ③ uses $d(\mathbf{x}^{t})\leq\overline{\rm{d}}$, and the lower bound of $\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$ in Lemma [5.6](#S5.Thmtheorem6); step ④ uses $\beta^{t}\geq\beta^{0}$.

Part (b). Combing Lemmas ([5.10](#S5.Thmtheorem10)) and ([5.11](#S5.Thmtheorem11)) together, we have:

$$ $\displaystyle\varepsilon_{y}\beta^{t}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}+\varepsilon_{x}\beta^{t}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}+\varepsilon_{z}\beta^{t}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|_{2}^{2}$ $\displaystyle\leq$ $\displaystyle\mathbb{L}^{t}-\mathbb{L}^{t}+\mathbb{T}^{t}-\mathbb{T}^{t+1}+\mathbb{U}^{t}-\mathbb{U}^{t+1}$ $\displaystyle=$ $\displaystyle\mathbb{P}^{t}-\mathbb{P}^{t+1}.$ $$

∎

###### Proof.

### E.4 Proof of Theorem 5.13

###### Proof.

We define $c_{0}\triangleq\tfrac{1}{\min(\varepsilon_{x},\varepsilon_{y},\varepsilon_{z})}\cdot\{\mathbb{P}^{1}-\underline{\mathbb{P}}\}$.

We define $\mathcal{E}^{t}\triangleq\beta^{t}\{\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}+\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}+\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|_{2}^{2}\}$.

We define $\mathcal{E}_{+}^{t}\triangleq\beta^{t}\{\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|+\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|+\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|\}$.

Using Lemma [5.12](#S5.Thmtheorem12), we have:

$$ $\displaystyle 0\leq-\min(\varepsilon_{x},\varepsilon_{y},\varepsilon_{z})\mathcal{E}^{t}+\mathbb{P}^{t}-\mathbb{P}^{t+1}.$ (35) $$

Telescoping Inequality ([35](#A5.E35)) over $t$ from $1$ to $T$, we have:

$$ $\displaystyle\textstyle\textstyle 0\leq$ $\displaystyle~{}\textstyle\tfrac{1}{\min(\varepsilon_{x},\varepsilon_{y},\varepsilon_{z})}\cdot\sum_{t=1}^{T}\{\mathbb{P}^{t}-\mathbb{P}^{t+1}\}-\sum_{t=1}^{T}\mathcal{E}^{t}$ $\displaystyle=$ $\displaystyle~{}\textstyle\tfrac{1}{\min(\varepsilon_{x},\varepsilon_{y},\varepsilon_{z})}\cdot\{\mathbb{P}^{1}-\mathbb{P}^{T+1}\}-\sum_{t=1}^{T}\mathcal{E}^{t}$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}\textstyle\tfrac{1}{\min(\varepsilon_{x},\varepsilon_{y},\varepsilon_{z})}\cdot\{\mathbb{P}^{1}-\underline{\mathbb{P}}\}-\sum_{t=1}^{T}\mathcal{E}^{t}$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}\textstyle c_{0}-\tfrac{1}{\beta^{T}}\sum_{t=1}^{T}\|\beta^{t}(\mathbf{x}^{t+1}-\mathbf{x}^{t})\|_{2}^{2}+\|\beta^{t}(\mathbf{y}^{t+1}-\mathbf{y}^{t})\|_{2}^{2}+\|\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1})\|_{2}^{2}$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}\textstyle c_{0}-\tfrac{1}{\beta^{T}}\tfrac{1}{3T}\{\sum_{t=1}^{T}\|\beta^{t}(\mathbf{x}^{t+1}-\mathbf{x}^{t})\|+\|\beta^{t}(\mathbf{y}^{t+1}-\mathbf{y}^{t})\|+\|\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1})\|\}^{2}$ $\displaystyle\overset{\text{\char 175}}{\leq}$ $\displaystyle~{}\textstyle c_{0}-\tfrac{1}{\beta^{T}3T}\{\sum_{t=1}^{T}\mathcal{E}_{+}^{t}\}^{2}$ (36) $$

where step ① uses $\mathbb{P}^{t}\geq\underline{\mathbb{P}}$ for all $t$; step ② uses the definition of $c_{0}$, the definition of $\mathcal{E}^{t}$, and the Hölder’s inequality that $\langle\mathbf{a},\mathbf{b}\rangle\leq\|\mathbf{a}\|_{1}\|\mathbf{b}\|_{\infty}$; step ③ uses the fact that $\|\mathbf{a}\|_{2}^{2}\geq\tfrac{1}{n}\|\mathbf{a}\|_{1}^{2}$; step ④ uses the definition of $\mathcal{E}_{+}^{t}$. We further obtain from Inequality ([E.8](#A5.Ex191)) that

$$ $\displaystyle\textstyle\sum_{t=1}^{T}\mathcal{E}_{+}^{t}\leq(3W)^{1/2}(\beta^{T}T)^{1/2}~{}~{}~{}~{}\overset{\text{\char 172}}{\Rightarrow}~{}~{}~{}~{}\textstyle\tfrac{1}{T}\sum_{t=1}^{T}\mathcal{E}_{+}^{t}\leq\mathcal{O}(T^{(p-1)/2}),$ $$

where step ① $\beta^{t}=\beta^{0}(1+\xi t^{p})=\mathcal{O}(t^{p})$.

∎

###### Proof.

### E.5 Proof of Lemma 5.15

###### Proof.

We define $\SS(\mathbf{x},\mathbf{y};\mathbf{z};\beta)\triangleq f(\mathbf{x})+\langle\mathbf{A}\mathbf{x}-\mathbf{y},\mathbf{z}\rangle+\frac{\beta}{2}\|\mathbf{A}\mathbf{x}-\mathbf{y}\|_{2}^{2}$.

We define $s(\mathbf{x})\triangleq\SS(\mathbf{x},\mathbf{y}^{t},\mathbf{z}^{t};\beta^{t})$, where $t$ is known from context.

We define $\mathcal{K}(\alpha,\mathbf{x},\mathbf{y},\mathbf{z};\beta,\mu)=-2\alpha\sqrt{d(\mathbf{x})}+\alpha^{2}\mathcal{U}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)$.

We define $\mathcal{U}(\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)\triangleq\SS(\mathbf{x},\mathbf{y};\mathbf{z};\beta)+\delta(\mathbf{x})-g(\mathbf{x})+h_{\mu}(\mathbf{y})$.

We define $\ell(\beta^{t})\triangleq L_{f}+\beta^{t}\|\mathbf{A}\|_{2}^{2}+\tfrac{2}{\alpha^{t+1}}W_{d}$, where $\alpha^{t+1}=\sqrt{d(\mathbf{x}^{t})}/\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$.

We define $\varepsilon_{x}\triangleq\tfrac{1}{2}\underline{\alpha}^{2}\underline{\ell}(\theta-1)$.

Initially, using the optimality condition of $\mathbf{x}^{t+1}\in\arg\min_{\mathbf{x}}\ddot{\mathcal{M}}^{t}(\mathbf{x};\mathbf{x}^{t},\alpha^{t+1})$, we have $\ddot{\mathcal{M}}^{t}(\mathbf{x}^{t+1};\mathbf{x}^{t},\alpha^{t+1})\leq\ddot{\mathcal{M}}^{t}(\mathbf{x}^{t};\mathbf{x}^{t},\alpha^{t+1})$. This results in $\langle\mathbf{x}^{t+1}-\mathbf{x}^{t},\nabla s(\mathbf{x}^{t})-\partial g(\mathbf{x}^{t})-\tfrac{2}{\alpha^{t+1}}\partial\sqrt{d(\mathbf{x}^{t})}\rangle+\tfrac{\theta\ell(\beta^{t})}{2}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}+\delta(\mathbf{x}^{t+1})\leq 0+0+\delta(\mathbf{x}^{t})$. Rearranging terms yields:

$$ $\displaystyle~{}\delta(\mathbf{x}^{t+1})-\delta(\mathbf{x}^{t})+\tfrac{\theta\ell(\beta^{t})}{2}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}$ $\displaystyle\overset{}{\leq}$ $\displaystyle~{}\langle\mathbf{x}^{t}-\mathbf{x}^{t+1},\nabla s(\mathbf{x}^{t})-\partial g(\mathbf{x}^{t})-\tfrac{2}{\alpha^{t+1}}\partial\sqrt{d(\mathbf{x}^{t})}\rangle$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}s(\mathbf{x}^{t})-s(\mathbf{x}^{t+1})+\tfrac{L_{f}+\beta^{t}\|\mathbf{A}\|_{2}^{2}}{2}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}+g(\mathbf{x}^{t+1})-g(\mathbf{x}^{t})$ $\displaystyle~{}+\tfrac{2}{\alpha^{t+1}}\{\sqrt{d(\mathbf{x}^{t})}-\sqrt{d(\mathbf{x}^{t+1})}+\tfrac{W_{d}}{2}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}\}$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}s(\mathbf{x}^{t})-s(\mathbf{x}^{t+1})+\tfrac{\ell(\beta^{t})}{2}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}+g(\mathbf{x}^{t+1})-g(\mathbf{x}^{t})-\tfrac{2}{\alpha^{t+1}}[\sqrt{d(\mathbf{x}^{t})}-\sqrt{d(\mathbf{x}^{t+1})}]$ $$

where step ① uses the facts that the function $s(\mathbf{x})$ is $(L_{f}+\beta^{t}\|\mathbf{A}\|_{2}^{2})$-smooth w.r.t. $\mathbf{x}$, $\alpha^{t+1}>0$, $g(\mathbf{x})$ is convex, and $\sqrt{d(\mathbf{x})}$ is $W_{d}$-weakly convex, yielding the following inequalities:

$$ $\displaystyle s(\mathbf{x}^{t+1})$ $\displaystyle\leq$ $\displaystyle s(\mathbf{x}^{t})+\langle\mathbf{x}^{t+1}-\mathbf{x}^{t},\nabla_{\mathbf{x}}s(\mathbf{x}^{t})\rangle+\tfrac{L_{f}+\beta^{t}\|\mathbf{A}\|_{2}^{2}}{2}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}$ $\displaystyle g(\mathbf{x}^{t})$ $\displaystyle\leq$ $\displaystyle g(\mathbf{x}^{t+1})+\langle\mathbf{x}^{t}-\mathbf{x}^{t+1},\partial g(\mathbf{x}^{t})\rangle$ $\displaystyle\tfrac{2}{\alpha^{t+1}}\{\sqrt{d(\mathbf{x}^{t})}-\sqrt{d(\mathbf{x}^{t+1})}\}$ $\displaystyle\leq$ $\displaystyle\tfrac{2}{\alpha^{t+1}}\{\langle\partial\sqrt{d(\mathbf{x}^{t})},\mathbf{x}^{t}-\mathbf{x}^{t+1}\rangle+\tfrac{W_{d}}{2}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}\};$ (38) $$

step ② uses the definition of $\ell(\beta^{t})=L_{f}+\beta^{t}\|\mathbf{A}\|_{2}^{2}+\tfrac{2}{\lambda^{t+1}}W_{d}$.

We further derive:

$$ $\displaystyle~{}\textstyle\mathcal{K}(\alpha^{t+1},\mathbf{x}^{t+1},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})-\mathcal{K}(\alpha^{t},\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}\textstyle\mathcal{K}(\alpha^{t+1},\mathbf{x}^{t+1},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})-\mathcal{K}(\alpha^{t+1},\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$ $\displaystyle\overset{\text{\char 173}}{=}$ $\displaystyle~{}\textstyle(\alpha^{t+1})^{2}\{s(\mathbf{x}^{t+1})-s(\mathbf{x}^{t})+\delta(\mathbf{x}^{t+1})-\delta(\mathbf{x}^{t})-g(\mathbf{x}^{t+1})+g(\mathbf{x}^{t})-\tfrac{2}{\alpha^{t+1}}[\sqrt{d(\mathbf{x}^{t+1})}-\sqrt{d(\mathbf{x}^{t})}]\}$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}\textstyle(\alpha^{t+1})^{2}\cdot\tfrac{(1-\theta)}{2}\ell(\beta^{t})\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}$ $\displaystyle\overset{\text{\char 175}}{\leq}$ $\displaystyle~{}\textstyle\underbrace{\tfrac{1}{2}\underline{\alpha}^{2}\underline{\ell}(1-\theta)}_{\triangleq-\varepsilon_{x}}\cdot\beta^{t}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2},$ $$

where step ① uses the fact that $\alpha^{t+1}=\arg\min_{\alpha}\mathcal{K}(\alpha,\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$, which implies the inequality $\mathcal{K}(\alpha^{t+1},\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})\leq\mathcal{K}(\alpha^{t},\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$; step ② uses the definition of the function $\mathcal{K}(\alpha,\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)$; step ③ uses Inequality ([E.5](#A5.Ex152)); step ④ uses $1-\theta<0$, $\alpha^{t}\geq\underline{\alpha}$, and $\ell(\beta^{t})\geq\beta^{t}\underline{\ell}$.

∎

###### Proof.

### E.6 Proof of Lemma 5.16

###### Proof.

We define $\mathcal{K}(\alpha,\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)=-2\alpha\sqrt{d(\mathbf{x})}+\alpha^{2}\{f(\mathbf{x})+\delta(\mathbf{x})-g(\mathbf{x})+h_{\mu}(\mathbf{y})+\langle\mathbf{A}\mathbf{x}-\mathbf{y},\mathbf{z}\rangle+\frac{\beta}{2}\|\mathbf{A}\mathbf{x}-\mathbf{y}\|_{2}^{2})\}$.

We define $\mathbb{T}^{t}\triangleq 12\overline{\alpha}^{2}(1+\xi)C_{h}^{2}/(\beta^{0}t)$, and $\mathbb{U}^{t}\triangleq\tfrac{1}{2}\overline{\alpha}^{2}C_{h}^{2}\mu^{t}$.

We define $\varepsilon_{z}\triangleq\tfrac{1}{2}\underline{\alpha}^{2}\xi$, and $\varepsilon_{y}\triangleq\tfrac{1}{2}\underline{\alpha}^{2}\{1-4(1+\xi)/(\chi^{2})\}$.

First, we focus on the sufficient decrease for variables $\mathbf{y}^{t+1}$, we have:

$$ $\displaystyle~{}\mathcal{K}(\alpha^{t+1},\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t};\beta^{t},\mu^{t})-\mathcal{K}(\alpha^{t+1},\mathbf{x}^{t+1},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$ $\displaystyle\overset{\text{\char 172}}{=}$ $\displaystyle~{}(\alpha^{t+1})^{2}\{\tfrac{\beta^{t}}{2}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|_{2}^{2}-\tfrac{\beta^{t}}{2}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}+h_{\mu^{t}}(\mathbf{y}^{t+1})-h_{\mu^{t}}(\mathbf{y}^{t})+\langle\mathbf{z}^{t},\mathbf{y}^{t}-\mathbf{y}^{t+1}\rangle\}$ $\displaystyle\overset{\text{\char 173}}{=}$ $\displaystyle~{}(\alpha^{t+1})^{2}\{\tfrac{\beta^{t}}{2}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|_{2}^{2}-\tfrac{\beta^{t}}{2}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}+\langle\mathbf{y}^{t+1}-\mathbf{y}^{t},\nabla h_{\mu^{t}}(\mathbf{y}^{t+1})-\mathbf{z}^{t}\rangle\}$ $\displaystyle\overset{\text{\char 174}}{=}$ $\displaystyle~{}(\alpha^{t+1})^{2}\{-\tfrac{\beta^{t}}{2}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}+\langle\mathbf{y}^{t+1}-\mathbf{y}^{t},\nabla h_{\mu^{t}}(\mathbf{y}^{t+1})-\mathbf{z}^{t}-\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1})\rangle\}$ $\displaystyle\overset{\text{\char 175}}{=}$ $\displaystyle~{}(\alpha^{t+1})^{2}\{-\tfrac{\beta^{t}}{2}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}+\langle\mathbf{y}^{t+1}-\mathbf{y}^{t},\nabla h_{\mu^{t}}(\mathbf{y}^{t+1})-\mathbf{z}^{t}-(\mathbf{z}^{t+1}-\mathbf{z}^{t})\rangle\}$ $\displaystyle\overset{\text{\char 176}}{=}$ $\displaystyle~{}-\beta^{t}(\alpha^{t+1})^{2}\tfrac{1}{2}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2},$ (39) $$

where step ① uses the definition of $\mathcal{K}(\alpha,\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)$; step ② uses the convexity of $h_{\mu^{t}}(\cdot)$ that $h_{\mu}(\mathbf{y}^{\prime})-h_{\mu}(\mathbf{y})\leq\langle\mathbf{y}^{\prime}-\mathbf{y},\nabla h_{\mu}(\mathbf{y}^{\prime})\rangle$ for all $\mathbf{y},\mathbf{y}^{\prime}\in\mathbb{R}^{m}$, and $\mu>0$; step ③ uses the Pythagoras relation that $\frac{1}{2}\|\mathbf{a}-\mathbf{c}\|_{2}^{2}-\frac{1}{2}\|\mathbf{b}-\mathbf{c}\|_{2}^{2}=-\frac{1}{2}\|\mathbf{a}-\mathbf{b}\|_{2}^{2}+\langle\mathbf{a}-\mathbf{c},\mathbf{a}-\mathbf{b}\rangle$; step ④ uses the optimality for $\mathbf{y}^{t+1}$ that: $\nabla h_{\mu^{t}}(\mathbf{y}^{t+1})=\mathbf{z}^{t}+\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1})$.

Second, we focus on the sufficient decrease for variables $\{\mathbf{z},\beta\}$. We have:

$$ $\displaystyle~{}\tfrac{1}{2}\xi\underline{\alpha}^{2}\beta^{t}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|_{2}^{2}+\mathcal{K}(\alpha^{t+1},\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t+1};\beta^{t+1},\mu^{t})-\mathcal{K}(\alpha^{t+1},\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t};\beta^{t},\mu^{t})$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}(\alpha^{t+1})^{2}\tfrac{\xi\|\mathbf{z}^{t+1}-\mathbf{z}^{t}\|_{2}^{2}}{2\beta^{t}}+\{\mathcal{K}(\alpha^{t+1},\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t+1};\beta^{t},\mu^{t})-\mathcal{K}(\alpha^{t+1},\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t};\beta^{t},\mu^{t})\}$ $\displaystyle~{}+\{K(\alpha^{t+1},\mathbf{x}^{t+1};\mathbf{y}^{t+1},\mathbf{z}^{t+1};\beta^{t+1},\mu^{t})-K(\alpha^{t+1},\mathbf{x}^{t+1},\mathbf{y}^{t+1},\mathbf{z}^{t+1};\beta^{t},\mu^{t})\}$ $\displaystyle\overset{\text{\char 173}}{=}$ $\displaystyle~{}(\alpha^{t+1})^{2}\cdot\{\tfrac{\xi\|\mathbf{z}^{t+1}-\mathbf{z}^{t}\|_{2}^{2}}{2\beta^{t}}+\langle\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1},\mathbf{z}^{t+1}-\mathbf{z}^{t}\rangle+\tfrac{\beta^{t+1}-\beta^{t}}{2}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|_{2}^{2}\}$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}(\alpha^{t+1})^{2}\cdot\{\tfrac{\xi}{2\beta^{t}}+\tfrac{1}{\beta^{t}}+\tfrac{\beta^{t}(1+\xi)-\beta^{t}}{2(\beta^{t})^{2}}\}\cdot\|\mathbf{z}^{t+1}-\mathbf{z}^{t}\|_{2}^{2}$ $\displaystyle\overset{}{=}$ $\displaystyle~{}(\alpha^{t+1})^{2}\cdot\{(1+\xi)\cdot\tfrac{1}{\beta^{t}}\}\cdot\|\mathbf{z}^{t+1}-\mathbf{z}^{t}\|_{2}^{2}$ $\displaystyle\overset{\text{\char 175}}{\leq}$ $\displaystyle~{}(\alpha^{t+1})^{2}(1+\xi)\tfrac{1}{\beta^{t}}\{\|\nabla h_{\mu^{t}}(\mathbf{y}^{t+1})-\nabla h_{\mu^{t-1}}(\mathbf{y}^{t})\|_{2}^{2}\}$ $\displaystyle\overset{\text{\char 176}}{\leq}$ $\displaystyle~{}(\alpha^{t+1})^{2}(1+\xi)\tfrac{1}{\beta^{t}}\cdot\{\tfrac{2(\beta^{t})^{2}}{\chi^{2}}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}+12C_{h}^{2}(\tfrac{1}{t}-\tfrac{1}{t+1})\}$ $\displaystyle\overset{\text{\char 177}}{\leq}$ $\displaystyle~{}\{(\alpha^{t+1})^{2}(1+\xi)\tfrac{2}{\chi^{2}}\beta^{t}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}\}+\tfrac{12(1+\xi)C_{h}^{2}\overline{\alpha}^{2}}{\beta^{0}}\cdot(\tfrac{1}{t}-\tfrac{1}{t+1}),$ (40) $$

where step ① uses $\underline{\alpha}\leq\alpha^{t}$; step ② uses the definition of $\mathcal{K}(\alpha,\mathbf{x},\mathbf{y};\mathbf{z};\beta,\mu)$; step ③ uses $\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1})=\mathbf{z}^{t+1}-\mathbf{z}^{t}$ and $\beta^{t+1}\leq\beta^{t}(1+\xi)$; step ④ uses Claim (b) of Lemma [5.4](#S5.Thmtheorem4); step ⑤ uses Lemma [5.4](#S5.Thmtheorem4); step ⑥ uses $\alpha^{t}\leq\overline{\alpha}$ for all $t\geq 1$.

Third, we focus on the sufficient decrease for variable $\mu$. We have:

$$ $\displaystyle~{}\mathcal{K}(\alpha^{t+1},\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t+1};\beta^{t+1},\mu^{t+1})-\mathcal{K}(\alpha^{t+1},\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t+1};\beta^{t+1},\mu^{t})$ $\displaystyle=$ $\displaystyle~{}(\alpha^{t+1})^{2}\cdot(h_{\mu^{t+1}}(\mathbf{y}^{t+1})-h_{\mu^{t}}(\mathbf{y}^{t+1}))$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}\tfrac{1}{2}C^{2}_{h}(\alpha^{t+1})^{2}\cdot(\mu^{t}-\mu^{t+1})$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}\tfrac{1}{2}C^{2}_{h}\overline{\alpha}^{2}(\mu^{t}-\mu^{t+1})=\mathbb{U}^{t}-\mathbb{U}^{t+1}$ (41) $$

where step ① uses Claim (e) of Lemma [3.9](#S3.Thmtheorem9); step ② uses $\alpha^{t}\leq\overline{\alpha}$ for all $t\geq 1$.

Adding Inequalities ([E.6](#A5.Ex164)), ([E.6](#A5.Ex169)), and ([E.6](#A5.Ex177)), we have:

$$ $\displaystyle~{}\mathcal{K}(\lambda^{t+1},\mathbf{x}^{t+1},\mathbf{y}^{t+1};\mathbf{z}^{t+1};\beta^{t+1},\mu^{t+1})-\mathcal{K}(\lambda^{t+1},\mathbf{x}^{t+1},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$ $\displaystyle\leq$ $\displaystyle~{}\mathbb{T}^{t}+\mathbb{U}^{t}-\mathbb{T}^{t+1}-\mathbb{U}^{t+1}-(\alpha^{t+1})^{2}\beta^{t}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}\cdot\tfrac{1}{2}\cdot\{1-4(1+\xi)/(\chi^{2})\}$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}\mathbb{T}^{t}+\mathbb{U}^{t}-\mathbb{T}^{t+1}-\mathbb{U}^{t+1}-\beta^{t}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}\cdot\varepsilon_{y},$ $$

where step ① uses $\alpha^{t+1}\geq\underline{\alpha}$, and the definition of $\varepsilon_{y}\triangleq\tfrac{1}{2}\underline{\alpha}^{2}\{1-4(1+\xi)/(\chi^{2})\}$.

∎

###### Proof.

### E.7 Proof of Lemma 5.17

###### Proof.

We define $\mathbb{P}^{t}\triangleq\mathbb{K}^{t}+\mathbb{T}^{t}+\mathbb{U}^{t}$.

We define $\mathbb{K}^{t}\triangleq\mathcal{K}(\alpha^{t},\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$, and $\mathbb{T}^{t}=12\overline{\alpha}^{2}(1+\xi)C_{h}^{2}/(\beta^{0}\underline{\rm{d}}t)$, and $\mathbb{U}^{t}=\tfrac{1}{2}C_{h}^{2}\overline{\alpha}^{2}\mu^{t}$.

Part (a). We derive the following inequalities:

$$ $\displaystyle\textstyle\mathbb{P}^{t}\overset{}{\triangleq}$ $\displaystyle~{}\textstyle\mathbb{K}^{t}+\mathbb{T}^{t}+\mathbb{U}^{t}$ $\displaystyle\overset{\text{\char 172}}{\geq}$ $\displaystyle~{}\textstyle\mathcal{K}(\alpha^{t},\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})+0$ $\displaystyle\overset{\text{\char 173}}{=}$ $\displaystyle~{}\textstyle-2\alpha^{t}\sqrt{d(\mathbf{x}^{t})}+(\alpha^{t})^{2}\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$ $\displaystyle\overset{\text{\char 174}}{\geq}$ $\displaystyle~{}\textstyle-2\overline{\alpha}\sqrt{\overline{\rm{d}}}+\underline{\alpha}^{2}\cdot\{\underline{\rm{F}}\underline{\rm{d}}-\underline{\rm{v}}/\beta^{t}\}$ $\displaystyle\overset{\text{\char 175}}{\geq}$ $\displaystyle~{}\textstyle-2\overline{\alpha}\sqrt{\overline{\rm{d}}}+\underline{\alpha}^{2}\cdot\{\underline{\rm{F}}\underline{\rm{d}}-\underline{\rm{v}}/\beta^{0}\}\triangleq\underline{\mathbb{P}},$ $$

where step ① uses $\mathbb{T}^{t}\geq 0$ and $\mathbb{U}^{t}\geq 0$; step ② uses the definition of $\mathcal{K}(\alpha^{t},\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$; step ③ uses $d(\mathbf{x}^{t})\leq\overline{\rm{d}}$, $\alpha^{t}\leq\overline{\alpha}$, and the lower bound of $\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$ in Lemma [5.6](#S5.Thmtheorem6); step ④ uses $\beta^{t}\geq\beta^{0}$.

Part (b). Combing Lemmas ([5.15](#S5.Thmtheorem15)) and ([5.16](#S5.Thmtheorem16)) together, we have:

$$ $\displaystyle\varepsilon_{y}\beta^{t}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}+\varepsilon_{x}\beta^{t}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}+\varepsilon_{z}\beta^{t}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|_{2}^{2}$ $\displaystyle\leq$ $\displaystyle\mathbb{K}^{t}-\mathbb{K}^{t}+\mathbb{T}^{t}-\mathbb{T}^{t+1}+\mathbb{U}^{t}-\mathbb{U}^{t+1}$ $\displaystyle=$ $\displaystyle\mathbb{P}^{t}-\mathbb{P}^{t+1}.$ $$

∎

###### Proof.

### E.8 Proof of Theorem 5.18

###### Proof.

We define $c_{0}\triangleq\tfrac{1}{\min(\varepsilon_{x},\varepsilon_{y},\varepsilon_{z})}\cdot\{\mathbb{P}^{1}-\underline{\mathbb{P}}\}$.

We define $\mathcal{E}^{t}\triangleq\beta^{t}\{\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|_{2}^{2}+\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|_{2}^{2}+\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|_{2}^{2}\}$.

We define $\mathcal{E}_{+}^{t}\triangleq\beta^{t}\{\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|+\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|+\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|\}$.

Using Lemma [5.17](#S5.Thmtheorem17), we have:

$$ $\displaystyle 0\leq-\min(\varepsilon_{x},\varepsilon_{y},\varepsilon_{z})\mathcal{E}^{t}+\mathbb{P}^{t}-\mathbb{P}^{t+1}.$ (42) $$

Telescoping Inequality ([42](#A5.E42)) over $t$ from $1$ to $T$, we have:

$$ $\displaystyle\textstyle\textstyle 0\leq$ $\displaystyle~{}\textstyle\tfrac{1}{\min(\varepsilon_{x},\varepsilon_{y},\varepsilon_{z})}\cdot\sum_{t=1}^{T}\{\mathbb{P}^{t}-\mathbb{P}^{t+1}\}-\sum_{t=1}^{T}\mathcal{E}^{t}$ $\displaystyle=$ $\displaystyle~{}\textstyle\tfrac{1}{\min(\varepsilon_{x},\varepsilon_{y},\varepsilon_{z})}\cdot\{\mathbb{P}^{1}-\mathbb{P}^{T+1}\}-\sum_{t=1}^{T}\mathcal{E}^{t}$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}\textstyle\tfrac{1}{\min(\varepsilon_{x},\varepsilon_{y},\varepsilon_{z})}\cdot\{\mathbb{P}^{1}-\underline{\mathbb{P}}\}-\sum_{t=1}^{T}\mathcal{E}^{t}$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}\textstyle c_{0}-\tfrac{1}{\beta^{T}}\sum_{t=1}^{T}\|\beta^{t}(\mathbf{x}^{t+1}-\mathbf{x}^{t})\|_{2}^{2}+\|\beta^{t}(\mathbf{y}^{t+1}-\mathbf{y}^{t})\|_{2}^{2}+\|\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1})\|_{2}^{2}$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}\textstyle c_{0}-\tfrac{1}{\beta^{T}}\tfrac{1}{3T}\{\sum_{t=1}^{T}\|\beta^{t}(\mathbf{x}^{t+1}-\mathbf{x}^{t})\|+\|\beta^{t}(\mathbf{y}^{t+1}-\mathbf{y}^{t})\|+\|\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1})\|\}^{2}$ $\displaystyle\overset{\text{\char 175}}{\leq}$ $\displaystyle~{}\textstyle c_{0}-\tfrac{1}{\beta^{T}3T}\{\sum_{t=1}^{T}\mathcal{E}_{+}^{t}\}^{2}$ (43) $$

where step ① uses $\mathbb{P}^{t}\geq\underline{\mathbb{P}}$ for all $t$; step ② uses the definition of $c_{0}$, the definition of $\mathcal{E}^{t}$, and the Hölder’s inequality that $\langle\mathbf{a},\mathbf{b}\rangle\leq\|\mathbf{a}\|_{1}\|\mathbf{b}\|_{\infty}$; step ③ uses the fact that $\|\mathbf{a}\|_{2}^{2}\geq\tfrac{1}{n}\|\mathbf{a}\|_{1}^{2}$; step ④ uses the definition of $\mathcal{E}_{+}^{t}$. We further obtain from Inequality ([E.8](#A5.Ex191)) that

$$ $\displaystyle\textstyle\sum_{t=1}^{T}\mathcal{E}_{+}^{t}\leq(3W)^{1/2}(\beta^{T}T)^{1/2}~{}~{}~{}~{}\overset{\text{\char 172}}{\Rightarrow}~{}~{}~{}~{}\textstyle\tfrac{1}{T}\sum_{t=1}^{T}\mathcal{E}_{+}^{t}\leq\mathcal{O}(T^{(p-1)/2}),$ $$

where step ① $\beta^{t}=\beta^{0}(1+\xi t^{p})=\mathcal{O}(t^{p})$.

∎

###### Proof.

## Appendix F Proofs for Section 6

### F.1 Proof of Theorem 6.3

###### Proof.

We let $t\geq 1$.

We define $\operatorname{Crit}(\mathbf{x}^{+},\mathbf{x},\mathbf{y}^{+},\mathbf{y},\mathbf{z}^{+},\mathbf{z})\triangleq\|\mathbf{x}^{+}-\mathbf{x}\|+\|\mathbf{y}^{+}-\mathbf{y}\|+\|\mathbf{z}^{+}-\mathbf{z}\|+\|\mathbf{A}\mathbf{x}^{+}-\mathbf{y}^{+}\|+\|\partial h(\mathbf{y}^{+})-\mathbf{z}^{+}\|_{2}^{2}+\|\partial\delta(\mathbf{x}^{+})+\nabla f(\mathbf{x}^{+})-\partial g(\mathbf{x})+\mathbf{A}^{\mathsf{T}}\mathbf{z}^{+}-\varphi(\mathbf{x},\mathbf{y})\partial d(\mathbf{x})\|$, where $\varphi(\mathbf{x},\mathbf{y})=\{f(\mathbf{x})+\delta(\mathbf{x})-g(\mathbf{x})+h(\mathbf{y})\}/d(\mathbf{x})$.

We define $\Gamma^{t}_{1}\triangleq\|\partial\delta(\mathbf{x}^{t+1})+\nabla f(\mathbf{x}^{t+1})+\mathbf{A}^{\mathsf{T}}\mathbf{z}^{t+1}-\partial g(\mathbf{x}^{t})-\varphi(\mathbf{x}^{t},\mathbf{y}^{t})\partial d(\mathbf{x}^{t})\|$.

We define $\Gamma^{t}_{2}\triangleq\|\mathbf{z}^{t+1}-\mathbf{z}^{t}\|+\|\partial h(\breve{\mathbf{y}}^{t+1})-\mathbf{z}^{t+1}\|+\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|$.

We define $\Gamma^{t}_{3}\triangleq\|\mathbf{y}^{t+1}-\breve{\mathbf{y}}^{t+1}\|+\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|+\|\breve{\mathbf{y}}^{t+1}-\mathbf{y}^{t}\|$.

Part (a). We now focus on FADMM-D.

We define $\lambda^{t}=\{f(\mathbf{x}^{t})+\delta(\mathbf{x}^{t})-g(\mathbf{x}^{t})+\langle\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t},\mathbf{z}^{t}\rangle+\tfrac{1}{2}\beta^{t}\|\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}\|_{2}^{2}+h_{\mu^{t}}(\mathbf{y}^{t})\}/d(\mathbf{x}^{t})$.

First, we focus on the optimality condition of the $\mathbf{x}$-subproblem. We have:

$$ $\displaystyle~{}-\partial\delta(\mathbf{x}^{t+1})+\partial g(\mathbf{x}^{t})+\lambda^{t}\partial d(\mathbf{x}^{t})$ $\displaystyle\ni$ $\displaystyle~{}\theta\ell(\beta^{t})(\mathbf{x}^{t+1}-\mathbf{x}^{t})+\nabla_{\mathbf{x}}\mathcal{S}^{t}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t})$ $\displaystyle=$ $\displaystyle~{}\theta\ell(\beta^{t})(\mathbf{x}^{t+1}-\mathbf{x}^{t})+\nabla f(\mathbf{x}^{t})+\mathbf{A}^{\mathsf{T}}\mathbf{z}^{t}+\beta^{t}\mathbf{A}^{\mathsf{T}}(\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}).$ (44) $$

Second, we derive the following inequalities:

$$ $\displaystyle~{}\|\partial d(\mathbf{x}^{t})\cdot\{\lambda^{t}-\varphi(\mathbf{x}^{t},\mathbf{y}^{t})\}\|$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}C_{d}\cdot|\tfrac{f(\mathbf{x}^{t})-g(\mathbf{x}^{t})+\langle\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t},\mathbf{z}^{t}\rangle+\tfrac{1}{2}\beta^{t}\|\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}\|_{2}^{2}+h_{\mu^{t}}(\mathbf{y}^{t})}{d(\mathbf{x}^{t})}-\tfrac{f(\mathbf{x}^{t})-g(\mathbf{x}^{t})+h(\mathbf{y}^{t})}{d(\mathbf{x}^{t})}|$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}\tfrac{C_{d}}{\underline{\rm{d}}}\cdot|\langle\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t},\mathbf{z}^{t}\rangle+\tfrac{1}{2}\beta^{t}\|\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}\|_{2}^{2}+h_{\mu^{t}}(\mathbf{y}^{t})-h(\mathbf{y}^{t})|$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}\tfrac{C_{d}}{\underline{\rm{d}}}\cdot\{\tfrac{\overline{\rm{z}}}{\beta^{t-1}}\|\mathbf{z}^{t}-\mathbf{z}^{t-1}\|+\tfrac{\beta^{t}}{2(\beta^{t-1})^{2}}\|\mathbf{z}^{t}-\mathbf{z}^{t-1}\|_{2}^{2}+\tfrac{1}{2}C_{h}^{2}\mu^{t}\}$ $\displaystyle\overset{\text{\char 175}}{\leq}$ $\displaystyle~{}\tfrac{C_{d}}{\underline{\rm{d}}}\cdot\{\tfrac{2\overline{\rm{z}}^{2}}{\beta^{t-1}}+\tfrac{\beta^{t}}{2(\beta^{t-1})^{2}}(2\overline{\rm{z}})^{2}+\tfrac{1}{2\beta^{t}}C_{h}^{2}\chi\}$ $\displaystyle\overset{\text{\char 176}}{=}$ $\displaystyle~{}\mathcal{O}(\tfrac{1}{\beta^{t}}),$ (45) $$

where step ① uses the fact that $d(\mathbf{x})$ is $C_{d}$-Lipschitz continuous, and the definitions of $\lambda^{t}$ and $\varphi(\mathbf{x}^{t},\mathbf{y}^{t})$; step ② uses $d(\mathbf{x}^{t})\geq\underline{\rm{d}}$; step ③ uses $0<h(\mathbf{y})-h_{\mu}(\mathbf{y})\leq\tfrac{\mu}{2}C_{h}^{2}$ (refer to Claim (b) of Lemma [3.9](#S3.Thmtheorem9)), the Cauchy-Schwarz Inequality, and the fact that $\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}=\tfrac{1}{\beta^{t-1}}(\mathbf{z}^{t}-\mathbf{z}^{t-1})$; step ④ uses $\|\mathbf{z}^{t}-\mathbf{z}^{t-1}\|\leq\|\mathbf{z}^{t}\|+\|\mathbf{z}^{t-1}\|\leq 2\overline{\rm{z}}$; step ⑤ uses $\beta^{t-1}\leq\beta^{t}\leq(1+\xi)\beta^{t-1}$.

Third, we derive the following results:

$$ $\displaystyle\Gamma^{t}_{1}\overset{}{\triangleq}$ $\displaystyle~{}\textstyle\|\partial\delta(\mathbf{x}^{t+1})+\nabla f(\mathbf{x}^{t+1})+\mathbf{A}^{\mathsf{T}}\mathbf{z}^{t+1}-\partial g(\mathbf{x}^{t})-\varphi(\mathbf{x}^{t},\mathbf{y}^{t})\partial d(\mathbf{x}^{t})\|$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}\textstyle\|\lambda^{t}\partial d(\mathbf{x}^{t})-\varphi(\mathbf{x}^{t},\mathbf{y}^{t})\partial d(\mathbf{x}^{t})+\nabla f(\mathbf{x}^{t+1})-\nabla f(\mathbf{x}^{t})$ $\displaystyle~{}+\mathbf{A}^{\mathsf{T}}(\mathbf{z}^{t+1}-\mathbf{z}^{t})-\{\theta\ell(\beta^{t})(\mathbf{x}^{t+1}-\mathbf{x}^{t})+\beta^{t}\mathbf{A}^{\mathsf{T}}(\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t})\}\|$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}\textstyle\|\lambda^{t}\partial d(\mathbf{x}^{t})-\varphi(\mathbf{x}^{t},\mathbf{y}^{t})\partial d(\mathbf{x}^{t})\|+\|\mathbf{A}^{\mathsf{T}}(\mathbf{z}^{t+1}-\mathbf{z}^{t})\|+\|\nabla f(\mathbf{x}^{t+1})-\nabla f(\mathbf{x}^{t})\|$ $\displaystyle~{}+\theta\ell(\beta^{t})\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|+\beta^{t}\|\mathbf{A}^{\mathsf{T}}(\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t})\|$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}\textstyle\mathcal{O}(\tfrac{1}{\beta^{t}})+\mathcal{O}(\beta^{t}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|)+\mathcal{O}(\beta^{t}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|)+\mathcal{O}(\beta^{t-1}\|\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}\|),$ (46) $$

where step ① uses Equalities ([F.1](#A6.Ex197)); step ② uses the triangle inequality; step ③ uses Inequality ([45](#A6.E45)), $\beta^{t-1}\leq\beta^{t}\leq(1+\xi)\beta^{t-1}$, and $\mathbf{z}^{t+1}-\mathbf{z}^{t}=\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1})$.

Fourth, we have the following inequalities:

$$ $\displaystyle\Gamma^{t}_{2}\triangleq$ $\displaystyle~{}\|\mathbf{z}^{t+1}-\mathbf{z}^{t}\|+\|\partial h(\breve{\mathbf{y}}^{t+1})-\mathbf{z}^{t+1}\|+\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}\mathcal{O}(\beta^{t}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|),$ (47) $$

where step ① uses $\mathbf{z}^{t+1}\in\partial h(\breve{\mathbf{y}}^{t+1})$, as shown in Lemma [5.3](#S5.Thmtheorem3), and $\mathbf{z}^{t+1}-\mathbf{z}^{t}=\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1})$.

Fifth, we have the following results:

$$ $\displaystyle\Gamma^{t}_{3}\triangleq$ $\displaystyle~{}\|\mathbf{y}^{t+1}-\breve{\mathbf{y}}^{t+1}\|+\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|+\|\breve{\mathbf{y}}^{t+1}-\mathbf{y}^{t}\|$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}\|\mathbf{y}^{t+1}-\breve{\mathbf{y}}^{t+1}\|+\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|+\|\breve{\mathbf{y}}^{t+1}-\mathbf{y}^{t+1}\|+\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}\mu^{t}C_{h}+\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|+\mu^{t}C_{h}+\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}\mathcal{O}(\tfrac{1}{\beta^{t}})+\mathcal{O}(\beta^{t}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|)+\mathcal{O}(\beta^{t}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|),$ (48) $$

where step ① uses the triangle inequality; step ② uses Claim (c) of Lemma ([3.10](#S3.Thmtheorem10)); step ③ uses $\mu^{t}=\tfrac{\chi}{\beta^{t}}=\mathcal{O}(\tfrac{1}{\beta^{t}})$, and $1\leq\tfrac{\beta^{t}}{\beta^{0}}=\mathcal{O}(\beta^{t})$.

Part (b). We now focus on FADMM-Q.

We define $\mathcal{U}(\alpha^{t},\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})\triangleq f(\mathbf{x}^{t})+\delta(\mathbf{x}^{t})-g(\mathbf{x}^{t})+h_{\mu^{t}}(\mathbf{y}^{t})+\langle\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t},\mathbf{z}^{t}\rangle+\frac{\beta^{t}}{2}\|\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}\|_{2}^{2}$, and $\alpha^{t+1}\triangleq\sqrt{d(\mathbf{x}^{t})}/\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$.

First, we focus on the optimality condition of the $\mathbf{x}$-subproblem. We have:

$$ $\displaystyle~{}\partial\delta(\mathbf{x}^{t+1})-\partial g(\mathbf{x}^{t})-\tfrac{2}{\alpha^{t+1}}\partial\sqrt{d(\mathbf{x}^{t})}$ $\displaystyle\ni$ $\displaystyle~{}-\theta\ell(\beta^{t})(\mathbf{x}^{t+1}-\mathbf{x}^{t})-\nabla_{\mathbf{x}}\mathcal{S}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t})$ $\displaystyle=$ $\displaystyle~{}-\theta\ell(\beta^{t})(\mathbf{x}^{t+1}-\mathbf{x}^{t})-\nabla f(\mathbf{x}^{t})-\mathbf{A}^{\mathsf{T}}\mathbf{z}^{t}-\beta^{t}\mathbf{A}^{\mathsf{T}}(\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}).$ (49) $$

Second, we derive the following inequalities:

$$ $\displaystyle~{}\|\tfrac{2}{\alpha^{t+1}}\partial\sqrt{d(\mathbf{x}^{t})}-\varphi(\mathbf{x}^{t},\mathbf{y}^{t})\partial d(\mathbf{x}^{t})\|$ $\displaystyle\overset{\text{\char 172}}{=}$ $\displaystyle~{}\|\tfrac{2}{\alpha^{t+1}}\tfrac{1}{2}d(\mathbf{x}^{t})^{-1/2}\partial d(\mathbf{x}^{t})-\varphi(\mathbf{x}^{t},\mathbf{y}^{t})\partial d(\mathbf{x}^{t})\|$ $\displaystyle\overset{\text{\char 173}}{=}$ $\displaystyle~{}\|\tfrac{\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})}{d(\mathbf{x}^{t})}\partial d(\mathbf{x}^{t})-\varphi(\mathbf{x}^{t},\mathbf{y}^{t})\partial d(\mathbf{x}^{t})\|$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}C_{d}|\tfrac{\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})}{d(\mathbf{x}^{t})}-\varphi(\mathbf{x}^{t},\mathbf{y}^{t})|$ $\displaystyle\overset{\text{\char 175}}{\leq}$ $\displaystyle~{}\tfrac{C_{d}}{\underline{\rm{d}}}|\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})-\{f(\mathbf{x}^{t})+\delta(\mathbf{x}^{t})-g(\mathbf{x}^{t})+h(\mathbf{y}^{t})\}|$ $\displaystyle\overset{\text{\char 176}}{\leq}$ $\displaystyle~{}\tfrac{C_{d}}{\underline{\rm{d}}}\cdot\{|\langle\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t},\mathbf{z}^{t}\rangle|+\tfrac{\beta^{t}}{2}\|\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}\|_{2}^{2}+|h_{\mu^{t}}(\mathbf{y}^{t})-h(\mathbf{y}^{t})|\}$ $\displaystyle\overset{\text{\char 177}}{\leq}$ $\displaystyle~{}\tfrac{C_{d}}{\underline{\rm{d}}}\cdot\{\tfrac{\overline{\rm{z}}}{\beta^{t-1}}\|\mathbf{z}^{t}-\mathbf{z}^{t-1}\|+\tfrac{\beta^{t}}{2(\beta^{t-1})^{2}}\|\mathbf{z}^{t}-\mathbf{z}^{t-1}\|_{2}^{2}+\tfrac{\mu^{t}}{2}C_{h}^{2}\}$ $\displaystyle\overset{\text{\char 178}}{\leq}$ $\displaystyle~{}\tfrac{C_{d}}{\underline{\rm{d}}}\cdot\{\tfrac{2\overline{\rm{z}}^{2}}{\beta^{t-1}}+\tfrac{\beta^{t}}{2(\beta^{t-1})^{2}}(2\overline{\rm{z}})^{2}+\tfrac{\chi}{2\beta^{t}}C_{h}^{2}\}$ $\displaystyle\overset{\text{\char 179}}{=}$ $\displaystyle~{}\mathcal{O}(\tfrac{1}{\beta^{t}}),$ (50) $$

where step ① uses $\partial\sqrt{d(\mathbf{x}^{t})}=\tfrac{1}{2}d(\mathbf{x}^{t})^{-1/2}\partial d(\mathbf{x}^{t})$; step ② uses the fact that $\alpha^{t+1}=\sqrt{d(\mathbf{x}^{t})}/\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t})$; step ③ uses the fact that $d(\mathbf{x})$ is $C_{d}$-Lipschitz continuous; step ④ uses $d(\mathbf{x}^{t})\geq\underline{\rm{d}}$; step ⑤ uses the definitions of $\mathcal{U}(\mathbf{x}^{t},\mathbf{y}^{t};\mathbf{z}^{t};\beta^{t},\mu^{t})$; step ⑥ uses $0<h(\mathbf{y})-h_{\mu}(\mathbf{y})\leq\tfrac{\mu}{2}C_{h}^{2}$ (refer to Claim (b) of Lemma [3.9](#S3.Thmtheorem9)), the Cauchy-Schwarz Inequality, and the fact that $\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}=\tfrac{1}{\beta^{t-1}}(\mathbf{z}^{t}-\mathbf{z}^{t-1})$; step ⑦ uses $\|\mathbf{z}^{t}-\mathbf{z}^{t-1}\|\leq\|\mathbf{z}^{t}\|+\|\mathbf{z}^{t-1}\|\leq 2\overline{\rm{z}}$ and $\mu^{t}=\chi/\beta^{t}$; step ⑧ uses $\beta^{t-1}\leq\beta^{t}\leq(1+\xi)\beta^{t-1}$.

Third, we derive the following results:

$$ $\displaystyle\Gamma^{t}_{1}\overset{}{\triangleq}$ $\displaystyle~{}\textstyle\|\partial\delta(\mathbf{x}^{t+1})+\nabla f(\mathbf{x}^{t+1})+\mathbf{A}^{\mathsf{T}}\mathbf{z}^{t+1}-\partial g(\mathbf{x}^{t})-\varphi(\mathbf{x}^{t},\mathbf{y}^{t})\partial d(\mathbf{x}^{t})\|$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}\textstyle\|\tfrac{2}{\alpha^{t+1}}\partial\sqrt{d(\mathbf{x}^{t})}-\varphi(\mathbf{x}^{t},\mathbf{y}^{t})\partial d(\mathbf{x}^{t})+\nabla f(\mathbf{x}^{t+1})-\nabla f(\mathbf{x}^{t})$ $\displaystyle~{}+\mathbf{A}^{\mathsf{T}}(\mathbf{z}^{t+1}-\mathbf{z}^{t})-\{\theta\ell(\beta^{t})(\mathbf{x}^{t+1}-\mathbf{x}^{t})+\beta^{t}\mathbf{A}^{\mathsf{T}}(\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t})\}\|$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}\textstyle\|\tfrac{2}{\alpha^{t+1}}\partial\sqrt{d(\mathbf{x}^{t})}-\varphi(\mathbf{x}^{t},\mathbf{y}^{t})\partial d(\mathbf{x}^{t})\|+\|\mathbf{A}^{\mathsf{T}}(\mathbf{z}^{t+1}-\mathbf{z}^{t})\|$ $\displaystyle~{}+\|\nabla f(\mathbf{x}^{t+1})-\nabla f(\mathbf{x}^{t})\|+\theta\ell(\beta^{t})\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|+\beta^{t}\|\mathbf{A}^{\mathsf{T}}(\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t})\|$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}\textstyle\mathcal{O}(\tfrac{1}{\beta^{t}})+\mathcal{O}(\beta^{t}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|)+\mathcal{O}(\beta^{t}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|)+\mathcal{O}(\beta^{t-1}\|\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}\|),$ (51) $$

where step ① uses Equalities ([F.1](#A6.Ex213)); step ② uses the triangle inequality; step ③ uses Inequality ([F.1](#A6.Ex215)), $\beta^{t-1}\leq\beta^{t}\leq(1+\xi)\beta^{t-1}$, and $\mathbf{z}^{t+1}-\mathbf{z}^{t}=\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1})$.

Fourth, we have the following inequalities:

$$ $\displaystyle\Gamma^{t}_{2}\triangleq$ $\displaystyle~{}\|\mathbf{z}^{t+1}-\mathbf{z}^{t}\|+\|\partial h(\breve{\mathbf{y}}^{t+1})-\mathbf{z}^{t+1}\|+\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}\mathcal{O}(\beta^{t}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|),$ (52) $$

where step ① uses $\mathbf{z}^{t+1}\in\partial h(\breve{\mathbf{y}}^{t+1})$, as shown in Lemma [5.3](#S5.Thmtheorem3), and $\mathbf{z}^{t+1}-\mathbf{z}^{t}=\beta^{t}(\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1})$.

Fifth, we have the following results:

$$ $\displaystyle\Gamma^{t}_{3}\triangleq$ $\displaystyle~{}\|\mathbf{y}^{t+1}-\breve{\mathbf{y}}^{t+1}\|+\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|+\|\breve{\mathbf{y}}^{t+1}-\mathbf{y}^{t}\|$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}\|\mathbf{y}^{t+1}-\breve{\mathbf{y}}^{t+1}\|+\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|+\|\breve{\mathbf{y}}^{t+1}-\mathbf{y}^{t+1}\|+\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}\mu^{t}C_{h}+\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|+\mu^{t}C_{h}+\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|$ $\displaystyle\overset{\text{\char 174}}{\leq}$ $\displaystyle~{}\mathcal{O}(\tfrac{1}{\beta^{t}})+\mathcal{O}(\beta^{t}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|)+\mathcal{O}(\beta^{t}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|),$ (53) $$

where step ① uses the triangle inequality; step ② uses Claim (c) of Lemma ([3.10](#S3.Thmtheorem10)); step ③ uses $\mu^{t}=\tfrac{\chi}{\beta^{t}}=\mathcal{O}(\tfrac{1}{\beta^{t}})$, and $1\leq\tfrac{\beta^{t}}{\beta^{0}}=\mathcal{O}(\beta^{t})$.

Part (c). Finally, we continue our analysis for both FADMM-D and FADMM-Q, deriving the following inequalities:

$$ $\displaystyle~{}\textstyle\tfrac{1}{T}\sum_{t=1}^{T}\operatorname{Crit}(\mathbf{x}^{t+1},\mathbf{x}^{t},\breve{\mathbf{y}}^{t+1},\mathbf{y}^{t},\mathbf{z}^{t+1},\mathbf{z}^{t})$ $\displaystyle\overset{\text{\char 172}}{\leq}$ $\displaystyle~{}\textstyle\tfrac{1}{T}\sum_{t=1}^{T}\{\Gamma_{1}^{t}+\Gamma_{2}^{t}+\Gamma_{3}^{t}\}$ $\displaystyle\overset{\text{\char 173}}{\leq}$ $\displaystyle~{}\textstyle\tfrac{1}{T}\sum_{t=1}^{T}\{\mathcal{O}(\beta^{t}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|)+\mathcal{O}(\beta^{t}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|)+\mathcal{O}(\beta^{t-1}\|\mathbf{A}\mathbf{x}^{t}-\mathbf{y}^{t}\|)$ $\displaystyle~{}\textstyle+\mathcal{O}(\beta^{t}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|)+\mathcal{O}(\beta^{t}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|)+\mathcal{O}(\tfrac{1}{\beta^{t}})\}$ $\displaystyle\overset{\text{\char 174}}{=}$ $\displaystyle~{}\textstyle\mathcal{O}(T^{(p-1)/2})+\tfrac{1}{T}\sum_{t=1}^{T}\mathcal{O}(\tfrac{1}{\beta^{t}})$ $\displaystyle\overset{\text{\char 175}}{=}$ $\displaystyle~{}\textstyle\mathcal{O}(T^{(p-1)/2})+\mathcal{O}(\tfrac{1}{T}T^{1-p}),$ (54) $$

where step ① uses the definition of $\operatorname{Crit}(\mathbf{x}^{+},\mathbf{x},\mathbf{y}^{+},\mathbf{y},\mathbf{z}^{+},\mathbf{z})$, and the triangle inequality that $\|\mathbf{A}\mathbf{x}^{t+1}-\breve{\mathbf{y}}^{t+1}\|\leq\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|+\|\breve{\mathbf{y}}^{t+1}-\mathbf{y}^{t+1}\|$; step ② uses Inequalities ([F.1](#A6.Ex204)), ([F.1](#A6.Ex209)), and ([48](#A6.E48)) for FADMM-D and Inequalities ([F.1](#A6.Ex223)), ([F.1](#A6.Ex228)), and ([F.1](#A6.Ex229)) for FADMM-Q; step ③ uses Theorem [5.13](#S5.Thmtheorem13) for FADMM-D and Theorem [5.18](#S5.Thmtheorem18) for FADMM-Q that $\tfrac{1}{T}\sum_{t=1}^{T}\{\beta^{t}\|\mathbf{x}^{t+1}-\mathbf{x}^{t}\|+\beta^{t}\|\mathbf{y}^{t+1}-\mathbf{y}^{t}\|+\beta^{t}\|\mathbf{A}\mathbf{x}^{t+1}-\mathbf{y}^{t+1}\|\}\leq\mathcal{O}(T^{(p-1)/2})$; step ④ uses $\sum_{t=1}^{T}\frac{1}{\beta^{t}}=\mathcal{O}(\sum_{t=1}^{T}\frac{1}{t^{p}})=\mathcal{O}(T^{1-p})$, as presented in Lemma [A.5](#A1.Thmtheorem5).

We define $\mathcal{W}^{t}\triangleq\{\mathbf{x}^{t+1},\mathbf{x}^{t},\breve{\mathbf{y}}^{t+1},\mathbf{y}^{t},\mathbf{z}^{t+1},\mathbf{z}^{t}\}$.
With the choice $p=1/3$, we have from Inequality ([F.1](#A6.Ex232)) that $\tfrac{1}{T}\sum_{t=1}^{T}\operatorname{Crit}(\mathcal{W}^{t})\leq\mathcal{O}(T^{-1/3})$. In other words, there exists $1\leq\bar{t}\leq T$ such that: $\operatorname{Crit}(\mathcal{W}^{\bar{t}})\leq\epsilon$, provided that $T\geq\mathcal{O}(\tfrac{1}{\epsilon^{3}})$

∎

###### Proof.

## Appendix G Computing Proximal Operators

In this section, we demonstrate how to compute the proximal operator for various functions involved in this paper. The proximal operator is defined as follows:

$$ $\displaystyle\min_{\mathbf{x}\in\mathbb{R}^{r}}p(\mathbf{x})+\tfrac{1}{2\mu}\|\mathbf{x}-\mathbf{x}^{\prime}\|_{2}^{2}.$ (55) $$

Here, $\mathbf{x}^{\prime}\in\mathbb{R}^{r}$ and $\mu>0$ are given.

### G.1 Orthogonality Constraint

When $p(\mathbf{x})=\iota_{\Omega}(\operatorname{mat}(\mathbf{x}))$ with $\Omega$ being the set of orthogonality constraints, Problem ([55](#A7.E55)) simplifies to the following nonconvex optimization problem:

$$ $\displaystyle\textstyle\bar{\mathbf{x}}\in\arg\min_{\mathbf{x}}\frac{1}{2\mu}\|\mathbf{x}-\mathbf{x}^{\prime}\|_{2}^{2},\,s.t.\,\operatorname{mat}(\mathbf{x})\in\Omega\triangleq\{\mathbf{V}\,|\,\mathbf{V}^{\mathsf{T}}\mathbf{V}=\mathbf{I}\}.$ $$

This is the nearest orthogonality matrix problem, where the optimal solution is given by $\bar{\mathbf{x}}=\operatorname{vec}(\hat{\mathbf{U}}\hat{\mathbf{V}}^{\mathsf{T}})$ with $\operatorname{mat}(\mathbf{x}^{\prime})=\hat{\mathbf{U}}{\rm{Diag}}(\mathbf{s})\hat{\mathbf{U}}^{\mathsf{T}}$ being the singular value decomposition of the matrix $\operatorname{mat}(\mathbf{x}^{\prime})$. See Lai & Osher () for reference.

### G.2 Generalized ℓ 1 subscript ℓ 1 \ell_{1} Norm

When $p(\mathbf{x})=\rho_{2}\|\mathbf{x}\|_{1}+\iota_{\Omega}(\mathbf{x})$ with $\Omega\triangleq\{\mathbf{x}\,|\,\|\mathbf{x}\|_{\infty}\leq\rho_{0}\}$, Problem ([55](#A7.E55)) simplifies to the following strongly convex problem:

$$ $\displaystyle\textstyle\bar{\mathbf{x}}\in\arg\min_{\mathbf{x}\in\mathbb{R}^{r}}\rho_{2}\|\mathbf{x}\|_{1}+\frac{1}{2\mu}\|\mathbf{x}-\mathbf{x}^{\prime}\|_{2}^{2},\,\operatorname{s.t.}\,\|\mathbf{x}\|_{\infty}\leq\rho_{0}.$ $$

This problem can be decomposed into $r$ dependent sub-problems

$$ $\displaystyle\textstyle\bar{\mathbf{x}}_{i}=\arg\min_{x}q_{i}(x)\triangleq\frac{1}{2\mu}(x-\mathbf{x}^{\prime}_{i})^{2}+\rho_{2}|x|,\,\operatorname{s.t.}\,-\rho_{0}\leq x\leq\rho_{0}.$ (56) $$

We define $\mathcal{P}_{[l,u]}(x)\triangleq\max(l,\min(u,x))$. We consider five cases for $x$. (i) $x_{1}=0$. (ii) $x_{2}=-\rho_{0}$. (iii) $x_{3}=\rho_{0}$. (iv) $x_{4}>0$ and $x_{4}<\rho_{0}$. By omitting the bound constraints, the first-order optimality condition gives $\tfrac{1}{\mu}(x_{4}-\mathbf{x}^{\prime}_{i})+\rho_{2}=0$, leading to $x_{4}=\mathbf{x}^{\prime}_{i}-\mu\rho_{2}$. When the bound constraints are included, we have $x_{4}=\mathcal{P}_{[0,\rho_{0}]}(\mathbf{x}^{\prime}_{i}-\mu\rho_{2})$. (v) $x<0$ and $x>-\rho_{0}$. By dropping the bound constraints, the first-order optimality condition yields $\tfrac{1}{\mu}(x_{5}-\mathbf{x}^{\prime}_{i})-\rho_{2}=0$, leading to $x_{5}=\mathbf{x}^{\prime}_{i}+\mu\rho_{2}$. When the bound constraints are considered, we have $x_{5}=\mathcal{P}_{[-\rho_{0},0]}(\mathbf{x}^{\prime}_{i}+\mu\rho_{2})$. Therefore, the one-dimensional sub-problem in Problem ([56](#A7.E56)) contains five critical points, and the optimal solution can be computed as:

$$ $\displaystyle\bar{\mathbf{x}}_{i}=\arg\min_{x}q_{i}(x),\,\operatorname{s.t.}\,x\in\{x_{1},x_{2},x_{3},x_{4},x_{5}\}.$ $$

### G.3 Simplex Constraint

When $p(\mathbf{x})=\iota_{\Omega}(\mathbf{x})$ with $\Omega\triangleq\{\mathbf{x}\,|\,\mathbf{x}\geq\mathbf{0},\,\mathbf{x}^{\mathsf{T}}\mathbf{1}=1\}$, Problem ([55](#A7.E55)) simplifies to the following strongly convex problem:

$$ $\displaystyle\textstyle\bar{\mathbf{x}}\in\arg\min_{\mathbf{x}}\frac{1}{2\mu}\|\mathbf{x}-\mathbf{x}^{\prime}\|_{2}^{2},\,\operatorname{s.t.}\,\mathbf{x}\geq\mathbf{0},\,\mathbf{x}^{\mathsf{T}}\mathbf{1}=1.$ $$

This problem is referred to as the Euclidean projection onto the probability simplex. It can be solved exactly in $\mathcal{O}(n\log(n))$ time Duchi et al. ().

### G.4 Generalized Max Function

When $p(\mathbf{x})=\max(0,\max(\mathbf{x}+\mathbf{b}))$ with $\mathbf{b}\in\mathbb{R}^{r}$, Problem ([55](#A7.E55)) simplifies to the following strongly convex problem: $\bar{\mathbf{x}}\in\arg\min_{\mathbf{x}}\frac{1}{2\mu}\|\mathbf{x}-\mathbf{x}^{\prime}\|_{2}^{2}+\max(0,\max(\mathbf{x}+\mathbf{b}))$. Using the variable substitution that $\mathbf{x}+\mathbf{b}=\mathbf{v}$, we have the following equivalent problem:

$$ $\displaystyle\textstyle\bar{\mathbf{v}}\in\arg\min_{\mathbf{v}}q(\mathbf{v})\triangleq\frac{1}{2\mu}\|\mathbf{v}-\mathbf{v}^{\prime}\|_{2}^{2}+\max(0,\max(\mathbf{v})),$ (57) $$

where $\mathbf{v}^{\prime}\triangleq\mathbf{x}^{\prime}+\mathbf{b}$.

In what follows, we address Problem ([57](#A7.E57)) by considering two cases for $\mathbf{v}^{\prime}$. (i) $\max(\mathbf{v}^{\prime})\leq 0$. The optimal solution can be computed as $\bar{\mathbf{v}}=\mathbf{v}^{\prime}$, and it holds that $q(\bar{\mathbf{v}})=0$. (ii) $\max(\mathbf{v}^{\prime})>0$. In this case, there exists an index $i\in[r]$ such that $\mathbf{v}^{\prime}>0$. It is not difficult to verify that the optimal solution $\bar{\mathbf{v}}$ satisfies $\max(\bar{\mathbf{v}})\geq 0$. Problem ([57](#A7.E57)) reduces to:

$$ $\displaystyle\textstyle\bar{\mathbf{v}}=\arg\min_{\mathbf{v}}\frac{1}{2\mu}\|\mathbf{v}-\mathbf{v}^{\prime}\|_{2}^{2}+\max(\mathbf{v}).$ (58) $$

This problem can be equivalently reformulated as: $\min_{\mathbf{v},\tau}\frac{1}{2\mu}\|\mathbf{v}-\mathbf{v}^{\prime}\|_{2}^{2}+\tau,\,\operatorname{s.t.}\,\mathbf{v}\leq\tau\mathbf{1}$, whose dual problem is given by:

$$ $\displaystyle\textstyle\bar{\mathbf{z}}=\arg\max_{\mathbf{z}}-\frac{\mu}{2}\|\mathbf{z}\|_{2}^{2}+\langle\mathbf{z},\mathbf{v}^{\prime}\rangle,\,\operatorname{s.t.}\mathbf{z}\geq 0,\,\,\|\mathbf{z}\|_{1}=1.$ (59) $$

The unique optimal solution $\bar{\mathbf{z}}$ for the dual problem in Problem ([59](#A7.E59)) can be computed in $\mathcal{O}(n\log(n))$ time Duchi et al. (). Finally, the optimal solution $\bar{\mathbf{v}}$ for Problem ([58](#A7.E58)) can then be recovered as $\bar{\mathbf{v}}=\mathbf{v}^{\prime}-\mu\bar{\mathbf{z}}$.

## Appendix H Additional Experimental Details and Results

In this section, we offer further experimental details on the datasets used in the experiments, and include additional results.

$\blacktriangleright$ Datasets. (i) For sparse FDA, robust SRM, and robust sparse recovery problems, we incorporate several datasets in our experiments, including randomly generated data and publicly available real-world data. These datasets serve as our data matrices $\mathbf{Q}\in\mathbb{R}^{\dot{m}\times\dot{d}}$ and the label vectors $\mathbf{p}\in\mathbb{R}^{\dot{m}}$. The dataset names are as follows: ‘madelon-$\dot{m}$-$\dot{d}$’, ‘TDT2-1-2-$\dot{m}$-$\dot{d}$’, ‘TDT2-3-4-$\dot{m}$-$\dot{d}$’, ‘mnist-$\dot{m}$-$\dot{d}$’, ‘mushroom-$\dot{m}$-$\dot{d}$’, and ‘randn-$\dot{m}$-$\dot{d}$’. Here, $`{\mathrm{randn}(\dot{m},\dot{d})}^{\prime}$ represents a function that generates a standard Gaussian random matrix with dimensions $\dot{m}\times\dot{d}$, and ‘TDT2-$i$-$j$’ refers to the subset of the original dataset ‘TDT2’ consisting of data points with labels $i$ and $j$. The matrix $\mathbf{Q}\in\mathbb{R}^{\dot{m}\times\dot{d}}$ is constructed by randomly selecting $\dot{m}$ examples and $\dot{d}$ dimensions from the original real-world dataset ([https://www.csie.ntu.edu.tw/~cjlin/libsvm/](https://www.csie.ntu.edu.tw/~cjlin/libsvm/)). We normalize each column of $\mathbf{D}$ to have a unit norm. As ‘randn-$\dot{m}$-$\dot{d}$’ does not have labels, we randomly and uniformly assign to binary labels with $\mathbf{p}\in\{-1,+1\}^{\dot{m}}$. (ii) For sparse FDA as in Problem ([2](#S1.E2)), we let $\mathbf{D}\triangleq(\bm{\mu}_{(1)}-\bm{\mu}_{(2)})(\bm{\mu}_{(1)}-\bm{\mu}_{(2)})^{\mathsf{T}}$, $\mathbf{C}=\bm{\Sigma}_{(1)}+\bm{\Sigma}_{(2)}$, where $\bm{\mu}_{(i)}\in\mathbb{R}^{n}$ and $\bm{\Sigma}_{(i)}\in\mathbb{R}^{n\times n}$ represent the mean vector and covariance matrix of class $i$ ($i=1$ or $2$), respectively, generated by $\{\mathbf{Q},\mathbf{p}\}$. We normalize the matrices $\mathbf{C}$ and $\mathbf{D}$ as $\mathbf{C}=\mathbf{C}/\|\mathbf{C}\|_{\mathsf{F}}$, and $\mathbf{D}=\mathbf{D}/\|\mathbf{D}\|_{\mathsf{F}}$. (iii) For robust SRM as in Problem ([14](#A2.E14)), we let $\mathbf{D}=\mathbf{Q}$ and $\mathbf{b}=\mathbf{p}$. Following Boţ et al. (), we generate $p$ matrices $\{\mathbf{C}_{(i)}\}_{i=1}^{p}$, where each $\mathbf{C}_{(i)}\in\mathbb{R}^{n\times n}$ is constructed as $\mathbf{C}_{(i)}=\tfrac{1}{n}\mathbf{Y}\mathbf{Y}^{\mathsf{T}}$, with $\mathbf{Y}=\mathrm{randn}(n,n)\times 10$. We let $p=100$. (iv) For robust sparse recovery as in Problem ([15](#A2.E15)), we simply let $\mathbf{A}=\mathbf{Q}$ and $\mathbf{b}=\mathbf{p}$, where $\mathbf{p}\in\{-1,+1\}^{\dot{m}}$ represents the data labels.

$\blacktriangleright$ Experimental Results on Robust SRM. We consider solving Problem ([14](#A2.E14)) using the proposed methods. For all methods, we set $\beta^{0}=0.01$. The results of the algorithms are shown in Figure [4](#A8.F4). We draw the following conclusions. (i) SPM appears to outperform both SPGM-D and SPGM-Q. We attribute this to the fact that the subgradient provides a good approximation of the negative descent direction. (ii) Both variants, FADMM-D and FADMM-Q, generally demonstrate better performance than the other methods, achieving lower objective function values.

$\blacktriangleright$ Experimental Results on Robust Sparse Recovery. We consider solving Problem ([15](#A2.E15)) using the following parameters $(\rho_{1},\rho_{2},\rho_{3})$$\in\{(10,1,\infty)$, $(10,10,\infty)$, $(10,100,\infty)$, $(100,1,\infty)$, $(100,100,\infty)\}$. For all methods, we initialize with $\beta^{0}=0.01$. Since $\sqrt{\|\mathbf{x}\|_{[k]}}$ is not necessarily weakly convex, FADMM-Q is not applicable, and we only implement FADMM-D. The results of the compared methods are presented in Figures [5](#A8.F5), [6](#A8.F6), [7](#A8.F7), [8](#A8.F8), [9](#A8.F9), from which we draw the following conclusions: Although in certain cases, SGM and SPGM-D provide comparable or better results than FADMM-D (see Figure [5](#A8.F5)(e), Figure [6](#A8.F6)(e), Figure [7](#A8.F7)(d), Figure [8](#A8.F8)(a,f), Figure [9](#A8.F9)(e,f)), the proposed FADMM-D generally delivers the best performance among the compared methods in terms of speed. These results further corroborate our earlier findings.

Figure: (a) madelon-2000-500
Refer to caption: /html/2411.07496/assets/x25.png

Figure: (a) madelon-2000-500
Refer to caption: /html/2411.07496/assets/x33.png

Figure: (a) madelon-2000-500
Refer to caption: /html/2411.07496/assets/x41.png

Figure: (a) madelon-2000-500
Refer to caption: /html/2411.07496/assets/x49.png

Figure: (a) madelon-2000-500
Refer to caption: /html/2411.07496/assets/x57.png

Figure: (a) madelon-2000-500
Refer to caption: /html/2411.07496/assets/x65.png

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 5
presentation: 2
questions: - The authors do not explain Assumption 5.1 well in Remark 5.2. By the algorithm, the iterate $x^t$ is only in the domain of $\delta(\cdot)$. You cannot say that it lies in a bounded set. The same issue occurs in Lemma 5.5. It might not be safe to assume that $x^t$ is bounded.

- The notation $\underline{\mathrm{Fd}}$ and $\overline{\mathrm{Fd}}$ should be $\underline{F} \, \underline{d}$ and $\overline{F} \, \overline{d}$, respectively.

- If the $\epsilon$-critical point is similar to that in Bot et al. (2023b), will the same complexity results hold?

- What is the method SGM mentioned in Section 7?

- The authors might need to compare their method to that in Bot et al. (2023b), at least for the Robust SRM problem.
soundness: 3
strengths: The authors discuss a class of fractional minimization problems, which seem not to be well addressed in the literature. The authors provide corresponding theoretical analysis and numerical results.
summary: This paper proposes an ADMM for solving a class of structured fractional minimization problems. The main techniques are based on smoothing methods and two well-established approaches for fractional minimization problems. The convergence rate of the proposed ADMM is established. Some numerical results are reported to show the efficiency of the proposed ADMM. Overall, the topic and results are interesting.
weaknesses: The results in Lemmas 3.9 and 3.10 are standard in the literature. The authors do not need to prove them in the appendix and should not claim the results ``represent novel contributions.''

After using the smoothing techniques, the hard term $h(Ax)$ will become $h_{\mu}(Ax)$. The authors could then use some standard methods from the fractional minimization community to solve this problem. The corresponding complexity will also be $\mathcal{O}(\epsilon^{-3})$. The authors might want to comment on this. It seems that Bot et al. (2023) also used this smoothing technique.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 2
questions: I am not an expert in non-convex optimization, I can only give some advice on writing papers：

1.The first sentence of the abstract is too long. It is recommended to split it to improve readability.

2.Line 73, "sufficient large" should be "sufficiently large".

3.Line 138, "To the best of our knowledge......" is too long. It is better to break it into short sentences for reading.

4.Line 236,  "is a widely used to develop practical optimization algorithms ", delete ”a“.

5.Line 454, "Additioanl"  -> "Additional".
soundness: 3
strengths: 1.The authors provide a comprehensive analysis of the proposed FADMM algorithm, including two specific variants: FADMM-D and FADMM-Q.

2.Comprehensive theoretical analysis, with proofs on convergence.

3.The authors conduct extensive experiments on both synthetic and real-world data, effectively demonstrating the efficiency of the FADMM algorithm.
summary: In this paper, the authors introduce FADMM, the first ADMM algorithm designed to solve general structured fractional minimization problems.  FADMM decouples the original problem into linearized proximal subproblems, featuring two variants: one using Dinkelbach’s parametric method (FADMM-D) and the other using the quadratic transform method (FADMM-Q). The proposed algorithm improves the slow convergence speed and numerical stability issues of traditional subgradient methods and smoothing proximal gradient methods. The authors conduct a convergence analysis of the FADMM algorithm by introducing a novel Lyapunov function, and they validate the effectiveness of the FADMM algorithm through extensive synthetic and real-world data.
weaknesses: I think the writing of this paper can be further improved.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 1
questions: - All the numerical examples given in the paper have a denominator which is convex. This leads me to question whether the generalization of the denonimator to weakly convex functions is even well-motivated; are there problems that really necessitate this assumption?

- Similarly, what is the significance of not assuming that delta is convex if later you assume that it's a simple function? When you take delta to be the indicator function of the set of orthogonal matrices, the proximal operator is not well-defined.

- In Remark 3.11 it is claimed that Lemma 3.9 and 3.10 are novel contributions but in fact many (perhaps all?) of these results are well-known results about Moreau envelopes so in what sense are they novel? The authors should either clarify this comment and be specific about what exactly is novel or to remove this remark and just cite the known references stating these results.

- Very little is said about the effect that the parameter choices have on convergence. In practice how does one go about choosing beta_0 or other hyperparameters? For instance, in the sparse FDA experiments it's written that beta_0 = 100rho which is actually quite large (1000 to 100,000).

Minor Questions:

- What is meant in line 73 when it is claimed that when rho is large, ||X||_[k] approximates ||X||_1 ?

- In line 76, shouldn't h(Ax) have a factor of rho?

- In lin 76, isn't it more clear to simply write that d and d^1/2 are convex?

- How much effort was made to tune the parameters used in all of the different methods?
soundness: 3
strengths: - The class of problems addressed is broader than what was previously treated in the literature. 

- The theoretical results about the convergence of the methods and their rates are strong and significant.

- The arguments made were rigorous and clearly stated. I wasn't able to review all the proofs in detail as there were many that were relegated to the appendix and the paper itself is quite long at nearly 40 pages.

- The methods appear to perform well in the numerical experiments compared to previous methods that can solve fractional minimization problems and other smoothing algorithms.
summary: This paper develops and analyzes alternating direction method of multipliers (ADMM) algorithms for solving structured fractional minimization problems. Building on recent work (Bot et al., 2023a,b; Li & Zhang, 2022), the main idea is to transform the fractional minimization problem into an equivalent composite minimization problem more amenable to operator splitting. The authors consider two classical transformations following Bot et al., 2023a,b and Li & Zhang, 2022 - Dinkelbach's parametric method and the quadratic transform method. Rather than exactly solving the transformed problems at each iteration (which could be costly), they propose to linearize them and solve this majorized version (which leads to ADMM style updates). This produces two algorithms, FADMM-D and FADMM-Q, corresponding to the two transformation approaches.

A key technical contribution is the use of smoothing via the Moreau envelope to handle the nonsmooth components in the numerator of the fractional objective. The authors establish convergence rates for both D and Q variants, showing they reach eps-approximate critical points within O(1/eps^3) iterations. The theoretical analysis is rigorous and all results are precisely stated. The definition of eps-approximate critical point, however, is nonstandard.

The two methods are validated on three applications that fit loosely within their abstract framework: sparse Fisher discriminant analysis, robust Sharpe ratio maximization, and robust sparse recovery. Note that these problems do not make full use of the relaxed assumptions outlined in the paper. Numerical experiments demonstrate that both variants typically outperform existing approaches in terms of wall-clock time to convergence and seem convincing.
weaknesses: - The technical density of the presentation harms the readability.

- The discussion after Remark 3.5, on the stationarity conditions for this problem, feels very rushed and I don't understand exactly the justifications for all the claims made. In particular there are many references but they are vague - I think it would improve a lot the clarity of the paper if you could specify a lemma or result from those papers that clearly justifies what you are claiming with the subdifferential caclulus here. This also applies to Lemma A.1.

- Definition 3.8 is the definition of the Moreau envelope - I am confused to see it called Nesterov smoothing. This comes up again in the questions section because some of these results about Moreau envelopes are already well-known, even in papers cited by the authors (i.e., Bohm and Wright).

- Many hyperparameters in the method with little guidance about how to choose them or their effect on convergence.

Meta-review: The paper presents a novel ADMM-based optimization method, tailored for structured fractional minimization problems, which seem not to be well addressed in the literature. The main techniques are based on smoothing methods (via the Moreau envelope) and two well-established approaches for fractional minimization problems. The authors provide corresponding theoretical analysis and numerical results. A Lyapunov function demonstrates convergence within an oracle complexity of $O(1/\epsilon^3)$, and empirical evaluations confirm applicability across domains like sparse Fisher discriminant analysis and robust sparse recovery. Overall, the topic and results are interesting. The reviewers are broadly positive about the submission.

Decision: Accept (Poster)