3
$\begingroup$

I'm attempting to follow a proof in a paper. In the proof, the authors make use of what I believe is the min-max inequality and exploit strong duality, but I'm unsure of the steps that are glossed over. Specifically, how do the authors get from the second to third equality in the equations repeated below?

I am aware of the min-max inequality in the context of the Lagrangian, but I don't know how it used below. Classically for the Lagrangian, we are minimizing over the decision variables, $\mathbf{x}$, and maximizing over $\mathbf{\lambda}$, but in the equation below $\mathbf{z}$ are the decision variables, and we seem to be maximizing over them, so I'm a bit confused.

For clarity, Equation 3.15 that is referenced in the equations below is simply the definition of a convex conjugate, and $h(\mathbf{z})$ is assumed to be a convex function. Additionally, $\lVert \, \cdot \, \rVert$ is some norm, $\lVert \, \cdot \, \rVert_\ast$ is the corresponding dual norm, and $^\prime$ denotes transpose.

Thank you for any and all help.

Reference to paper (pg. 60):

Ruidi Chen and Ioannis Ch. Paschalidis (2020), “Distributionally Robust Learning”, : Vol. 4, No. 1–2, pp 1–243. DOI: 10.1561/2400000026


$$ \sup_{\mathbb{Q}\in \Omega} \mathbb{E}_{\mathbb{Q}}\left[ h(\mathbf{z})\right] = \min_{\lambda \geq 0} \left\{ \lambda \epsilon + \frac{1}{N} \sum_{i=1}^N \sup_{\mathbf{z} \in \mathcal{Z}} \left[h(\mathbf{z}) -\lambda\lVert\mathbf{z}-\mathbf{z}_i \rVert\right] \right\} \tag{3.17} $$

Using (3.15), we may write the inner maximization in (3.17), as: $$ \begin{aligned}\sup_{\mathbf{z} \in \mathcal{Z}} \left[h(\mathbf{z}) -\lambda\lVert\mathbf{z}-\mathbf{z}_i \rVert\right] &= \sup_{\mathbf{z} \in \mathcal{Z}}\sup_{\mathbf{\theta}\in\mathbf{\Theta}} \left[ \mathbf{\theta}^\prime \mathbf{z} - h^\ast(\mathbf{\theta}) - \lambda\lVert \mathbf{z} - \mathbf{z}_i\rVert \right]\\ &= \sup_{\mathbf{z} \in \mathcal{Z}}\sup_{\mathbf{\theta}\in\mathbf{\Theta}} \inf_{\lVert\mathbf{r} \rVert_\ast \leq \lambda} \left[ \mathbf{\theta}^\prime \mathbf{z} - h^\ast(\mathbf{\theta}) + \mathbf{r}^\prime(\mathbf{z}-\mathbf{z}_i) \right]\\ &= \sup_{\mathbf{\theta}\in\mathbf{\Theta}} \inf_{\lVert\mathbf{r} \rVert_\ast \leq \lambda}\sup_{\mathbf{z} \in \mathcal{Z}} \left[ (\mathbf{\theta} + \mathbf{r})^\prime \mathbf{z} - h^\ast(\mathbf{\theta}) - \mathbf{r}^\prime\mathbf{z}_i \right] \\ &\leq \sup_{\mathbf{\theta}\in\mathbf{\Theta}} \inf_{\lVert\mathbf{r} \rVert_\ast \leq \lambda}\sup_{\mathbf{z} \in \mathbb{R}^d} \left[ (\mathbf{\theta} + \mathbf{r})^\prime \mathbf{z} - h^\ast(\mathbf{\theta}) - \mathbf{r}^\prime\mathbf{z}_i \right] \end{aligned} $$ where the second equality follows from the definition of the dual norm and the third equality uses duality. The inner maximization over $\mathbf{z}\in\mathbb{R}^d$ achieves $\infty$ unless $\mathbf{r} = -\mathbf{\theta}$.

$\endgroup$
7
  • $\begingroup$ "Distributionally robust learning" - that sounds interesting. Also, please use Mathjax instead of copy-pasting an image of the passage. $\endgroup$
    – Galen
    Commented Dec 14, 2023 at 17:14
  • $\begingroup$ It is a very interesting concept/field! It seems one would need all of the screen shot to understand the question. Should I rewrite the passage in Mathjax? I thought it would be easier to just screen shot, as the screen shot is self-contained and fairly clear. Thank you! :) $\endgroup$
    – jmd
    Commented Dec 14, 2023 at 17:16
  • $\begingroup$ I can appreciate that copy-pasting is faster. It is preferred if you would provide it in Mathjax in this instance and in the future. It is recommended as a general practice because images take up more server space dedicated to the site. It also makes the content searchable using the both the site's search engine and the SQL database API. $\endgroup$
    – Galen
    Commented Dec 14, 2023 at 17:20
  • $\begingroup$ Did you mean how do the authors get from second to third equality? Did not read the paper but I believe it is because strong duality holds, since the problem is convex and Slater's condition holds. The last inequality is simply because $\mathcal{Z}\subseteq \mathbb{R}^d$. $\endgroup$
    – V.S.e.H.
    Commented Dec 14, 2023 at 19:50
  • $\begingroup$ Hi @V.S.e.H.: Yes, I certainly meant equality. I'll adjust that now. In an answer or a comment, could you please go step-by-step with your assumptions and the logical progression ? $\endgroup$
    – jmd
    Commented Dec 15, 2023 at 0:21

1 Answer 1

1
$\begingroup$

The min-max theorem has a general form which is independent of the concept of the Lagrangian. You can use it for any function, and you get the inequality. If you want equality (what you do not need now actually), you can also consider a minimax theorem without mentioning the Lagrangian. As minimax theorems are derived from duality theory, the authors of your book might have referred to this in their comment in the proof.

I recommend the book of Convex Analysis by Tyrrell Rockafellar to learn about duality theory and how it is used to derive minimax theorems, there is really a lot in this book on the topic. For the actual case, we can use the following minimax theorem (Corollary 37.3.2):

Let $C$ and $D$ be non-empty closed convex sets in $R^m$ and $R^n$, respectively, and let $K$ be a continuous finite concave-convex function on $C \times D$. If either $C$ or $D$ is bounded, one has $sup_{u\in C}\inf_{v\in D} K(u,v) = \inf_{v\in D}\sup_{u\in C}K(u,v)$.

So in your case, $\mathcal{Z}$ is a closed convex set (what you forgot to mention), so you can define $K_\mathbf{\theta}(\mathbf{z},\mathbf{r}) = \theta'\mathbf{z} - h^*(\theta) + r'(\mathbf{z}-\mathbf{z}_i)$ on the domain $C \times D$ with $C = \mathcal{Z}$ and $D = \{\mathbf{r} : \|\mathbf{r}\|_* \le \lambda\}$, and apply the above minimax theorem because $K$ is linear in both of its variables (so it is concave-convex), and $D$ is bounded (and closed convex): $$ \sup_{\mathbf{z}\in\mathcal{Z}}\sup_{\theta\in\Theta}\inf_{\|\mathbf{r}\|_*\le \lambda} K_\theta(\mathbf{r},\mathbf{z}) = \sup_{\theta\in\Theta}\sup_{\mathbf{z}\in\mathcal{Z}}\inf_{\|\mathbf{r}\|_*\le \lambda} K_\theta(\mathbf{r},\mathbf{z}) = \sup_{\theta\in\Theta}\inf_{\|\mathbf{r}\|_*\le \lambda}\sup_{\mathbf{z}\in\mathcal{Z}} K_\theta(\mathbf{r},\mathbf{z}) . $$

$\endgroup$
7
  • $\begingroup$ So for this problem, you would say: define some function $g(\mathbf{z}, \mathbf{r}; \mathbf{\theta})\triangleq \mathbf{\theta}^\prime \mathbf{z} - h^\ast(\mathbf{\theta}) + \mathbf{r}^\prime(\mathbf{z}-\mathbf{z}_i)$. $\endgroup$
    – jmd
    Commented Dec 23, 2023 at 22:51
  • $\begingroup$ Since $g(\cdot, \mathbf{r}; \mathbf{\theta})$ is concave for fixed $\mathbf{r}$ (as it is affine) and $g(\mathbf{z}, \cdot; \mathbf{\theta})$ is convex for fixed $\mathbf{z}$ (as it is also affine), then $\sup_{\mathbf{z} \in \mathcal{Z}}\sup_{\mathbf{\theta}\in\mathbf{\Theta}} \inf_{\lVert\mathbf{r} \rVert_\ast \leq \lambda} g(\mathbf{z}, \mathbf{r}; \mathbf{\theta}) = \sup_{\mathbf{\theta}\in\mathbf{\Theta}} \inf_{\lVert\mathbf{r} \rVert_\ast \leq \lambda} \sup_{\mathbf{z} \in \mathcal{Z}} g(\mathbf{z}, \mathbf{r}; \mathbf{\theta}) $? $\endgroup$
    – jmd
    Commented Dec 23, 2023 at 22:52
  • $\begingroup$ And as you mentioned, the "duality" that the authors mention comes from thinking of $g(\mathbf{z}, \mathbf{r}; \mathbf{\theta})$ as the Lagrangian for some optimization problem (but this is not explicitly needed)? I understand completely the rationale. I am just confused about how to handle the $\sup_{\mathbf{\theta} \in \mathbf{\Theta}} \left( \cdots \right)$. $\endgroup$
    – jmd
    Commented Dec 23, 2023 at 22:54
  • $\begingroup$ Yes, as the $\mathcal{Z}$ and $\Theta$ sets are unrelated, you simply change the order of the supremums of $z$ and $\theta$ and treat $\theta$ as constant when applying the minimax theorem. You can emphasize this by writing $g_{\theta}(z,r)$. It is also important that the supremum over $z$ and the infimum over $r$ take place over convex sets. $\endgroup$
    – gabalz
    Commented Dec 24, 2023 at 9:05
  • 1
    $\begingroup$ Actually, you need compact convex sets for the minimax theorem, and as I just see your $\mathcal{Z}$ can be unbounded (it is assumed to be closed and convex only). So maybe you indeed need a more specialized duality result to get the equality which exploits the linearity in $z$. The inequality by the min-max theorem works without any of this hassle. $\endgroup$
    – gabalz
    Commented Dec 24, 2023 at 10:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .