10
$\begingroup$

A function $f$ is said to be strongly convex with respect to a norm $\|\cdot\|_p$ if for all $x,y$, $$f(x) \geq f(y) + \nabla f(y)^T(x-y) + \frac{1}{2}\|x-y\|^2_p.$$

There are a bunch of functions used in machine learning, statistics, etc. that are extremely well known to be strongly convex with respect to the $2$ or $1$ norm

Examples:

$\sum_{j = 1}^m x_j^2$ is 2-strongly convex with respect to $\|\cdot\|_2$

$\sum_{j = 1}^m x_j \log(x_j) $ is 1-strongly convex with respect to $\|\cdot\|_1$

Does there exist any strongly convex function with respect to a norm $\|\cdot\|_p, p>2$?

$\endgroup$
7
  • $\begingroup$ Does $0 \geq \dfrac{1}{2} (\max_i |x_i - y_i| )^2$ hold for all $x,y \in \mathbb{R}$? $\endgroup$
    – Norman
    Jul 23, 2020 at 7:06
  • $\begingroup$ All norms are equivalent on $\mathbb R^m$, so a strongly convex function is strongly convex wrt any norm. $\endgroup$ Jul 23, 2020 at 7:11
  • 1
    $\begingroup$ @GabrielRomon I'm perplexed. A lot of efforts are put in to prove things are strongly convex wrt a certain norm. Such as the Pinsker's inequality. mltheory.github.io/CS7545/scribe/lec3.pdf $\endgroup$
    – Norman
    Jul 23, 2020 at 7:17
  • 1
    $\begingroup$ @GabrielRomon If I don't care, then what you say is 100% true, and any strongly convex function in one norm is strongly convex in another with a slightly adjusted factor. If I do care, then I'm stuck $\endgroup$
    – Norman
    Jul 23, 2020 at 7:23
  • 1
    $\begingroup$ A lot of optimization algorithms will require you to know or be able to estimate the strong convexity constant to determine things like step size. You probably care. $\endgroup$ Jul 23, 2020 at 7:26

1 Answer 1

3
$\begingroup$

It depends on what you mean by that. In finite dimensional spaces, as other people noted, all norms are equivalent. However, the constants relating them can scale with the dimension.

If you are interested in functions that would have a strong convexity constant that is independent of the dimension (while having dimension independent divergence on sets of dimension-independent diameters), then no such function exists for $p > 2.$ For proof, see Example 4.1 in https://arxiv.org/pdf/1301.0465.pdf.

$\endgroup$

You must log in to answer this question.

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