We show that any randomized first-order algorithm which minimizes a
$d$-dimensional, $1$-Lipschitz convex function over the unit ball must either
use $\Omega(d^{2-\delta})$ bits of memory or make $\Omega(d^{1+\delta/6-o(1)})$
queries, for any constant $\delta\in (0,1)$ and when the precision $\epsilon$
is quasipolynomially small in $d$. Our result implies that cutting plane
methods, which use $\tilde{O}(d^2)$ bits of memory and $\tilde{O}(d)$ queries,
are Pareto-optimal among randomized first-order algorithms, and quadratic
memory is required to achieve optimal query complexity for convex optimization.

该研究表明，任何随机第一阶段算法在单位球上最小化 $d$ 维、1-Lipschitz 凸函数时，必须使用 $Ω(d^{2−δ})$ 位内存或进行 $Ω(d^{1+δ/6−o (1)})$ 次查询，否则凸优化的最优查询复杂度需要使用四次方内存。

随机凸优化的内存 - 查询权衡

Memory-Query Tradeoffs for Randomized Convex Optimization

We provide several new depth-based separation results for feed-forward neural
networks, proving that various types of simple and natural functions can be
better approximated using deeper networks than shallower ones, even if the
shallower networks are much larger. This includes indicators of balls and
ellipses; non-linear functions which are radial with respect to the $L_1$ norm;
and smooth non-linear functions. We also show that these gaps can be observed
experimentally: Increasing the depth indeed allows better learning than
increasing width, when training neural networks to learn an indicator of a unit
ball.

本文提供了一些新的基于深度的前馈神经网络分离结果，证明了各种类型的简单自然函数可以更好地用深层网络逼近比更浅的更大的网络，这包括指示球和椭圆体的指示器，$L_1$ 范数下径向非线性函数，以及平滑的非线性函数。我们还展示了这些差距的实验观察结果：当训练神经网络学习一个单位球的指示器时，增加深度比增加宽度更容易收敛学习。

神经网络中逼近自然函数的深度 - 宽度权衡

Depth-Width Tradeoffs in Approximating Natural Functions with Neural  Networks

This article investigates, by probabilistic methods, various geometric
questions on B_p^n, the unit ball of \ell_p^n. We propose realizations in terms
of independent random variables of several distributions on B_p^n, including
the normalized volume measure. These representations allow us to unify and
extend the known results of the sub-independence of coordinate slabs in B_p^n.
As another application, we compute moments of linear functionals on B_p^n,
which gives sharp constants in Khinchine's inequalities on B_p^n and determines
the \psi_2-constant of all directions on B_p^n. We also study the extremal
values of several Gaussian averages on sections of B_p^n (including mean width
and \ell-norm), and derive several monotonicity results as p varies.
Applications to balancing vectors in \ell_2 and to covering numbers of
polyhedra complete the exposition.

利用概率方法，研究了 B_p^n 上的各种几何问题，包括坐标板的子独立性、线性泛函的矩、Gaussian 平均值在 B_p^n 的截面上的极值等，并对向量平衡和多面体的覆盖数等问题进行了应用。