We consider a generalization of the classic linear regression problem to the
case when the loss is an Orlicz norm. An Orlicz norm is parameterized by a
non-negative convex function $G:\mathbb{R}_+\rightarrow\mathbb{R}_+$ with
$G(0)=0$: the Orlicz norm of a vector $x\in\mathbb{R}^n$ is defined as $
\|x\|_G=\inf\left\{\alpha>0\large\mid\sum_{i=1}^n G(|x_i|/\alpha)\leq
1\right\}. $ We consider the cases where the function $G(\cdot)$ grows
subquadratically. Our main result is based on a new oblivious embedding which
embeds the column space of a given matrix $A\in\mathbb{R}^{n\times d}$ with
Orlicz norm into a lower dimensional space with $\ell_2$ norm. Specifically, we
show how to efficiently find an embedding matrix $S\in\mathbb{R}^{m\times
n},m<n$ such that $\forall x\in\mathbb{R}^{d},\Omega(1/(d\log n)) \cdot
\|Ax\|_G\leq \|SAx\|_2\leq O(d^2\log n) \cdot \|Ax\|_G.$ By applying this
subspace embedding technique, we show an approximation algorithm for the
regression problem $\min_{x\in\mathbb{R}^d} \|Ax-b\|_G$, up to a $O(d\log^2 n)$
factor. As a further application of our techniques, we show how to also use
them to improve on the algorithm for the $\ell_p$ low rank matrix approximation
problem for $1\leq p<2$.

本文针对经典线性回归问题进行推广，研究了 Orlicz 范数的损失函数，并提出了一种新的盲嵌入，用于将具有 Orlicz 范数的矩阵空间嵌入到具有二范数的较低维空间，从而得到回归问题和低秩矩阵逼近问题的近似算法。

用 Orlicz 范数进行子空间嵌入和线性回归

Subspace Embedding and Linear Regression with Orlicz Norm

Lederer and van de Geer (2013) introduced a new Orlicz norm, the
Bernstein-Orlicz norm, which is connected to Bernstein type inequalities. Here
we introduce another Orlicz norm, the Bennett-Orlicz norm, which is connected
to Bennett type inequalities. The new Bennett-Orlicz norm yields inequalities
for expectations of maxima which are potentially somewhat tighter than those
resulting from the Bernstein-Orlicz norm when they are both applicable. We
discuss cross connections between these norms, exponential inequalities of the
Bernstein, Bennett, and Prokhorov types, and make comparisons with results of
Talagrand (1989, 1994), and Boucheron, Lugosi, and Massart (2013).

本文介绍了另一种与 Bennett 不等式相关的 Orlicz 范数，并比较该范数与 Bernstein 范数的不等式结果，涉及到 Bernstein、Bennett 和 Prokhorov 类型的指数不等式，并与 Talagrand 的研究结果及 Boucheron, Lugosi 和 Massart 的研究结果进行比较。

Bennett-Orlicz 范数

The Bennett-Orlicz norm

We introduce two new concepts designed for the study of empirical processes.
First, we introduce a new Orlicz norm which we call the Bernstein-Orlicz norm.
This new norm interpolates sub-Gaussian and sub-exponential tail behavior. In
particular, we show how this norm can be used to simplify the derivation of
deviation inequalities for suprema of collections of random variables.
Secondly, we introduce chaining and generic chaining along a tree. These
simplify the well-known concepts of chaining and generic chaining. The supremum
of the empirical process is then studied as a special case. We show that
chaining along a tree can be done using entropy with bracketing. Finally, we
establish a deviation inequality for the empirical process for the unbounded
case.

本文引入了伯恩斯坦 - 奥利克斯范数、基于树状结构的锁定与锁定泛化，用熵和分支预测树实现锁定的链式化，讨论了非有界情形下经验过程的偏差不等式。