Автоматика и телемеханика, № 10, 2019

(Магдебургский университет, Германия),

О. КОЛЬЕ, д-р (olivier.collier@u-paris10.fr)

(Modal’X, Университет Париж-Нантер и CREST, Франция),

Л. КОМЕНЖ, д-р (comminges@ceremade.dauphine.fr)

(CEREMADE, Университет Париж-Дофин и CREST, Франция),

А.Б. ЦЫБАКОВ, д-р физ.-мат. наук (alexandre.tsybakov@ensae.fr)

(CREST, ENSAE, Париж, Франция),

Ю. ВАНГ (yuhaow@mit.edu)

(LIDS-IDSS, MIT, Кембридж, Массачусетс, США)

МИНИМАКСНАЯ ТОЧНОСТЬ ПРОВЕРКИ ГИПОТЕЗ В

РАЗРЕЖЕННОЙ ЛИНЕЙНОЙ РЕГРЕССИИ¹

Рассматривается задача проверки гипотезы о том, что параметр моде-

ли линейной регрессии равен нулю против s-разреженной альтернативы,

отделенной от нуля в ℓ₂-расстоянии. Показывается, что в модели гауссов-

ской линейной регрессии с p < n, где p — размерность параметра, а n —

размер вы√рки, неасимптотическая минимаксная скорость тестирования

имеет вид

(s/n) log(1 +

√p/s). Также показывается, что это минимакс-

ная скорость оценивания ℓ₂-нормы параметра регрессии.

Ключевые слова: линейная регрессия, разреженность, обнаружение сиг-

нала.

DOI: 10.1134/S0005231019100040

1. Введение

Настоящая работа посвящена задаче проверки гипотез о параметре моде-

ли линейной регрессии при разреженных альтернативах. Эта задача имеет

различные приложения в генетике, передаче и обнаружении сигналов, сжа-

тии данных. Подробное описание этих приложений можно найти, например,

в [6]. Важную роль играет поиск оптимальных методов проверки таких ги-

потез, причем один из естественных подходов состоит в том, чтобы понятие

оптимальности определять в минимаксном смысле. Минимаксная постанов-

ка задачи проверки гипотез при разреженных альтернативах была впервые

изучена в [1, 2], где рассматривалась модель гауссовской последовательности.

В этих работах применялся асимптотический подход в предположении, что

¹ Работа А. Карпантье поддержана грантами Emmy Noether grant MuSyAD CA 1488/1-1,

GK 2297 MathCoRe on Mathematical Complexity Reduction 314838170, GRK 2297 MathCoRe,

SFB 1294 Data Assimilation “The seamless integration of data and models”, Project A03, фи-

нансируемыми фондом Deutsche Foschungsgemeinschaft (DFG) и французско-немецким уни-

верситетом в рамках программы докторского колледжа Потсдам-Тулуза CDFA 01-18. Ра-

бота О. Колье выполнена в рамках проекта Labex MME-DII (ANR11-LBX-0023-01). Рабо-

та А.Б. Цыбакова поддержана институтом GENES и грантами IPANEMA (ANR-13-BSH1-

0004-02) и Labex Ecodec (ANR-11-LABEX-0047).

индекс разреженности зависит от размерности степенным образом. Неасимп-

тотическая постановка для модели гауссовской последовательности была рас-

смотрена в [3], где границы для минимаксной скорости тестирования были

установлены с точностью до логарифмического множителя. Наконец, точная

неасимптотическая минимаксная скорость тестирования для модели гауссов-

ской последовательности была получена в [4]. В настоящей работе результа-

ты [4] обобщаются на линейную регрессионную модель с гауссовским шумом.

Заметим, что задача минимаксного тестирования для линейной регрессии при

разреженных альтернативах уже изучалась в [5-7]. А именно, в [5, 6] рассмат-

ривалась асимптотическая постановка при дополнительных предположениях

о параметрах задачи, а в [7] были установлены неасимптотические границы

с точностью до логарифмического множителя, аналогичные [3]. Цель данной

работы состоит в том, чтобы найти неасимптотическую минимаксную ско-

рость тестирования в модели гауссовской линейной регрессии без каких-либо

специфических предположений о параметрах задачи. Здесь дается ответ на

этот вопрос в случае, когда p < n, где p — размерность, а n — размер выборки.

Рассмотрим модель

(1)

Y =Xθ+σξ,

где σ > 0, ξ ∈ Rⁿ — векторный гауссовский белый шум, т.е. ξ ∼ N (0, I_n), I_n —

единичная матрица размера n×n, X — матрица размера n×p со случайными

элементами и θ ∈ R^p — неизвестный параметр. Далее везде предполагается,

что X не зависит от ξ.

Ниже будут использованы следующие обозначения. Для u = (u₁, . . . , u_p) ∈

∈ R^p через ∥ · ∥₂ обозначим ℓ₂-норму, т.е.

∑

∥u∥²² =

u2i,

i=1

и пусть ∥ · ∥₀ обозначает ℓ₀-полунорму, т.е.

∑

∥u∥₀ =

1{ui=0},

i=1

где 1{·} — индикаторная функция. Обозначим через 〈u, v〉 = uTv скаляр-

ное произведение векторов u ∈ R^p и v ∈ R^p, а через λ_min(M) и tr[M] ми-

нимальное собственное значение и след матрицы M ∈ R^p×p. Для целого

s ∈ {1,...,p} рассмотрим множество B₀(s) всех s-разреженных векторов в

пространстве R^p:

B₀(s) := {u ∈ R^p : ∥u∥₀ ≤ s}.

Рассмотрим следующую задачу проверки гипотез по наблюдениям (X, Y ):

(2)

H₀ : θ = 0 против альтернативы H₁

: θ ∈ Θ(s,τ),

где

Θ(s, τ) = {θ ∈ B₀(s) : ∥θ∥₂ ≥ τ}

для некоторых s ∈ {1, . . . , p} и τ > 0. Пусть Δ = Δ(X, Y ) — статистика со

значениями в {0, 1}. Определим риск теста, основанного на Δ, как сумму

ошибки первого рода и максимальной ошибки второго рода:

P₀(Δ = 1) + sup P_θ(Δ = 0),

θ∈Θ(s,τ)

где P_θ обозначает совместное распределение пары (X, Y ), удовлетворяю-

щей (1). Наименьшее возможное значение этого риска равно минимаксному

риску

{

}

R_s,τ := inf

P₀(Δ = 1) + sup P_θ(Δ = 0)

θ∈Θ(s,τ)

где нижняя грань inf берется по всем {0, 1}-значным статистикам Δ. Опре-

делим минимаксную скорость тестирования для класса B₀(s) относительно

ℓ₂-расстояния как значение λ > 0, для которого выполняются следующие два

свойства:

(i) (верхняя граница) для любого ε ∈ (0, 1) существует A_ε > 0, не зависящее

от p, n, s, σ, такое что для всех A > A_ε

(3)

R_s,Aλ

≤ ε,

(ii) (нижняя граница) для любого ε ∈ (0, 1) существует a_ε > 0, не зависящее

от p, n, s, σ, такое что для всех 0 < A < a_ε

(4)

R_s,Aλ

≥ 1 - ε.

Заметим, что определенная таким образом скорость λ неасимптотическая, и

поэтому данное определение отличается от классического асимптотическо-

го определения минимаксной скорости тестирования, которое можно найти,

например, в [8]. В [4] показано, что когда X — единичная матрица и p = n

(что соответствует модели гауссовской последовательности), неасимптотиче-

ская минимаксная скорость тестирования на классе B₀(s) по отношению к

ℓ₂-расстоянию имеет следующий вид:

{

√

s log(1 + p/s²), если s <

√p,

(5)

λ=

σp1/4,

если s ≥

√p.

Для модели регрессии со случайным X, удовлетворяющей некоторым силь-

ным предположениям, асимптотическая минимаксная скорость тестирования

при n, p и s стремящимся к ∞ так, что s = p^a для некоторого 0 < a < 1, изуче-

на в [5]. В частности, в [5] показано, что для этой конфигурации параметров

и при условии, что матрица X имеет независимые одинаково распределен-

ные (н.о.р.) стандартные нормальные компоненты, асимптотическая скорость

имеет вид

(√

)

1/4

s log(p)

(6)

λ = σ min

,n-1/4,

√n

Аналогичный результат для несколько иначе определенной альтернативы H₁

получен в [6].

Ниже будет показано, что без каких-либо специфических ограничений на

параметры n, p и s неасимптотическая нижняя граница для минимаксной

скорости тестирования имеет вид

(√

)

1/4

s log(2 + p/s²)

(7)

λ = σ min

,n-1/4,

√n

какова бы ни была матрица X с изотропным распределением и независимы-

ми субгауссовскими элементами (определения изотропности и субгауссовости

распределения даны в разделе 3). Кроме того, будет показано, что верхняя

граница совпадает по порядку с нижней в случае, когда X — матрица с н.о.р.

стандартными гауссовскими элементами и p < n. Заметим, что при p < n вы-

ражение (7) принимает вид

(√

)

1/4

s log(2 + p/s²)

(8)

λ = σ min

√n

Также полезно отметить, что, поскольку для s ≤

√p функция s → s log(2 +

+p/s²) возрастает и удовлетворяет неравенству log(2+p/s²) ≤ 2log(1+p/s²),

скорость (8) можно эквивалентным образом (с точностью до числового по-

стоянного множителя) записать в виде

⎧

√

⎪

s log(1 + p/s²)

⎨

, если s <

√p,

(9)

λ=⎪

⎪

p1/4

⎩ σ

если s ≥

√p.

√n,

Это выражение аналогично (5). Наконец, заметим, что скорость может быть

записана в следующей более компактной форме:

(√

)

√

1/4

s log(2 + p/s²)

s log(1 +

√p/s)

(10)

σ min

≍σ

√n

где ≍ обозначает эквивалентность с точностью до числового постоянного мно-

жителя.

2. Верхние границы для минимаксных скоростей

В этом разделе предполагается, что p < n и X — матрица с н.о.р. стандарт-

ными гауссовскими элементами, и устанавливается верхняя граница (9) для

минимаксной скорости тестирования. Для этого используется связь между

проверкой гипотез и оценкой функционалов. Сначала будет введена оцен-

ка^Q квадратичного функционала ∥θ∥²² и установлена верхняя граница для

его риска. Затем из этого результата будет выведена верхняя граница для

риска оценки^N нормы ∥θ∥₂, определяемой следующим образом:

√

N=max( Q,0).

Наконец, используя

N как статистику критерия, получим верхнюю оценку

минимаксной скорости тестирования.

Введем обозначение

(

)

α_s = E

Z²|Z² > 2log(1 + p/s²)

где Z — стандартная нормальная величина, и положим

{

}

y_i =

(X^TX)-1X^TY

где

{(X^TX)-1X^TY }_i

— i-я компонента оценки наименьших квадратов

(X^TX)-1X^TY . Заметим, что обратная матрица (X^TX)-1 существует почти

наверное, так как в этом разделе предполагается, что X является матрицей

с н.о.р. стандартными гауссовскими элементами и p < n, так что X почти

наверное имеет полный ранг. Рассмотрим следующую оценку квадратичного

функционала ∥θ∥²² :

⎧

⎪

∑

⎪

y2i - σ²tr[(X^TX)-1],

если s ≥

√p,

⎨

i=1

Q :=

⎪

∑

[

]

⎪

⎩

y2i - σ²(X^TX)-1iiα_s

1_{y2

√p.

>2σ²(X^TX)-1ii log(1+p/s²)},еслиs<

i=1

Здесь и далее (X^TX)-1ij обозначает (i, j)-й элемент матрицы (X^TX)-1.

Для любых целых чисел n, p, s таких, что s ≤ p, положим

⎧

⎪s log(1 + p/s2)

⎨

, если s <

√p,

ψ(s, p) =

⎪

1/2

⎩^p

если s ≥

√p.

Теорема 1. Пусть n,p,s — целые числа такие, что s ≤ p, n ≥ 9 и

p ≤ min(γn,n - 8) для некоторой константы 0 < γ < 1. Пусть r > 0, σ > 0.

Предположим, что все элементы матрицы X — н.о.р. стандартные гаус-

совские случайные величины. Тогда существует константа c > 0, завися-

щая только от γ, такая что

(

)

[

]

r²

sup

E_θ

(Q - ∥θ∥²²)2 ≤c σ2

+ σ⁴ψ²(s,p)

θ:∥θ∥₀≤s,∥θ∥₂≤r

Доказательство теоремы 1 дано в Приложении.

Рассуждая точно так же, как в доказательстве теоремы 8 в [4], из теоре-

мы 1 выводим следующую верхнюю оценку квадратичного риска оценки^N.

Теорема 2. Пусть выполнены условия теоремы 1. Тогда существует

константа c^′ > 0, зависящая только от γ, такая что

[

]

sup E_θ

N - ∥θ∥₂)2

≤ c^′σ²ψ(s,p).

θ∈B₀(s)

√

Из теоремы 2 следует, что для теста Δ^∗ = 1{ˆN>Aλ/2}, где λ = σ

ψ(s, p)

(т.е. то же значение λ, что и в (9)), справедливы неравенства

P₀(Δ^∗ = 1) + sup P_θ(Δ^∗ = 0) ≤

θ∈Θ(s,Aλ)

≤P₀

N >Aλ/2)+ sup P_θ

N - ∥θ∥₂ ≤ -Aλ/2) ≤

θ∈B₀(s)

E_θ[

N - ∥θ∥₂)²]

≤2

sup

≤C_∗A-2,

θ∈B₀(s)

(A/2)²λ²

где C_∗ > 0 — некоторая константа. Используя это замечание и выбирая A_ε =

= (C_∗/ε)1/2, получаем верхнюю оценку (i), определенную в предыдущем раз-

деле. Этот вывод сформулирован в следующей теореме.

Теорема 3. Пусть выполнены условия теоремы 1 и пусть λ определя-

ется через (9). Тогда для любого ε ∈ (0,1) существует A_ε > 0, зависящее

только от ε и γ, такое что

R_s,Aλ ≤ ε

для всех A > A_ε.

3. Нижние границы для минимаксных скоростей

В этом разделе предполагается, что распределение матрицы X изотроп-

но и имеет независимые σ_X -субгауссовские строки для некоторого σ_X > 0.

Изотропия X означает, что E_X (X^TX/n) = I_p, где E_X обозначает математи-

ческое ожидание по распределению P_X матрицы X.

Определение 1. Пусть b > 0. Вещественнозначная случайная величи-

на ζ называется b-субгауссовской, если

E exp(tζ) ≤ exp(b²t²/2),

∀t ∈ R.

Случайный вектор η со значениями в R^d называется b-субгауссовским, если

все скалярные произведения 〈η, v〉 с векторами v ∈ R^d, такими что ∥v∥₂ = 1,

являются b-субгауссовскими случайными величинами.

Следующая теорема о нижней границе является неасимптотической и она

справедлива без ограничений на параметры n, p, s за исключением неизбеж-

ного условия s ≤ p.

Теорема 4. Пусть ε ∈ (0,1), σ > 0 и пусть целые n,p,s таковы, что

s ≤ p. Предположим, что распределение матрицы X изотропно и X имеет

независимые σ_X-субгауссовские строки при некотором σ_X > 0. Тогда суще-

ствует a_ε > 0, зависящее только от ε, и σ_X, такое что для

(√

)

1/4

s log(2 + p/s²)

(11)

τ = Aσmin

,n-1/4,

√n

с произвольным A, удовлетворяющим 0 < A < a_ε, имеем

R_s,τ ≥ 1 - ε.

Доказательство теоремы 4 дано в Приложении.

Следующий результат является непосредственным следствием теорем 3

и 4.

Следствие 1. Пусть выполнены условия теоремы 1. Тогда минимакс-

ная скорость тестирования на классе B₀(s) по отношению к ℓ₂-расстоянию

задается через (8).

Кроме того, из теоремы 4 получаем следующую нижнюю границу мини-

максного риска оценки ℓ₂-нормы ∥θ∥₂.

Теорема 5. Пусть выполнены условия теоремы 4 и пусть λ определено

в (7). Тогда существует константа c_∗ > 0, зависящая только от σ_X , такая

что

[

]

inf sup E_θ

T - ∥θ∥₂)2

≥c_∗λ²,

T θ∈B₀(s)

где infˆT обозначает инфимум по всем оценкам.

Результат теоремы 5 вытекает из теоремы 4, если заметить, что для τ в (11)

иλв(7) имеем τ =Aλидля любой оценк

T справедливы неравенства

[

]

[

]

[

]

sup

E_θ

T - ∥θ∥₂)2 ≥

E₀

T²] + sup Eθ

T - ∥θ∥₂)2

≥

θ∈B₀(s)

θ∈Θ(s,τ)

[

]

≥

P₀

T >τ/2)+ sup P_θ

T ≤ τ/2)

≥

θ∈Θ(s,τ)

(Aλ)

≥

R_s,τ.

Следствие 2. Пусть выполнены условия теоремы 1 и пусть λ опреде-

лено в (8). Тогда минимаксная скорость оценки нормы ∥θ∥₂ относительно

среднеквадратичного риска для класса B₀(s) равна λ², т.е.

[

]

c_∗λ² ≤ inf sup E_θ

T - ∥θ∥₂)2

≤c^′λ²,

T θ∈B₀(s)

где c_∗ > 0 — числовая константа, а c^′ > 0 — константа, зависящая только

от γ.

Это утверждение является непосредственным следствием теорем 2 и 5.

Замечание 1. Из доказательств, приведенных в Приложении, видно,

что результаты этого раздела остаются в силе, если заменить везде ℓ₀-шар

B₀(s) на ℓ₀-сферуB0(s) = {u ∈ R^p : ∥u∥₀ = s}.

ПРИЛОЖЕНИЕ

П.1. Вспомогательные леммы для доказательства теоремы 1

Приведем два основных вспомогательных результата, используемых в до-

казательстве теоремы 1. Первый из них позволяет оценить математическое

ожидание от отрицательных степеней минимального собственного значения

эмпирической матрицы ковариаций. Второй используется при оценке ошибки

идентификации ненулевых компонент в разреженной постановке. Для этого

нужны точные границы для корреляций между урезанными вариантами двух

центрированных коррелированных случайных величин с распределением χ²¹.

Напомним сначала два общих факта, которые будут использоваться для по-

лучения первого результата.

В дальнейшем будем обозначать одним и тем же символом C различные

положительные константы, встречающиеся в выкладках.

Лемма 1 ([9], см. также [10]). Пусть матрица X удовлетворяет усло-

виям теоремы 1 и пусть λ_min(Σ) — наименьшее собственное значение вы-

борочной ковариационной матрицыΣ =1nX^TX. Тогда для любого t > 0 с ве-

роятностью не менее 1 - 2exp(-t²/2) имеем

√

^√p

√n≤λmin(Σ)≤1+

√n.

Лемма 2 ([11, лемма A4], см. также [12, лемма 4.14]). Пусть 1 ≤ p ≤ n.

Пусть R_i — i-й столбец матрицы X ∈ R^n×p и R_-i — линейная оболочка

векторов {R_j : j = i}. Если X — матрица полного ранга, то

(X^TX)-1ii = dist(R_i, R_-i)-2,

где dist(R_i, R_-i) — евклидово расстояние вектора R_i до пространства R_-i.

Лемма 3. Пусть n ≥ 9 и p ≤ min(γn,n - 8) для некоторой постоян-

ной γ такой, что 0 < γ < 1. Предположим, что все компоненты матри-

цы X ∈ R^n×p — н.о.р. стандартные гауссовские случайные величины. Тогда

существует константа c > 0, зависящая только от γ, такая что

[

]

(Π.1)

E λ-2min(Σ)

≤ c.

Доказательство. Положим β =

√γ. Из неравенства p ≤ γn и леммы 1

имеем

(√

)

(√

)

^√p

P λ_min(Σ) < 1 - β -√

≤ P λ_min(Σ) < 1 -

≤

√n

≤ 2exp(-t²/2).

Полагая здесь t =

√n(1 - β)/2, приходим к неравенству

(

)

(

)

⁽1-β⁾

n(1 - β)²

P λ_min(Σ) <

≤ 2exp

Используя это неравенство, получим

(

)

[

]

√ [

]_√

⁽1-β)-4

n(1 - β)²

(Π.2)

E λ-2min(Σ) ≤

+ E λ-4min(Σ)

2 exp

Оценим теперь сверху математическое ожидание E[λ-4min(Σ)]. Ясно, что

[

]

(Π.3)

λ-1min(Σ) ≤ tr

Σ-1 .

Из леммы 2 следует, что почти наверное

[

]₄

(

)

∑

tr[Σ-1]

⁴ =n⁴

dist(R_i, R_-i)-2

≤n⁴p³

dist(R_i, R_-i)-8.

i=1

Поскольку случайные величины dist(R_i, R_-i) одинаково распределены и p ≤

≤ n, имеем

]

[(

)₄

[

]

(Π.4)

E tr[Σ-1]

≤n⁸E

dist(R₁, R-1)-8

Остается только оценить сверху E[dist(R₁, R-1)-8]. Если S — подпростран-

ство Rⁿ размерности p - 1, то случайная величина dist(R₁, S)² имеет χ²-рас-

пределение χ2n-p+1 с n - p + 1 степенями свободы. Следовательно, так как

R-1 — линейная оболочка случайных векторов, не зависящих от R₁, и про-

странство R-1 — почти наверное (p - 1)-мерное, то

[

]

E[dist(R₁, R-1)-8] = E

(χ2n-p+1)⁴

(Π.5)

≤

(n - p - 1)(n - p - 3)(n - p - 5)(n - p - 7)

105

Объединяя (Π.2)-(Π.5), получим

(

)

[

]

⁽1-β)-4

n⁸

√

n(1 - β)²

E λ-2min(Σ) ≤

2 exp

105

что доказывает лемму.

Теперь перейдем ко второму вопросу данного раздела, т.е. к оценке сверху

корреляций. Здесь понадобится следующая лемма о хвостах стандартного

нормального распределения.

Лемма 4. Для η ∼ N(0,1) и всякого x > 0 имеем

√

exp(-x²/2) ≤ P(|η| > x) ≤

2π(x +

x² + 4)

(Π.6)

≤

√

exp(-x²/2),

2π(x +

x² + 2)

√

(

)

(Π.7)

E[η²1_{|η|>x}] ≤

exp(-x²

/2),

√

(

)

(Π.8)

E[η⁴1_{|η|>x}] ≤

x³ + 3x +

exp(-x²

/2).

Более того, если x ≥ 1, то

(Π.9)

x² < E[η² | |η| > x] ≤ 5x².

Неравенства (Π.6)-(Π.8) даны, например, в [4, лемма 4], а (Π.9) легко вы-

текает из (Π.6) и (Π.7).

Лемма 5. Пусть (η,ζ) — гауссовский вектор со средним 0 и матрицей

(

)

ковариаций Γ =

, 0 < ρ < 1. Положим α = E[η² | |η| > x]. Тогда суще-

ствует числовая постоянная C > 0 такая, что

[

]

(η² - α)(ζ² - α)1_{|η|>x}1_{|ζ|>x}

≤ Cρ²x4 exp(-x²/2)

для всякого x ≥ 1.

Доказательство. Из (Π.9) получаем, что α ≤ 5x². Таким образом, ис-

пользуя (Π.8) и условие, что x ≥ 1, находим

[

]

[

]

(ζ² - α)²1_{|ζ|>x}

≤E

(ζ⁴ + α²)1_{|ζ|>x}

≤

(Π.10)

[

]

(

)

≤ 26E

ζ⁴1_{|ζ|>x}

≤ Cx3 exp

-x²/2

Следовательно,

[

]

(η² - α)(ζ² - α)1_{|η|>x}1_{|ζ|>x}

≤

[

]

[

]

(

)

≤E

(η² - α)²1_{|η|>x}

(ζ² - α)²1_{|ζ|>x}

≤ Cx3 exp

-x²/2

√

Это доказывает лемму для ρ ≥ 1/

√

Рассмотрим теперь случай, когда 0 < ρ < 1/

5. Заметим, что, поскольку

√

α ≤ 5x², для 0 < ρ < 1/

5 также выполняется неравенство

ρ<

√α.

В силу симметричности распределения (η, ζ) имеем

[

]

E (η² - α)(ζ²

- α)1_{|η|>x}1_{|ζ|>x}

(Π.11)

[

]

= 2E (η² - α)(ζ²

- α)1_{|η|>x}1_{ζ>x} .

√

= (ρζ +

= означа-

ет равенство по распределению и Z — стандартная гауссовская случайная

величина, не зависящая от ζ. Таким образом,

[

]

[

]

E (η² - α)(ζ²

− α)1_{|η|>x}1_{ζ>x}

= ρ²E (ζ² - α)²

1{|ρζ+√1-ρ2Z|>x}¹{ζ>x}⁺

√

[

]

(Π.12)

+ 2ρ

1 - ρ²E ζZ(ζ²

- α)1{|ρζ+√1-ρ2Z|>x}¹{ζ>x}⁺

[

]

+ (1 - ρ²)E (Z² - α)(ζ²

- α)1{|ρζ+√1-ρ2Z|>x}¹{ζ>x}^.

Оценим сверху каждое из трех слагаемых в правой части (Π.12). Для первого

слагаемого, используя (Π.10), получаем оценку

[

]

√

ρ²E (ζ² - α)²1

1_{ζ>x}

≤

{|ρζ+

1-ρ²Z|>x}

(

)

(Π.13)

[

]

x²

≤ 26ρ²E ζ⁴1{ζ>x}

≤ Cρ²x3 exp

Чтобы оценить второе слагаемое, запишем сначала

[

]

[

]

√

(Π.14)

E ζZ(ζ²

− α)1

1_{ζ>x}

= E ζ(ζ²

- α)g(ζ)1_{ζ>x} ,

{|ρζ+

1-ρ²Z|>x}

√

где g(ζ) := E[Z1

| ζ]. Непосредственно проверяется, что

{|ρζ+

1-ρ²Z|>x}

(

)

(

)

(x - ρζ)²

(x + ρζ)²

g(ζ) = exp

- exp

2(1 - ρ²)

Таким образом, g(ζ) положительна при ζ > x. Следовательно, имеем

[

]

[

]

(Π.15)

E ζ(ζ²

− α)g(ζ)1_{ζ>x}

≤E ζ³g(ζ)1{ζ>x} .

Кроме того,

(

)(

(

))

(x - ρζ)²

2xρζ

g(ζ) = exp

1 - exp

≤

2(1 - ρ²)

1-ρ²

(Π.16)

(

)

2xρζ

≤ 1 - exp

≤

1-ρ²

Объединяя (Π.14)-(Π.16) с (Π.8) и учитывая, что ρ ≤¹² , получаем

(

)

√

[

]

x²

(Π.17)

2ρ

1 - ρ²E ζZ(ζ²

≤Cρ²x4 exp -

− α)1{|ρζ+√1-ρ2Z|>x}¹{ζ>x}

Рассмотрим теперь третье слагаемое правой части (Π.12). Докажем, что

[

]

√

(Π.18)

E (Z² - α)(ζ²

- α)1

1_{ζ>x}

≤ 0.

{|ρζ+

1-ρ²Z|>x}

Имеем

[

]

[

]

E (Z² - α)(ζ²

= E (ζ²

- α)f(ζ)1_{ζ>x} ,

− α)1{|ρζ+√1-ρ2Z|>x}¹{ζ>x}

где

[

]

√

f (ζ) := E (Z² - α)1

|ζ

{|ρζ+

1-ρ²Z|>x}

-√

∫∞

(

)

∫

1-ρ²

(

)

z²

(z² - α) exp

dz +

(z² - α) exp

dz.

√

−∞

1-ρ²

Заметим, что x <

√α в силу (Π.9). Чтобы доказать (Π.18), достаточно пока-

зать, что

√

(Π.19)

∀ζ ∈ [x,

√α],

f (ζ) ≥ f(

α)

√

(Π.20)

∀ζ ∈[√α,∞),

f (ζ) ≤ f(

α).

Действительно, предположим, что (Π.19) и (Π.20) выполнены. Тогда имеем

[

]

[

]

√

E (ζ²

− α)f(ζ)1{x<ζ≤√α}

≤ E (ζ² - α)f(

α)1{x<ζ≤√α}

[

]

[

]

√

= -E (ζ² - α)f(

α)1_{ζ>√α}

≤ -E (ζ²

- α)f(ζ)1_{ζ>√α} ,

где равенство следует из того, что

[

]

[

]

E (ζ²

− α)1_{ζ>x}

E (ζ²

- α)1_{|ζ|>x}

ввиду симметричности нормального распределения и определения α. Таким

образом, чтобы закончить доказательство леммы, остается показать (Π.19)

и (Π.20). Сначала установим (Π.19), для чего достаточно показать, что

f^′(ζ) < 0 при ζ ∈ [x,

√α]. Поскольку 0 < ρ < x/√α и x <√α, имеем

(x - ρy)²

√

(Π.21)

< α при всех y ∈ [x,

α].

1-ρ²

Используя (Π.21), для всех ζ ∈ [x,

√α] будем иметь

(

)₂)((

)

))

x + ρζ

(x-ρζ)

⁽ 2ρxζ⁾

⁽(x + ρζ)²

f^′(ζ)

√

exp

√

-α exp

-α

≤

1-ρ²

⎛

⎞

(

)

))

x + ρζ

⁽⁽(x - ρζ)²

⁽(x + ρζ)²

≤

√

exp^⎝-¹

√

⎠

-α -

-α

1-ρ²

⎛

⎞

(

)

x + ρζ

=-√

exp^⎝-¹

√

⎠4xρζ

< 0.

1-ρ²

Это влечет (Π.19). Наконец, докажем (Π.20). Для этого достаточно устано-

вить следующие три факта:

(i) f^′ непрерывна и f^′(√α) < 0;

(ii) уравнение f^′(y) = 0 имеет не более одного решения в интервале [√α, +∞);

(iii) f(∞) = lim_y→∞ f(y) ≤ f(√α).

Свойство (i) уже доказано выше. Чтобы доказать (ii), прежде всего заме-

тим, что решение уравнения^ddy f(y) = 0 также является решением уравнения

h(y) = 0, где

(

)(

(

)

(x - ρy)

2ρxy

4ρxy

h(y) :=

- α exp

-1

1-ρ²

Пусть теперь y₁ и y₂ — решения квадратного уравнения(x-ρy)2

= α:

1-ρ²

√

α(1 - ρ²)

y₁ =

и y₂ =

В силу (Π.21) имеем y₁ <

√α < y₂. Следовательно, h(y) < 0 на интервале

[√α, y2]. Кроме того, на интервале (y2, +∞) функция h строго выпукла и

h(y₂) < 0. Отсюда следует, что h принимает нулевое значение только в одной

точке интервала (y₂, +∞). Следовательно, (ii) доказано.

Остается показать, что f(√α) ≥ f(∞) =∫∞-∞(z2 - α) exp(-z2/2)dz. Пере-

писывая f(√α) в виде

x-ρ√α

√

∫

1-ρ²

(

)

√

z²

α) = f(∞) -

(z² - α) exp

dz,

√α

-√ ρ

1-ρ²

получаем, что неравенство f(∞) ≤ f(√α) вытекает из (Π.21). Это доказы-

вает (iii) и, значит, (Π.20). Доказательство (Π.18) завершено. Лемма теперь

следует из (Π.11)-(Π.13), (Π.17) и (Π.18).

П.2. Доказательство теоремы 1

Рассмотрим отдельно случаи s ≥

√p и s <√p.

Случай s ≥

√p. Из (1) получаем, что почти наверное

(X^TX)-1X^TY = θ + ϵ,

где

ϵ= σ(X^TX)-1X^Tξ.

Учитывая это, имеем

]

[(

)₂

(

[

])₂

E_θ

Q - ∥θ∥²²

=E_θ

2θ^Tϵ+ ∥ϵ∥²² - σ²tr

(X^TX)-1

≤

(Π.22)

(

)₂

(

[

])₂

≤8E_θ

θ^Tϵ

+2E_θ

∥ϵ∥²² - σ²tr

(X^TX)-1

Заметим, что при фиксированном X случайный вектор ϵ имеет нормальное

распределение со средним 0 и матрицей ковариаций σ²(X^TX)-1. Следова-

тельно, при фиксированном X случайная величина θ^Tϵ имеет нормальное

распределение со средним 0 и дисперсией σ²θ^T(X^TX)-1θ. Таким образом,

(

)₂

[

]

E_θ

θ^Tϵ

≤σ²r²E

λ-1min(X^TX)

. Значит, применяя лемму 3, имеем

(

)₂

(Π.23)

E_θ

θ^Tϵ

≤Cσ²

где C — постоянная, зависящая только от γ. Рассмотрим теперь второй член

в правой части (Π.22). Обозначим через λ_i, i = 1, . . . , p, собственные значения

матрицы (X^TX)-1 и через u_i, i = 1, . . . , p, соответствующие ортонормальные

собственные векторы. Положим v_i =

√λ_iuTiX^Tξ. Имеем

(

)₂

(

[

])

∑

E_θ

∥ϵ∥²² - σ²tr

(X^TX)-1

² =σ⁴E

λ_i[v2i - 1]

i=1

При фиксированном X случайные величины v₁, . . . , v_p являются н.о.р. стан-

дартными гауссовскими. Используя этот факт и лемму 3, получаем

(

[

])₂

E_θ

∥ϵ∥²² - σ²tr

(X^TX)-1

(

)

(Π.24)

∑

[

(

)]

σ⁴p

= 2σ⁴E

λ²

≤ 2pσ⁴E

λ-2min

X^TX

≤C

n²

i=1

где C — постоянная, зависящая только от γ, Объединяя (Π.22)-(Π.24), полу-

чаем результат теоремы при s ≥

√p.

Случай s <

√p. Положим S = {i : θ_i = 0}. Имеем

)₂

(

)₂

(∑

E_θ

Q-∥θ∥²

≤ 3E_θ

(y2i - σ²(X^TX)-1iiα_s - θ2i)

i∈S

)₂

(∑[

]

(Π.25)

+3E_θ

y2i -σ²(X^TX)-1iiα_s

1_{y2

≤2σ²(X^TX)-1ii log(1+p/s²)}

i∈S

⎛

⎞₂

∑[

]

+3E_θ⎝

ϵ2i -σ²(X^TX)-1iiα_s

1_{y2

⎠_,

>2σ²(X^TX)-1ii log(1+p/s²)}

i∈S

где ϵ_i обозначает i-ю компоненту ϵ. Оценим теперь сверху каждый из трех

членов в правой части (Π.25). Для оценки первого члена заметим, что

)₂

(∑

E_θ

(y2i - σ²(X^TX)-1iiα_s - θ2i)

≤

i∈S

(Π.26)

)₂

(∑

≤ 8E_θ

θ_iϵ_i

+ 2E_θ

(ϵ2i - σ²(X^TX)-1iiα_s)

i∈S

Второе слагаемое в правой части (Π.26) удовлетворяет неравенству

)₂

(∑

E_θ

(ϵ2i - σ²(X^TX)-1iiα_s)

≤

i∈S

∑∑

(Π.27)

≤ 2σ⁴(α2s + 3)E

(X^TX)-1ii(X^TX)-1jj ≤

i∈S j∈S

[

]

≤ 2σ⁴(α2s + 3)s²E

λ-2min(X^TX)

Из (Π.9) получаем

(Π.28)

α_s ≤ 10log(1 + p/s²

Используя (Π.26)-(Π.28) вместе с леммой 3 и (Π.23), находим, что

)₂

(∑

(Π.29)

E_θ

(y2i - σ²(X^TX)-1iiα_s - θ2i)

≤ Cσ⁴s2 log²(1 + p/s²)/n²,

i∈S

где константа C зависит только от γ.

Кроме того, нетрудно видеть, что второй член в правой части (Π.25), мень-

ше, с точностью до числового постоянного множителя, чем

∑∑

Eσ⁴

(X^TX)-1ii(X^TX)-1jj(α2s + 4 log²(1 + p/s²)).

i∈S j∈S

Действуя так же, как в (Π.27), и применяя лемму 3 и (Π.28), получаем

)₂

(∑[

]

E_θ

y2i - σ²(X^TX)-1iiα_s

1_{y2

≤

≤2σ²(X^TX)-1ii log(1+p/s²)}

(Π.30)

i∈S

≤ Cσ⁴s2 log²(1 + p/s²)/n²,

где константа C зависит только от γ. Для третьего члена правой части (Π.25)

имеем

⎛

⎞₂

∑[

]

(Π.31)

E_θ ⎝

ϵ2i - σ²(X^TX)-1iiα_s

1_{y2

⎠ =

>2σ²(X^TX)-1ii log(1+p/s²)}

i∈S

∑∑ (

)

=σ⁴

E (X^TX)-1ii(X^TX)-1jj

ξ2i - α_s)

ξ²

- α_s)1{|˜ξ

1{|˜ξ

i|>x}

j|>x}

i∈S j∈S

где

√

ϵi

2 log(1 + p/s²),

ξ_i =

√

σ²(X^TX)-1

Заметим, что E

ξ2i|X) = E

ξ2j|X) = 1 и при фиксированном X вектор

ξ_i

ξ_j) ∈

∈ R² имеет гауссовское распределение с нулевым средним и ковариацией

(X^TX)-1ij

ρ_ij =

√

(X^TX)-1

Используя лемму 5, получим, что существуют числовые константы C такие,

что

∑∑ (

)

E (X^TX)-1ii(X^TX)-1jj

ξ2i - α_s)

ξ²

- α_s)1{|˜ξ

1{|˜ξ

i|>x}

j|>x}

i∈S j∈S

∑∑ (

[

])

E (X^TX)-1ii(X^TX)-1jjE

ξ2i - α_s)

ξ2j - α_s)1{|˜ξ

1{|˜ξ

≤

i|>x}

|>x}

i∈S j∈S

∑ [

]

≤ C E (X^TX)-1ii(X^TX)-1jj ρ²

x⁴ exp(-x²/2) =

i,j=1

[

]

=CE

∥(X^TX)-1∥2F

x⁴ exp(-x²/2) ≤

[

≤CE

∥(X^TX)-1∥²

log²(1 + p/s²) ≤

^F p

[

]

≤CE

λ-2min(X^TX)

s² log²(1 + p/s²),

где ∥(X^TX)-1∥_F — норма Фробениуса матрицы (X^TX)-1. Наконец, лемма 3,

(Π.31) и последняя выкладка влекут, что существует постоянная C, завися-

щая только от γ, такая что

⎛

⎞₂

∑[

]

E_θ ⎝

ϵ2i - σ²(X^TX)-1iiα_s

1_{y2

⎠ ≤

>2σ²(X^TX)-1ii log(1+p/s²)}

(Π.32)

i∈S

σ⁴s² log²(1 + p/s²)

≤C

n²

Доказательство завершается соединением неравенств (Π.25), (Π.29), (Π.30) и

(Π.32).

П.3. Вспомогательные леммы для доказательства теоремы 4

Напомним сначала некоторые общие факты о нижних границах для рис-

ков в задаче проверки гипотез. Пусть Θ — измеримое множество, не обяза-

тельно множество Θ(s, τ), и пусть μ — вероятностная мера на Θ. Рассмотрим

произвольное семейство вероятностных мер P_θ, индексированное параметром

θ ∈ Θ. Обозначим через P_μ смесь вероятностных мер

∫

P_μ = P_θ μ(dθ).

Определим χ²-расхождение между двумя вероятностными мерами P^′ и P как

∫

χ²(P^′,P) = (dP^′/dP)²dP - 1,

если P^′ ≪ P , и положим χ²(P^′, P ) = +∞ в противном случае. Следующая

лемма играет ключевую роль в методе Ле Кама доказательства нижних гра-

ниц (см., например, [4, лемма 3]).

Лемма 6. Пусть μ — вероятностная мера на Θ и пусть {P_θ : θ ∈ Θ} —

семейство вероятностных мер на X , индексированных параметром θ ∈ Θ.

Тогда для любой вероятностной меры Q на X имеем

{

}

√

inf Q(Δ = 1) + sup P_θ(Δ = 0)

≥ 1 - χ²(P_μ,Q),

θ∈Θ

где нижняя грань inf берется по всем статистикам Δ со значениями в

{0, 1}.

Применяя лемму 6 с Q = P₀, видим, что достаточно выбрать подходящую

меру μ и ограничить χ²(P_μ, P₀) сверху величиной, строго меньшей 1, чтобы

получить искомую нижнюю границу для R_s,τ . Следующая лемма полезна

при оценке χ²(P_μ, P₀).

Лемма 7. Пусть μ — вероятностная мера на Θ и пусть {P_θ : θ ∈ Θ} —

семейство вероятностных мер на X , индексированных параметром θ ∈ Θ.

Пусть Q — вероятностная мера на X такая, что P_θ ≪ Q для всех θ ∈ Θ.

Тогда

(∫

)

dP_θdP_θ′

χ²

(P_μ, Q) = E(θ,θ′)∼μ2

- 1.

Здесь E(θ,θ′)∼μ2 обозначает математическое ожидание относительно рас-

пределения пары (θ,θ^′), где θ и θ^′ — независимые случайные величины, каж-

дая из которых распределена в соответствии с μ.

Доказательство. Достаточно заметить, что

∫

(dP_μ)

χ²(P_μ,Q) =

- 1,

тогда как

∫

(dP_μ)²

dP_θμ(dθ)_Θ dP_θ′ μ(dθ^′)

dP_θdP_θ′

μ(dθ)μ(dθ^′)

Θ Θ

Найдем теперь выражение для χ²-расхождения в лемме 7, когда P_θ —

вероятностное распределение, порожденное моделью (1) и Q = P₀.

Лемма 8. Пусть P_θ — распределение (X,Y ), удовлетворяющее (1). То-

гда

χ²(P_μ,P₀) = E(θ,θ′)∼μ2 E_X exp(〈Xθ,Xθ^′〉/σ²) - 1.

Доказательство. Применяем лемму 7 и замечаем, что для любых

(θ, θ^′) ∈ Θ × Θ имеют место равенства

∫

dP_θdP_θ′

dP₀

∫

(

)

E_X exp

(∥y - Xθ∥²² + ∥y - Xθ^′∥²² - ∥y∥²²) dy =

(2πσ)n/2

2σ²

Rⁿ

∫

(

)

E_X exp -

(∥y∥²² - 2〈y, X(θ + θ^′)〉+ ∥X(θ + θ^′)∥²² - 2〈Xθ, Xθ^′〉) dy =

(2πσ)n/2

2σ²

Rⁿ

⎛

⎞

∫

(

)

=E_X ⎝exp(〈Xθ,Xθ′〉/σ2)

exp

∥y - X(θ + θ^′)∥²

dy^⎠ =

(2πσ)n/2

2σ²

Rⁿ

= E_X exp(〈Xθ,Xθ^′〉/σ²).

Лемма 9. Пусть a ∈ R — постоянная и пусть W — случайная величина.

Тогда

⎛

⎞

∞

∫

E exp(W ) ≤ exp(a)^⎝1 + e^tp(t)dt⎠ ,

где p(t) = P (|W - a| ≥ t).

Доказательство. Имеем

E exp(W ) ≤ exp(a)E exp(|W - a|) =

∫∞

= exp(a) P (exp(|W - a|) ≥ x) dx =

⎡

⎤

∞

∫

= exp(a)^⎣1 + P (exp(|W - a|) ≥ x) dx⎦ =

⎡

⎤

∞

∫

= exp(a)^⎣1 + e^tp(t)dt⎦ .

Лемма 10. Предположим, что матрица X имеет изотропное распреде-

ление с независимыми σ_X -субгауссовскими строками при некотором σ_X > 0.

Тогда для всех x > 0 и всех θ, θ^′ ∈ R^p имеем

(

)

P_X

|〈Xθ, Xθ^′〉 - n〈θ, θ^′〉| ≥ ∥θ∥₂∥θ^′∥₂x

≤ 6exp(-C1 min(x,x²/n)),

где константа C₁ > 0 зависит только от σ_X.

Доказательство. Используя однородность, достаточно рассмотреть

случай, когда ∥θ∥₂ = ∥θ^′∥₂ = 1. Это и будет предполагаться далее в доказа-

тельстве. Тогда имеем

∥Xθ∥²² + ∥Xθ^′∥²² - ∥X(θ - θ^′)∥²²

2 - ∥θ - θ^′∥²²

〈Xθ, Xθ^′〉 =

〈θ, θ^′〉 =

что приводит к неравенству



(



₁



₁



₁



Xθ,Xθ^′〉 - 〈θ,θ^′〉



Xθ∥²² - 1



Xθ^′∥²² - 1

≤

⁺

^n〈

^n∥



)

₁



(Π.33)

+^

∥X(θ - θ^′)∥²² - ∥θ - θ^′∥²²



Третье слагаемое в правой части (Π.33) приводится перенормировкой к тому

же виду, что и первые два слагаемых. Учитывая это, для доказательства

леммы достаточно показать, что

(



)

₁



(Π.34)

P_X

Xθ∥²² -1

≤2exp(-C′1 min(v,v²)n),

∀ v > 0,∥θ∥₂

= 1,

≥

^n∥

где константа C′1 > 0 зависит только от σ_X .

Обозначим i-ю строку матрицы X через x_i. Тогда

∑

∥Xθ∥²² - 1 =

(Z2i - 1),

i=1

где Z_i = xTiθ — независимые σ_X -субгауссовские случайные величины, та-

кие что E(Z2i) = 1 при i = 1, . . . , n. Следовательно, Z2i - 1, i = 1, . . . , n, —

независимые субэкспоненциальные случайные величины с нулевыми сред-

ними, и (Π.34) немедленно вытекает из неравенства Бернштейна для суб-

экспоненциальных случайных величин (ср., например, [10, следствие 5.17]).

Лемма 11. Предположим, что матрица X имеет изотропное распреде-

ление с независимыми σ_X -субгауссовскими строками при некотором σ_X > 0.

Тогда существует число u₀ > 0, зависящее только от σ_X , такое что для

всех θ, θ^′ с ∥θ∥₂, ∥θ^′∥₂ ≤ un-1/4 и всех u ∈ (0, u₀) имеем

E_X exp(〈Xθ,Xθ^′〉) ≤ exp(n〈θ,θ^′〉)(1 + C₀u²),

где константа C₀ > 0 зависит только от σ_X.

Доказательство. По лемме 10 для всех x > 0 с P_X-вероятностью не

менее 1 - 6e-C1 min(x,x2/n) имеем



^〈Xθ, Xθ^′〉 - n〈θ, θ^′〉≤∥θ∥2∥θ′∥2x ≤ u2n-1/2x.

Следовательно, для всех t > 0 с P_X -вероятностью не менее

√nt/u²,t²/u⁴)

1 - 6e-C1 min(

имеем



^〈Xθ, Xθ^′〉 - n〈θ, θ^′〉≤t.

Отсюда и из леммы 9 вытекает, что для всех u ≤ u₀ := (C₁/2)1/2 выполнены

неравенства

⎛

⎞

∞

∫

nt/u²,t²/u⁴))dt⎠≤

E_X exp(〈Xθ,Xθ^′〉) ≤ exp(n〈θ,θ^′〉)⎝1 + 6 et-C1 min(^√

⎛

⎞

∫

∞

∫

∞

√

≤ exp(n〈θ, θ^′〉) ⎝1 + 6 et(1-C1

n/u²)dt + 6 et-C1t²/u4 dt⎠ ≤

⎛

⎞

∫

∞

∫

∞

√

≤ exp(n〈θ, θ^′〉) ⎝1 + 6 e-C1

nt/(2u²)dt + 6 e-t(C1t/u4-¹⁾dt⎠ ≤

⎛

⎞

∫

∞

12u⁴

≤ exp(n〈θ, θ^′〉)^⎝1 +12√

e2u4/C1 + 6

e-t2C¹/(2u4)dt⎠ ≤

C₁

2u⁴/C₁

(

)

≤ exp(n〈θ, θ^′〉)

1+C₀u²

где использован тот факт, что C₁

√n/u² > 2 и константа C₀ > 0 зависит толь-

ко от C₁ и, следовательно, только от σ_X .

П.4. Доказательство теоремы 4

Пусть s — целое число, такое что 1 ≤ s ≤ p, и пусть τ > 0. Обозначим через

μ_τ равномерное распределение на множестве всех векторов в R^p, имеющих

в точности s ненулевых коэффициентов, каждый из которых равен τ/√s.

Заметим, что носитель меры μ_τ содержится в Θ(s, τ).

Возьмем теперь τ = τ(s, n, p), определенное в (11), и положим μ = μ_τ . В си-

лу лемм 6-8, чтобы доказать теорему 4, достаточно показать, что

(Π.35)

E(θ,θ′)∼μ2

E_X exp(〈Xθ,Xθ^′〉/σ²) ≤ 1 + o_A

(1),

где o_A(1) стремится к нулю при A → 0.

Прежде чем доказывать (Π.35), введем некоторые упрощения. Во-первых,

заметим, что для τ, определенного в (11), левая часть (Π.35) не зависит

от σ. Таким образом, в дальнейшем будем полагать σ = 1 без потери общ-

ности. Далее заметим, что достаточно доказать теорему для случая s ≤

√p.

Действительно, для s >

√p можно использовать включения Θ(s,τ(s,n,p)) ⊇

⊇Θ(s^′,τ(s,n,p))⊇Θ(s^′,τ(s^′,n,p)), где s^′ — наибольшее целое число, меньшее

или равное

√p. Поскольку

(

)

1/4

τ (s^′, n, p) ≍ min

,n-1/4

√n

а скорость (11) также имеет этот порядок для s >

√p, достаточно доказать

нижнюю оценку для s ≤ s^′ и, следовательно, для s ≤

√p. Принимая во внима-

ние эти упрощения, в дальнейшем будем считать без ограничения общности,

что s ≤

√p, σ = 1 и

(√

)

s log(1 + p/s²)

(Π.36)

τ := A min

,n-1/4

Теперь докажем (Π.35) при этих предположениях. По лемме 11 для всех 0 <

A < u₀ имеем

(Π.37)

E(θ,θ′)∼μ2

E_X exp(〈Xθ,Xθ^′〉) ≤ E(θ,θ′)∼μ2

exp(n〈θ, θ^′〉)(1 + C₀A²

Предположим, что A < 1. Рассуждая точно так же, как в доказательстве

леммы 1 в [4], находим

⎛

⎞

∑

(Π.38) E(θ,θ′)∼μ2

exp(n〈θ, θ^′〉) = E

exp^⎝nτ²s-1

(θ,θ^′)∼μ2τ

1{θj=0}1{θ^′j=0}⎠ ≤

j=1

(

)_s

≤

exp(nτ²s-1)

≤

(

)_A2⁾s

s⁽

≤

s²

(

)_s

A²

≤

≤ exp(A²),

где было использовано неравенство (1 + x)A2 - 1 ≤ A²x, выполненное при

0 < A <1 и x > 0. Из (Π.37) и (Π.38) получим, что для всех 0 < A < min(1,u₀)

имеет место неравенство

E(θ,θ′)∼μ2

E_X exp(〈Xθ,Xθ^′〉) ≤ exp(A²)(1 + C₀A²)

при некоторых u₀ > 0 и C₀ > 0, зависящих только от σ_X . Это завершает до-

казательство теоремы.

СПИСОК ЛИТЕРАТУРЫ

Ingster Y.I. Some Problems of Hypothesis Testing Leading to Infinitely Divisible

Distributions // Math. Methods Statist. 1997. No. 6. P. 47-49.

Donoho D.L., Jin J. Higher Criticism for Detecting Sparse Heterogeneous

Mixtures // Ann. Statist. 2004. No. 32. P. 962-994.

Baraud Y. Non Asymptotic Minimax Rates of Testing in Signal Detection //

Bernoulli. 2002. No. 8. P. 577-606.

Collier O., Comminges L., Tsybakov A.B. Minimax Estimation of Linear and

Quadratic Functionals Under Sparsity Constraints // Ann. Statist. 2017. No. 45.

P. 923-958.

Ingster Y.I., Tsybakov A.B., Verzelen N.

Detection Boundary in Sparse

Regression // Electron. J. Stat. 2010. No. 4. P. 1476-1526.

Arias-Castro E., Candes E., Plan Y. Global Testing Under Sparse Alternatives:

ANOVA, Multiple Comparisons and the Higher Criticism // Ann. Statist. 2011.

No. 39. P. 2533-2556.

Verzelen N. Minimax Risks for Sparse Regressions: Ultra-High Dimensional

Phenomenons // Electron. J. Stat. 2012. No. 6. P. 38-90.

Ingster Y.I., Suslina I.A. Nonparametric Goodness-of-Fit Testing under Gaussian

Models. N.Y.: Springer, 2003.

Davidson K.R., Szarek S.J. Local Operator Theory, Random Matrices and Banach

Spaces. Handbook of the geometry of Banach spaces / Eds.: W.B. Johnson,

J. Lindenstrauss. 2001. V. 1. P. 317-366

10.

Vershynin R. Introduction to the Non-Asymptotic Analysis of Random Matrices.

Compressed sensing. Cambridge: Cambridge Univ. Press. 2012. P. 210-268.

11.

Tao T., Vu V. Random Matrices: Universality of Esds and the Circular Law //

Ann. Probab. 2010. V. 38. No. 5. P. 2023-2065.

12.

Bordenave C., Chafa¨ı D. Around the Circular Law // Probab. Surveys. 2012. No. 9.

P. 1-89.

Статья представлена к публикации членом редколлегии А.В. Назиным.

Поступила в редакцию 19.07.2018

После доработки 03.10.2018

Принята к публикации 08.11.2018