The $\ell_{1,\infty}$ norm is an efficient structured projection but the
complexity of the best algorithm is unfortunately $\mathcal{O}\big(n m \log(n
m)\big)$ for a matrix in $\mathbb{R}^{n\times m}$. In this paper, we propose a
new bi-level projection method for which we show that the time complexity for
the $\ell_{1,\infty}$ norm is only $\mathcal{O}\big(n m \big)$ for a matrix in
$\mathbb{R}^{n\times m}$, and $\mathcal{O}\big(n + m \big)$ with full parallel
power. We generalize our method to tensors and we propose a new multi-level
projection, having an induced decomposition that yields a linear parallel
speedup up to an exponential speedup factor, resulting in a time complexity
lower-bounded by the sum of the dimensions. Experiments show that our bi-level
$\ell_{1,\infty}$ projection is $2.5$ times faster than the actual fastest
algorithm provided by \textit{Chu et. al.} while providing same accuracy and
better sparsity in neural networks applications.

提出了一种新的双层投影方法，其 l1,inf 范数在矩阵中的时间复杂度仅为 O (nm)，在具有完全并行能力时为 O (n+m)，同时还将方法推广到张量，并提出了一个引发线性并行加速和指数加速因子的分解的多级投影方法，结果是时间复杂度的下限为维度之和。实验证明，该双层 l1,inf 投影方法比文献中提供的最快算法快 2.5 倍，同时在神经网络应用中具有相同的准确度和更好的稀疏性。

多层级指投影与指数并行加速；应用于稀疏自编码器神经网络

Multi-level projection with exponential parallel speedup; Application to  sparse auto-encoders neural networks

In distributed statistical learning, $N$ samples are split across $m$
machines and a learner wishes to use minimal communication to learn as well as
if the examples were on a single machine. This model has received substantial
interest in machine learning due to its scalability and potential for parallel
speedup. However, in high-dimensional settings, where the number examples is
smaller than the number of features ("dimension"), the speedup afforded by
distributed learning may be overshadowed by the cost of communicating a single
example. This paper investigates the following question: When is it possible to
learn a $d$-dimensional model in the distributed setting with total
communication sublinear in $d$?
Starting with a negative result, we show that for learning $\ell_1$-bounded
or sparse linear models, no algorithm can obtain optimal error until
communication is linear in dimension. Our main result is that that by slightly
relaxing the standard boundedness assumptions for linear models, we can obtain
distributed algorithms that enjoy optimal error with communication logarithmic
in dimension. This result is based on a family of algorithms that combine
mirror descent with randomized sparsification/quantization of iterates, and
extends to the general stochastic convex optimization model.

研究了在分布式学习中，如何在总通信次数亚线性的情况下通过镜像下降与随机稀疏化 / 量化迭代相结合的算法来实现线性模型的最优误差学习，从而探讨了高维环境下分布式学习的可行性。