1
$\begingroup$

Suppose we have two convex sets $A,B$. It is straightforward to show the sum $A+B = \{a+b:a \in A,b\in B\}$ is convex. For take any $c=a+b$ and $c'=a'+b'$ and consider the convex combination

$$xc+(1-x)c' = x(a+b)+(1-x)(a'+b')$$ $$= \big(xa+(1-x)a'\big) + \big( xb+(1-x)b'\big).$$

By convexity the two summand are in $A,B$ respectively. Hence the sum is in $A+B$ as required.

Now suppose $A$ is $\alpha$-strongly convex and $B$ is $\beta$-strongly convex. That means the for each $a,a' \in A$ and $x \in [0,1]$ that the ball centred at $xa+(1-x)a'$ of radius $\alpha x(1-x)$ is contained in $A$. Likewise for each $b,b' \in B$ and $x \in [0,1]$ that the ball centred at $xb+(1-x)b'$ of radius $\beta x(1-x)$ is contained in $B$.

Can we say anything about the strong-convexity parameter of $A+B$? By that I mean $\inf\{ \gamma \ge 0: A+B$ is $\gamma$-strongly convex $\}$.

$\endgroup$
5
  • $\begingroup$ Are you supposing that $\alpha$ and $\beta$ are also "sharp" in the sense that they're the smallest possible strong convexity constant with respect to $A$ and $B$? $\endgroup$
    – Zim
    Jul 28, 2020 at 16:11
  • $\begingroup$ @Zim Oh yeah we'd have to assume that to say anything about the inf for $A+B$. But even lower bounds for $A+B$ would be nice. $\endgroup$
    – Daron
    Jul 28, 2020 at 16:19
  • $\begingroup$ Wait, isn't the "sharpest" strong convexity constant the largest one? If $\gamma_1<\gamma_2$, then the ball of radius $\gamma_1$ is contained in the ball of radius $\gamma_2$, so if $C$ is $\gamma_2$ strongly convex, then it must be $\gamma_1$ strongly convex. $\endgroup$
    – Zim
    Jul 28, 2020 at 17:29
  • $\begingroup$ @Zim Yes you're right. We should be talking about the sup and not the inf. $\endgroup$
    – Daron
    Jul 28, 2020 at 17:55
  • $\begingroup$ great, well I think $\max\{\alpha,\beta\}$ might be the best we can do (see answer below). $\endgroup$
    – Zim
    Jul 29, 2020 at 15:53

1 Answer 1

1
$\begingroup$

I'm going for the largest strong convexity constant, since any smaller value also works.

If $A$ is $\alpha$-strongly convex and $B$ is $\beta$-strongly convex, then $A+B$ is $\gamma:=\max\{\alpha,\beta\}$-strongly convex.

Proof: Let $a_1,a_2\in A$, let $b_1,b_2\in B$, and let $\eta\in[0,1]$. For notational simplicity, I will set $a:=\eta a_1+(1-\eta)a_2$ and $b:=\eta b_1+(1-\eta)b_2$. Now suppose that $z$ is in the ball centered at $\eta(a_1+b_1) + (1-\eta)(a_2+b_2)=a+b$ with radius $\eta(1-\eta)\gamma$. It suffices to show that $z\in A+B$. By the construction of $\gamma$ and definition of $z$, either

\begin{equation} \|a+b-z\|=\|a - \left(z - b\right)\| \leq \eta(1-\eta)\gamma=\eta(1-\eta)\max\{\alpha,\beta\} =\eta(1-\eta)\alpha, \tag{1} \end{equation} or, \begin{equation} \|a+b-z\|=\|b - \left(z - a\right)\|\leq \eta(1-\eta)\beta. \tag{2} \end{equation}

If (1) holds, then $z-b$ is in the ball centered at $a$ with the proper radius. Since $A$ is strongly convex, this implies $z-b\in A$ and hence $z\in A+b\subset A+B$. Likewise, if (2) holds, then $z-a$ is in the ball centered at $b$ with the proper radius. Since $B$ is strongly convex, we find $z-a\in B$ and hence $z\in B+a\subset A+B$.

$\endgroup$

You must log in to answer this question.

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