Disciplined Saddle Programming
Authors: Philipp Schiele
Eric Sager Luxenberg
Stephen P. Boyd
Venue: Accepted by TMLR ()

Abstract: We consider convex-concave saddle point problems, and more generally convex optimization problems we refer to as saddle problems, which include the partial supremum or infimum of convex-concave saddle functions. Saddle problems arise in a wide range of applications, including game theory, machine learning, and finance. It is well known that a saddle problem can be reduced to a single convex optimization problem by dualizing either the convex (min) or concave (max) objectives, reducing a min-max problem into a min-min (or max-max) problem. Carrying out this conversion by hand can be tedious and error prone. In this paper we introduce disciplined saddle programming (DSP), a domain specific language (DSL) for specifying saddle problems, for which the dualizing trick can be automated. The language and methods are based on recent work by Juditsky and Nemirovski, who developed the idea of conic-representable saddle point programs, and showed how to carry out the required dualization automatically using conic duality. Juditsky and Nemirovski's conic representation of saddle problems extends Nesterov and Nemirovski's earlier development of conic representable convex problems; DSP can be thought of as extending disciplined convex programming (DCP) to saddle problems. Just as DCP makes it easy for users to formulate and solve complex convex problems, DSP allows users to easily formulate and solve saddle problems. Our method is implemented in an open-source package, also called DSP.

Published in Transactions on Machine Learning Research (01/2024)
Disciplined Saddle Programming
Philipp Schicle
philipp.schiill www.aaaceealaa......meeeeeecceee
Department of Statistics
Ludwigg Maximilians- Universittt München
Eric Luxenberg
erichuz@stanford..dd edu
Department Electrical Engineering Stanford University
Stephen Boyd
boyd@sttnford.d edu
Department of Electrionl Engineering Stanford University
Reviewed on OpenReview: https://openrentt net/ forum? id= KhML fEIoUm
Abstract
We consider convex-concave saddle point problems, and more generally convex optimization problems refer saddle problems, which include the partial supremum or infinumm of convex-concave saddle functions. Saddle problems arise in wide range of applications, including game theory, machine learning, and finance. Tt is well known that a saddle problem can be reduced to single convex optimization problem by dualizing either the convex (min) or concave (max) objectives, roducing a min-max problem into min-min (or max-max) problem. Carrying out this conversion by hand can be tedious and error prone. In this paper introduce disciplined saddle programming (DSP), domain specific language (DSL.) for specifying saddle problems, for which the dualizing trick can be automated. The language and methods are based on recent work by Juditsky & Nemirovski (2022), who developed the idea of conic-representable saddle point programs, and showed how to carry out the required dualization automatically using conic duality. Juditsky and Nemirovski's conic representation of saddle problems exlends Nesterov and Nemirovski's earlier development of conic representable convex problems; DSP can be thought of as extending disciplined convex programming (DCP) saddle problems. Just DCP makes it casy for users to formulate and solve complex convex problems, DSP allows users to easily formulate and solve saddle problems. Our method is implemented in an open-source package, also called DSP.
1 Introduction
We consider saddle problems, by which we mean convex-concave saddle point problems or, more gener- ally, convex optimization problems that include the partial supremurm or infimum of convex-concave. saddle functions. Saddle problems arise in various fields such as game thoory, robust and minimax optimization, machine learning, and finance.
While there are algorithms specifically designed to solve some types of saddle point minimax problems, another approach is to convert them into standard convex optimization problems using trick based on duality that can be traced back to al least the 1920s. The idea is lo express the infima or suprema that appear in the saddle problem via their duals, which converts them to suprema or infima, respectively, Roughly speaking, this turns a min-max problem into a min-min (or max-max) problem, which can then be solved by standard methods. Specific cases of this trick are well known; the classical example is converting matrix game, a specific saddle point problem, into linear program (T.P) (Morgenstern & Von Neumann,

---

Published in Transactions on Machine Learning Research (01/2024)
While the dualizing trick has been known and used for almost 100 years, it has always been done by hand, for specific problems. It can only be carried out by those who have working knowledge of duality in convex optimization, and are aware of the trick.
1953
In this paper we propose an automated method for carrying out the dualizing trick. Our method is based on the theory of conic representation of saddle point problems, developed recently by [Juditsky & Nemirovski (2022). Based on this development, we have designed a domain specific language (DSL) for describing saddle problems, which we refer to disciplined saddle programming (DSP). When problem description complies with the syntax rules, i.e., is DSP- PSP-compliant, it is easy to verify that it is a valid saddle problem, and more importantly, automatically carry out the dualizing trick. We have implemented the DSL in an open source software package, also called DSP, which works with CVXPY (Diamond & Boyd 2016), a DSL for specifying and solving convex optimization problems. DSP makes it easy to specify and solve saddle problems, without any expertise in (or even knowledge of) convex duality. Even for those with the required expertise to carry out the dualizing trick by hand, DSP is less tedious and error prone.
DSP is disciplined, meaning it is based on small number of syntax rules that, if followed, guarantee that the specified problem is valid saddle problem. It is analogous to disciplined convex programming (DCP) (Grant ct al. 2006), which is a DSL for specifying convex optimization problems. When a problem specification follows these syntax rules, i.e. is DCP-compliant, it is a valid convex optimization problem, and more importantly can be automatically converted to an equivalent cone program, and then solved. As a practical matter, DCP allows a large number of users to specify and solve even complex convex optimization problems, with no knowledge of the reduction to cone form. Indeed, most DCP users are blissfully unaware of how their problems are solved, i.e., a reduction to cone form. DCP was based the theory of conic representations of convex functions and problems, pioneered by Nesterov & Nemirovski (1992). Widely used implementations of DCP include CVXPY (Diamond & Boyd 2016). Convex.jl Udell et al. (2014), CVXR (Fu et al. 2020). YALMIP (Lofberg) 2004), and CVX (Grant & Boyd 2014). Like DCP did for convex problems, DSP makes it casy to specify and solve saddle problems, with most users unaware of the dualization trick and reduction used to solve their problems.
1.1 Previous and related work
Studying saddle problems is a long-standing area of research, resulting in many theo- retical insights, numerous algorithms for specific classes of problems, and a large number of applications.
Saddle problems.
Saddle problems are often studied in the context of minimax or maximin optimization (Dem' "ern'y & Mal-
ozemov 1990 Du & Pardalos 1995). which, while dating back to the 1920s and the work of von Neumann and Morgenstern on game theory (Morgenstern & Von Neumann 1953), continue to be active areas of rescarch, with many recent advancements for example in machine learning (Goodfellow et al.) 2014). A variety of methods have been developed for solving saddle point problems, including interior point meth- ods (Halldórsson & Tütüneū 2003: Nemirovski] 1999), first-order methods (Korpelevich) 1976 Nemirovski 2004 Nesterov 2007 Nedié & Ozdaglar 2009 Chen et al.) 2013). and sccond-order methods (Nesterov & Polyak 2006; Nesterov 2008]; where many of these methods are specialized to specific classes of saddle problems. Depending on the class of saddle problem, the methods differ in convergence rate. For example, for the subset of smooth minimax problems, an overview of rates for different curvature assumptions is given in Thekumpprampil et al. (2019). Due to their close relation to Lagrange duality, saddle problems are commonly studied in the context. of convex analysis (see, for example, Boyd & Vandenberghe (2004) $5.4), Rockafellar 1970, $33-37), Rookafellar & Wets (2009. $11.J), Borwein & Lewis (2006) $4.3)), with an analysis via monotone operators given in Ryu & Yin (0022).
The practical usefulness of saddle programming in many applications is also increasingly well known. Many applications of saddle programming are robust optimization problems (Bertsimas et al. 2011 Ben-Tal Tal et al. 2009). For example, in statistics, distributionally robust models can be used when the true distribution of the data generating process is not known (Dou & Anitescu 2019). Another common area of application is in finance, with Cornuéjols et al. (2018) $19.3-4) 4) describing a range of financial applications that can be characterized as saddle problems. Similarly, [oyd et al. (2017): Goldfarb & Iyengar (2003); Lobo & Boyd 22000) describe variations of the classical portfolio optimization problem saddle problems.
2

---

Published in Transactions on Machine Learning Research (01/2024)
Disciplined convex programming. DCP is grammar for constructing optimization problems that are provably convex, meaning that they can be solved globally, efficiently and accurately. Tt is based on the rule that the convexity of a function f is preserved under composition if all inner expressions in arguments where f is nondccreasing are convex, and all expressions where f is nonincreasing are concave, and all other expressions are affine. A detailed description of the composition rule is given [oyd Vandenberghe (2004] $3.2.4). Using this rule, functions can be composed from small set of primitives, called atoms, where each atom has known curvature, sign, and monotonicity. Every function that can be constructed from these atoms according to the composition rule is convex, but the converse is not true. The DCP framework has been implemented in many programming languages, including MATLAB (Grant & Boyd 2014 Lofberg, 2004), Python @Dammond & Boyd 2016), R (Fu et al. 2020), and Julia (Udell et al. 2014), and is used by researchers and practitioners in a wide range of fields.
Well-structured convex-concave saddle point problems. As mentioned carlier, disciplined saddle programming is based on Juditsky and Nemirovski's recent work on well-structured convex-concave saddle point problems (Juditsky & Nemirovski 2022).
1.2 Our contributions
We summarize our contributions follows:
We introduce disciplined saddle programming, a domain specific language for specifying and solving convex-concave saddle problems. To solve the saddle problems, automated dualization is applied to the conic representation of the problem. We extend the existing literature by deriving a procedure that returns both the convex and concave coordinates the saddle point. This also guarantees that a valid saddle point was found without the need to check for technical conditions (such as compactness). These developments make the theory of conic representable saddle problems practically applicable for the first time.
We specify and implement the first DSL that encodes sufficient conditions for conic representability of saddle problems. We develop an open-source Python package, also called DSP, providing a ussenfriendly interface for specifying and solving saddle problems. Using this implementation, we demonstrate the effectiveness of the framework by solving variety of saddle problems from different application domains.
2
Saddle programming
2.1 Saddle functions
A. saddle function (also referred to as a convex-concave saddle function) f : X x x is one for which ((.y) convex for any fixed y E V, and f(x,,)) is concave for any fixed E X. The argument domains X RCR and y S R must be nonempty closod convex. We refer to as the convex variable, and y as the concave variable, of the saddle function
Examples.
Functions of x or alone. A convex function of æ, or a concave function of y, are trivial examples of saddle functions.
Lagrangion of a conver optimization problem. The convex optimization problem
minimize So(Ø) subject to Ar =bb b, fi(x)) s 0, i= 1= 1......m m,
with variable x E R", where fo...., fm are convex and A E pxn has Lagrangian
Mx, v, [(x) + of (Ar +A +... Amfm(r))
3

---

Published in Transactions on Machine Learning Research (01/2024)
for À 2 0 (elementwise). It is convex in and affine (and therefore also concave) in (v, A), it is saddle function with
X =
dom ft,
== R x R
0=
Bi-affine function. The function f(x, = (Ar+b) with X Rd and y= R², is evidently saddle function. The inner product z"y is special case of bi-affine function. For bi-affine function, either variable serve the convex variable, with the other serving the concave variable.
Conwer-concave inner product. The function f(x,y) = F(x)"G(y), where F R - is nonnegative elementwise convex function and R + R is a nonnegative elementwise concave function.
Weighted l norm. The function
1/2
n1
f(x, =
Σ
with x= R and y R4, is saddle function.
Weighted log-sum-cap. The function
f(x, y) = log Σ ys exp
with x and y RT, is saddle function.
Weighted geometric mean. The function f(x,y) -11- Mi with X' = R and Y R is saddle function.
Quadratic form with quadi-semieeffiitt matriz. The function
P s {1
f(x, v)
S
Q
where the matrix is quasi-semideffiite, i.e., P E S (the set of symmetric positive semidefinite matrices) and -Q E S
Quadratic form. The function f(x, Y) TYx with X R and y S (the set of symmetric positive semidefinite n n matrices), is a saddle function.
As more esoteric example, the function f(z, Y) x/11/2 with X = R and y S is saddle function.
Combination rules. Saddle functions be combined in several ways to yield saddle functions. For examplc the sum of two saddle functions is saddle function, provided the domains have nonempty inter- section. A saddle function scaled by nonnegalive scalar is a saddle function. Scaling a saddle function with a nonpositive scalar, and swapping its arguments, yields a saddle function: g(x,y) = -f æ) is a saddle function provided f is. Saddle functions are preserved by pre-composition of the convex and concave variables with an affine function, i.e., if f is a saddle function, so is f(Ar + b, Cr + d). Indeed, the bi-affine function is just the inner product with affine pre-composition for each of the convex and concave variables.

---

Published in Transactions on Machine Learning Research (01/2024)
2.2 Saddle point problems
A saddle point (x" ,9) X V is any point that satisfies
f(x" v) S .g") f(a,y v²) for all I X, y y.
(1)
In other words, x² minimizes f(r y*) over a E a, and y" maximizes f(x", y) over y E V. The basic saddle point problem is find such saddle point,
find x", y which satisfy equation
(2)
The value of the saddle point problem is f(x",'""
Existence saddle point for a saddle function is guaranteed, provided some technical conditions hold. For example, Sion's theorem Siin 1958h guarantees the existence of a saddle point when y compact. There are many other cases.
Examples.
Matria game. In a matrix game, player chooses i E {l,...,m), and player two chooses E .......n, resulting in player one paying player two the amount Cij. Player one wants to minimize this payment, while player two wishes to maximize it. In a mixed strategy, player one makes choices at random, from probabilitios given by x and player two makes independent choices with probabilities given by y. The expected payment from player one to player two then [(r,y) = x" Cy. With 0, 1"x 1}, and similarly for V, a saddle point corresponds to an equilibrium, where no player improve her position by changing (mixed) strategy. The saddle point problem consists of finding stable equilibrium, i.e., optimal mixed strategy for each player.
X' = (x
Lagrangion. A saddle point of Lagrangian of a convex optimization problem is primal-dual optimal pair for the convex optimization problem.
2.3 Saddle extremum functions
Suppose is saddle function. The function G X R. (20) defined by
G(x) = sup / (I, v): x xEX,
(3)
vEy
is called saddle mar function. Similarly, the function H: RUURUSO defined by
H(x) inf (x,1), y ye
(4)
ZEX
is called a saddle min function. Saddle max functions are convex, and saddle min functions are concave. We will use the term saddle extremum (SE) functions to refer to saddle max or saddle min functions. Which is meant is clear from context, i.e., whether it is defined by minimization (infimum) or maximization (supremum), or its curvature (convex or concave). Note that in SE functions, we always maximize (or take supremum) the concave variable, and minimize (or take infimum) over the convex variable. This means that evaluating G(x) Hyy) involves solving convex optimization problem.
Examples.
Dual function. Minimizing a Lagrangian L(x, v, A) over x gives the dual function of the original convex optimization problem.
Maximizing a Lagrangian L(z,v, v, over y (v, A) gives the objective function restricted the feasible set.

---

Published in Transactions on Machine Learning Research (01/2024)
Conjugate of a convez function. Suppose f is convex. Then g(x, v) = f(z)-="y y is saddle function, the Lagrangian of the problem of minimizing I subject to = 0. Its saddle min is the negative conjugate function: inf, g(,, v) -
Sum of k largest entries. Consider [(x, v) x² y, with y (v 10 s 1, 1yy = k). The associated saddle max function G is the sum of the largest entries of æ.
Saddle points via SE functions. A pair (x*. ) is a saddle point of saddle function f if and only if x minimizes the convex SE function G in equation over X, and y* maximizes the concave SE function H defined in equation 4 over E V. This means that can find saddle points, i.e., solve the saddle point problem equation 2 by solving the convex optimization problem
yy"
minimize G(x) subject x x
(5)
with variable and the convex optimization problem
maximize (1) subject to y E V,
(6)
with variable The problem equation 5 is called a minimax problem, since we are minimizing function defined as the maximum over another variable. The problem equation called a maximin problem.
While the minimax problem equation and maximin problem equation are convex, they cannot be directly solved by conventional methods, since the objectives themselves defined by maximization and minimiza- tion, respectively. There are solution methods specifically designed for minimax and maximin problems {Lin) et al. 2020 Mutapcic & Boyd, 2009), but as we will see minimax problems involving SE functions can be transformed to equivalent forms that can be directly solved using conventional methods.
2.4 Saddle problems
In this paper consider convex optimization problems that include SE functions in the objective con- straints, which we refer to as saddle problems. The convex problems that solve the basic saddle point problem equation 5 and equation X are special cases, where the objective is an SE function. As another example con- sider the problem of minimizing a convex function subject to the convex SE constraint H (y) S O, which can be expressed as
minimize subject to f(z. v) < for all y y,
((x)
(7)
with variable x. The constraint here is called a semi-infinite construint, since (when y is not a singleton) it can be thought of as an infinite collection of convex constraints, one for cach y E y (Hettich & Kortanck 1993).
Saddle problems include the minimax and maximin problems (that can be used to solve the saddle point problem), and semi-infinite problems that involve SE functions. There are many other examples of saddle problems, where SE functions can appear in expressions that define the objective and constraints.
Robust cost LP. As a more specific example of a saddle problem consider the linear program with robust cost,
supeec cT subject to Ar = b, x 2 0
minimize
(8)
with variable x E R" with C {cl Fc < g). This is an LP with worst case cost over the polyhedron C (Bertsimas al. 2011 Bal et al. 2009). This is a saddle problem with convex variable æ, concave variable y, and objective which is saddle max function.

---

Published in Transactions on Machine Learning Research (01/2024)
2.5 Solving saddle problems
Special cases with tractable analytical expressions. There are cases where SE function can be worked out analytically. An example is the max of a linear function over a box,
sup y' = (1/2)(u + +1) (1/2)(u- 1x) SSySa
where the absolute value is elementwise. We will see other cases in our examples.
Subgradient methods. We can readily compute subgradient of saddle max function (or supergradi- ent of saddle min function) at given imput, by simply maximizing over the concave variable (minimizing over the convex variable), which is itself convex optimization problem, and then obtaining subgradient (supergradient) at that maximizer (minimizer). We can then use any method to solve the saddle problem using these subgradients, e.g., subgradient-type methods, ellipsoid method, or localization methods such as the analytic center cutting plane method. In Mutapeic Boyd (2009) such an approach used for general minimax problems.
Methods for specific forms. functions with the special form
Many methods have been developed for finding saddle points of saddle
f(x, = = Ky (xx) + (by),
where ø is convex, is concave, and K is matrix (Bredies & Sun 2015 Condat 2013 Chambolle & Pock, 2011 Nesterov 2005a b Chambolle & Pock 2016). Beyond this example, there are many other special
forms of saddle functions, with different methods adapted to properties such as smoothness, separability, and
2.6 Dual reduction
A well-known trick can be used to transform saddle point problem into an equivalent problem that does not contain SE functions. This method of transforming an inner minimization is not new; it has been used since the 1950s when Von Neumann proved the minimax theorem using strong duality in his work with Morgenstern on game theory (Morgenstern Von Neumann, 1953). Using this observation, the minimax problem of a two player game is equivalent to an LP. Duality allows us to express the convex (concave) SE function We think of this reduction and constraints.
showed that
infimum (supremum), which facilitates the use of standard convex optimization. equivalent problem that removes the SE functions from the objective
Robust cost LP. We illustrate the dualization method for the robust cost LP equation g The key is to express the robust cost or saddle max function supFess of x as an infimum. We first observe that this saddle max function the optimal value of the LP
maximize x²c subject to Fc Fcs
with variable e. Its dual is
g2 subject FT =x A 0,
minimize
| Fe < g), and assuming is nonempty, this dual problem has the same with variable A. With C {c optimal value the primal, i.e.,
sup supe
T x=== inf A
eEC
A20, F" x=
Substituting this into equation g we obtain the problem
minimize
g" X
(9)
subject to Ar = b,
x x20, FT = x, X

---

Published in Transactions on Machine Learning Research (01/2024)
with variables and X. This simple LP is equivalent to the original robust LP equation S in the sense that
if X*) is solution of equation g then x² is solution of the robust LPP equation g
We will see this dualization trick in far more general setting in $
3
Applications
In this section we describe a few applications of saddle programming.
3.1 Robust bond portfolio construction
We describe here simplified version of the problem described in much more detail in Luxenberg et al.) (2022). Our goal is to construct a portfolio of n bonds, giving by its holdings vector h R where h2 is the number of bond i held in the portfolio. Each bond produces a cash flow, i.c., sequence of payments to the portfolio holder, up to some period T. Let Gi,t be the payment from bond in time period Let y E R be the yield curve, which gives the time value of cash: A payment one dollar at time is worth exp(-ty:) current dollars, assuming continuously compounded returns. The bond portfolio value, which is the present value of the total cash flow, can be expressed as
" V(h,y) = ΣΣ hicr exc(-exp(-ty)))
This function is convex in the yields y and concave (in fact, linear) the holdings vector h.
Now suppose we do not know the yield curve, but instead have a convex set V of possible values, with y V. The worst case value of the bond portfolio, over this set of possible yield curves, is
Ww (h) inf V(h,y). yEy
We recognize this saddle min function. (In this application, y is the convex variable of the saddle function V, whereas elsewhere in this paper y to denote the concave variable.)
We consider a robust bond portfolio construction problem of the form
minimize ((h)
(10)
subject to E H. vwo(h) 2 Vllm
where & is a convex objective, typically a mcasure of return and risk, H. is a convex set of portfolio constraints (for example, imposing 2 0 and a lotal budget), and yli is a specified limit on worst. case value of the portfolio over the yield curve set V, which has a saddle min
constraint.
For some simple choices of the worst case value can be found analytically. One example is when y has maximum element. In this special case, the maximum element is the minimizer of the value over y (since V is monotone decreasing function of y). For other cases, however, we need to solve the saddle problem equation 10
3.2 Model fitting robust to data weights
We wish to fit model parametrized by 0 E θ C R" to observed data points. We do this by minimizing weighted loss over the observed data, plus regularizer,
m
w, m1)((0)+r(0
where & is the convex loss function for observed data point i, r is convex regularizer function, and the weights Wi are nonnegative. The weights can be used to adjust data sample that was not representative,

---

Published in Transactions on Machine Learning Research (01/2024)
in Barratt et al. (2021), to ignore some of the data points (by taking w; 0), in Broderick et al. 2020 Evidently the weighted loss is saddle function, with convex variable 0 and concave variable w.
We consider the case when the weights are unknown, but lie in a convex set, w E W. The robust fitting problem to choose to minimize the worst case loss over the set of possible weights, plus the regularizer,
w,l,(0) r
We recognize the first term, e.e., the worst case loss the set of possible weights, saddle max function. For some simple choices of W the worst case loss can be expressed analytically. For example with
= fw ios w s 1' =k], k},
(with & E nl), the worst case loss is given by
max WEW
wrl,(0)= = (fl,......
fm))
where & is the sum-of-k-largest entries [Boyd & Vandenberghe 2004 $3.2.3). (Our choice of symbol k suggests that k is an integer, but need not be.) In this case we judge the model parameter by its worst loss on any subset of k of data points. Put another way, we judge 0 by dropping the m data points on which it does best (i.e., has the smallest loss) (Brodcrick et al. 2020).
CVXPY directly supports the sum-of-k-largest function, the robust fitting problem can be formulated and solved without using DSP. To support this function, CVXPY carries out transformation very similar to the one that DSP docs. The difference is that the transformation in CVXPY is specific to this one function, whereas the one carried out in DSP is general, and would work for ot convex weight sets. One such case would be to constrain the Wasserstein distance the weights to a nominal distribution.
3.3 Robust production problem with worst case prices
We consider the choice of a vector of quantities E Q S R". Positive entries indicate goods we buy, and negative quantities are goods we sell. The set possible quantities Q is our production set, which convex. In addition, we have manufacturing cost associated with the choice 9. given by p(q), where is convex function. The total cost is the manufacturing cost plus the cost of goods (which includes revenue), <(4) +p" q. where p R. is vector of prices.
We consider the situation when we do not know the prices, but we have a convex set they lie in, p P. The worst case cost of the goods is max p" The robust production problem is
minimize Φ(q) max pT subject to g E Q
(11)
with variable q. Here too we can work out analytical expressions for simple choices of P, such as a range for each component, in which case the worst case price is the upper limit for goods we buy, and the lower limit for goods we sell. In other cases, we solve the saddle problem equation II
3.4 Robust Markowitz portfolio construction
Markowitz portfolio construction (Mrkowitzz 1952 chooses a set of weights (the fraction of the total portfolio value held in each asset) by solving the convex problem
maximize nTw ww Tww subject 1T 1. w W.
where the variable the vector of portfolio weights w E R μ E R" is a forecast of the assct returns, 7 > 0 is the risk aversion parameter, Σ E S is a forecast of the asset return covariance matrix, and W is a convex set of feasible portfolios. The objective is called the risk adjusted (mean) return.
9

---

Published in Transactions on Machine Learning Research (01/2024)
Markowitz portfolio construction is known to be fairly sensitive to the (forecasts) j and Σ, which have to be chosen with some care; see, e.g., Black & Litterman (1991). One approach is to specify convex uncertainty set u that (n, 2) must lie in, and replace the objective with its worst case (smallest) value over this uncertainty set. This gives the robust Markowitz portfolio construction problem
maximize subject to 1 w =1 w E W,
(u) (n" w - -yw' Ew)
with variable w. This is described in, e.g., Boyd et al. (2017): Goldfarb & Iyengar 2003 Lobo & Boyd (2000). We observe that this is directly a saddle problem, with a saddle min objective, i.e., maximin problem.
For some simple versions of the problem can work out the saddle min function explicitly. One example, given in Boyd et al. (017)) uses U M x S; where
M (u+ + 8 6 Pi, i 1,....n). n), S = [ + A Σ + A = 0, Any S 7 (E) i,j = =1, -.....,,
where p 0 is vector of uncertainties in the forecast returns, and n E (0, is parameter that scales the perturbation to the forecast covariance matrix. (We interpret 8 and A as perturbations of the nominal mean and covariance and Σ, respectively.) We can express the worst case risk adjusted return analytically as
n [wa)
inf (nE)eu
(n w ywu = p² ywu Ew - [wl - m
"wu
Σ
>> i
1/2
The first two terms are the nominal risk adjusted return; the last two terms (which are nonpositive) represent the cost uncertainty.
4 Disciplined saddle programming
4.1 Saddle function calculus
We use the notation Φ(x, y) X' x C R m + R. to denote a saddle function with concave variables x and convex variables y. The set of operations that, when performed on saddle functions, preserves the saddle property are called the saddle function calculus. The calculus quite simple, and consists of the following operations:
Conic combination of saddle functions. Let (1 = 1,...,k k be saddle functions. Let 0: 2 0 for each i. Then the conic combination, 6(x,1) = Eim (, w:), is saddle function.
Affine precomposition of saddle functions. Let o(x,y) y) be a saddle function, with x E R and y R". Let A E nxg b R", C Rmxp, and d R Then, with u E R and u R the affine precomposition, 6(Au+b,Cu b, Cu d), saddle function.
3. Precomposition of saddle functions. Let o(2,8) X' y C R nM + R be a saddle function, with x E R and y E R The precomposition with a function f R² + R", d(f(u), v), is a saddle function if for each I,..., n one of the following holds:
f((u) is convex and & is nondecreasing in x, for all y E E and all x E X.
[[(uu) is concave and ø is nonincreasing in x; for all y and all E X.
Similarly, the precomposition with function g R + R", g()), is a saddle function if for
each j = 1,..., m one of the following holds:
(v) is convex and ó is nonincreasing in y, for all X and all y E y. (v) is concave and is nondecreasing in yy for all X and all y e V
10

---

Published in Transactions on Machine Learning Research (01/2024)
4.2 Conic representable saddle functions
Nemirovski and Juditsky propose class of conic represenlable saddle functions which facilitate the auto- mated dualization of saddle problems (Juditsky & Nemirovski 2022). We will first introduce some termi- nology and notation, and then describe the class of conic representable saddle functions.
Notation. We use the notation o(x,)) : X x C R + R to denote a saddle function which convex in æ and concave in y. Let K2: K, and K members of a collection K. of closed, convex, and pointed cones with nonempty interiors in Euclidean spaces such that K contains a nonnegative ray, is closed with respect to taking finite direct products of its members, and is closed with respect to passing from cone to its dual. We denote conic membership 2 E K by z Σ O. We call set X C R² K-representable if there exist constant matrices A and B, constant vector c, and cone K E K such that
x= f Eu Ar Bu 3K c}.
CVXPY (Diamond & Boyd 2016) implement function exactly when its epigraph {(r,u) f(x) u} is K-representable.
Conic representable saddle functions.
Let X' and y be nonempty and possossing K-representations
= fx Du Ar Bu 3x ct.
y = tv Du Cy + Do 3x e).
A saddle function o(x, X x y + R is K-representable if there exist constant matrices P, Q, R, constant vectors and and cone K K. such that for each E X and y E V,
o(x, v) inf (f +t| Qu Rx 3K s).
f3..
Here f is a vector of the same dimension as is scalar, and u is vector. This definition generalizes simple class of bilinear saddle functions. See Juditsky & Nemirovski (2022) for much more detail.
Automated dualization. Suppose we have a KCrrepresentable saddle function & as above. The conic form allows us to derive dualized representation of the saddle extremum function
4 (x) = sup o(x, y)
yEy
which again admits a tractable conic form, meaning that it can be represented in a DSL like CVXPY. Specifically,
(x) = sup ((x, v) wEy
sup inf {ff y + +f Qu+ Rx 3K s)
vey fiuu
inf { sup (fT y + fit.a (ye)
Pf + Pf+ + Rx 5K 8
(12)
inf fit.a yEy
sup (s² +1
Pf+ 1p Qu + Rr 3K 8
c²>= D } + Pf + Qu Rx 3K of
= inf f.t.
inf Te A
(13)
where in equation 12 we use Sion's minimax theorem Sion 1958) to reverse the inf and sup, and in equa- tion 13 we invoke strong duality to replace the supremum over y with an infimum over X. Concretely, strong duality and the conic structure allow us equate
sup {5Ty Cy De IK e) = inf (ATe c=>= D 0, A A 0}.
11

---

Published in Transactions on Machine Learning Research (01/2024)
where K is the dual cone of K. This is exactly the automated dualization made possible by the conic representable form of & (which DSP provides). Given the conic representation of o, the dualized form is obtained via the explicit formula given in equation 13
The final line implies a conic representation of the epigraph of Φ(x),
Ne C² = f. D = A A tp+ Qu RE
((z,u) (xx) S uj
(z,u) S,,
which is tractable and can be implemented a DSL like CVXPY. This transformation is exact, and so there is no notion of approximation error or optimality gap arising from the dualization procedure.
A mathematical nuance. Switching the inf and sup in equation 12 requires Sion's theorem to hold. sufficient condition for Sion's theorem to hold that the set y is compact. However, the min and max can be exchanged even y not compact. Then, due the max-min inequality
max min f(z v) S min max f(z, v), =Ex yE
vEy ZEd
the equality equation is replaced with a less than or equal to, and we obtain a convex restriction. Thus, if a user creates a problem involving an SE function (as opposed a saddle point problem only containing saddle functions in the objective), then DSP guarantees that the problem generated restriction. This mcans that the variables returned are feasible and the returned optimal value is an upper bound the optimal value for the user's problem.
13
Obtaining convex and concave saddle point coordinates. One challenge that arises in transforming the mathematical concept of conic representable saddle functions into a practical implementation is that the automated dualization removes the concave variable from the problem. Additionally, the procedure relies on the technical conditions such as compactness, which we believe should not be exposed in a user interface. We now address these points.
In our implementation, saddle problem with an SE function in the objective is solved by applying the above automatic dualization to both the objective and - and then solving each resulting convex problem. Note that Φz2, y) is convex in and concave in y, while -0(x, is concave in and convex in y. We do in order to obtain both the convex and concave components of the saddle point, since the dualization removes the concave variable. To see this, note that equation 13 contains z but not y (and the opposite holds for the negated problem). The saddle problem is only reported as solved if the optimal value of the problem with objective o, u, is within a numerical tolerance of the negated optimal value of the problem with objective 0, -l. If this holds, this actually implics that
max min 6(2,v) v) min max (fx, v), yEy ZEd
=Ex yEy
i.e., equation 12 was valid, even for example y is not compact. To see this, note that solving for ø as well as Ø results in an upper and a lower bound on the optimal value of the saddle point problem,
max min ((x,)) S min max ((x, v) < u, and max min - -6(x, < min max - v) S -l. ZEX yEy
yEY' #EX
ZEd yEy
yE zE
Using symmetry and combining the above inequalities, we obtain
1 S max min p(x,y) I min max Φ(0, v) S aex yEy
yey #ex
Suppose now that u. Note that since
0( v²) S max "(x",1/ = and "(*",v") 2 min (z,
xex
12

---

Published in Transactions on Machine Learning Research (01/2024)
have that 6(x".97 1 = u. That is, the pair (x", obtains the optimal value of the saddle point problem. All that remains is to verify that this pair satisfies the saddle point property. We have that o(x", I "0x",y") for all y E V, since otherwise u = =(x*,)² < maxgey 0(z", .y) = u, contradiction. Similarly, o(x, y²) 2 6(x","" .y") ) for all x E X. Taken together, these inoqualitics state that (x". .yy" is a saddle point, since
6(x'.1) S "0x"" s (xx,0"), Ve Y
Thus, a user need not concern themselves with the compactness of (or any other sufficient condition for Sion's theorem) when using DSP to find saddle point: if a saddle point problem is solved, then the saddle point properly is guaranteed to hold. This mathematical insight extends the work of JJditsky & Nemirovski 20022), which assumes compactness of y, allowing users who might be unfamiliar with this tochnical restriction to use DSP.
5 Implementation
In this section we describe our Python implementation of the concepts and methods described in $4 which we also call DSP. It can be accessed online under open source license at https://gitin: http://tttub.ccc/vvccceeeee /homm//xgrp/////ooo DSP works with CVXPY (Diamond & Boyd 2016). an implementation of a DST. for convex optimization based on DCP. We use the term DSP in two different ways. We use it to refer to the mathematical concept of disciplined saddle programming, and also our specific implementation; which is meant should be clear from the context. The term CSp-compliant refers to a function or expression that is constructed according to the DSP composition rules given $5.2 It can also refer to problem that is constructed according these rules. In the code snippets below, we use the prefix cp to indicate functions and classes from CVXPY. (We give functions and classes from DSP without prefix, whereas they would likely have prefix such dsp in real code.)
5.1 Atoms
Saddle functions in DSP are created from fundamental building blocks or atoms. These building blocks extend the atoms from CVXPY Diamond & Boyd (2016). In CVXPY, atoms are either jointly convex or concave in all their variables, but in DSP, aloms are (jointly) convex in a subset of the variables and (jointly) concave in the remaining variables. We describe some DSP atoms below. The listing is not exhaustive, and additional atoms can be added as necessary.
Inner product. The atom inner (x,y) represents the inner product xyy. Since either y could represent the convex variable, we adopt the convention in DSP that the first argument of inner is the convex variable. According to the DSP rules, both arguments to inner must be affine, and the variables they depend on must be disjoint.
Saddle inner product. The atom saddle @addle_inner( (F, G) corresponds to the function G(y), where F and G are vectors of nonnegative and respectively elementwise convex and concave functions. It is DSP- compliant if F is DCP convex and nonnegative and G is DCP concave. Tf the function G is not DCP nonnegative, then the DCP constraint G >= 0 is attached to the expression. This is analogous to how the DCP constraint x >= 0 is added to the expression cp. (x). As an example consider
f saddle inner inw.rnnnnnnni.e.eeeeee square (an.suurccquu (x), cp.log(y)).
This represents the saddle function
f v) x2 logy I(x 2 1).
where I is the (0, xc) indicator function of its argument.
Weighted Ea norm. The beighted_norm22 (x, y) atom represents the saddle function (Σ y,22) 1/2 with y 2 0. It is DSP-compliant if x is either DCP affine or both convex and nonnegative, and y is DCP concave. Here too, the constraint, y >= 0 is added if y not DCP nonnegative.
13

---

Published in Transactions on Machine Learning Research (01/2024)
Weighted log-sum-cxp. The weighted_ sum__ssms______ (x y) log (Ei=1 Y/ 2:),, with 2 O. It is DSP-compliant if x is DCP convex, and y is DCP concave. The constraint >= O is added if is not DCP nonnegative.
atom represents the saddle function
Quasi-semideffnite quadratic form. The quasidef caaaiidef_quddddee form y, P, Q, S) atom represents the function
P $ ST
$]
f(r
Q y
where the matrix quasi-semidefnite, i.e,, E S and -Q E S It is DSP-compliant if a is DCP affine and y is DCP affine.
Quadratic form. The saddle_ ( Y) atom represents the function x² Ya, where Y is PSD matrix. It is DSP-compliant if DCP affine, and Y is DCP PSD.
5.2 Calculus rules
The atoms can be combined according the calculus described below form expressions that are DSP- compliant. For example, saddle functions can be added scaled. DCP-compliant convex and concave expressions promoted to saddle functions with no concave convex variables, respectively, For example, with variables y, and 2, the expression
f 2.5 saddle _inlee___ierr__ee (eprrrcc.sqquuaaa square(x), (x), cp. spg(g)) + cp. mymmiimmmmmy z
is DSP-compliant, with convex variable x, concave variable y, and affine variable z.
Calling the is is_dsp method of an expression returns True if the expression DSP-compliant. The meth- ods convex_variablee concave_variableee _vrriabaaee,,,,, and affine_ variables, list the convex, concave, and affine variables, respectively. The convex variables variables. We refer to the convex variables as the unanbiguously convex variables, and similarly for the concave variables. The three lists of variables gives a partition of all the variables the expression depends on. For the expression above, f.is_ f.is_dap() evaluates as True, f. convex variables () returns the list [x], f. concave, variables() returns the list [y], and f. affffnne w.fffineevvriilllll variables() returns the list [z]. Note that the role of z is ambiguous in the expression, since it could be either a convex or concave variable.
concave
those that could only be convex, and similarly for concave
No mixing variables rule. The DSP rules prohibit mixing of convex and concave variables. For example if we add two saddle expressions, no variable can appear both convex and concave variable lists.
DSP-compliance is sufficient but not necessary to be a saddle function. Recall that if an ex- pression is DCP convex (concave), then is convex (concave), but the converse is false. For example, the expression cp. sp.sqrt(1 (1 + cp.square (x)) represents the convex function vI +1+a x², but is not DCP. But we can express the same function as cp. nornoom2 (ep. hstack ([1, x])), which DCP. The same holds for DSP and saddle function: Tf expression is DSP-compliant, then it represents a saddle function; but it represent saddle function and not be DSP-compliant. As with DCP, such expression would need to be rewritten in DSP-compliant form, lo use any of the other features of DSP (such a solution method). As an example, the expression x. @ C @ represents the saddle function x² zTCy, but is not DSP-compliant. The same function can be expressed as inner (x, C @ y), which is DSP-compliant. While this restrictive syntax is an inherent limitation of disciplined convex programming in general, it is required for any parser based on the DSP composition rules.
When there affine variables in DSP-compliant expression, it means that those variables could be considered either convex concave; either way, the function is saddle function.
Example. The code below defines the bi-linear saddle function f(z, v) x Cy, the objective of matrix game, with the convex variable and y the concave variable.
14

---

Published in Transactions on Machine Learning Research (01/2024)
Creating saddle function.
from dap import # notational convenience
import cvxpy cp
import numpy as
5 x cp. cp. DoVaiiablee22 (2)
y cp. Vp.aaiiable
mp.array ([[1, 2], [3, 1]1)
f inner (x, C y)
11 f dsp() # True
12
13 f. convex_ www.eoo variablese
[x]
14 f. concave_varribller
[y]
affffnee_ variables
#
0
Lines 1-3 import the necessary packages (which we will use but not show in the sequel). In lines 5-7, wo create two CVXPY variables and constant matrix. In line 9 we construct the saddle function using the DSP atom inner. Both its arguments are affine, if saddle fundciii is DSP-compliant, which it is. In lines 13-15 we call functions that return lists of the convex, concave, and affine variables, respectively. The results of lines 13 15 might seem odd, but recall that inner marks its first argument as convex and its second as concave.
this matches the DSP rules. In line 11 we check
5.3 Saddle point problems
Saddle point problem objective.
To construct a saddle point problem, we first create an objective using
obj MinimizeMaximizeet (f),
where f is a CVXPY expression. The objective obj DSP-compliant if the expression DSP-compliant.
This is analogous to the CVXPY roctors cp. Mppiiiimieee (f) and cp.Maximize (f), which create objectives from expressions.
Saddle point problem. A saddle point problem is constructed using
prob SaddlePoiintProblemmoo0 (obj, constraints, cvx_vars, CCV varr)
Here, obj is a MinimizeMaximiza objective, constraints is a list of constraints, cvx_vars vars is a list of convex variables and ccv vars is a list of concave variables. The objective must be DSP-compliant for the problem to be DSp-compliant. We now describe the remaining conditions under which the constructed problem is DSP-compliant.
Each constraint in the list must be DCP, and only involve convex variables or concave variables; convex and concave variables cannot both appear in any constraint. The list of convex and concave variables partitions all the variables that appear in the objective or the constraints. In cases where the role of a variable is unambiguous, it is inferred, and does not need to be in either list. For example with the objective
MinimizeMaariniza (neegheeoggg lag__o____pppppeeeeeee (x, y) cp. exp cp. log(v z)
x and u must be convex variables, and and v must be concave variables, and so do not need to appear in the lists used to construct a saddle point problem. The variable z, however, could be either a convex or concave variable, and so must appear in one of the lists.
The role of variable can also be inferred from the constraints: Any variable that appears a constraint with convex (concave) variables must also be convex (concave). With the objective above, the constraint
15

---

Published in Transactions on Machine Learning Research (01/2024)
+ <= 1 would serve to classify concave variable. With this constraint, could pass empty variable lists to the saddle point constructor, since the roles of all variables can be inferred. When the roles of all variables are unambiguous, the lists are optional.
The roles of the variables in a saddle point problem prob can be found by calling prob. convec_oeeeeeeeee Saave___ariabbee(( and prob. concave, variables O), which return lists of variables, and is a partition of all the variables appearing in the objective or constraints. This is useful for debugging, to be sure that DSP agrees with you about the roles of all variables. A DSP-compliant saddle point problem must have an empty list of affine variables. (If it did not, the problem would be ambiguous.)
Solving a saddle point problem. The solve method of a SaddlePointProbl.n object canomicalizes and solves the problem. This involves checking the objective and constraints for DSP-compliance. The conic representation of the problem is obtained, which involves setting up an auxiliary problem and compiling it using CVXPY. Then, the dualization is carried out, which results another CVXPY problem which is then solved to yield the objective value. This has the side effect of setting all convex variables' .value attribute. To also obtain the values of the concave variables, the saddle point problem is solved again with negated objective and the roles of the minimization and maximization variables reversed. We emphasize that as DSP acts as a compiler, it does not implement any optimization algorithms itself, but rather relies on the solvers accessible through CVXPY.
Example. Here we create and solve a matrix game, continuing the example above where was defined. We do not need pass in lists of variables since their roles can be inferred.
Creating and solving a matrix game.
obj MinimizeMaximize((f (f)
constraints = [x >= 0, cp. sum (x) == 1, y >= o, cp. (y) 1]
prob = SaddlePointProblee((tt)) constraints)
prob. is _s__sp(( # True
prob. convex_eoocccccooooooocoocccoooe variables ()
convex_variables
# [x]
prob. concave variables()
cobbocacvve__ariialeee ()
[y]
prob. affineffeeeeaaeeeaa affine variables
# []
prob. solve () # solves the problem
prob. value # 1.66666666666666667
12 x. value #
0.33338338])
19 value #
0. 66666666))
5.4 Saddle extremum functions
Local variables.
An SE function has one of the forms
G(z) sup f(x, v) y
H inf f(z v). zEX
where f saddle function. Note that y in the definition of G, and x in the definition of H, are local dummy variables, understood to have connection to any other variable. Their scope extends only to the definition, and not beyond.
To express this subtlety in DSP, we use the class LocalVariable to represent these dummy variables. The variables that are maximized over (in a saddle max function) or minimized over (in a saddle min function) must be declared using the VocalVarialle() constructor. Any LocalVariable an SE function cannot appear in any other SE function.
Constructing SE functions. We construct SE functions in DSP using
16

---

Published in Transactions on Machine Learning Research (01/2024)
saddle max constraints)
saddle _atee_mi(n constraints).
Here, is a CVXPY scalar expression, and constraints list of constraints. We now describe the rules for constructing DSP-compliant SE function.
If saddle, max is being constructed, f must be DSP-compliant, and the function's concave variables, and all variables appearing in the list of constraints, must be LocalVariables while the function's convex variables must all be regular Variables. A similar rule applies for saddle __in.
The list of constraints is used to specify the set over which the sup or inf taken. Each constraint must DCP-compliant, and can only contain LocalVariables.
With Variable, y_loc LocalVariable, loc LocalVariable, and Variable, consider the following two SE functions:
f_1 saddle_max (inner (x, y_loc) 2, [y_loc 1]) f_2 saddle_man max (inner (x, y_loc) z_loc, ly_loc <= 1, _oc <= 1])
Both are DSP-compliant. For the first, calling f f_1. convex wtteee_vvaiaaeeleeeeeaee variables() concaee, variables () would return [y_loc]. For the second, calling 2. coovex_variaable would return [x], and f f_2. concave sate_aarrabbleeceeeee return [y ly_,oc, 2_loc].
() would return [x, z], and calling
Let be Variable. Both of the following are not. DSP-compliant:
f_3 saddle_md @oddle_maxtte (inner (x, y_loc)
[y_loc <= 1, 2 <= 1]) f_4 saddle max (inner (x, y) z_ loco [y_loc <= 1, 2_loc <= 1])
The first is not DSP-compliant because z is not a LocalVariable, but appears in the constraints. The second not DSP-compliant because y is not a LocalVariable, but appears as a concave variable in the saddle function.
SE functions are DCP. When they DSP-compliant, saddle_nd is convex function, and saddle_min min is concave function. They can be used anywhere in CVXPY that a convex concave function is appropriate. You can add them, compose them (in appropriate ways), use them in the objective or either side of constraints (in appropriate ways).
Examples. Now we provide full examples demonstrating construction of saddle max, which we can use to solve the matrix game described in 5.3 saddle problem involving SE function.
Creating a saddle max.
Creating variables cp. (2riable(2)
Creating local variables y_loc = LocalVariable (2)
Convex in x, concave in y_loc
saddle aadlle_inner(e x, y y_loc)
maximizes y_loc
G = saddle maa_max( (f, ly_loc >= 0, sum = 1))
Note that is CVXPY expression. Constructing a saddle min works exactly the same way.
17

---

Published in Transactions on Machine Learning Research (01/2024)
5.5 Saddle problems
A saddle problem is convex problem that uses SE functions. To be DSP-compliant, the problem must be DCP (which implies all SE functions are DSP-compliant). When you call the solve method on a saddle problem involving SE functions, and the solve successful, then all variables' value fields are overwritten with optimal values. This includes LocalVariables that the SE functions maximized or minimized over; they are assigned the value of particular maximizer or minimizer of the SE function the value of the non-local variables, with no further guarantees.
Example. We continue our example from 5.4 and solve the matrix game using either saddle max.
Creating and solving a saddle problem using a saddle max to solve the matrix game.
prob cp.Problem (enobleeep.MMmmmmzeeeeeee Minimize (G), [x >= 0, cp. (x) 1])
prob. is isbbip # True
prob. solve() # solving the problem
prob. value # 1.666666666666667
v.value # array(10.66666667,, 0. 0.33333333])
6 Examples
In this section we give numerical examples, taken from $ showing how to create DSP-compliant problems. The specific problem instances we take are small, since our main point to show how easily the problems can be specified in DSP. But DSP will scale to far larger problem instances. Again, code and data for these examples are available at
http://ttttbu.ttootneeeeeeeeeett cvxgrp/dsppppppp
6.1 Robust bond portfolio construction
Our first example is the robust bond portfolio construction problem described in $3.1 We consider portfolios of n 20 bonds, over a period T' = 60 half-years, i.e., 30 years. The bonds are taken as representative ones in a global investment grade bond portfolio; for more detail, see Luxenberg et al. (2022). The payments from the bonds are given by E 20 with cash flow of bond i in period denoted 61 The goal is choose holdings h 2220 with the portfolio constraint set given by
H (h h 0, p =
i.e., the investments must be nonnegative and have total value (budget) B, which take to be $100. Here E R220 20 denotes the price of the bonds on September 12, 2022. The portfolio objective is
@(h) 2 [1 h mk) ) o pll1.
where mike R220 is the market portfolio scaled to a value of $100, and denotes Hadamard or elementwise multiplication. This called the turn-over distance, since tells us how much we would need to buy and sell to convert. our portsolio to the market port.folio.
The yield curve set y is described in terms of perturbations to the nominal or current yield curve yom E R which is the yield curve on September 12, 2022. We take
T-1 (641 - 8,)2 s sw) )
y
nom + y
118| < gmax ||ō112 < K,
We interpret 5 E R 60 as a shock to the yield curve, which we limit elementwise, in absolute sum, and in smoothness. The specific parameter values are given by
gmax 0.02, 0.9,
10-6
18

---

Published in Transactions on Machine Learning Research (01/2024)
In the robust bond portfolio problem equation 10 we take Vlim 90, that is, the worst case value of the portfolio cannot, drop below 890 for any E y.
We solve the problem using the following code, where we assume the cash flow matrix C, the price vector the nominal yield curve y_nom, and the market portfolio h_ mkt are defined.
Robust bond portfolio construction.
Constants and parameters
n, T C. shape
delta_max: max, kappa, omega 0.02, 0.9, 1e-6 100
V V_lim 90
# Creating variables
= cp.Variable nonneg=True)
10 delta LocalVariable?? (T)
11 y y_nom delta
12
# Objective
phi 0.5 cp. (cp. ctp.muuttipyhh, p) -pp.ultiply(C (h_mkt, p))
16
18 # Creating saddle min function
17 =
18 for range (n)
19
t_plus_1 np. arange (T)
Account for zero-indexing
+= saddle, inner (nnnercp..co exp exp wtt.p.mllppllll...oc..m.mm..plpm (-t_pplllyy_____11... y)), h[i] c(i))
20
Y = [
23
cp. pp.norm_ inf (delta) delta_max max,
cp. normi (delta) <= kappa, (delta[1:] (dellaa
24
25
cp.sum ham__squrres
delta[:-1]) omega,
26
27
V_wc = saddle_min(V, Y)
Creating and solving the problem problem
31
Min.iiii [h 0 p B, V_wc >= V_lim]) 15.32
32 problem.solved
We first define the constants and parameters lines 2-5, before creating the variable for the holdings h in line 8, and the LocalVariable delta, which gives the yield curve perturbation, in line 10. In line 11 we define y as the sum of the current yield curve y_ y_mom and the perturbation delta. The objective function is defined in line 14. Lines 17 20 define the saddle function V via the saddle inner atom. The yield uncertainty set Y is defined in lines 22 26, and the worst case portfolio value is defined in line 25 using saddle min. We use the concave expression saddle_me min to create and solve CVXPY problem in lines 31-32.
Table D summarizes the results. The nominal portfolio is the market portfolio, which has zero turn-over distance to the market portfolio, i.e., zero objective value. This nominal portfolio, however, does not satisfy the worst-case portfolio value constraint, since there are yield curves y that cause the portfolio value drop to around $87, less than our limit of $90. The solution of the robust problem has turn-over distance $15.32, and satisfies the constraint that the worst-case value be at least. $90.
19

---

Published in Transactions on Machine Learning Research (01/2024)
Nominal portfolio
Robust portfolio
Turn-over distance
$0.00
$15.32
Worst-case value
$86.99
$90.00
Table 1: Turn-over distance and worst-case value for the nominal (market) portfolio and the robust portfolio. The nominal portfolio does not meet our requirement that the worst-case value be least 890.
6.2 Model fitting robust to data weights
We consider an instance of the model fitting problem described in 3.2 We use the well known Titanic data sct (Harrell Jr. & Cason 2017), which gives several attributes for cach passenger on the ill-fated Titanic voyage, inchuding whether they survived. A classifier is fit to predict survival based on the features sex, age (binned into three groups, 0-26, 26 26-53, and 53 80), and class (1, 2, or 3). These features are encoded as a Boolean vector a, E R². The label yi means passenger survived, and yi -1 otherwise. There are 1046 examples, but fit our model using only the 50 passengers who embarked from Queenstown, one of three ports of embarkation. This is somewhat non-representative sample; for example, the survival rate among Queenstown departures is 26%, whereas the overall survival rate is 40.8% This is a common situation in machine learning, where the distribution of labels in the training data does not match that of the test dataset (known as label shift), for which we seek a robust solution.
We scek a lincar classifier d = sign(a? 8o), where I E R the classifier parameter vector and Bg E is the bias. The hinge loss and & regularization are used, given by
(()) = m0, 1 -y;a
r(0) 1
with 7 = 0.05.
The data is weighted partially correct for the different survival rates for our training set (26%) and the whole data (40.8)). To do this we wy 21 when Yt and uy 22 when yi -1. We require w 0 and 1Tw 1, and
0.408 0.05 < my S 0.408 + 0.05.
11=1
Thus W consists of weights on the Queenstown departure samples that correct the survival rate to within 5% the overall survival rate.
The code shown below solves this problem, where we assume the data matrix already defined as A_tr train (with rows of ) the survival label vector is defined y train, and the indicator of survival in the training set is defined surv.
Model fitting robust data weights.
Constants and parameters m, = A_ train. shape
inds 0 surv == 0
inds 1 surv ==
eta 0.05
Creating variables theta = Va.aariable (n)
beta_0 0 cp. (priabbelee
weights = cp. Variable (m, nonneg=True)
11 ourv_weiggt 0 = cp. sp.aabiblee
12 surv_weight
cp. Variable()
13
14 Defining the loss function and the weight constraints
18 y hat Artrain @ theta + beta_ 0
20

---

Published in Transactions on Machine Learning Research (01/2024)
Nominal classifier
Robust classifier
Train accuracy
82.0%
80.0%
Test accuracy
76.0%
78.6%
Table Nominal and worst-case objective values for classification and robust classification models.
loss pp.pos(1 cp pppmultipllyyy_train. y b_bat))
objective wannmiizeeaxxiiizeeeeaaaaa inner (loss, weights)
18
eta cu.sum_ haaimamuuueesseee (theta))
19
20
constraints
21
cp. (weights) 1,
22
0.408 0.05 <= weights @ surv,
28
weights @ surv <= 0.408 + 0.05,
weights [i] == surv surv_weight_00 weights [inds_1] _]] == surv surv_weight_b 1,
24
27
Creating and solving the problem 29 problem SaddeePoiimPrrbbeee000oooct.. constraints)
28
30
problem.solved
After defining the constants and parameters in lines 2-5, we specify the variables for the model cocfficient and the weights in lines 8-9 and 10 12, respectively. The loss function and regularizer which make up the objective are defined next in lines 15 18. The weight constraints defined in lines 20 26. The saddle point problem is created and solved in lines 29 and 30.
The results are shown in table 2 We report the test accuracy on all samples in the datasel with different port of embarkation than Queenstown (996 samples). We see that while the robust classification model has slightly lower training accuracy than the nominal model, achieves a higher test accuracy, generalizing from the non-representative training data better than the nominal classifier, which uses uniform weights.
6.3 Robust Markowitz portfolio construction
We consider the robust Markowitz portfolio construction problem described in $3.4 We take = 6 assets, which are the (five) Fama-French factors (Fama & French 2015) plus a risk-free asset. The data is obtained from the Kenneth R. French data library (French) 2022), with monthly return data available from July 1963 to October 2022. The nominal return and risk are the empirical mean and covariance the returns. (These obviously involve look-ahead, but the point of the example is how to specify and solve the problem with DSP, the construction of real portfolio.) We take parameters 0.02, r7 0.2, and risk aversion parameter 7 =
In the code, use mu and Sigma for the mean and covariance estimates, respectively, and the parameters are denoted rho, eta, and gamma.
Robust Markowitz portfolio construction.
Constants and parameters = len (mu)
rho, eta, gamma = 0.2, 0.2, 1
Creating variables
ap.aaiiable.. nonneg=True)
delta loc LocalVariable (n)
21

---

Published in Transactions on Machine Learning Research (01/2024)
Nominal portfolio
Robust portfolio
Nominal objective
.295
.211
Robust objective
.065
.076
Table Nominal and worst-case objective for the nominal and robust portfolios.
Sigmm__ertuuree = LocalVariable (n, n), PSD=True) Delta_ loc LocalVariable ((n, n))
11
12
Creating saddle min function
13 mu saddle (dellee w)
14
gamma saddle foatle_uuad_for(tt gigma_eerturbedl
15
Sigma_diag Sigma. diagonal Sigma.diagonal local constraints = abs (delta_loc) <= rho,
18
== Sigma Delta_lo _occ
19
cp. ap. _eeetalllllll
eta np.sqrt (up. outer (Sigma_ Sagma_diag)
20
21
20
saddle sfddle_min(f, cocal_constraints)
# Creating and solving the problem
problem cp.Problem (cp. Maximize (G), Icp.sum(t == 1])
problem. solvee 0.076
We first define the constants and parameters, before creating the weights variable in line 6, and the local variables for the perturbations in lines 8 10. The saddle function for the objective is defined in line 13, followed by the constraints on the perturbations. Both are combined into the concave saddle min function, which is maximized over the portfolio constraints lines 25-26.
The results are shown in table 3 The robust portfolio yields slightly lower risk adjusted return of 0.291 compared to the nominal optimal portfolio with 0.295. But the robust portfolio attains higher worst-case risk adjusted return of 0.076, compared to the nominal optimal portfolio which attains 0.065.
References
S. Barratt, G. Angeris, and S. Boyd. Optimal representative sample weighting. Statistics and Computing, 31(2):1-14, 2021.
Ben-Tal, L. El Ghaoui, and A. Nemirovski. Robust optimization, volume 28. Princeton university press, 2009.
Bertsimas, D. Brown, and C. Caramanis. Theory and applications of robust optimization. SIAM review, 53(3):464 501, 2011.
F. Black and R. Litterman. Assct allocation. The Journal of Fized Income, ((2):7-18, 1991. ISSN 1059-8596. doi: 019905/jfi.191140660 URL htttp://jfii www.pppreeearrc..cmomooeetenttee
J. Borwein and A. Lewis. Conves Analgsis. Springer, 2006.
S. Boyd and Vandenberghe. Conver Optimization. Cambridge University Press, 2004.
S. Boyd, E. Bussoti, Diamond, R. Kahn, K. Koh, P. Nystrup, and J. Speth. Multi-period trading via convex optimization. Foundations and Trends in Optimization, 3(1):1-76, 2017. doi: 20.5501/440000023. URL
doi http://wf.......oo//ooo////00000
22

---

Published in Transactions on Machine Learning Research (01/2024)
K. Bredies and H. Sun. Preconditioned douglas- rachford splitting methods for convex-concave saddle-point problems. STAM Journal on Numerical Analysis, (3(1):421-444) 2015.
T. Broderick, R. Giordano, and R. Meager. An automatic linite-sample robustness metric: When dropping little data make big difference? arXiv preprint orXiv:3011.14999 2020.
A. Chambolle and T. Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision, 40(1):120-145, 2011.
A. Chambolle and T. Pock. On the ergodic convergence rates of a first-order primal-duse dual algorithm. Math- ematical Programminn, 159(1): 287, 2016.
Y. Chen, G. Lan, and Y. Ouyang. Optimal primal-dual methods for a class saddle point problems, 2013. URL https://arxiv.orgg https///39..55.0
L. Condat. A primal-dual splitting method for convex optimization involving lipschitzian, proximable and linear composite terms. Journal of optimization theory and applications, 158(2):460 479, 2013.
G. Cormuéjols, J. Peña, and R. Tütüncü. Oplimization Methods in Finance. Cambridge University Press, 2 edition, 2018. doi: 10.1017/9781107997333
V. Dem'yanov and V. Malozemov. Introduction to minimaz. Courier Corporation, 1990.
S. Diamond and S. Boyd. CVXPY: A Python-embeddded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
X. Dou and M. Anilescu. Distributionally robust optimization with correlated data from vector au- toregressive processes. Operations Research Letters, 47(4):294 299, 2019. ISSN 0167-6377. doi: URL
p11/800666637119000099
D. Du and P. Pardalos. Minimaz and applications, volume 4. Springer Science & Business Media, 1995.
E. Fama and K. French. A five-factor asset pricing model. Journal of Financial Economics, 116(1):1 22, 2015. ISSN 0304-405X. doi:
URL
K. French. Kenneth r. french data library, 2022. URL http:p////tbab.okk...raaaaaaattr ken. atrench/datta_ibraary html html
A. Fu, B. Narasimhan, and Boyd. CVXR: An package for disciplined convex optimization. Journal of Statistical Software, 94(14):1- 34,, 2020. doi: 10.18633/jss.v044.11
Goldfarb and G. Iyengar. Robust portfolio selection problems. Mathemalics of Operations Research, 28 (1):1-38) 38, 2003. ISSN 0364765X, 15265471. URL http://www. http///ww.jtrrrr.oo......o jstor org/stable/441695
Goodfellow, J. Pouget-Abadie, M. Mirza, Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. Tn Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
M. Grant and Boyd. CVX: Matlab software for disciplined convex programming, version 2.1. 2014.
M. Grant, S. Boyd, and Y. Ye. Disciplined convex programming. In Global optimization, pp. 155-210. Springer, 2006.
B. Halldórsson and R. Tütüncü. An interior-point method for class of saddle-point problems. Journal of Optimization Theory and Applications, 116(3):559955) 590, 2003.
F. Harrell Jr. and T. Cason. Titanic dataset, 2017. URL https://www.openi ortpm////r/////555555
R. Hettich and K. Kortanek. Semi-infinite programming: Theory, methods, and applications. SIAM review, 35(3))380-43) -29, 1993.
23

---

Published in Transactions on Machine Learning Research (01/2024)
A. Juditsky and A. Nemirovski. On well-structured convex-concane concave saddle point problems and variational inequalities with monotone operators. Oplimization Methods and Sofhware, (7 1602, 2022. doi: 00.1880/10556788.222..9222.
URL
105567888888188111111 2021 . 1928111
G. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12: 747-756, 1976.
T. Lin, C. Jin, and M. Jordan. Near-optimal algorithms for minimax optimization. In Conference Learning Theory, pp. 2738 2779. PMLR, 2020.
M. Lobo and S. Boyd. The worst-case risk of portfolio. Technical report, 2000. URL https://web. staaford.edu/ http///////////pppp///////////// bnd.
J. Lofberg. Yalmip : toolbox for modeling and optimization matlab. In 2004 IEEE International Conference on Robotics and Automation (IEEE Cat. No.04CH37505, pp. 284 289, 2004. doi: 10.1109/ CACSD.200411383900
E. Luxenberg, P. Schicle, and Boyd. Robust bond portfolio construction via convex-concave saddle point optimization, 2022. URL https://aaxxi: wwwaarii...aaaaaaa.aaaaaeeaaaaee
owg//bas/ wtwaaa/////. 02570
Markowitz. Portfolio selection. Journal of Finance, 7:77 91, 1952.
O. Morgenstern and J. Von Neumann. Theory of gomes and economic behavior. Princeton University Press, 1953.
A. Mutapeic and S. Boyd. Cutting-set methods for robust convex optimization with pessimizing oracles. Oplimization Methods & Software, 24(3):381-44 406,, 2009.
A. Nedić and A. Ozdaglar. Subgradient methods for saddle-point problems. Journal of optimization theory and applications, 142(():205-225 2288, 2009.
A. Nemirovski. On self-concordant convex concave functions. Optimization Methods and Software, (1(44)): 303 384, 1999. doi: 10.1080//105577899900007737 URL https:///oll http://///eeiirorooo././////0000
A. Nemirovski. Prox-method with rate of convergence o(1/t) for variational incqualitics with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal Optimization,
2004.
Y. Nesterov. Excessive gap technique in nonsmooth convex minimization. SIAM Journal on Optimization, 16(1):235 249, 2005a.
Y. Nesterov. Smooth minimization of non-smooth functions. Mathematical programmingg 103 2005b.
Y. Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109(2):319 344, 2007.
Y. Nesterov. Accelerating the cubic regularization of newton's method on convex problems. Mathematicul Programming, 1815 2008.
Y. Nesterov and A. Nemirovski. Conic formulation of a convex programming problem and duality. Opti- mization Methods & Software, 1:95-115, 1992.
Y. Nesterov and B. Polyak. Cubie regularization of newton method and its global performance. Mathematical Programming, 108(1):177 205, 2006.
R. Rockafellar. Conver analysis, volume 18. Princeton university press, 1970.
R. Rockafellar and R. Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
E. Ryu and W. Yin. Large-Scale Conver Optimization: Algorithms & Analyses via Monotone Operators. Cambridge University Press, 2022.
24

---

Published in Transactions on Machine Learning Research (01/2024)
M. Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171-176, 1958.
Thekumparampil, P. Jain, P. Netrapalli, and Oh. Efficient algorithms for smooth minimax optimization. In Advonces in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL
http://owccciiig...oooooocccc/pp [5caalaasaaee1113366660011110003 par
M. Udell, K. Mohan, D. Zeng, Hong, S. Diamond, and S. Boyd. Convex optimization in Julia. SC14
Workshop on High Performance Technical Computing Dynamic Languages, 2014.
25


Reviews:
[{"review_id": "CYpsu3pT8F", "reviewer": "Reviewer_s9NH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- Parts 1 to 3 are outstandingly clear, and filled with examples, the main idea, which is to dualize one of the optimization problems is clearly explained through an example. It provides a clear introduction to Juditsky and Nemiroski 2022.\n- Code is great and modular\n\nWeaknesses: \n- For me, the main weakness of the paper is that Part 4, where the main contribution of the authors lies, is not clear enough.\nIn particular, I am not sure I correctly understood what type of problems the proposed framework is handling.\nIMO this is  due to:\n1 - The use of non-standard notation to define functions\n2 - The definition of the main introduced object, \"conically representable saddle functions\", which should be much more polished\n(see requested changes below)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The main contributions are the following:\n- The authors provide a very clear **introduction to saddle problems** and provide a **great intuition** on how to transform them into convex conic programs. It helps a lot to digest Juditsky and Nemiroski 2022 on which the theoretical part of the manuscript is based.\n- Authors provide a **systematic way** of transforming a specific type of **constrained saddle** problem into a **convex program**, these types of problems are called \"disciplined saddle programs\"", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Most of my concerns are regarding the clarity of Part 4\n\nContributions:\n- I would merge the 2 first points in the contribution (p3, section 1.2)\n\nClarity before part 4:\n- I found the definition of the mathematical objects very hard to parse, I had to read them multiple times to correctly understand what they were precisely. In particular, I would recommend encapsulating the mathematical definitions of saddle functions, saddle points, saddle problems, saddle extremum function, and conic representable saddle functions in the definition environment for clarity.\n- I found it weird to decouple the definition of saddle functions and saddle points, I would merge them\n- Before section 2.4, when you mention differentiating through functions defined as a maximum, maybe you could quickly mention Danskin theorem, and or the implicit differentiation line of work\n- I did not understand the \"subgradient methods\" paragraph in section 2.5\n- In the example \"robust cost LP\" in section 2.6, maybe you could recall what is $\\mathcal{C}$ to avoid the reader searching before\n\nClarity of Part 4:\n- I am strongly against the notation $\\phi(x, y)$ to denote a function, the standard notation is $\\phi$, or $(x, y) \\rightarrow \\phi(x, y)$. I do not see the benefit of using $\\phi(x, y)$. IMO the whole part 4 should be rewritten using $f$ for functions.\n- **What is exactly a conically representable saddle point function? ** Is this a **bilinear constrained min max?** This is what I parse from the definition, but I am confused since non-bilinear examples are presented in the implementation section part 5.\nWhat is t in the definition of conically representable saddle point functions? It seems it is not defined. Honestly I was very disappointed by this part. The authors did such a great pedagogical job in Parts 1 to 3, and dryly introduced their main concept, with a laconic  \"Juditsky and Nemiroski 2022 for details\"\n- In section 4.2, at \"automated dualization\", what is the concept \"power of the conic form\"? \n- In section 4.2, at \"obtaining convex and concave saddle point coordinates\", I was not able to understand why solving the problem with $f$ and $-f$ yields the saddle points from the solution of the convex problem \n\nTypos:\n- first equation in 2.5 ,= >> =", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "u7fD0a4c70", "reviewer": "Reviewer_FqVv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \nThe paper is well-written and easy to follow.\n\n**First open-source package:** This paper introduces a domain-specific language (DSL) called disciplined saddle programming (DSP). To the best of my knowledge, it is the first open source for solving saddle problems.\n\n**User friendliness:**  The inclusion of numerous illustrative examples greatly enhances the reader's grasp of how to formulate and solve problems using DSP. Users can use it without knowledge of duality tricks and without the prior verification of the existence of saddle points.\n\nWeakness: There are mainly two concerns:\n\n**Implementation insight:** This paper provides a packaged implementation of Juditsky and Nemirovski’s work for conic representable saddle point programming. It would be better if you could elaborate more on the technical contribution to implementation/difficulties encountered in the implementation.  \n\n**Comparison with SOTA  methods:** As a solver, it would be beneficial to compare the time consumption and convergence performance with the current state-of-the-art methods. This empirical evidence would be valuable for assessing the real-world applicability and effectiveness of the proposed method.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a domain-specific language (DSL) called disciplined saddle programming (DSP), catering to conic-representable saddle point programs. It is the first toolbox that can be directly used for these problems, where duality tricks can be used automatically. This paper contributes an open-source package that enables users to effectively tackle saddle problems without requiring any understanding of duality tricks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It would be better to include a section to describe the challenge in the implementation and the comparison with other state-of-the-art methods.", "broader_impact_concerns": "No broader impact concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CApVJL9z8f", "reviewer": "Reviewer_7kLT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. Drawing from theoretical insights in existing literature, the authors have transformed the theory into a practical approach for specifying and solving convex-concave saddle problems. Additionally, the authors developed a user-friendly open-source package compatible with CVXPY. To my knowledge, this package is the first end-to-end toolbox designed for solving min-max problems.\n\n2. The paper is also clearly written, and the authors have incorporated numerous illustrative examples from various domains, showcasing the applicability of DSP. As such, this paper can also serve as a comprehensive guide to the DSP package.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces and implements a domain-specific language called disciplined saddle programming (DSP). DSP is designed specifically for specifying and addressing convex-concave saddle problems. Building on the research by Juditsky & Nemirovski in 2022, DSP utilizes the concept of conic-representable saddle point programs and leverages the automatic dualization technique to reduce bilevel problems to single convex optimization using conic duality. The authors have implemented DSP as an open-source package, streamlining the process for users to formulate and solve saddle problems.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The foundational ideas and methodologies for this work stem from Juditsky & Nemirovski's research in 2022 (https://doi.org/10.1080/10556788.2021.1928121). The primary contribution of this paper lies in its implementation of their methods into a user-friendly package for solving saddle point problems. However, the paper does not easily allow readers to assess the authors' engineering endeavors in translating the theory into a user-friendly toolkit. It would greatly enhance the reader's experience if the authors could provide more details or perhaps a dedicated section illustrating the engineering and developmental challenges.\n\n2. Overall, the paper is easy to follow. However, I am mainly confused about the following point: \nWhile the authors tried to derive a procedure to obtain both the convex and concave coordinates of the saddle point after reducing to a single convex problem, the representation of this process lacks clarity. A potential improvement for the authors would be to incorporate an implementation example for this procedure, as it plays a crucial role in enhancing the toolbox's practicality.", "broader_impact_concerns": "No further concerns about the ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KpCx0MzwY9", "reviewer": "Reviewer_MvoZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is really well-written, intuitive, and easy to follow. Even for people not familiar with the saddle point problem, it gives enough background on how the saddle point problem is formulated from application contexts and how the proposed method can be programmed and implemented. \n\nMy main concern is on the following two points: \n\n- (i) The interests of the work to general ML audience. In the examples and numerical experiments, i.e. Section 3 and Section 6, most of the examples are from finance or operations research applications, with the only exception of the weighted ERM problem in Section 3.2. This weighted ERM problem is no doubt an important topic for the distributional robust optimization or adversarial learning community in ML. But it seems this paper only demonstrates for the case where the weight choice set $\\mathcal{W}$ is a polyhedron specified by linear constraints. In my opinion, it would make the paper more attractive if the numerical experiments consider more weight choice set such as a set specified by the $\\chi$-square distance or the Wasserstein distance towards the uniform distribution, as this would better resonate with the “ML” applications. \n\n- As a minor point, the numerical example in Section 6.2 is not quite for a robust ML purpose, but it is more of a simple label-shift adjustment to match the survival rate between the training set and the test set. \n\n- (ii) The technical contribution of the work: From a technical viewpoint, it seems to me that the paper is more of the results Juditsky & Nemirovski (2022) and its contribution is more on the engineering side for a systematic way to implement the automatic dualization idea proposed therein. Please correct me if I miss anything; and I would suggest the authors to better clarify the technical contribution of the paper against that paper and the existing literature or whether the paper is positioned as one that purely contributes for an engineering implementation.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a disciplined way for automatically dualizing the saddle programming problem. It provides a detailed background for the saddle programming with examples covering many related fields and applications. It derives the method from scratch and describes in full details how the method can be implemented in CVXPY. Three numerical experiments demonstrate how the method applies to different contexts.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Besides the above two points, I think the following two aspects can be some viable options for improving the manuscripts:\n\n- Optimality gap: From the technical sections to the numerical experiments of the paper, there is not much mentioned about the optimality gap of the output solution from the proposed method. Like for the numerical experiments, the solution is only compared against the nominal solution which can be a trivial solution for application contexts of Section 6.1 and 6.2. In my opinion, an advantage over the nominal solution doesn't tell much about the quality of the given solution. As I understand, it should be not difficult (correct me if I am wrong here) to derive an optimality gap which can better demonstrate the quality of the solution. There can also be other ways to visualize and better assess the quality of the solution. The current comparison against the nominal solution seems too simple.\n\n- Computational time: I understand that the focus of the paper is to provide a systematic and automatic way to convexify saddle point problem, and the computation time for solving a problem depends on the used solver and the intrinsic difficulty of the underlying problem. Yet some numerical experiments can be more helpful and insightful to ML audience. For example, for the reweighting ERM problem in Section 3.2, how different choices of the weight set affect the computational time, and how the computational time may scale with number of samples. These might be out of the scope of the current positioning of the paper, but can be of interests to people in related topics. Also, for financial applications, the computational time and the scalability is also of great importance in practice. Some demonstrations on the computational aspects of the numerical experiments in Section 6.1 and 6.3 can be helpful.\n\nMinor comments:\n\nI appreciate the clarity of the writing of the paper. There are still minor typos and I'd suggest the authors to proofread the paper again thoroughly:\n\n- Page 3: $\\lambda_n$ should be $lambda_m$. \n- Page 3: the set $\\mathcal{Y}$ should be $R^p\\times R^{m}_+$. \n- Page 4: As \"a\" more esoteric example\n- Page 6: there is an extra comma after $sup\\  y^\\top x$\n- Page 9: the norm of $\\delta$ should be $||\\cdot||$; and also what's the norm used here?\n- Page 17: maybe specify the dimension of $\\delta$ and $\\delta=(\\delta_1,...,\\delta_T)$\n\nAt the end of this review, my sincere apologies to the authors and editor team for the delay in submitting my review :-)", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "atgycWXKbj", "reviewer": "Reviewer_toyQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths:\n\n- **Automated Dualization**: The paper's central contribution of automating the dualization trick for saddle problems fills a gap in the existing literature. This can significantly simplify problem formulation and reduce the risk of errors, making it accessible to a broader audience.\n\n- **Domain-Specific Language (DSL)**: Introducing a dedicated DSL for specifying saddle problems, similar to disciplined convex programming (DCP) for convex problems, enhances usability. This approach abstracts away the complex mathematical steps involved in the dualization process.\n\n- **Applications in Diverse Fields**: By highlighting the applications of saddle problems in game theory, machine learning, and finance, the paper showcases the practical relevance of the proposed methodology. This adds value to researchers and practitioners in these areas.\n\n- **Open-Source Implementation**: The provision of an open-source implementation of DSP enhances reproducibility and allows other researchers to use and build upon the proposed approach.\n\n## Weaknesses:\n\n- **Scope of Implementation**: The paper briefly mentions implementing DSP as a Python package and using it in conjunction with CVXPY for convex optimization. However, the paper does not discuss potential limitations, challenges, or performance considerations associated with the implementation.\n\n- **Theoretical Foundations**: While the paper mentions the theoretical underpinnings of DSP and its extension from disciplined convex programming (DCP), it might be beneficial to provide more in-depth explanations of how the dualization process is automated using conic duality.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper titled \"Disciplined Saddle Programming\" introduces the concept of disciplined saddle programming (DSP), a domain-specific language (DSL) for specifying and solving saddle problems, which are convex-concave optimization problems arising in various fields like game theory, machine learning, and finance. The paper's primary contribution is the development of a methodology that automates the dualization trick, which converts saddle problems into standard convex optimization problems. DSP allows users to easily formulate and solve saddle problems, even without expertise in convex duality. The authors extend the idea of disciplined convex programming (DCP) to saddle problems and provide an open-source implementation of DSP.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Implementation Details**: Expand upon the implementation details of DSP. Discuss its limitations, challenges, and potential improvements. Provide examples of benchmarks or case studies showcasing the performance and efficiency of the DSP implementation in comparison to manual approaches.\n\n**Theoretical Background**: Expand Section 4 Disciplined saddle point programming. Elaborate on the theoretical foundations of DSP, specifically how the dualization process using conic duality is automated. This could involve providing illustrative examples or derivations to aid the reader's understanding.", "broader_impact_concerns": "no broader impact concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work provided an open source implementation of the methods in Juditsky and Nemiroski 2022, for solving certain saddle problems. One of the major contributions is the automation of the dualization process, making saddle problem formulation accessible to a broader audience who may not be familiar with the details of saddle point problems. The reviewers have generally praised the paper's clarity, usability, and practical relevance, highlighting its open source implementation. 

Reviewers have also raised a few concerns. Most concerns received responses; e.g., a few reviewers asked about the technical contribution, and the authors answered in one response that the implementation challenges include "hiding compactness requirements from users, obtaining both 
x and y portions of saddle points, and local variables". 
Reviewers are mostly happy about the responses, but also highlight the needed changes, including "adding clarity of the novel section + explain in detail the implementation challenges".

Besides, there is a general issue that may need to be addressed. In the response to each reviewer, the authors seem to only reply to "Requested Changes" but not "concerns" or "weakness" points. Anyhow, the reviewers do not object too much on the paper. I think this is partially because some are answered in the response to all reviewers, and some of the concerns are answered in other places. For instance, a few reviewers asked about the challenges in implemention, but only the questions that appear in "Requested Changes" received direct response, and the concerns in other places "(ii) The technical contribution of the work" (Reviewer MvoZ's comment) did not received direct reponse. That being said, I think a brief response to major concerns of each reviewer is needed, with possibly a pointer to the comments in other places. 

Summary: Before acceptance, the authors need to make the requested changes, especially those in the recommendation part of the reviewers, and let the reviewers know the changes. 
I would also suggest to add responses to the major concerns of each reviewer, so that future readers do not get confused on whether the concerns are addressed or not.
Decision: Accept (poster)