ADMM for Structured Fractional Minimization
Authors: Ganzhao Yuan
Venue: ICLR 2025 Poster (2025)
Keywords: Fractional Minimization
Nonconvex Optimization
Proximal Linearized ADMM
Nonsmooth Optimization
Convergence Analysis
Primary area: optimization

Abstract: This paper considers a class of structured fractional minimization problems. The numerator consists of a differentiable function, a simple nonconvex nonsmooth function, a concave nonsmooth function, and a convex nonsmooth function composed with a linear operator. The denominator is a continuous function that is either weakly convex or has a weakly convex square root. These problems are prevalent in various important applications in machine learning and data science. Existing methods, primarily based on subgradient methods and smoothing proximal gradient methods, often suffer from slow convergence and numerical stability issues. In this paper, we introduce {\sf FADMM}, the first Alternating Direction Method of Multipliers tailored for this class of problems. {\sf FADMM} decouples the original problem into linearized proximal subproblems, featuring two variants: one using Dinkelbach's parametric method ({\sf FADMM-D}) and the other using the quadratic transform method ({\sf FADMM-Q}). By introducing a novel Lyapunov function, we establish that {\sf FADMM} converges to $\epsilon$-approximate critical points of the problem within an oracle complexity of $\mathcal{O}(1/\epsilon^{3})$. Extensive experiments on synthetic and real-world datasets, including sparse Fisher discriminant analysis, robust Sharpe ratio minimization, and robust sparse recovery, demonstrate the effectiveness of our approach.

Published as a conference paper at ICLR 2025
ADMM FOR STRUCTURED FRACTIONAL MINIMIZA- TION
Ganzhao Yuan
Peng Cheng Laboratory, China yuangzhêpcl. .c
ABSTRACT
This paper considers class of structured fractional minimization problems. The numerator consists of a differentiable function, a simple nonconvex nonsmooth function, concave nonsmooth function, and convex nonsmooth function com- posed with a linear operator. The denominator a continuous function that is either weakly convex has weakly convex square root. These problems are prevalent in various important applications machine learning and data science. Existing methods, primarily based on subgradient methods and smoothing prox- imal gradient methods, often suffer from slow convergence and numerical stabil- ity issues. In this paper, we introduce FADMM, the first Altemating Direction Method of Multipliers tailored for this class of problems. FADMM decouples the original problem into linearized proximal subproblems, featuring two vari- ants: one using Dinkelbach's 's parametric method (FADMM-D) and the other using the quadratic transform method (FADMM-Q). By introducing a novel Lyapunov function, establish that FADMM converges to e-approximate critical points of the problem within an oracle complexity ((1/²)). Extensive experiments on synthetic and real-world datasets, including sparse Fisher discriminant analysis, robust Sharpe ratio minimization, and robust sparse recovery, demonstrate the ef- fectiveness of our approach.
INTRODUCTION
This paper focuses on the following class of nonconvex and nonsmooth fractional minimization problem (where + denotes definition):
u(x)
min F(x)=
where u(x) è f(x 5(x) - g(x) I(Ax).
d(x)
Here, X E R" and A E m We impose the following assumptions on Problem I (i) The function (x) differentiable and possibly nonconvex. (ii) The function 5(x) is possibly noncon- vex, nonsmooth, and non-Lipschitz. (iii) Both functions g(x) and l((x) are convex and possibly nonsmooth. (iv) Both functions 6(x) and h(y) are simple, such that their proximal operators can be computed efficiently and exactly. (r) The function d(x) is Lipschitz continuous, and either d(x) itself or its square root, d/2) is weakly convex. (vi) To ensure Problem
(1 is well-defined, we sume that all functions gxx), 8(x), hyy), and d(x) are proper and lower semicontinuous, u(x) 2 0, and d(x) 2 0 for all and y.
Problem serves as a fundamental optimization framework in various machine learning and data science models, such sparse Fisher discriminant analysis (Bishop & Nasrabadi 2006). (robust) Sharpe ratio maximization (Chen et al.) 2011), robust sparse recovery (Yuan) 2023 Yang & ZZang
2011), limited-angle CT reconstruction (Wang et al. 222 ,, AUC maximization (Wang al. 2022). and signal-to-noise ratio maximization (Shen & Yu 201 8a b). An alternative formulation of Prob-
lem (1) can be obtained by replacing the maximization with the minimization, as explored in the fractional optimization literature (Stancu-Minasee 2012, Schaible 1995). Although these two for- mulations are generally distinct, the corresponding algorithmic developments can readily adapt to either formulation.
Future versions of this paper he found httpp://awwv...oggaas//////////t

---

8(x) = (2(2X) gxx = X|| [K). A I, h (AA) = p X|[ and d(x) = tr(X DX). Importantly, both d(x) and d(xx)// are Wa- Wa-weakly convex with Wa = O. Published as a conference paper at ICLR 2025
1.1 MOTIVATING APPLICATIONS
Many models in machine learning and data science can be formulated as Problem T the sparse Fisher discriminant analysis application below, with additional applications, including robust Sharpe ratio maximization and robust sparse recovery, detailed in Appendix B
We present
Sparse Fisher Discriminant Analysis (Sparse FDA). Given observations from two distinct classes, let (G E IR" and (())) E Ruxx represent the mean vector and covariance matrix of class (i or 2), respectively. Classical FDA (Bishop Nasrabadi] 2006 Xu & 2020) aims to find an orthogonal subspace X between-class variance relative to the within-clas, variance. This leads to the following optimiza- tion problem: minxen tr (E))) + X)/tt(X(X((XXXX
with Q - {X] X X }, that maximizes the
((22))(4( ) (12)) )x)). Induc-
ing sparsity in the solution helps mitigate overfitting and enhances the interpretability of the model in high-dimensional data analysis (Journée et al.) 2010). We consider the following Difference- of-Convex (DC) model (Bi et al.
2014
Bi & Pan 2016 Gotoh et al., 2018) for learning sparse
orthogonal loadings for FDA:
tr(x CX)
+ p(|[X]I (XX)
| l(m)
min
S. s.t. $2
X
tr tx(X
where
- -Ma))) ) C- En1 (gy, and |X|| is the & norm of the largest
(in magnitude) elements of the matrix X. Problem (2) exhibits a beneficial exact penalty property (Bi
et al. 2014 Bi & Pan 2016). such that || [s] closely approximates |X|| when p exceeds a certain
threshold, thereby leading to solution X with k-sparsity. We define in ) as the indicator function
of the set Ω. Problem (2) coincides with Problem (1) with x vec(X), f(x) tr(X trx),
1.2 CONTRIBUTIONS AND ORGANIZATIONS
The contributions of this paper are threefold. (i) We propose FADMM. new ADMM tailored for nonsmooth composite fractional minimization problems. This method includes two specialized variants: FADMM based on Dinkelbach's '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 e-critical point with a computational complexity of O() This is the first report of iteration complexity results for estimating approximate stationary points for this class of fractional programs. (ii) 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 reviews related work. Section 3 presents technical preliminaries. Section Aictioon/deiiiii details the proposed algorithm. Section discusse global conver- gence. Section 6 addresses iteration complexity. Section 7 provides some experiment results, and Section 3 Meonlludes the paper.
RELATED WORK
We review some nonconvex optimization algorithms that are related to solve the fractional program in Problem (]].
Algorithmss in Limited Scenarios. Existing fractional minimization algorithms primarily address a special instance of Problem (1) that miny F(x) & u(x)/d(xx where u(x) A f(x) + 5(x). (i) Dinkelbach's 's Parametric Algorithm (DPA) (Dinkelbach) 1967) is a classical approach. The frac- tional program has an optimal solution x and only if x is an optimal solution to the problem miny u(x) xd(x), where Ā Fx). Since the optimal value À is generally unknown, iterative methods are used. DPA generates a sequence {x'} as: **1 arg ming u(x) X x()(x). with X
updated as x F (x*). (iī) The Quadratic Transform Algorithm (QTA) (Zhou & Yang 2014 Shen
& Yu 2018:1 8a b) reformulates the problem as: min, -d(x)/u(s + minx,a a a a²u(x)
2ad(x)
QTA generates sequence {x*) as: x arg minx (xxx(())((( 20 1(2))/2 with a updated
as a 1/2 u1x')=1 This method is particularly suited for solving multiple-ratio fractional
2

---

Published as a conference paper at ICLR 2025
programs. (ii)) Linearized variants of DPA and QTA (Li & Zhang 2022 Bot et al. 2023a) 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 al- gorithms at each step, efficiently avoiding inner loops to solve complex nonconvex problems. The proposed ADMM algorithm is built on linearized DPA and QTA solve the subproblems.
General Algorithms for Solving Problem (i) Subgradient Projection Methods (SPM) Li
al. 2021) provide simple and intuitive approach solving Problem (T. SPM iteratively updates
the solution by moving along the negative subgradient direction and projecting onto the feasible set: x Pry(x* n g' where g' E (x & is the constraint set, and 1f' is a diminishing step size. However, due to the non-uniqueness of g'. these methods often exhibit slower conver- gence and numerical instability. (ii) Smoothing Proximal Gradient Methods (SPGM) (Beck & Rosset, 2023; Yuan 2024a; [Bian & Chen 2020, Böhm & Wright, 2021) combine gradient-based optimization with smoothing techniques to handle nonsmooth terms the objective function. By approximating nonsmooth components with smooth surrogates, SPGM enables more efficient up- dates via the proximal gradient method, achieving convergence for complex nonsmooth problems. Notably, the proposed FADMM algorithm reduces SPGM when the multiplier is set to zero in all iterations. (ii) Full Splitting Algorithm (FSA) (Bot et al. 2023b) applies a smoothing technique by introducing strongly concave term into the dual maximization problem, effectively framing the method as a primal-dual approach. However, the convergence analysis of FSA relies on the Kurdyka-Lojasiewiz
(KL) inequality of the problem, and no iteration complexity results are pro- vided. Overall, our proposed FADMM algorithm demonstrates faster convergence and superior numerical stability compared to SPM, SPGM, and FSA.
Other Fractional Minimization Algorithms. (i) Charnes-Cooper transform algorithm con- programming problem to a standard linear programming problem Charnes & Cooper 1962). Using the transformation y प(х
verts an original
x t = पズद Problem dI) can be re-
formulated as: minl,y y tu(y/ /t), s.t. td(y /t) 1. (ii) Coordinate descent algorithms Yuaan 2023) iteratively solve one- mne-dimensional subproblems globally and are guaranteed to converge to stronger coordinate-ve wise stationary points for a specific class of fractional programs. (ii) Inertial proximal block coordinate methods (Bot et al. (203a)), based on the quadratic transform, have been proposed to address a class of nonsmooth sum-of-ratios minimization problems.
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 con- vergence. The standard ADMM was first introduced (Gabay & Mercier 1976), with complexity analysis for convex settings conducted in (He & Yuan, 2012; & Svaiter 2013). Motivated by research on the convergence analysis of nonconvex ADMM & Pong Bot et al. 2019; (Bo & Nguyen 2020 Yuan 2024b), tured fractional minimization problems. To the best of our knowledge, this is the first instance of
et al.. 2016)] propose applying ADMM to solve struc-
ADMM being applied to fractional programs. Our goal is to investigate both the theoretical iteration complexity required to reach an approximate stationary point and the empirical performance of the proposed method.
TECHNICAL PRELIMINARIES
This section presents technical preliminaries on basic assumptions, stationary points, and Nesterov's 's smoothing techniques. Notations, additional technical preliminaries, and relevant lemmas are pro- vided in Appendix Section
3.1 BASIC ASSUMPTIONS AND STATIONARY POINTS
We impose the following assumptions on Problem ( throughout this paper.
Assumption 3.1. There exists a universal positive constant X such that ||ж||| S x for all x e dom(F).
Assumption 3.2. The function f(-) is Ly-smooth such that | - VS(()| S L x'|l
holds for all x' E RD. This implies that: (xx) f(x') (x)()')) x')) -1 (cf
Lemma 1.2.3 in (Nesterov) 2003).
3

---

Published as a conference paper at ICLR 2025
Assumption 3.3. Let ps 0, x' R", and y' Rm.. Both proximal operators, Prox(y':h h, μu) - arg argminy 2u h(y) and P f arg minx 2n 1=|xx- 1xxxx1l x111 0x(),, can be computed efficiently and exactly.
Assumption 3.4. The function d(x) is Ca-Lipschitz continuous with Ca 2 0, and meets one of the following conditions for some W 0: (a) d(x) is Wa-weakly convex. (b) /d(x) is Wa-weakly convex.
Remark 3.5. (i) Assumplion 3.7 holds by setting 0(x) xx(x), where Q is a compact set. This follows from the fact that if x E dom _ {x F(x) +003, then feasible, ensuring that ||*||| & & for some X > 0. (i)) Assumption 3.2
2 is commonly used in the convergence analysis of
nonconvex algorithms. (ii) Assumption 3.3 is mild and is satisfied by our applications. Appendix
details the computation of proximal operators.
We now introduce the definition of stationary points for Problem (T) A straightforward option is the Fréchet stationary point (Rockafellar & Wets. 2009
Mordukhovich (006). Recall that solution 0F(x) O(f +
Fréchet stationary point of Problem ( if: 0
A)/d)
However, computing Fréchet stationary point is challenging for general nonconvex nonsmooth programs. Following the work of (Li al. 2022b Li & Zhang 20222 Bot al.) 2023a bj Yuan
2023), we adopt weaker notion of optimality, namely critical points (or limiting lifted stationary points), defined as follows:
Definition 3.6. (Critical Point) A solution & dom F)) is critical point of Problem [ if: 0 (5(x) + f 0g(()) + A ATh(AA) - (x)))
Remark 3.7. Using Lemma A.1 in Appendix A.2 obtain that OF(x) E g(x) 2(08())
0g(x) + ATal(Ax) F(x (d)(x)) for any x. According to Definition 3.6 O E OF(x) implies that & is a critical point of Problem [7] while the converse is generally not true. However, under certain
mild conditions discussed in (Bot et al. 2023b a). Definition 3.6 aligns with the standard Fréchet
stationary point that E F*)).
3.2 NESTEROV'S S SMOOTHING TECHNIQUE
The nonsmooth nature of the function h(y) presents challenges for the algorithm design and theoret- ical analysis. To address this, we approximate h(y) with a smooth function (y) using Nesterov's smoothing technique [Nesterov] 2003 2013, Devolder et al., 2012), which relies on the conjugate function of h(y). We introduce the following useful definition in this context.
Definition 3.8. For a proper, convex, and lower semicontinuous function hly) : TR + IR, the Nesterov's smoothing function for h(y) with a parameter js (0,)0) is defined as: hy)
max, (y, (v) v
We outline some key properties of Nesterov's smoothing function.
Lemma 3.9. (Proof Appendix C.I) Assume that h(y) is Ch.-Lisschizz continuous. We let μ > 0, and 0 < f2 S f1. We have the following results:
(a) The function byly)) is (l/p)-smooth and convex, with its gradient given by Vhn(y) = arg max, ((y,v) 110)-h"(( hv(vv= [[v]2], it holds that Vhp(y) = # (y Prox(y::, p)).
(b) 0 < h(y) - h,, - / CR
(c) The function (y) is Lipsschchitz continuous.
(d) h1 = 2p I|y - 8113 + h(y), where ý = Prox(y: h.
(e) 0 < hpp (y) - hpp (y) S 3
[ 122)
( // (y) Whn (y)ll S
C)Cr.
Lemma 3.10. (Proof in Section
C.2
Assume that h(y) is Cr. Cn-Lipschitzz continuous. Consider ý Prox(b; (b; hy, 1/ B), where b E R and B, p 0. We have:
arg miny (x) + 30lly bll
(a) y = y+9ub
1+8p where y A Prox(b: h 1/3).
(b) 8(b y) Oh(5)).
(c) |yy 311 S pCn-
4

---

Published as a conference paper at ICLR 2025
Remark 3.11. (i) Lemmas 3.9 and 3.10 can be derived using standard convex analysis and play
essential role in the analysis of the proposed FADMM algorithm. (ûi Nesterov's 's smoothing function
(Nesterov 2003) is essentially equivalent to the Moreau envelope smoothing function (Böhm & Wright 2027 Beck (017), as demonstrated in Lemma 3.).). (üü) Lemma 3. 10 demonstrates how compute the proximal operator Prox(b; hys 1/8) using Prox(b; h J 173). where B 0 and b E 1nth are given parameters.
4 THE PROPOSED FADMM ALGORITHM
This section presents the proposed FADMM Algorithm for solving Problem 11 featuring two vari-
ants: one based on Dinkelbach's ' parametric method (FADMM-D) (Dinkelbach) 1967) and the other on the quadratic transform method (FADMM-Q) (Zhou & Yang 2014 Shen & Yu 2018a). No- tably, FADMM-D and FADMM-Q target different problem structures: FADMM-D is designed for Assumption 3.4(a), while FADMM-Q is suited for Assumption 3.4 3,4bl b), with potential extensions to multi-ratio fractional programs (Bot et al. 2023a).
We first introduce a new variable E RT and reformulate Problem as: y (f(x + 8(x) g(x) + h (d))) Ax = y. where hy) is the Nesterov's s smoothing function of hly), with - 0 as the smoothing parameter. Notably. similar smoothing techniques have been used in the design of augmented Lagrangian methods (Zeng et al. 2022), ADMM (Li al., 2022a Yuan 2025]
2024b), and minimax optimization (Zhang et al. 2020 From this problem, we define two functions,
referred to as modified augmented Lagrangian functions, as follows:
L(x,y; 3, 1))
(3)
d(x)
Kla,,,y;2;3,11 3, 2(x) (004)+=2330)) o2
(4)
where
U(x,y;28,,1) A [(() + (Ax y, 1 Ax v11 +5(x) -((x) + hy)
(5)
Here, (3 is the penalty parameter and 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 {x", y² z² Ae, f ) or {a', xx'''', y", z', , , 1o 1 where 8 f +1++ (tt), μ² 3.. and ( E.P, x} are fixed constants.
Majorization Minimization (MM). MM is effective optimization strategy minimize complex functions and widely used to develop practical optimization algorithms (Mairal 2013 Razaviyayn et al., 2013). This technique iteratively constructs majorization function that upper- bounds the objective, enabling efficient optimization and gradual reduction of the objective function. We define s(x) A S(x,y', ,'x 2'; where is known from context. Given that s(x) is (L + 3rt | | g(x) is convex, and both d(x) or /d(x) are Wa-weakly convex, we construct the majorization functions for the four functions as follows.
(a) s(x) < U (x:x') A s(xt) + (x xx, Vs(')) + 8 | -x x11
(b) -x(x) < R(x; xt) A -(x*) x), Vg E 0g(x').
(c) d(x) < xxxx _ d(x') xxxx Wx ||x
x 112 VE ad(xt).
(d) / /d(x)= < V((x A /d(xt) (x x², E) + Wa
2
||X
- x" x11.. WA ddxx))
FADMM-D Algorithm. Based on Equation 3 FADMM-D alternately updates the primal vari-
ables (x, y) and the dual variable z. (i) To update the variable x, we approximately solve Dinkel-
bach's ' parametric subproblem as follows: + x arg ming (*(x) - s(x) +8(x)- -g(x)- - X (x),
where X' L(x', ((x''y"; z'; S" p²)). However, this problem is challenging in general. We apply MM
methods and consider the following problem:
minx. (x; X²) A 5(x) + (xx + R(x:x") + x'V(x; + (=))(x - -x (6)
where ((35) 2 L, + A + WWa and 0 1. One can verify that (x; X²) is ma- jorization function, satisfying (x) M x² 29) and ('((x!) = Mx(xxxx X2) for all x and
5

---

Published as a conference paper at ICLR 2025
Algorithm 1: FADMM: The Proposed ADMM using Dinkelbach's Parametric Method or the Quadratic Transform Method for Solving Problem (I)
(SO) Initialize {x", yx, y2,²).
(S1) Choose & E (0, 20), 8 E (1, oo), p E (0, 1), and X E (2VT+ oo).
(S2) Choose ( large enough such that 5o y (Fd), satisfying Assumption 5.7
for / from 0 to 7 do
(S3) 3 = (3 + ((P), /² = x/3
(S4) Solve the x-subproblem using FADMM-D FADMM-Q:
if FADMM-D then
Set A U(x*x ,(x',y';z's 3 ; /xx//(xx)), and x++1 E arg minx (x;'', ,²).
end
if FADMM-Q then
Set a a=+1_ v /d(x')/l [Uxx) yx: y²:2';3" 14), and x E arg ming a att1).
end
(S5) y ++1 arg miny h (y) + 2 lyy bl where b' y -yy((xx ; 818/
8r
It can be solved y +8' n'b' where y'+1 A Prox(b'; 1/3²).
1+
(S6) t = x² + (Ax 1+1 -(tt).
end
x". Problem 6 reduces to the computation of a proximal operator for the function 6(x), yielding
x arg minl xx; X²) Prox(x'; 6, (6(3*)), where x' xx g/()(()*)) and g e
Vs(x*) - 0g(x') - xx)) (ii) When minimizing the modified augmented Lagrangian function
in Equation over y, the problem reduces to solving: y E arg miny hy (y) 1 ly b
where b'
VyS(x
(iii) We adjust the dual variable z using the standard
gradient ascent update rule in ADMM.
FADMM-Q Algorithm. Based on Equation (4). FADMM-Q alternates between updating
the primal variables y) and the dual variable z. (i) To update the variable a, set the gradient of K(a,, x, y; 3) w.r.f. a to zero, resulting in the update rule: a+1l
/ /d(x*)/U((x+ z"; B", ,,"). (ii) To update the variable x, we approximately solve the following problem: x+1 arg miny V (x) s(x) + 8(x) g(x) - /d(x). To tackle this challenging
problem, we employ MM methods and formulate the following problem:
min min.''((;; xx;'' +1 ((x) L1 (x;x') + x(xxx')+ a (xxxx)) + 0- 1-10((0))x x² l2, (7)
where E(8t) A Ly +
8 || 3 S Wd, and > 1. One can show that W² S M'xxx''' xxxx"aa++) a11)
and V (x') I (x'x'''' a² 1 for all and x'. Problem (7) can be efficiently and effectively solved, as reduces to the computation of proximal operator for the function 0(x), yielding x x'+1 E
arg minx M'xxx aatt) = Prox(xx; 5, (E(3))), where x' = x² - -g((((()*) and E Vs(x')- d(x'). /d(x').
(iii) We use the same strategy as in FADMM-D to update the primal variable y and the dual variable z.
0g(x') 2 0v
We summarize FADMM-D and FADMM-Q in Algorithm 1 and provide the following remarks.
Remark 4.1. (i) The y y-suppobblem in Step (S5) of Algorithm 2 can be solved by invoking Lemma
3.10 ( The introduction of the strongly convex term "=)((3")lxx x' 112 with 0 > 1 as in Prob- Tems 66) and 7 is crucial to our analysis. (ii)) By minimizing K(a, x, 2; 3, (1) and setting its gradient w.r.t. a to zero, we obtain -1/K(aa Y;y; B, n). Thus, Formulations (3) and (4) are equivalent in a certain sense.
U(x, y; z; B. {)/((x), which leads L(x, y; B. p))
GL.OBAL 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 detailed, separate analysis for each.

---

Published as a conference paper at ICLR 2025
5.1 INITIAL THEORETICAL ANALYSIS
First, we impose the following condition on Algorithm
Assumption 5.1. Let {x') be generated by Algorithm For all 6, there exist constants (d, d}
such that 0 < <d < d(x')= S d and constants {F. F} such that < F F F(x)) <(x) F.
Remark 5.2. (t) The existence of the upper bounds and F is guaranteed by the boundedness of and the continuity of the functions d(x) and F(x) within their respective effective domains. (i) The lower bound condition d > 0 is mild and widely utilized in the literature (Li Zhang 2022 Yuan
2023 Bot et al., 2023b). (iii) The lower bound condition > 0 is reasonable; otherwise, it suffices solve the fractiinli problem: miny u(x).
Second, we provide first-order optimality conditions for the solution y
Lemma 5.3. (Proof in Appendix D.7 First-Order Optimality Conditions) For & 2 we have:
zz+1 Vhy (y*+1) E Oh()*+1).
Third, using the subsequent lemma, we establish upper bound for the term ||z z'
Lemma 5.4. (Proof in Section D.2 Controlling Dual using Primal) For all 2 1, we have: ||z 11 z'
(3') + 1l y + ( 241
Fourth, show that the solution {x', g z²) is always bounded for all t 0.
Lemma 5.5. (Proof in Appendix D.3 Lert 2 0. There exists universal constants {X. such that ||x||| S x, ||2*]] 2, and Iyy|l S
Fifth, the subsequent lemma establishes bounds for the term L1x'' .y', 8'),) Lemma 5.6. (Proof in Appendix D.4 For all t 2 1, we have; E-d-x/P s ;' F.d+ vvB5, where y & 8z.2 2 and v A 24z².
Given Lemma 5.6 we make the following additional assumption.
Assumption 5.7. Assume A
30 y/(F d) >
( Remark 5.8. (i) By Assumption we have 3 go > (/(F-al d), ensuring U(x gh:20 B ,p))) >
O and X 0 for both FADMM-D and FADMM-Q for all t 1. These inequalities are crucial to our analysis (see Inequalities (37. (38)) (ii) Assumption 5.7 automatically satisfied when t is sufficiently large due to increasing penalty update rules. In practice, 3o 1 can be used.
Finally, we demonstrate some critical properties for the parameters { X², a", {(3)))
Lemma 5.9. (Proof in Appendix D.5 Let 2 1. For both FADMM-D and FADMM-Q. we have;
(a) 8 < Be+1 S (1 E)
(b) There exist positive constants {X, }} such that 25 S
(c) There exist positive constants fa, a such that @ S a² a..
(d) There exist positive constants L2, {} such that fC ((3t) s Bt.
5.2 ANALYSIS FOR FADMM-D
This subsection provides the convergence analysis of FADMM-D.
We define e & E(O 12)( > Ey - (1 - 4(1 + <)/x²) ((d) > 0, and e, A E/(2d) 0. We define the following sequence associated with a specific potential function:
p
L(x z':
12(1 + ( +
ATt
AU
We first present two useful lemmas regarding the decrease of the variables (x) and (y, 2, 1,11).
Lemma 5.10. (Proof in Section E. Decrease on the Function L(x, y; z; B.p) w.r. x) For all
t 1, we have: ez8² [|x|+1 x² +(x++1 y": z B 1²)) & L(x', 2²; 88 ,.))).
7

---

Published as a conference paper at ICLR 2025
Lemma 5.11. (Proof in Section E.2 Decrease on the Function [(x. y; (1)
w.E.t
(y, z, (.) For all 2 1, we have: Eyg" ly y'112 + E,3 Ax +
y +
[(x++1, y t ge+1 f C(x 2 Be p()) U + T --+1- T
The following lemma demonstrates decrease property on potential function.
Lemma 5.12. (Proof in Section E.3 Decrease on Potential Function) We let We define
g _ 8 {||x+ x" 112 lly y' Ax
112) We have:
(a) There exists a univeral positive constant P such that Ipt P. (b) It holds that min(en, Ex) < ptt1
The following theorem establishes the global convergence FADMM-D.
Theorem 5.13. (Proof Section E.4 Global Convergence) We let 2 We define & &
8 [1[xx++1 x'11 Ily-=1 - y"1 + || -)) We have: 1 + E S O(T(o-1)/2) In other words, there exists index with 1 S T T such that E S (((T()-))2)).
Remark 5.14. (i) With the choice p E (0, 1). Theorem (513 implies that E4 converges 0 in the ergodic sense. (ii) The convergence & + 0 is significantly stronger than the convergence ||x+11 x'11 |ly - y' + |A y - 0 as {33 Jt=1 is increasing.
5.3 ANALYSIS FOR FADMM-Q
This subsection presents the convergence analysis of FADMM-Q.
We define e - 1) > Ey - 21 - 4(1 + (x))))x)))))))))))))) and e, A 5Ea2 > 0. We define the following sequence associated with specific potential function:
T' A K(aa, xt, y": B* ,x²) + 12xx (1 + C)C ((91)
ÅT
20
The following two lemmas establish the decrease of the variables (X,x} and {y, z, B.B.1,, p].
Lemma 5.15. (Proof in Section
E.5 Decrease on the Function KCAA, x, y; z; B, μ)) w.r.. À and x) For
all t 2 1, we have: K(X++1 x" .y:
z'; 3t p²) + ==xx+ x'113 112 I KC x² B'
Lemma 5.16. (Proof in Section
E.6
w.n.f. Decrease on the Function x. yi z; 3, +++ +
(y, z. (.) For all t 2 1, have: Eyp² lyt+1 y'112 E2 Axt
XC(++1 -x+11 x11 y 21 +,+,11+1 , +1+ 1C(++1 x 41 y' S p²) U + T - - T
The following lemma shows decrease property on potential function. Lemma 5.17. (Proof in Section
E.7 Decrease on Potential Function) We let 2 1. We define
gx 8t [1x=+++ x" 112 + Ily++
1 + Ax y1+) We have:
(a) There exists a univeral positive constant P such that Td 2 P.
(b) It holds that min(E., Ey, Ex Eg
< pp pt+1
The following theorem establishes the global convergence of FADMM-Q.
Theorem 5.18. (Proof in Section E.8 Global Convergence) We let 2 1. We define & A
3r [[|x++1 x'I| |ly y'1 + ||x|+1 -)) We have: 4 - El S ((T(x-1)/2) In other words, there exists an index with 1 S T such that E < ((T()-1)/2)
Remark 5.19. Theorem 5.18 is analogous Theorem 5.13 with εf, converging to O in the ergodic sense.
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 I which will play an important role in our analysis.
8

---

Published as a conference paper at ICLR 2025
Definition 6.1. (c-Critical Point) We define Crit(x* .x .y . - |x* - x1| Ily
||z +IAx+ -y x*+++||0 || - +1100(x )+ --0g)))))((1 +A -p((x.y ad( (x)x)) ||,
and y) {x) + 6(x) g(x) + h(y)) xx). A solution (x xx .y.z is critical
point of Problem ( if:
Crit(xt, x . 2c)
Remark 6.2. (i) If 0, Definition 6.1 simplifies to the (exact) critical point described in
Definition 3.6 (ii The study in (Bot et al. 2023b) introduces a notation of approximate limiting subdifferential to define the e-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 Iteration Complexity for Both FADMM-D and FADMM-Q) We define W {x*+1, xx' ..²+1,, ,y, ,²,z"+1 z.). Let the sequence {W") be generated by FADMM-D
or FADMM-Q. p E (0, 1), we have:
Crit(W") P( (TTO-1))))
In particular, with the choice p= 1/3, we have Crit(W*) S O(T-1/3). In other words, there exists 1 & f < T such that: Crit(W") S c. provided that T 2 (
Remark 6.4. (i) To our knowledge, Theorem 6.3 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 & Rossel 2023 Böhm & Wright 2027). (ii) The point (x xx gi+1, ,y,,,, z²+1, z') rather than the point lem (7) in Theorem 6.3
.y 2. serves as an approximate critical point of Prob-
EXPERIMENTS
This section evaluates the effectiveness of FADMM-D and FADMM-Q on sparse FDA. Additional experiments on robust Sharpe ratio minimization, and robust sparse recovery, please refer to Ap-
pendix Section !
Compared Methods. We compare FADMM-D and FADMM-Q with three state-of-the -f-ie------e-rtttt
general- purpose algorithms that solve Problem (]] (i) the Subgradient Projection Method (SPM)
[Li et al. 2021), (i) the Smoothing Proximal Gradient Method (SPGM) (Beck & Rosset 2023
Yuan 2024a Bian & Chen 2020, Böhm & Wright 202T and (ii) the Full Splitting Algorithm (FSA) (Bot et al., (023b)) For FADMM-D and FADMM-Q, if we fix z' = 0 and Ju 0 for all in
Algorithm I they respectively reduce to two SPGM variants: SPGM-D and SPGM-Q. For FSA, adapt the algorithm from (Bor et al. 2023b) to notation to address Problem ( Implemen- tation details FSA are provided in Appendix Section H We examine two fixed small step sizes,
y (10-3 3 1004), leading to two variants: FSA-1 and FSA-II.
Experimental Settings. For all SPGM and FADMM. we consider the default parameter settings (E,0,p,X) (1/2, 1.01, 1/3, 2 + 10-00-1). For SPM, we the default diminishing step size ny =1 where f is the same penalty parameter as in SPGM and FADMM. For all algorithms, we initialize their solutions drawn from a 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 I describes how to generate the data used in the experiments. We compare the objective values for all methods after running seconds with 20. The corresponding MATLAB code is available on the author's 's research webpage.
Experimental Results on Sparse FDA. We consider solving Problem 22) using the following parameters r = 20, & = 0.1 x and p E (10, 100, 1000, 10000). According to the exact penalty theory (Bi et al. 2014 Bi Pan 2016), a reasonable value for 3 is expected to be at least larger than p. We set 8 100p, which appears to work well. The experimental results for E {10. 1000} are presented in Figures and while the results for E {100, 10000} are provided in Appendix Section [ Based on these results, we draw the following conclusions.
(i) SPM tends to be less efficient in comparison to other methods. This is primarily because, the case of a sparse solution, the subdifferential set of the objective function is large and provides poor approximation of the

---

Published as a conference paper at ICLR 2025
madelon madellon-2000-000 2000-500
(b) 1212-112-1000-11
(c) IDT2-3-4 1000-1200
mmist 2080-768
R
Tima beordo
(c) mushroomm2000-112
giscttc-800-1000
randa-330-1000
(h) randn-300-1500
Figure I: Results on sparse FDA on different datasets with
10.
(a) madelon-2000-500
TDT2-1-2-1000-0000
(c)
1DT223-4-1000-122
(d)
mmist-2000-768
mushroom-2000 2000-1112
(I) gisette- gisette-800-111 800-1000
randn-300-11 300-1000
(h) randn-300-1500
Figure 2: Results sparse FDA different datasets with p 1000.
(negative) descent direction. (ii) SPGM-D and SPGM-Q. utilizing a variable smoothing strategy, generally demonstrates better performance than SPM. (ii) 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. (iv) The proposed FADMM-D and FADMM-Q still outperform FSA, which uses a sufficiently small step size to ensure convergence.
8 CONCLUSIONS
In this paper, we introduce FADMM, the first ADMM algorithm designed to solve general struc- tured fractional minimization problems. Our approach integrates Nesterov's smoothing technique (cquivalent to the Moreau envelope smoothing technique) into the algorithm's 's updates to guaran- tee convergence. We present two specific variants of FADMM: one using Dinkelbach's parametric method (FADMM-D) and the other using the quadratic transform method (FADMM-Q). Addition- ally, establish the iteration complexity of FADMM for convergence approximate critical points. Finally, we validate the effectiveness of our methods through experimental results.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported by NSFC (12271278, 61772570), and Guangdong Natural Science Funds for Distinguished Young Scholar (20188000306025)
REFERENCES
Amir Beck. First-order methods optimization. SIAM, 2017.
Amir Beck and Israel Rosset. A dynamic smoothing technique for a class of nonsmooth optimization problems manifolds. SIAM Journal Optimization, 33(3):1433-14933 2023.
Dimitri Bertsekas. Convex optimization algorithmss Athena Scientific, 2015.
Shujun Bi and Shaohua Pan. Error bounds for rank constrained optimization problems and applica- tions. Operations Research Letters, 44(3):336 34116634111100 2016.
Shujun Bi, Xiaolan Liu, and Shaohua Pan. Exact penalty decomposition method for zero-norm minimization based on mpec formulation. SIAM Journal on Scientific Computing, 36(4))A1451 A1477, 2014.
Wei Bian and Xiaojun Chen. A smoothing proximal gradient algorithm for nonsmooth convex regression with cardinality penalty. SIAM Journal Numerical Analysis, 58(1):858 883, 2020.
Christopher M Bishop and Nasser M Nasrabadi. Pattern Recognition and Machine Learning, vol- ume 4. Springer, 2006.
Radu Ioan Bot and Dang- Phog Nguyen. The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates. Mathematics of Operations Research, 45(2):682-7133 2020.
Radu Ioan Bot, Emno Robert Csetnek, and Dang- Nguyen. proximal minimization algorithm for structured nonconvex and nonsmooth problems. SIAM Journal on Optimization, 39(2):1300 1328, 2019.
Axel Böhm and Stephen J. Wright. Variable smoothing for weakly convex composite functions. Journal of Optimization Theory and Applications, 188(3):628 649, 2021.
Radu Ioan Bot, Minh N Dao, and Guoyin Li. Inertial proximal block coordinate method for class of nonsmooth sum-of-ratios optimization problems. SIAM Journal on Optimization, 33(2):361-395 2023a.
Radu Ioan Bot, Guoyin Li, and Min Tao. A full splitting algorithm for fractional programs with structured numerators and denominators. arXiv:23/2.14334 /4341, 2023b.
Abraham Charnes and William W Cooper. Programming with linear fractional functionals. Naval Research logistics quarterly, 9(3-4):181-186 1962.
Li Chen, Simai He, and Shuzhong Zhang. When all risk-adjusted performance measures the same: In praise the sharpe ratio. Quantitative Finance, 11(10):1439 1447,11477,74 2011.
Olivier Devolder, François Glineur, and Yurii Nesterov. Double smoothing technique for large-scale linearly constrained convex optimization. SIAM Journal on Optimization, 22(2):702-7211 2012.
Werner Dinkelbach. On nonlinear fractional programming. Management science, 13(7):492-498, 1967.
Dmitriy Drusvyatskiy and Courtney Paquette. Efficiency of minimizing compositions of convex functions and smooth maps. Mathematical Programming, 178:503-558, 2019..
John Duchi, Shai Shalev-Shwartz Yoram Singer, and Tushar Chandra. Efficient projections onto the ball for learning in high dimensions. In International Conference on Machine Learning (ICML), pp. 272-279, 2008.
11

---

Published as a conference paper at ICLR 2025
Daniel Gabay and Bertrand Mercier. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Computers & Mathematics with Applications, 2(1): 17-40, 1976.
Jun-ya Gotoh, Akiko Takeda, and Katsuya Tono. De formulations and algorithms for sparse opti- mization problems. Mathematical Praiiculllrrrrre Programming, 169(1):11-177,, 2018.
Bingsheng He and Xiaoming Yuan. On the O(1/n) convergence rate of the douglas- rachford alter- nating direction method. SIAM Journal on Numerical Analysis, 50(2):700- 2012.
Mingyi Hong, Zhi-Quan Luo, and Meisam Razaviyayn. Convergence analysis of alternating direc- tion method of multipliers for a family of nonconvex problems. SIAM Journal on Oplimization, 26(1):337-366 2016.
Michel Journée, Yurii Nesterov, Peter Richtárik, and Rodolphe Sepulchre. Generalized power method for sparse principal component analysis. Journal of Machine Learning Research, 11 (Feb):517-553, 2010.
Rongjie Lai and Stanley Osher. A splitting method for orthogonality constrained problems. Journal of Scientific Computing, (8(2):431-444) 2014.
Guoyin Li and Ting Kei Pong. Global convergence of splitting methods for nonconvex composite optimization. SIAM Journal on Optimization, 25(4):2434-2460, 2015.
Jiaxiang Li, Shiqian Ma, and Tejes Srivastava.
A riemannian admm.
arXiv preprint
arXiv:2211.02163, 2022a.
Qia Li and Na Zhang. First-order algorithms for class of fractional optimization problems. SIAM Journal on Optimization, 32(1):100-12)) 2022.
Qia Li, Lixin Shen, Na Zhang, and Junpeng Zhou. proximal algorithm with backtracked extrap- olation for class of structured fractional programming. Applied and Computational Harmonic Analysis, 56:98-16510 122, 2022b. ISSN 1063-5203.
Xiao Li. Shixiang Chen, Zengde Deng, Qing Qu, Zhihui Zhu, and Anthony Man-Cho So. Weakly convex optimization over stiefel manifold using riemannian subgradient-type methods. SIAM Journal on Optimization, (1(3):1605-1633 2021.
Julien Mairal. Optimization with first-order surrogate functions. In International Conference on Machine Learning (ICML), volume 28, pp. 783-791,2011 2013.
Renato DC Monteiro and Benar Svaiter. Iteration-complextty block-dccomposition algorithms and the alternating direction method of multipliers. SIAM Journal on Optimization, 23(1):475- 507. 2013.
Boris S. Mordukhovich. Variational analysis and generalized differentiation i: Basic theory. Berlin Springer, 330, 2006.
Boris S Mordukhovich, Nguyen Mau Nam, and ND Yen. Fréchet subdifferential calculus and opti-
mality conditions in nondifferentiable programming. Optimization, 55(5-6):685-708, 2006.
Yu Nesterov. Gradient methods for minimizing composite functions. Mathematical programming. 140(1): 2013.
Yurii Nesterov. Introductory Lectures on Convex Optimization: Basic Course, volume 87. Springer Science & Business Media, 2003.
Neal Parikh, Stephen Boyd, al. Proximal algorithms. Foundations and trendy@ in Optimization, 1(3):127-23,, 2014.
Meisam Razaviyayn, Mingyi Hong, and Zhi-Quan Luo. A unified convergence analysis of block successive minimization methods for nonsmooth optimization. SIAM Journal on Optimization, 23(2): 126-1153, 2013. 2013.
12

---

Published as a conference paper at ICLR 2025
R. Tyrrell Rockafellar and Roger J-B. Wets. Media, 317, 2009.
Variational analysis. Springer Science & Business
Siegfried Schaible. Fractional programming. pp. 495-608, 1995.
Kaiming Shen and Wei Yu. Fractional programming for communication systems part i: Power control and beamforming. IEEE Transactions on Signal Processing, (66100)2616-266) 2018a.
Kaiming Shen and Wei Yu. Fractional programming for communication systems part uplink scheduling via matching. IEEE Transactions on Signal Processing, 66(10):2631-2444 2018b.
Antonio Silveti- Cesare Molinari, and Jalal Fadili. Generalized conditional gradient with aug- mented lagrangian for composite minimization. SIAM Journal on Optimization, 30(4):2687- 2725, 2020.
Ioan M Staneu-Minasian Minasian. Fractional programming: theory, methods and applications, volume 409. Springer Science & Business Media, 2012.
Chao Wang. Min Tao, James G Nagy, and Yifei Lou. Limited-angle ct recostrrcttion via the 1.//22 minimization. SIAM Journal on Imaging Sciences, 14(2):499-777, 2021.
Guanghui Wang, Ming Yang, Lijun Zhang, and Tianbao Yang. Momentum accelerates the conver- gence of stochastic aupre maximization. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 3753-3771, 2022.
Zhiqiang Xu and Ping Li. A practical riemannian algorithm for computing dominant generalized eigenspace. In Conference on Uncertainty in Artificial Intelligence (UAI), pp. 819-828, 2020.
Junfeng Yang and Yin Zhang. Alternating direction algorithms for i l-ppoollems in compressive sensing. SIAM Journal on Scientific Computing, 33(1):250-273 2011.
Ganzhao Yuan. Coordinate descent methods for fractional minimization. In International Confer- ence on Machine Learning (ICML), pp. 40488-40518, 2023.
Ganzhao Yuan. Smoothing proximal gradient methods for nonsmooth sparsity constrained optimiza- tion: Optimality conditions and global convergence. In International Conference on Machine Learning (ICML), 2024a.
Ganzhao Yuan. Admm for nonsmooth composite optimization under orthogonality constraints. arXiv:240S.15129, 2024b.
Ganzhao Yuan. Admm for nonconvex optimization under minimal continuity assumption. In Inter- national Conference Learning Representations (ICLR), 2025.
Alp Yurtsever, Olivier Fercoq, Francesco Locatello, and Volkan Cevher. A conditional gradient framework for composite convex minimization with applications to semidefinite programming. In International Conference on Machine Learning (ICML.. pp. 5727-5736, 2018
Jinshan Zeng, Wotao Yin, and Ding-Xuar Zhou Moreau envelope augmented lagrangian method for nonconvex optimization with linear constraints. Journal of Scientific Computing, 91(2):61, 2022.
Jiawei Zhang, Peijun Xiao, Ruoyu Sun, and Zhiquan Luo. A single-loop smoothed gradient descent- ascent algorithm for nonconvex-concave min-max problems. Advances Neural Information Processing Systems (NeurIPS), 33:7377-7389, 2020.
XueGang Zhou and JiHui Yang. Global optimization for the sum of concave-convex ratios problem. Journal of Applied Mathematics, 2014()):879739, 2014.
13

---

Published as a conference paper at ICLR 2025
Appendix
The appendix is organized follows.
Appendix A
presents notation, technical preliminaries, and relevant lemmas.
Appendix
B
provides additional motivating applications.
Appendix
contains proofs for Section 3
Appendix
contains proofs for Section
Appendix
contains proofs for Section 5
Appendix
contains proofs for Section
Appendix explains the computation the proximal operator.
Appendix demonstrates additional experimental details and results.
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)
|||| Euclidean norm: ||x|| = ||x|| = V (x,
XT_ the transpose of the matrix X
vec(X): the vector formed by stacking the column vectors of X with veo(X) Ra
mat(x): convert x E g into a matrix with mat(vee(X) (X)) X with mat(x) E Rexr
Op zero matrix of size r: the subscript is omitted sometimes
I,: identity matrix with I, E Rrxr
X = matrix is symmetric positive semidefinite
||X||= Frobenius norm: EEi X2 1/2
0x(x): limiting subdifferential of f(x) at
4x()) the indicator function of set Ω with (x(x) = 0 if x E Q and otherwise +o0
tr(A): Sum of the elements on the main diagonal with tr(A) = Σ, Ai,
(X, Y): Euclidean inner product, i.e., (X, Y) Eij X1; Yúp
|X|| Operator/Spectral norm: the largest singular value of X
dist(E, E') the distance between two sets with dist(E,E)) & inf infxeE |x x'I
[]F(()]]: [}aF(x)) = infxceF(x) ||z||F = dist(O, (F))
| & norm of the largest (in magnitude) elements of the matrix
x4: the i-th element of vector
Xs,j or X:j the (hh element of matrix X
Pa((')= Orthogonal projection of X' with Pa(X') = arg minxen |X' X|
δ.(x) + Ōœ(x): standard Minkowski addition (or subtraction) between sets åp((x) and 0xp(x)
A.2 TECHNICAL PRELIMINARIES ON NONSMOOTH NONCONVEX OPTIMIZATION
We present various techniques convex analysis, nonsmooth analysis, and nonconvex analysis Mordukhovich et al.) 2006 Mordukhovich 2006 Rockafellar & Wets. 2009; Bertsekas 2015),
encompassing conjugate functions, weakly convex functions, the Fréchet subdifferential, limiting subdifferential, and rules for and quotient in the Fréchet subdifferential context.
14

---

Published as a conference paper at ICLR 2025
For any extended real- valued (not necessarily convex) function f R" (-00, too], we denote by dfm == {x E R" : f(x) < + its effective domain. The function f(x) is proper if dom f) + 0. The function f (x) is lower-semicontinuus at some point X R" if lim x f 2 f f(x).
Conjugate Functions. For a proper, convex, lower semicontinuous function h(y) R H RR we denote the (Fenchel) conjugate function of h(y)) as h- (y) - supvedam(h) {y vv h(v)), and it follows that hy) h(y) suPvedom(h-) {y 1y - h- (v)),. where ht* (y) is called the biconjugate function. For any μ O, we have that (ph)" (y) = suPxedom(M) {(y,x) ph(x))
(x) For any x, E RR, the following statements are equivalent (see (Rockafellar & Wets, 2009). Proposition 11:3): (x.y) = h(x) + h hy(y) y E ah(x) + x E (y) The conjugate of the support function of closed convex set 52 is its indicator function, i.c., h(y) supven (v.y), and h." (v) = in (v) Typical nonsmooth functions for h(y) include (lly max y) I1 loll
with their respective conjugate functions h" (y) being (1[-1.))m)) (y), (001] 11 (y)).
Weakly Convex Functions. The function d(x) is weakly convex if constant Wa 2 0 exists, Wa ||x convex, with the smallest such Wa known as the modulus of weak convexity. making +((x)++ 2
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-continuuut functions with -smoohh mappings that have Lipschitz continuous Jacobians
Drusvyyaskii & Paquette 2019).
Fréchet Subdifferential and Limiting (Fréchet) Subdifferential. The Fréchet subdifferential of F at x E (f)(F), denoted as (x)), is defined as
dF(*) VEER VVER:
R" lim inf F(x)
F(X)
(v. x) x
0).
x xxxx
The limiting subdifferential of F(x) at x E dom(F), denoted as OF(x). is defined as
OF(x) & VEE Ex* + F(x) + F(X), vt E @FF(xt) - v, Vkk
It is straightforward to verify that OF(x) S aF(x). (()F)(z) adF(z) and (()F)x)) (a)( hold for any x E dom(F) and a > O. Additionally, if F(.) is differentiable at x, then 0F(x) = (x = -[V((x)) with Fx(x) being the gradient of F(-) at x; when F(-) convex, (F(x) and 0z(x) reduce to the classical subdifferential for convex functions, i.e., (x(x)= = 0F(x) = {v E R" F(z) - F(x) - (v, - x) 2 0, Vz E R"
Sum and Quotient Rules for the Fréchet Subdifferential. First, examine sum rules for the Fréchet subdifferential. Let ΦI, 82 R" + (-xc, +oo be proper, closed functions, and let x E dom((p1) n dom((22. Then, (x) + 0x2(xx S Ō(61 + (x), where equality holds 4p or 422 differentiable at x (See Corollary 10.9 in (Rockafellar & Wets. 2009)). Moreover, 0(f) + (x) S (x) + @xp((x) holds when 1o or 4o is locally Lipschitz continuous at x, and it holds with equality when 1 or 62 is continuously differentiable
(See Exercise 10.10 in
Rockafellar & Wets. 2009)).
We review the quotient rules for the Fréchet subdifferential. The concept calmness (Rockafellar & Wets. 2009) plays an important role in our analysis. A proper function R + (-o0, + is ) if there exist E > 0 and λ > 0 such that [g(x) - g(x') S x||x x')
said to be calm at x E dom(gg
for all x' E E) A {z E IR" ||z - x| < E}. Many convex functions, including Lipschitz
continuous functions, satisfy the calmness condition.
We define y R + (-o0, +oo] at x E R as:
(x()
if E dom( and (2(() + O,
(x) =
(x()
+00,
else.
The following lemma concerns the quotient rules for the Fréchet subdifferential.
15

---

Published as a conference paper at ICLR 2025
Lemma A.1. Let (1 IR + (-00, and (22 I=" + R. be functions which are finite at x with (22(x) > We denote a1 := &1 (x) and 02 == P2(x). Suppose that yi is closed and continuous at relative to coom(f1), that 92 is calm We have the following results:
(a) It holds that: 0p(x) = d3 (0(a2p) (x)).
(b) If (2((x) differentiable at x, then 0p(xx) ag (azd(p(x)) - on Vp2(x)))
(c) If a1 2 0 and (22(x) is convex, then 0l(xx az (0(0211)xx) andp2(x)) S
1 22 (0(11)(x))) (x)(
Proof. Refer Proposition 2.2 in (Li & Zhang 2022) and Lemma 2.1 in (Bot et al. 2023a). We
omit the proofs for conciseness.
A.3 RELEVANT LEMMAS
We present some useful lemmas that will be used subsequently.
Lemma A.2. (Extended Morcau Decomposition) Assume h2y) is convex. For any > and b E
RT. we define Prox(b; h, μi) & mig h(y) + | | y11.. It holds that: b = Prox(b; h, μ1) + a Prox ; h", 1
Proof. The conclusion of this lemma can be found in Nesterov 2013 completeness, we present the proof.
Parikh et al. 2014). For
We define y A Prox(b; h, n). We derive:
b- E k(u)(())
& y E (((h))))(b y)
y) E (((uh)))(( b (b -b-y)
e - y y- Prox (uh));
3 b Prox(b; h, 11) + p Prox ( h² #
where step ! uses the definition of the conjugate function, and the property of the subdifferential that Th(y)) y Oh 0h*(v), (v): step @ uses the following derivations that: arg miny (1h)) (y) +
lly bll arg miny ph" (y/p) blly bll aag miny h²" hy((") f b/ull2
y Prox h* 1
Lemma A.3. Let Br A 81 {(P) and ne th. where 3o 2 andd & E (0, 1). For any integer t t2 1. we have: (1--) - 1 t+
Proof. We define l(t)) A tP, where p E (0, 1).
Given the concavity of f(t), follows that: h(y) h(x)) S (y-xx, x,, Vh(z)). Letting x = t
and
y = t, for all > 1, we have:
P- -1-113 S pll 1)p-1
(8)
Part (a). When f 1, we have:
(4 1)2 (
6
(30
g1
1)2 3 = g2 3 3
-2
1+1
Part (b). When / > 2, derive:
1 a² - 1)2
1)2
2
14E00 _
- 1)2 <
1
1)2
[+t(!-1)=
1ー
1)
((t 1 = 1-
6
H1
16

---

Published as a conference paper at ICLR 2025
where step ① uses μ² 3 step @ uses 3r = (1 (t"); step @ uses 1
1-5ep
1+
g(t-1)m>
step @ uses Inequality ( and I I; step & uses --- S
6 for any integer 2 2. F+I
Lemma A.4. For all t 2 L. p (0, 1). It holds that: -1 S 1)p 10 -2p(t 1)0-1 50.
Proof. We assume i 2 and E (),
First, consider the function (tt) = t We have Vh(t) pt and (2)(t) p(p 1) < 0.
Therefore, Iu(() is concave. For all æ > 0 and y > 0, we have: h(x) - h(y) 2 (r Vh(r)).
Letting and y = L have:
8 (t 1)p -pt
(9)
Letting 1.4 and y
have:
(t + 1)P t² 2 p(t + 1)p-1
(10)
Second, we shown that 80 < 2 1)-11 Given 2 have: (+1 2, leading to (++ (tt1p-13 28-1 2
We obtain:
0 2
(11)
Part (a). We now prove the upper bound. We derive: (t + 1)p t² - 2p(t + 1 (p-1)
S ptp-1
2p(t + 1)(x-1) S 0, where step @ uses Inequality ( step @ uses Inequality
1
Part (b). We now focus on the lower bound. We obtain: (1 + 1)P IP 2p(1 + 1)p-1 2 p(l +
@ 1yp-1- 1pp-1-2p(t-- + 1 +(t+1)p-1 -p -1, where step @ uses Inequality (10 step 2 uses (t 1) < 1; step @ uses S 1.
Lemma A.5. For all t 2 1, P
< E (0, 1). It holds that: (1 (1-p)Ti-P<) >D' 1
I
T'-P I-p
Proof. let 2 1, p (0, 1). and q E (0, 1). We define h(t) & [t + 1)
9ta
First, we prove that h(1) 1229
2 0. We let f(4) = 29 - - We have Vf(g)= =
l2(2)2 2q and V2 fz)(()) 1n(2)22n - < 12(2) 2 0. Therefore, f(q) concave. The global minimum lies in the boundary point. We have h(1) 2 min(f(1),{(0) min(20
02, 0², 21 - 1 12) 0 = 0. Therefore, we have:
h(1) = 2 1 - O.
(12)
Second, we prove that htt) We have: Vh(t) (t 1)0-1 -tt-tgtt--1 2 8--1 9t--1= (1 11-9) 4)(4-1 2 0. Therefore, the function lo(t) is increasing. We further obtain:
n(t)= A 1 (t 1). q qt 2 h(1)
0,
(13)
where step ① uses Inequality 12
Third, we define h(t) P. Using the integral test for convergence
we have:
1 T+1 Ma)de Σ M() ((1) S h(x)dx.
17

---

Published as a conference paper at ICLR 2025
Part (a). We define g(ø) = I-p
1 1.-P.. We derive: Ei to S g(1) + Sr x dd _ + g(T)
g(1) 1 (T) 1 - Ti- T(--))
1-p where step @ uses Vg(x) = step 2
1-p
1-p
uses Inequality with y = and 1 T.
Part (b). We derive: E p 2 Σ 1= S
p++
Pd
f x Pdr 2 g(T + 1) g(1) =
[T+
(T (T+1)
1 2 (1 p)T P, where step @ uses Vg(æ)) = x P; step @ uses Inequality I-p
with q = p and t = T.
B ADDITIONAL MOTIVATING APPLICATIONS
Robust Sharpe Ratio Maximization (Robust SRM). Recall that the standard SRM, which op- erates without data uncertainty and is commom in finance, can be formulated as: maxxen d x-x where = 0 is the risk covariance matrix, d E R are the expected returns, / is the risk rate, and Ω - {x x 2 0, 1 = 1} ensures valid portfolio weights (see (Chen et al., 2011 Bo! et al. 2023b)). In contrast, the robust SRM, designed to handle scenario data uncertainty, is defined by: milxee? maxx; (b, (Dx):
xTCx
max, x ,,,x where each ((a) 52x= > 0, b E RT and D E [Rmx.. The corresponding equivalent optimization problem is formulated as:
max(0, max(b - Dx)) max!" x C()x
min XER
.s...x Ω.
(14)
We use max(0, max(b - max(b-Da))
Dx)) instead of simply max(b Dx) to explicitly enforce nonnegativity
in the numerator for all x E Ω. Problem (14) corresponds to Problem ( with f(x) g(x) = 0, 5(x) = 'o (x). A DD, hu()) = max maxxyy + b)), and d(x) max" x (x)x. Notably, both dxx) and d(xx) 1/2 are Wa Wa-weakly convex with Wa = 0.
Robust Sparse Recovery. It is signal processing technique, which can effectively acquire and reconstruct the signal by finding the solution of the underdetermined linear system. Given design matrix A E mx and an observation vector b RT robust sparse recovery can be formulated
as the following fractional optimization problem (Li & Zhang 2022 2023):
Yang & Zhang 2011
Yuan
min Pi Ax blI1 + x2| XER"
t.t.xx Ω
(15)
[x][M]]
where Q 2 {x] x < po). and po. P1, are positive constants provided by the users. Problem
15 coincides with Problem (1) with f(x) = g(x) O, dx) = <x(x) + p2 |x|]] h(y) I| bll
and (xx) = | [ Importantly, d(x) is W Wa-weakly convex with Wa = 0.
C PROOFS FOR SECTION
C.I PROOF OF LEMMA 3.9
Proof. The results of this lemma can be derived using standard convex analysis. Some of these results are well-established and scattered throughout the literature (Nesterov) 2003] Yurtsever et al.)
2018 Silveti-Falls et al. 2020: Nesterov 2013). For completeness, we provide the full proofs of the lemma
For any y R: we define (y) & max, (y, v) -v) - j--ttoonlly convex. the maximization problem has a unique solution and thus the subgradient set is single set (Nesterov) 2003), i.e., (y) (y) arg max, ((y, h²(vv) [
Since μ 0 and [[v is
18

---

Published as a conference paper at ICLR 2025
Part (a). We now prove that (y) is (1/p)-smooth For any y1. E RR, define V1
arg maxy ( - - hv(()= (1 and V2 = arg ( l²(v)= 2 We have:
lly y2llll1 - v2ll (y1 - -2, V1 - v2)
l/
(Vv1 - V2, - v2) + (0h"(vi) -
Ivee
|lll
V2 v1ll2 +0,
where step @ uses the Cauchy-Schwarr Inequality; step @ uses the optimality of Vi that y1 Oh (v1) μ = 0 and the optimality V2 that y2 - ah" (v2) WV2 = O; step uses the monotonicity of subdifferentials for the convex function h hv(v). Dividing both sides by [[v v2ll.
we have:
v - S :. which implies that the function (y) is (1/p)-smooth.
We now prove that the function (y) is convex. For any Y1 E In and > 0. we define u1 = arg maxx.((y1..) u) - h-" (u) #/ || [2]] and u, = arg max (y2, u) h²(u)= - [/ We
have:
ha(y1) - 1 (y2)
(y1) (()2, u2) - 11" (u2) ||uu 12:
(y1) - (6y2, un) - ((((()) - ||u
2 ((y1, u1) - -²((u)) - 1| [12] ((y2. un) (",))) 21 12)
(u1,y1-y2))
where step ① uses the definition of by (y2) and u2: step @ uses the optimality of ug: step @ uses the definition of (y.).
Part (b). For any y E Thm and f > O, we define hy) max, (y, v) 1²(v)) 11
ul A arg aargaaxu (y, u) h1' (u)}. and u2 A arg max i (y, u) h²" h*(l) [1]
b-i). We now prove that 0- < lly)) hy))). We have:
hy(y)) max(v' Ty - hv))()) -v)
S mmax(vT) Ty - [v))]] + max 1
h(y),
where step ④ uses a general property of the maximum function when applied to the sum of two functions; step @ uses the definition of hly) = maxv(v"x y h (v)} and the fact that max. - v = O.
b-ii). We now prove that h(y) hv) S C0G. We have:
Myy) hyl 1 ((y, un) -u*("))) hy(y)
(ly, un) - -=r))) ((y, hh(un)) (1111113)
21 / (x)]1
where step D uses the definition of h(y): h(y) = ((y, un - -=())) step uses the definition of
(y) and the optimality of uz: hy) fly, uz) h² (ug) - 1 [u [1]) (ly, un) h² (u,)
(/ml(() step @ uses Claim (b) of this lemma.
19

---

Published as a conference paper at ICLR 2025
Part (c). We now prove that the function (y) is Ch -L-Liscchitz continuous. For any y E R" and
f O, we define (y) & maxy (y, v) - (v) +[vv] 1. We have:
(yy _ arg ((,, v) - 11vv1
arg (h'(v)+++++)) y
_ Prox p h"; 1/p)
(y Prox(y: h p))
(16)
(Prox(( h pi),
(17)
where step ① uses the fact that the function (y) is smooth and its gradient can be com- puted as: (y) = arg max (y, v) - (v) - _ step @ uses the definition of Prox(b; h) u) A arg miny h(y) + zn. [|b y112: step @ uses the extended Moreau decomposi-
tion property shown in Lemma A.2 step 4 uses the optimality of Prox(y; h. μ1) that 0 (. (Prox h, (4) y). Using Equation 17 we directly conclude that (hy
is Ci-Liisscitzz continuous with V/, (y)) - Cj.
Part (d). We show how compute (y). For any y E R and μ O, we define hy) &
max, (y. - hv( [11 and v = arg maxy ((y,)) h²
123. We have:
y uV (
(y Nv, v) h-" (v) + hly μV).
(18)
where step @ uses the equivalence relation: (x (y) + ý 0h(()) + (y) for all x and y, as stated in Proposition 11.3 of [Rockafellar & Wels. 2009) Therefore, we have:
ly)
① (y, v) - h2" (v) - 1
1 v) - -(y -v, v) - -ily - pv) - 11
Vy - (y -y--v v) + >>(Prox(y; h. 11) - ~/2 |
h(Prox(y: h, 1J) + |1 (y Prox(y: : h. p))
where step ④ uses the definition of h (y): step @ uses Equation 18 that h" (v) = (y μv, v) hiy nv);; step @ uses v (y Prox(y: (y; h, 11), as shown in Equation (16).
Part (e). For any y E Imm and μh P2 > with #2 S μ1, we define un = arg max ma u1
h" (u) - u (2) and U2 = arg max ( (y, U) hu) 4 (1
e-i). We now prove that < hpz (y) - hpm (y) for all 0 < μi S pi We have:
hu (v) - hx)
((y, u1) - 11" (u,) - - 14:1[1,11 [ - hwa (y)
(yy, ui) - (hr())) - 11 - ((y, u1) - -u-())) - (1
Ma 1 |
where step ① uses the definition of hu, (y): h (y) = {(y, u1) - h1" -u,) 11 || [|]] step step @ uses
the definition of hpz (y) and the optimality of ug! hpz (v) ((y, u2)
h-" (uz)
122 || 113) Z
((y, un) h² (un) #2 | [1 step @ uses μ22 S p1.
20

---

Published as a conference paper at ICLR 2025
e-ii). We now prove that 222 (y) - hus (y) I 21 C for all 0 #2 S p1. We have:
Muo (y) Aps (y)
{yy, U22 11" (11)
Ka 112 ())
hpp (y)
(y, U2)) 11" (up)
M2 [|_ {(y, u2) h1" hh()2)))))))))))))(()
My 2
|22l22
Mi p2
u2 12 P1 [h,,, (y)ll
M1 ا Ch
where step @ uses the definition of hu (y): Auz (y) f(y, u2) - 11" (u2)
2 |
[2]: step 2 uses
the definition of hy (y) and the optimality of un: hu (y) ((y,
h-" (u))
- u [1 2
(yy, U2) h²" (u2)
| l13;; step @ uses Claim (b) of this lemma.
Part (f). We now prove that // (y) - Vhha (x)ll s Li 1)C, for all 0 < <12 S μ4. Using
Equality 116 we have:
(y) = (y - -Prox(y; H,
We now examine the following mapping H(v) - u(y - Prox(y; h, 1/0)). We derive:
lim
M(v+6)- H(w)
lim (ortiyy-PPaxxyyhh////40000 Proooyyyho))))
6-0
5-+0
lim
8-0
y Prox(y:: h, 1/v).
Therefore, the first-order derivative of the mapping H(v) wet. v always exists and can be computed as: V H(v) y Prox(y; h, 1/v), resulting in:
Vu, v >
[
< Ily h,
Letting 1/Pr and v 12, derive:
v ,, (y) (y]ll
1y hr,
1/21-1/P9
(Pllon(Prox(y: h, px))
MrC,,
where step ① uses the optimality of Prox(y: h, v1) that 0 Oh(Prox(y: h, p1)) +
1 (Prax(y; h, (1) - y) for all #1; step @ uses the Lipschitz continuity of h(-). We further ob- in
tain:
Vhp, (x) Vhyn (x)l S 1 +1 -ICA = - - 1)Cr.
122
C.2 PROOF OF LEMMA 3.10
Proof. Consider the strongly convex minimization problem: ý arg miny hu(y)) + 3Blly bll.. which can he equivalently repressed as:
(ý, v) arg min max Ty - hv) ||vl 1 f ---bbil 12]]
Using the optimality of the variables {y. v). we have:
y = b 1 V.
(19)
0 Oh. (v) WV +
(20)
21

---

Published as a conference paper at ICLR 2025
Plugging Equation (99 into Equation 20 to eliminate y yields:
--h pv + V..
(21)
Second, we derive the following equalities:
@ arg max (v) + (v. b) #1lv112 2/ 1
(22)
= arg min (-(vv= - (v, b) + + 1>
arg min (1(vv) + 2 + ) b/(μ + 1112
Prox( w hi m+1/73
x+1/B (b- Prox h + })
(23)
E @h(Prox h u })),
(24)
where step ① uses the fact that Equation 21 is the necessary and sufficient first-order optimality condition for Problem (22); step @ uses the definition of Prox(-;-.-) step 3 uses the extended Moreau decomposition that Prox (a; h (4) + u Prox(";;", h", 1/p) for μ > 0 and a, as shown in Lemma A.2 step @ uses the following necessary and sufficient first-order optimality condition for Prox(b: h 8)
#+15B {b- - Prox + })} e Oh(Prox(b;h, p })).
Part (a). Combining Equation
23 with Equation
19
to eliminate V, we have:
y b B a+1/B Prox h + 1/3)}
b n8+1 fb Prox(b; h, 1/8)).
Part (b). We define y A Prox(b; h, H + 1/3). We have:
3(b y) ab+1 {b- Prox h1 + 1/3)}
a+1/B {b- }
v E ah
(25)
where step @ uses Claim (a) of this lemma; step @ uses the definition of y; step @ uses Equality 23 ; step 4 uses Equality (24) that v E dh
Part (c). We now prove that y 811 S μCh. We derive:
yy y
b Bu+I (b - y) - -
Bu 1+8p 11 - bll
Bp (p 1/ 1/3)|iah(5)1
1+0p
Bu 1+3p (μ 1/8)Cb = μCO:
Buti (b- y): step @ uses Equality 25 that b - ý E (μ + 1/8)0k(y); step 3 uses the fact that h(y) is Cx-Lipschitz continuous.
where step @ uses Claim (a) of this lemma that y =
22

---

Published as a conference paper at ICLR 2025
D PROOFS FOR SECTION 4
D.1 PROOF OF LEMMA 5.3
Proof. Part (a). We now show that zz+1 Vhy (hinccy(+)) (y For any 2 we have:
++ 13 Vhye (y ) + 8d (y - y²) + (x Ax z²
Vhyye (y ++ + By(tt - y²) + VyS(x
Vhne (y =z"t1
where step @ uses the optimality condition for y step @ uses vyS(x*+) y':2':80) By
Ax z²; step @ uses z z' (Ax -ytt)).
Part (b). We now show that Vhn (y ++ E @h(r)t2). For any 2 0, we have:
(b y(t ah(y++1)
(Ax (+ + z² 1Bt -(1
1t!1
where step ① uses Lemma b)) step @ uses bt = = - VyS(xx'1 2 = y
(B Ax z²) 2² Ax ++1 + z /3 step uses z²+1 z² = (Axxx( -p--1).
D.2 PROOF OF LEMMA 5.4
Proof. Since can be arbitrary, for any t t> 1, we have from Lemma 5.3
0 = Th - z =++1
0 = Vhya-i (y²) - z'.
Combining the two equalities above, we have, for any 1 2 1:
++1 z' Vhyt (y +1) (
This further leads to the following inequalities:
||z z' 11
Vhyue (y 11 Vhat 113
V Vhy (1) Thyi (y*) Vh (y²) -
2 Vh (y (11 Tha (y¹) + 2 Wh (y") Vh2 1>x')11
3 211 + (y ++ (y*t1
y'11 + 2( + 1)²C%
a (0))
$ x² Ily 4+1 y + 2C -
6
where step ① uses
step @ uses ft a + bbl3 < 2 2|aa|/2 + 2/
1 -moothhess of hn (y) for all y, and
Lemma 3.9 f) that
| (y) - V/ - -IC, for all 0 < #2 < pr step 3 uses n²¹ = *
for any integer t 1. and Lemma A.3 that n 2)² & œt
D.3 PROOF OF LEMMA 5.5
Proof. We define 7 A max([1z9) Ck), and y max(lly"11 2z4 + ||
Part (a). The conclusion ||x|| < directly follows by assumption.
23

---

Published as a conference paper at ICLR 2025
Part (b). We now show that
|z'|| < z. Using Lemma a.) we have Vt 2 0, z²+ Vhy (y+++1)
This leads to Vt 2 1,
|
x W (xy))())) (y")l I| $ Ch. Therefore, it holds that Vt 2 0, ||/1 S
max([|=9],, C.) A z.
Part (c). We now show that ||y'Il S.. For all 2 0, we have:
lly
|y
@
Jo (z t+ 2²) Ax
180 (1|Z || + || II) + |||||***
+ + |
where step @ uses x0+1 = x' + 3r 3Ax - y step @ uses the triangle inequality, the norm
inequality, and 3 & g:: step @ uses the boundedness of z and x'. Therefore, it holds that Vt 2 o, Ily S max([|y"||, _or + | x) y.
D.4 PROOF OF LEMMA 5.6
Proof. We define U (x, y: 3, (4) & 8(x) - f(xx g(x) + h,,(y) + (Ax- yy.z) +511Ax y122-
We define y - 822 + xxx², and _ 166?.
First, given hyy) is convex, for all y, y' Rm, we have:
h(y') - hly) S (Oh(y'),'' -y)
(26)
Second, for any y R. and & 2 I, we have:
(Ax' - -y ah(y))
_ - (z' z²11, - -hly))
3 ||z z2-11 111.11zz= ah(y)ll
# 2z (7 + [10h(y)]l)
$ #/4 27 27,
(27)
where step @ uses the z²+1 z' (Axx y(+1); step @ uses the norm inequality and
3r < 2,3-11; step 3 uses ||z'|| < 7 and /h (y)ll S Cn S 7, as shown in Lemma D.3
Third, for any t 1, have:
gt Ax
y011 Ø
8'1
1
(z' z'
)11
B
3
2
||z -
(
1| 211
$
(2/12/1 + 2/122'
$22
(28)
where step ① uses the z+1 z' = +1x*+1 y + step @ uses 3t < 25t-11 step uses
3r 2 300 for all / ' 0; step @ uses |a blß < 21la| + 2|
step @ uses || < n.
24

---

Published as a conference paper at ICLR 2025
Part (a). We now derive the lower bound for any t 2 1, follows:
U(x', y 2 8 n - f(x²) + -(x²) - g(x)) + (Ax' y", 2²) + 86 || - -y'13 + N (x9)
2 F d(x') - -(Ax') + (Ax' - y²2z²) + 2/2 11Axx -y'13 + (y')
8
*
2 F d(x(xxx + +M(y)) m(Ax)) (Axx -²,=²') + (x') h(y'))
* 2 F -(x('') + (Ax' -y'z'' -bx()x))) c²
2 F d(x')xx
88 X2²
Br. 23
- F d(x')= TF:
where step C uses F(x') A +((xx))())) (elsss")ggxx00 g(xxx
( 2 F; step @ uses T
8 A|xx' - -y'13 2 0; step
d(x))
@ uses Inequality (26) with y y' and y' Ax', and the fact that h(y) S hy) + +,, (Lemma
3.9 b)); step @ uses Inequality (27p. jet N.. and C₁ S 2, step @ uses the definition of y.
Part (b). We now derive the upper bound for any 2 1, as follows:
U(x', 12)
- f(xx)+ + 5(x)) - g(x') + (Ax' y', 2²) + 3t || - y21 + n (x')
2
@ ] Fd((x) M(Ax') + (Ax' yy',z') + _ |Ixx' y'11 + hyc
< F h (Axx)) +
8
+ _ || - -y'1l + n(y²))
< FF. + (Ax' - y² -ah(y)) + - 1I - y²12
Σ F.. d (8+8)#²
3
S F + 3F:
where step ① uses Fxx') f(x
ix +Ax(Xx)) S F: step @ uses d(x²) S d, and hy, S
h(y) for all y and μı; step @ uses Inequality 26
with y = Ax' and y' = y": step 4 uses Inequalities
and (28).
D.5 PROOF OF LEMMA
Proof. Part (a). For any t 2 O, we have:
g g++l
1+E(+11"
+1) 14EM - 1+50"
S 11+6.
(29)
g
where step @ uses the fact that (1 (4+11 1) St + 12 for all p E (0. 1) and t 2 0; step @ uses the fact
that a+g < + & for all a 2 1 and & 2 0.
Part (b). For all t 2 1, we derive the upper bound and lower bound for A
x A u(xx 1' (x") (4") d(xc)
<
F-J47/B'
1 F-J47/80
- T.
d
x A U(x' "" "0'""")") d(xt)
Ed-y/p'
Ed-y/po X.
d
Part (c). For all 2 0, we derive the upper bound and lower bound for ++1.
a 1+1
Vd(x)
a.
PT
a 1+1
d
U(x y
F-t
F-d-7/30
25

---

Published as a conference paper at ICLR 2025
Part (d). We first focus on FADMM-D with ((3*) A Ly 1 + XWa. For all t 2 1, we have:
((8') 2 (11 A 12
{(8') - b' A 2 + 3'
AWa.
We now focus on FADMM-Q with ((5)) 2 Ly + 3 + For all t 2 1, we have:
((8)) 2 8* |
((8)) - J + 3 + 2Wa.
E PROOFS FOR SECTION 5
E. PROOF OF LEMMA 5.
Proof. We define S(x,y:2) (3) f(x) + (Ax y:z) + 21 y12.
We define s(x) _ S(x, yf 2²; (3)),, where & is known from context.
We define L( B,
x U(( y:;;
We define (( B. S(x 3) + 6(x) g(x) + (y).
We define ((8*) Lj + 8 A 2 + X'W. where X = M(xx' y (1")
d(x))
We define & A (0 1) > O.
Initially, using the optimality condition of x²#1 E arg minx M' xx,)x>>;,),,..."" we have: ;x,x')
(x xx,,
X²) < x'x''x'', X²). This leads to (xt+1 -x', vs(x') - 0g(x')) X(d((x))) +
0
1 xf1 11 +1x S 1+000 0 + 5(x*). Rearranging terms yields:
8(x 42) - 6(x') + 0e(3*)
2 || ++ x" 11
(x' - x +1 vs(x'') 0g(x') - X' xxd(x'))
s(x') - +1x + 4 || 12 x - x1 + (( - -(xx))
2
+ xd(xxx 111 d(x')) + x W4 ||x++1 xx
2
sxx') + + [وg") ||x+|| x'112 =g(x+1)=== - -((')) +
(30)
where step 2 uses the facts that the function s(x) (Ly + 3' -mmotth w.r.t. x, A > 0, g(x)
is convex, and d(x) is Wa-weakly convex, yielding the following inequalities:
$(x(t1) - s(x') 1 (xtt1 xt, vs(x()) + 1 s(x") -(x < (0g(x"), xxx - x((1))
|xt+1 - -x x11
Xd((x') x'd(x(+1) < X1 (dd(xx)) xxxx - x xa 2
Wa |x - x² x2112
(31)
step @ uses the definition of E(3²) I, 3 + XWa.
26

---

Published as a conference paper at ICLR 2025
We further derive:
[(x't1, y':2'; B' (1) - [(xt, 2 11))
Ml (y²) 8 + sxx +2) g(xx+1)}} x²
d(x
Z( (y") 8xx) g(x²) )  ||x ++ - xx112 + s(x*) - X'((x')) + X - X
8
a(x |( (1 (yr) 8xx)) - g(x)) + 60'اا ||x ++| -x'13 - -00(x)) g(x²) + (p
2
((80) ( 00
||x ++1 x'13 11
2
1(3*) ((3"))lx**
||xx+t ++
_x111
{1 - 8}
28
- 3¹| ||x
-x
x2
where step uses the definition of L(x², y²; m²) = A step @ uses Inequality 30 step 3
uses X'd(x') - s(x') = 8(xx) - g(x²) + hyy (y"); step @ uses d(x) I and 1; step @ uses the definition of sn A (0 11)8 > O.
E.2 PROOF OF LEMMA 5.11
Proof. We define ((x,y; A d(x) [f(x) g(x) + hx) + (Ax y.z) + +111Ax- y113)- 111))-
We define T 12(1 + () I)). and T C2221/ (2d).
We define E & (/d2), and 5 - (1 4(1 3//x2)/(2)
First, we focus on a decrease for the function L(x, y; z; B, 1) w.r. y. We have:
C(x ,=+1, 22;; gt, )²) - L(x y"; 2' 3 12)
d(x 1j f/y" - y1+11 z²) + //2 Ax y + 1| 5/2 |Ax - y + -
(v')}
ال 1y 1(r" -1 z' + 8 (Ax ++ y (1) )) + hr (x+tl) - -pp -//((x')) - o Ely - 13
80
a Ty ((y' - +1 , 2 +1 > + hpc (y +11 - -nr (x²) - _ 111 - -y'113 111
1) ((y yxt1, 2 Ahyn (1)) E/' |1x++1 - x²112)
Iyy +1 111
(32)
2d(xx
where step ① uses the definition of L(x, z; p.) step @ uses the Pythagoras relation that b
c122 bll b cll - l blβ + (a c, b): step 3 uses z z' ('(Ax(+1 y y(+1); ));
step @ uses the convexity of hae (-); step 5 uses the optimality for yt+1 in Lemma 5.3 a) that:
hh (y(+1)= 2!+1
27

---

Published as a conference paper at ICLR 2025
Second, we focus decrease for the function [(x, y: 2: B. w.n.t. {z. We have:
2d 3 |z
z' + f(x +1, gt n²)) [(x , , x²)
20(x # 1| 2111 + (f(x ++1 y 2
1+ ++ ; B n1)) - ((x , - ,
2 13 144)
+ (f(x +1
1 1 - L(x +1 , x 18, ,,,1m)
(( (25 (, ||| 11:4-11000 x113 + (Axt*l ++| yth x+ x²) + (g - 8') Ax
2
d(xi+1) . 22 ||z||| z2112 + 1x=+1~='11 (1= "1 -xxxx =11 2(31)2
d(xtroj( ( + 1 + { ||zz - 2'11
Σ d(xt+1) f8 x²
1+8
( 2( |1y - y'11 + 12 - -
( 2(1+() 8² 0|y | - -² + 12(+5)00 3dd (1 (1-1111 1
(33)
x
where step ① uses d(x 1 d: step @ uses the definition of L(x,y; B, p): step @ uses (Axx'++ ) z'+1 z' and go+1 I 30(1 + E): step @ uses Lemma 5,4 step 3
uses Lemma 5.4 step @ uses d(x d. and Br 2 30.
Third, we focus on a decrease for the function f(x, y: z: 3, pb) w.r.t μ.. We have:
[(x - 2 11 g,t ,1 11 - [(x ++1 , , , gtt1 ,(²)
Fy (h +1 (y 1)
1- - hy 1
2d(x 12 (k' p¹ )1+ Ch
(v' n
(1) Ch:
(34)
2d
where step uses Lemma
3.9
e); step @ uses d(x')= 2 d.
Adding Inequalities
32
33
and
34 we have:
C(x , ++| +1; get1
, +1 - ((x :²:z²z ,x²) + T + U - -T U
< - e Ax y 112
-d 191ly(+1 y2112 {1 1(1+2)
x² }
@
x - E | [+1
- - 3 lly - y y1112 Eyy
where step O uses the definition of Ey - (1- 10144(1-1 + 2/
E.3 PROOF OF LEMMA 5.12
Proof. We define L' A [(x', 2'; 1²),, and T = +2(1+ (2(1+))) and U Chudl(2d)
((d))
We define P' L + T U
Part (a). We derive the following inequalities:
ys L''+T++U
[(x', ;'; 3 (4') +0
u1(x y 't (n))
d(x²)
F-d-v/a' d
Fdd 8/ 4 P.
28

---

Published as a conference paper at ICLR 2025
where step 1 uses T 2 and U 2 0; step @ uses the definition of C(x', z' St, 1²); step @ uses d(xx) I d, and the lower bound of ,'';'' 3*, μ²) in Lemma 5.6 step 4 uses 3 2 30.
Part (b). Combing Lemmas 5.10 and 5.11 together, we have:
Eg 3 Iyy y" 12 + 8 ||x - xx112 + e Ax -egt--ye -
I L' L + T T U 11+11
= I ptt1
E.4 PROOF THEEORM 5.13 5.13
Proof. We define cu (l)
1
{P! - -]).
We define gx 1/ (011x=+++1 - x²11 + |1y - yy'll + || 11+
We define E - [[xx' - x'1l + Ily y''l + Ax 1--+1-y"2 -1++11].
Using Lemma 5.12 we have:
5 min(en, Sy, Ex) + Ip - pp+1
(35)
Telescoping Incquality 35) over t from 1 to T, we have:
0 S
1= [ p Ei= g
[p] pT+11 Σ E
{pl - P] Σ g
min((21Fg152)
Co
3r
Ei=1
T
||31 (xl+ 1+ x3)1 || (yttt y0) + 1|8 (Ax y1+
5 3rh 37
t=1 || (x ++ || + || (y ++1 yL) + || (Ax 1+1 111
@ S 00
ST 1==1 1
7
(36)
where step 1 uses p > P. for all L; step @ uses the definition of co. the definition of & and the Hölder's inequality that (a, b) < ||a|| |bb] step @ uses the fact that ||al| ||al|s: step @ uses the definition of E We further obtain from Inequality (43 that
ΣT. & S (3
- + & S(TTO-11)
where step 3r = (1+
= O(P).
E.5 PROOF OF LEMMA 5.15
Proof. We define S(x,y; 9) f(x) + (Ax - y.2) + |1 - y1-
We define sxx) e S(x, yf zi: )² where t is known from context.
We define 1C(a, x.c. B, 14) 2a 2(x) (
1).
We define u(xx,y;;;;; B, A 5( 5) 6 - g(x) + (y).
We define f(,8)) A T.f + 3' A b 2 Wa, where 2+1 v /d(x')//U(x( , 32: mt).
We define &.r 1 -0000
Initially, using the optimality condition of ++ argming M (x; x², a.+1), have
(x al11) (x'''t; This results in (x'+1 x², Vs(xt) -0g(xt)
29

---

Published as a conference paper at ICLR 2025
1 /d((x))) + 20(8g)
|xx xx11 1/2 + 6(x*+1x } +=00++66x* 6(x'). Rearranging terms yields:
2
8(x 11 8(xx)= + ) | - x21
2
$ (x' - x x1 Vs(xx)) - -8g(x') - - 0 d(x*))
I s(x²) - s(x 1 + -1- |A1 $|x - x 112 + g(x -
+ - { v (xxx)) - / /((x + We x|x x1133
2
S (xxx) - ((x 1) + A(3") |x+ - x112 + g((xtt) - -((xx) - - - /d(x+t1))
2
(37)
where step @ uses the facts that the function s(x) is (To + +11]Al1))ssmooth
-smooth w.r.t x, at > 0,
g(x) is convex, and / /d(x) is Wa-weakly convex, yielding the following inequalities:
1(x I s(x') + fx - x", Vxs(x²)) + 1,+
X ++ - xx111
9(x') I g(x ) + (x' -x*t1 0g((x))
बोन d((t)) vd(x I ( (((@)d((xx) d(xx), x' - -xtt1) + Wa |x
2
-x'12)
(38)
step @ uses the definition of E(B+) - Ls + 341 A 1/22 + x Wa.
We further derive:
K(alt1, x²+1, 2':3 n²) Kla', x²,
Klaat], xttt], "t:t,y';:: zy; B )1)) - k(att1, x², z²; B", ,1²)
i (2
-/. Io [(xx - vd(x')1 s(x' + 6(x(+1) 5(x²) g(x + g(x²)
3 (at (_-0 ((3)) ||x +1 - xt11 112
(222(1 2(1 0) 3 [| - x11
--
where step ① uses the fact that a = arg ming K(a,, x x', z²;z"; (":",,,)) a²) which implies the inequal- ity K((a-! x', y'; 8 ,x¹) S K(aa,, x², y':z'; B ,x);; step @ uses the definition of the function K((a,x, x, z; B, 1c); step & uses Inequality (37) ; step @ uses 1 - 0 < 0, a² 2 a, and ((3') 2 S
E.6 PROOF OF LEMMA 5.16
(²(5(x) + 5(x) - 9(x) + ky)(y) + (Ax Proof. We define K(a,, 8(,,,, = -20
2.
+ 1 |A y112)].
We define T A 12a²(1 + C) and U & Ca
We define A _ and Ey A te 4(1 + {)))
First, we focus on the sufficient decrease for variables 1 we have:
K(a xx+11 , ,1, ;; 2²; 3r, ,1¹ - K( x y ,';;3,,)))))
(2 g8 2 Ax y +1 12 g | Ax y'112 + h (1) - hyp (y') + (2' ( -
(a g'
Ax - t [ 2
g' || y²113 + (y - yy, (/ppe - -x')}
_ (1= 1/1 2 - - -y'l8 12 + (y r+1 - y" That (1) - z' - 33x'(Axx"*
++1 1}}
_ 10 f fly
1 -y'l2 + (y y¹ Vhyt (y ) z' -z - -z²))}}
- 8 (a | 11,
(39)
30

---

Published as a conference paper at ICLR 2025
where step ① uses the definition of K(a, y: 3, pt); step @ uses the convexity of (gs(.) that (yy) - (y) I (y' y, Vh (y')) for all y. E R.. and μr > 0; step uses the Pythagoras
relation that 2 a - clß - 22llbb c - a blß 1 (a - c, a - b); step 4 uses the optimality
for yor that: Vhy (y*+1)= =z + (Ax
Second, we focus the sufficient decrease for variables {z, 33. We have:
((att),xt+), 5 8* | + + K( ,x(t] y + g n²) K(att? ,x+t1 y ; 0t ,²)
(a (1
[A((a 1+1 x .y't1 tt B n²) K(aatt x('=,,,++1______ ,y z S 11))
20
+ (K(aa ++| x y
g :²) K(a ++1 x ++|
y 1 , ,²,²
_ (att12 . / =2'1 (Ax +1 - yt+1 x x²) +
-
2 Ax! - 1
23
1 (a 120 + 3 + (1(1+))
2(3 }. |z/+11 2/11
(a {(1+E) } ||z - 2'112
(a*+1)((++))) () V (y-+t)) -h (y )13)
3 (a/11)(11+ + +) ( ايمي 1ly - - + 120
$ ((att2)((1 +) 6) 30 B 1l 1+
y"1 2 +
12(+
(40)
0
where step ① uses a'; step @ uses the definition of K(aa, x. v: z: 8, (t); step 3 uses ('xxx++1 ) z 1-1 z' and 3 $ 30 E); step & uses Lemma 5.4:); step @ uses Lemma 5.4 step
K uses a' for all / 2 1.
Third, we focus on the sufficient decrease for variable μ.. We have:
x(tttl,tt1,, K(attl, xtt1 . 2 get1, ,1 -K(att x²+1, y 2 gett 11²)
= (att1)2 (ha (y - (y
$ ( (u' - -u )
$ A - t = U²- -U+11
(41)
where step ① uses Lemma 3.9 e); step @ uses a' S a for all / 2 1.
Adding Inequalities
39
40 and (1 we have:
X(X*+1 ++1 x ++ y
1 iz 1z=,,,1100 g " 11 - KC(++1 xx*! xx"''_''='"" "':z'''''''"
< T U' - T++ U++ -
y 1 - 4(14(11))/xx)
< T U' - T T - 11yl ++1 - y Ey.
where step uses a ++1 > a. and the definition of s, - 2 - 1011-441-0 +2)(2)))
E.7 PROOF LEMMA 5.17
Proof. We define 1st 2 T + U
We define K' A K(aa,, x², y'; ,²), and T = =12a?(1 + ())// and U }C302
31

---

Published as a conference paper at ICLR 2025
Part (a). We derive the following inequalities:
p 2 K'' + T + U
K(a', x², y"; n 8r 11²) +0
2 - 2a' V d(xt) + (a')(((( y
2 2 + a²a (Fd= 3/3
2 + + (Rd x/
where step @ uses T 2 0 and U 2 0: step @ uses the definition of K(a', x'y'' z':'" u²); step
@ uses d(xx) < d, a² I a, and the lower bound of Lix'', yy: 2 B n²) in Lemma 5.6 step @ uses
3r 30.
Part (b). Combing Lemmas 5.15 and 5.16 together, we have:
s fly ++1
y" 12 + En 1|x 1 - x11 + || - 1
s K Kt + T - -T + U U
Ipt ptt1
E.8 PROOF OF THEOREM 5.18
Proof. We define cu A (l1(5))8y152)) {P'-PP) PP.
We define Ex & [1xx x11 + 11y -3' + || 11)
We define E - -[(l===11 x'1l + Ilytt1 -y'll + Ax 11.
Using Lemma 5.17 we have:
0 5 Ex) + p p1+1
(42)
Telescoping Inequality 42 over t from 1 to T, we have:
0 6in(
(pt
p(+1} - Ets Et
(p2 pl'+1| ΣT gt
1A MA8
(pl - P]- Σ E
8z Σl= 18 +1 x²) x3)113 + -1)11 + 1| (Ax - -1
Cg
1
1 T
- || (x +1 x()) + [y y")l + -
3d
3T
# 5 00 38 | 8
(43)
where step 1 uses Pd > P for all 1; step @ uses the definition of co. the definition of E and the Hölder's incquality that (a, b) < ||a|||||b|| step uses the fact that ||alß 2 A|la//f: step uses the definition of εL. We further obtain from Inequality (43) that
EJ & < (37
& EEL & S0(T0-11))
where step 3 = (1P) O(PP).
32

---

Published as a conference paper at ICLR 2025
F PROOFS FOR SECTION 6
F. PROOF OF THEBRRM 6.3
Proof. We let 1 2 1.
We define Crit(xt x, y y, z 2) -
11xt
x1 + Iyy yll + 1z= z|| + ||Axt - -yt|1 +
[]ab(y)) zt 12 + 1106(xt) + Vf(xx) 0g(x) + A A xt - x((xx))dd((x) y)ad(x)]l where y)x,
{f(x) 5(x)- g(x) h(y)) (d(xx)
We define ri _ [[05(x++1) VS(x + ATz 0g(x*) (x(x', ("xx",""))8B xa)d((())
We define r2 _ ||z 1 + 10h(3+t) -
-1 11+ ||xx+1 -y
We define r33 ||y - 11+ + ||x||1 - x*11 + 11 - y'1l-
Part (a). We now focus on FADMM-D.
We define X {f(x²) 8(x)) g(x') + (Ax' y
- 2²) + 2 |Ix y-'112 - (y)
First, we focus on the optimality condition of the x-subproblem. We have:
-)( + + + X'dd(x'))
((( xx) y ;':2';
=
+ AT + 3 A (Ax'xx'0 y²).
(44)
Second, we derive the following inequalities:
[[0d(x') {x* "xx"x,x)))
W Ca 1(x' ((x))=((x)++ (Ax' y 2 0r |Ax
-xx))= +h((")
d(x))
d(x))
(Ax' - - + 3 |Ax - y' 1 + 10---15
(x") -h(y')
1
Ms I
Ca
7
1111z - zz z'~111 +
gr 1|z - -z' + 1Rn2d
18-1
2(
(
+
gr
(2n)² + 23 Chx]
1
(45)
where step ① uses the fact that d(x) is Ca-Lipschitz continuous, and the definitions of X and pp(x", y"); step @ uses d(x') 2 di step @ uses 0 < h(y) (y) I C (refer to Lemma
3.9 the Cauchy-Schwarr
Inequality, and the fact that Ax' -y 3 (z' 2111); step @ uses
I z'11| < | + || || < 22; step & uses 3t-1 < 3d S (1 + g)
Third, we derive the following results:
r é | + Vf(x+*))++++)))))+)) A - 0g(xx) - p0xx', yd xd)))l
@ < [x0d(x')) - s0(xt y y'))a((()) +f vx((tt
+ ( - 2 - (00(8') (1 x²)
-x))I
3 [xadd(x)) - ((xt y')),'''' + (z (2 2') + -
+ +00(3')((x*** - -x1l + 8d T T(xx' y¹)l
*
$ 0 ( + 0 y +1 0 (8 ||x ++ x + O(B II),,
(46)
where step uses Equalities step uses the triangle inequality; step @ uses Inequality 45 3r-1 < B² (1 -1 and z¹ z' =3 (Ax++1 y++1).
33

---

Published as a conference paper at ICLR 2025
Fourth, have the following inequalities:
r - Iz f-1 z'1l + (10h()++)))))))))))))))))))())) -z" 21+1|1+++ ||Ax +1 -y
1 ++1 ID,
(47)
where step uses 1 E @h(y*+1) (refer to Lemma 5.3 and 21+1 = -Ax - y(+ Fifth, we have the following results:
r
1y 51+1 || + | - x'1 + 11st1 y'1l
1 ++ - 11 + | - x''1 + +|5ttt1 - y + lly -y y"1l
1d'O, + ||x x
+ n² Cr + ||y yy'll
0 3r + 0 (3' x ++| x" 1) + 0 -
(48)
where step @ uses the triangle inequality; step @ uses Lemma (3)10(c); step @ uses n¹ 3
( and 1 T = O
Part (b). We now focus on FADMM-Q.
We define U((", x", y':''''''' 3t n²) & f(x') 1', and a+1 & /((xx)/((x' z"; 3 ,²),
((xx'))+hx thp (y') (Ax' y",z") + 1 |Ax
First, we focus on the optimality condition the x-subproblem. We have:
0 - 0g(xx) - 3 - 00((3))) - x---Ve -xX((x' "'Sxx"y";'':"" x² 00(33))))))))0)) (x(t))((+1111))))) - x*) - VV(x') AT - B (AX
(49)
Second, derive the following inequalities:
2 2 d(xx)) ,xx", , o')x)(
of ((((')) 1/2x))))/22dd(x)) - p(xx' . (d)))l
1
u(xx y' wn) 0d((x') - -(xx, y¹ od(('')l
d(x')
Cal U((x''' y''''
((xx,*))
d(x')
Ca [(x'', y²:z²; 18, ,14 - (f('x) ) + 6(x²) - g(xx) + h
Ca (Ax' y", 2²) _ || Axx y2'12 + 11 (y²) h(y')l)
< Ca
Iz' - zz 111
マーーー 2 - 21- + 4 4 cR.
232
ge
(2%)
x C/
2 1y
23
(50)
where step ① uses [x*) =
step @ uses the fact that 1+1 =
/u(x)) z': B*); step @ uses the fact that d(x) is Ca-Lipschitz continuous; step + uses
d(x() 2 d; step @ uses the definitions of U(x'', z': (²),));; step @ uses < h(y) h (y) S *C (refer to Lemma 3.9 b)), the Cauchy-Sehwarr Schwarz Inequality, and the fact that Ax' y' =
--11 (z' - z' z²-1); step ① uses ||z - z'-1| S ||''|| + =||z-1| < 27 and 4r² = x/ step uses
g- s B² (1 81
34

---

Published as a conference paper at ICLR 2025
Third, we derive the following results:
ATZ rf _ + V.f((((()(+)))))
0g(x*) - "(xx'xx))))) x')O(((1)
IAo
11 2. 0 1 0dd(v))(x))))))))))))))))))))0 - y'))) V - Vf((x'
+ A (z! - -z') - (00 (x x') + AAA AA'AX - y'I
< 11 2 2 oV [dxx)) =(x', x(x'x")) + || TA (2 - 21))l
+ V V
||| x'1 + 8* | AAxxxx y')ll
3 0
1 ge 0 Ax
0 xx - x (l) 0(8(~11 - I"),
(51)
where step uses Equalities 49 step uses the triangle inequality; step uses Inequality
(50)
3 S 3 < (1 + 8) and 2 z' = 3r (Ax y(+1).
Fourth, we have the following incqualities:
r - | 2²11 + |( x +1| + ||Ax ++1 y
(52)
where step 1 uses ++ E @h(r++1) (refer to Lemma 5.3 and zz+ z' = Br (Axxtt1 -xxttt) y)t1). Fifth, we have the following results:
13 A Ily 1 || + ||x -xIl + | 1u-1-yy y'll
11y g1+ + |x - x'1 + || ylt + 1ly -y
W 1d'h + ||x - x μ¹ C22 + lly - y'1l
2 0 (1 0 x x" |) + O Ily y'1l).
(53)
where step @ uses the triangle inequality; step @ uses Lemma (c): step @ uses n¹
( and 1 S _ OBB).
Part (c). Finally, we continue our analysis for both FADMM-D and FADMM-Q, deriving the fol- lowing inequalities:
T EL Crit(x'+ +1 x x .y", 22,1+1112
< 7' +
+
-
+ 0 - x"1 + -y
$ 1/T3-1))23 + + 0
1 O //2) + (
(54)
where step ① uses the definition of Crit(x x,y y, zt z). and the triangle inequality that
Axx+11 y ++1l| < ||Ax+*1 - y+1
+ | ++i
|: step @ uses Inequalities (46). (47) and
48 for FADMM-D and Inequalities 51. (52) and (5) for FADMM-Q; step uses Theorem
5.13 for FADMM-D and Theorem 5.18 for FADMM-Q that
1
xf11 + 1'y
7
+ Axx| --11|l O(T(P
1/2): step 4 uses > gt
1 = 2
- - OTT as
presented in Lemma
We define W A (x(+1 xe, yet1 .y', + z') With the choice p 1/3, we have from Inequality
that + DT Crit(W") < 1/3). In other words, there exists < f. < T such that:
Cril(w)) S provided that T 2 O
35

---

Published as a conference paper at ICLR 2025
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 follows:
min p(x) +
2p x
x 12
(55)
XER
Here, x' E IR" and p > 0 are given.
G.1 ORTHOGONALITY CONSTRAINT
When p(x) = in (mat(x)) with Ω being the set of orthogonality constraints, Problem (55 simplifies to the following nonconvex optimization problem:
x arg minx 2/r
x -x'1l2: s.t. mat(x: Ω -VIvV=
This is the nearest orthogonality matrix problem, where the optimal solution is given by x vee (ÚVT) with mat(x') ÜDiag(s)U' being the singular value decomposition of the matrix mat (x'). See (Lai & Osher 2014) for reference.
G.2 GENERALIZED & NORM
When p(x) = P2 ||x|| (x with Ω a fx ||x||>> I Po). Problem (55) simplifies the following
strongly convex problem:
X E arg minlxeR P2 |x|| I + 2z ||x 112, s. L. || S Po-
This problem can be decomposed into r dependent sub-problems
x; arg min, di (x) A 2μ (x x()² + pa|o0 s. -Po S x S Po-
(56)
We define Pl. (x) - max(l, min(u, x)). We consider five cases for π. (2) 21 = 0. (i) 32 -Pn- (iif) (iv) I4 > 0 and
By omitting the bound constraints, the first-order optimality
condition gives 1 (x4 x() + Pv 0, leading 24 x μP2. When the bound constraints are included, we have I1 = Po. (x] - 1422). (v) x < 0 and x > -Po- By dropping the bound constraints, the first-order optimality condition yields # (x5 -x)) -2 P2 = 0, leading to Iτ x When the bound constraints considered, have 25 P Pi-po.0f po.0 (x/ /422). Therefore, the one- dimensional sub-uuuuuioo sub-problem in Problem (56) contains five critical points, and the optimal solution can be computed
x; = arg min 9 (x), s.t. x E (01 F2, FA,
G.3 SIMPLEX CONSTRAINT
When p(x) = (x(x) with Ω a fx 0, x = 1}. Problem 55) simplifies to the following strongly convex problem:
x E arg mink || - s. x 2 0, x 1.
This problem is referred to as the Euclidean projection onto the probability simplex. can be solved exactly in Onn log(n)) time (Duchi et al. 2008).
G.4 GENERALIZED MAX FUNCTION
When p(x) = max(0, (0, max(x b)) with b E R", Problem convex problem: arg ming 2n
55 simplifies to the following strongly
1 | x 112 max(0, max x b)). Using the variable substitution
that x + b = v, we have the following equivalent problem:
E arg miny g(v)=
A 1 ||v
v'122 + max(0, max(v));
(57)
where v' A x' + b.
36

---

Published as a conference paper at ICLR 2025
In what follows, address Problem 57 by considering two cases for v'. (i) mmx(v') - 0. The
optimal solution can be computed as V v', and holds that q(v) = 0. (i) max(v') > 0. In this case, there exists index E [r] such that v' > O. It is not difficult to verify that the optimal solution v satisfies max(v) 2 0. Problem (57) reduces to:
arg milly
max(v).
(58)
This problem can be equivalently reformulated as: minl,r zu V1 dual problem is given by:
71, whose
arg max, 1 (z, v'), s. 0. | =
(59)
The unique optimal solution z for the dual problem in Problem (59 can be computed in On log(n))
time (Duchi et al. 2008). Finally, the optimal solution v for Problem (58) can then be recovered as nzz.
H IMPLEMENTATION OF THE FULL SPLITTING ALGORRTHM (FSA)
This section details the implementation of the Full Splitting Algorithm (FSA) (Bot et al. 2023b) for
solving Problem (I) as summarized in Algorithm 2 For simplicity, we set 3 and use constant step size 7d 7 for all where 7 E {10-3, 10
Algorithm 2: FSA: Bot al.'s Full Splitting Algorithm for Solving Problem 11.
(SO) Initialize (x", zz, uu).
(S1) Choose suitable / E (0, 2), tH
(S2) Set {a'} {1/7*} for t.l
for t from 0 to T do
(S3) Let o¹ E V + AT' O'0((x)).
(S4) x E arg minx 5(x) + a
(u' - (o6--g/a")) g//2))13
(S5) u' (1 B) 3x
(S6) +11 = Prox( Ax h", )
(S7) 0t+1 L(x"xx', "a'""""a""'""" aanr
where
d(x*)
L(x, z, u. a, A f(x)
(z, Ax) - (2(2))) + 5(x) + 1| u 1112
end
I ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS
In this section, we offer further experimental details on the datasets used in the experiments, and include additional results.
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 our data matrices Q E Rindd and the label vectors p Rh. The dataset names are as follows: 'madelon-mi-d'. IDTT--12-mm-',, "TDT2-3-4-i--'' 'mnist-vin d', 'mushroom-ia-d" 'gisette-rit-d', and 'randn-ri-dd'. Here, 'randu(mn, d) represents function that generates standard Gaussian random matrix with dimensions in 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 Q x is constructed by randomly selecting in examples and d dimensions from the original We normalize each column of to have a unit norm. As 'randn-ri-dd does not have labels, we randomly and uniformly assign to binary labels with p E (-1, +1 (i) For sparse FDA as in Problem ( we let D & (M() (42) (14) (22) C Σnn) Eg, where (() R and Σ(s) R represent the mean vector and covariance matrix of class (i orr respectively, generated by (Q, p). We normalize the matrices C and D C C/| Cllr, and D D/ Dilr. (ii) For
real-world dataset (https: www. csie ntu. edu. wtwp:ttwwwwwiiiibsstseee
37

---

Published as a conference paper at ICLR 2025
madelon- madelon-2000-500 2000-500
(b)
TDT2-1 2-100-1--10--00000
(c) TDT2-3-4 1000-1200
mmist: 20000--6000-66
Tima beocr011
Time decondd
(c) nustrromm2000-112
(f) giscttc-800-1000
randn-300-1000
(h) randn-300-1500
Figure 3: Experimental results on sparse FDA on different datasets with p = 100.
Loke P0L-3
(a) Maddelon-200-SSU
(b) 1DT2-112-1000-1
(c) TDT2-3-4 4-1000-1200
mnist- 200st-2000-768
(c) mushrromm2200-112
(f) gisette-800-1000
mundn-300-1000
(h) randn-300-1500
Figure 4: Experimental results on sparse FDA on different datasets with p 10000.
robust SRM as Problem 14 we let D = Q and = p. Following (Bot et al.
2023b), we
generate p matrices {C( 1p Fi=1- where each C(s) E RRax is constructed as C(t) -YY with
Y = randn(n, (n, n.) 10. We let
100. (iv) For robust sparse recovery as in Problem 15 we
simply let Q and b p. where p E [-1, +1)" represents the data labels.
Additional Experimental Results on Sparse FDA. We present additional experimental results on sparse FDA for p E (100, 10000] in Figures and 4
These results reinforce our conclusions
presented in the main paper.
Experimental Results on Robust SRM. We consider solving Problem (14) using the proposed methods. For all methods, we set 8 0.001. The results of the algorithms are shown in Fig- ure 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.
Experimental Results on Robust Sparse Recovery. We consider solving Problem [5] us- ing the following parameters (pi, P2, Pa)E {110, (10, 10, oo), (10, 100, oo), (100, 1, oo),
38

---

Published as a conference paper at ICLR 2025
[x|||r [&] is not necessarily weakly convex, FADMM-Q not applicable; thus, we only implement FADMM-D. The results of the compared methods are presented in Figures 6
(100, 100, oo)). For all methods, initialize with 8 0.001. Since /|x
To from which draw the following conclusions: Although SPM, SPGM-D, and FSA yield comparable or better results than FADMM- D in certain cases, the proposed FADMM-D generally achieves the best performance among the compared methods in terms of speed. These results further corroborate our earlier findings that the proposed method faster and more numerically robust.
madelon
madelan-2n00-500 2000-500
(b) TDT2-112-1000-0000
(c) TDT2-3-4.100-0 1000-1200
mmist 200is-22000-68
gisette-800-
runda-300 1onddn-300-110
(h) randn-300-1500
Figure Results on Sharpe ratio maximization on different datasets.
(a) 20000000-2000500
(b) 1-12-1-2-1000-1000
(c) 1002--3--1000-12200
mmist-2000-768
mushroom 2000 112
( gisette 800. 1000
randn.300 300-10000000000 1000
(h) randn. 300. 1500
Figure 6: Results robust sparse recovery on different datasets with (p1. P2, Po) (10, 1,
39

---

Published as a conference paper at ICLR 2025
Town
madelon TDD221-2-1000-100
(c) TDT2.3-4 mmist-2000-776
Tie
mushroom-2200 2000- 112
gisette-SEi 500-1000
runda-300 1aelaa-30--100000 1000
(h) randn-301- 300---000010000
Figure 7: Results on robust sparse recovery on different datasets with (p1, P2: Po) = (10, 10, oc).
2000-500
TDT2-1122 1000
(c) TDT2-3 20000-66
(e) mushroom-22000 2000-1112
gisette-800-100
randa-300-100
(h)
handn-300-1500
Figure 8: Results on robust sparse recovery on different datasets with (21,
P2, Po) = (10, oo).
40

---

Published as a conference paper at ICLR 2025
madelon
2oddelon-2000-000 2000-500
(b) TDTT2-1-2-100-1100
(c) TDT2.3-4 maist-2000-00
mushroom-20000 2000-112 112
gisette-Sei Soeette-S00-11 300-1000
runda-3000 300-1000
(h) candn-30D-13 150005000
Figure 9: Results on robust sparse recovery on different datasets with (p1, P2: Po) = (100, oc).
2000-500
TDT221122
(c) TDT2-3-4 1000
mustaroom-2000111 gisette-800-100
randa-30001100
(h) randn-300-1500
Figure 10: Results on robust sparse recovery on different datasets with (p1, P2, Po) = (100, 100, oc).
41


Reviews:
[{"review_id": "KQMf5su4Mf", "reviewer": "Reviewer_7KB3", "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.", "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.\n\n- The notation $\\underline{\\mathrm{Fd}}$ and $\\overline{\\mathrm{Fd}}$ should be $\\underline{F} \\, \\underline{d}$ and $\\overline{F} \\, \\overline{d}$, respectively.\n\n- If the $\\epsilon$-critical point is similar to that in Bot et al. (2023b), will the same complexity results hold?\n\n- What is the method SGM mentioned in Section 7?\n\n- The authors might need to compare their method to that in Bot et al. (2023b), at least for the Robust SRM problem.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 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.", "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.''\n\nAfter 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "huNCt7Eu7X", "reviewer": "Reviewer_AqZe", "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.", "questions": "I am not an expert in non-convex optimization, I can only give some advice on writing papers：\n\n1.The first sentence of the abstract is too long. It is recommended to split it to improve readability.\n\n2.Line 73, \"sufficient large\" should be \"sufficiently large\".\n\n3.Line 138, \"To the best of our knowledge......\" is too long. It is better to break it into short sentences for reading.\n\n4.Line 236,  \"is a widely used to develop practical optimization algorithms \", delete ”a“.\n\n5.Line 454, \"Additioanl\"  -> \"Additional\".", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.The authors provide a comprehensive analysis of the proposed FADMM algorithm, including two specific variants: FADMM-D and FADMM-Q.\n\n2.Comprehensive theoretical analysis, with proofs on convergence.\n\n3.The authors conduct extensive experiments on both synthetic and real-world data, effectively demonstrating the efficiency of the FADMM algorithm.", "weaknesses": "I think the writing of this paper can be further improved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fqutGj4d81", "reviewer": "Reviewer_EekD", "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.\n\nA 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.\n\nThe 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.", "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?\n\n- 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.\n\n- 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.\n\n- 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).\n\nMinor Questions:\n\n- What is meant in line 73 when it is claimed that when rho is large, ||X||_[k] approximates ||X||_1 ?\n\n- In line 76, shouldn't h(Ax) have a factor of rho?\n\n- In lin 76, isn't it more clear to simply write that d and d^1/2 are convex?\n\n- How much effort was made to tune the parameters used in all of the different methods?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "- The class of problems addressed is broader than what was previously treated in the literature. \n\n- The theoretical results about the convergence of the methods and their rates are strong and significant.\n\n- 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.\n\n- The methods appear to perform well in the numerical experiments compared to previous methods that can solve fractional minimization problems and other smoothing algorithms.", "weaknesses": "- The technical density of the presentation harms the readability.\n\n- 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.\n\n- 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).\n\n- Many hyperparameters in the method with little guidance about how to choose them or their effect on convergence.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)