3
$\begingroup$

Let $F\subset \mathbb{R}^n$ be a finite set and $\sigma$ be uniformly distributed over $\{-1,1\}^n$. The usual Rademacher average of $F$ (modulo normalizing factors) is $$ R_n(F)=\mathbb{E}_\sigma \max_{f\in F}\sum_{i=1}^n \sigma_if_i. $$ Now let us define two operations on $F$: $\mathrm{conv}(F)$ and $[F]_\vee$. The former is just the convex hull of the vector-set $F$ in $\mathbb{R}^n$. The latter is defined by $$ [F]_\vee=\{ f\vee g :f,g \in F\}, $$ where $(f\vee g)_i=\max\{f_i,g_i\}$ is the coordinate-wise maximum. It is well-known (and easy to show) that $ R_n( \mathrm{conv}(F)) = R_n( F) $.

Question: is it true that $$ R_n( [\mathrm{conv}(F)]_\vee) = R_n( [F]_\vee) $$ ?

The inequality $ R_n( [F]_\vee) \le R_n( [\mathrm{conv}(F)]_\vee) $ holds due to set containment. Also, $\mathrm{conv}(F)$ is an infinite set, so the $\max$ in the definition should be replaced by a $\sup$.

Update. Fedor Petrov has constructed a counterexample, which I've accepted. The more general conjecture I had was as follows. Define the $k$-fold max operator $[F]_k$ by $$ [F]_k=\{ f_1\vee f_2\ldots\vee f_k :f_i \in F\}. $$ Is there a universal constant $c$ (independent of $n$ and $k$) such that $$ R_n( [\mathrm{conv}(F)]_k) \le c R_n( [F]_k) $$?

$\endgroup$
  • $\begingroup$ But $[\mathrm{conv}(F)]_\vee$ is not already a finite set? And it looks that the maximum over a subset may be only less than a maximum over a large set, so the opposite inequality should take place. $\endgroup$ – Fedor Petrov Apr 30 at 19:53
  • $\begingroup$ @FedorPetrov Please see edits. $\endgroup$ – Aryeh Kontorovich Apr 30 at 20:58
  • $\begingroup$ so your question is equivalent to "is it true that $R_n( [\mathrm{conv}(F)]_\vee)=R_n( [F]_\vee)$"? $\endgroup$ – Fedor Petrov Apr 30 at 21:02
  • $\begingroup$ yes, I edited again $\endgroup$ – Aryeh Kontorovich Apr 30 at 21:11
3
$\begingroup$

It looks that no. Take $n=4$ and $F$ containing four vectors: $f=(2,-2,1,-5); g=(-2,2,1,-5); h=(0,0,-5,1)$. We have $f\vee g=(2,2,1,-5)$, $f\vee h=(2,0,1,1)$, $g\vee h=(0,2,1,1)$. Thus $\max_{w\in [F]_\vee} (w_3+w_4-w_1-w_2)=0$. On the other hand $\frac{f+g}2\vee h=(0,0,1,1)$, therefore $\max_{w\in [\mathrm{conv}(F)]_\vee} (w_3+w_4-w_1-w_2)\geqslant 2$.

$\endgroup$
  • $\begingroup$ Your example appears to work, but I think an additional calculation is needed. $F$ only contains the 3 vectors $f,g,h$, yes? Your calculation shows supremacy for a given choice of $\sigma$, not for the average over $\sigma$. I performed the calculation, though, and there's a gap, so the example seems valid. $\endgroup$ – Aryeh Kontorovich May 1 at 14:40
  • $\begingroup$ The values that I get for the two Rademacher averages are 100 and 102, respectively -- not very large. $\endgroup$ – Aryeh Kontorovich May 1 at 14:49
  • $\begingroup$ But for any $\sigma$ we have an inequality (may be non strict) in the same direction. Thus equality could only appear if all of them turn into equalities, right? $\endgroup$ – Fedor Petrov May 1 at 15:22
  • $\begingroup$ Yes, point taken. So the question is, how much of a (multiplicative) gap can you force for a single $\sigma$? For what fraction of the $\sigma$'s? I've expanded the conjecture in case this challenge appeals to you :) $\endgroup$ – Aryeh Kontorovich May 1 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.