We study the generalization performance of gradient methods in the
fundamental stochastic convex optimization setting, focusing on its dimension
dependence. First, for full-batch gradient descent (GD) we give a construction
of a learning problem in dimension $d=O(n^2)$, where the canonical version of
GD (tuned for optimal performance of the empirical risk) trained with $n$
training examples converges, with constant probability, to an approximate
empirical risk minimizer with $\Omega(1)$ population excess risk. Our bound
translates to a lower bound of $\Omega (\sqrt{d})$ on the number of training
examples required for standard GD to reach a non-trivial test error, answering
an open question raised by Feldman (2016) and Amir, Koren, and Livni (2021b)
and showing that a non-trivial dimension dependence is unavoidable.
Furthermore, for standard one-pass stochastic gradient descent (SGD), we show
that an application of the same construction technique provides a similar
$\Omega(\sqrt{d})$ lower bound for the sample complexity of SGD to reach a
non-trivial empirical error, despite achieving optimal test performance. This
again provides an exponential improvement in the dimension dependence compared
to previous work (Koren, Livni, Mansour, and Sherman, 2022), resolving an open
question left therein.

研究了梯度方法在基础随机凸优化条件下的泛化性能，并关注其与维数的依赖关系。针对全批量梯度下降（GD），通过构建学习问题，在维数为 $ d = O（n^2）$ 的情况下，可以证明经过调整以达到经验风险最优表现的典型 GD（使用 n 个训练样本）在具有常数概率的情况下，收敛为近似经验风险最小化器，且其相对于总体风险具有 Ω（1）的过量风险。这个界限对于标准 GD 需要达到非平凡测试误差的训练样本数量有一个下界 Ω（√d），回答了 Feldman（2016）和 Amir，Koren 和 Livni（2021b）提出的一个开放问题，表明非平凡的维数依赖性是不可避免的。此外，针对标准的一次遍历随机梯度下降（SGD），我们证明了同样的构建技术在样本复杂度上提供了类似的 Ω（√d）下界，以达到非平凡的经验误差，尽管它可以实现最优的测试性能。与之前的工作（Koren，Livni，Mansour 和 Sherman，2022）相比，这提供了维数依赖性的指数级改进，解决了其中的一个开放问题。

用梯度实现的维度冲击：随机凸优化中的梯度方法的泛化

The Dimension Strikes Back with Gradients: Generalization of Gradient  Methods in Stochastic Convex Optimization

We provide the first polynomial-time convergence guarantees for the
probability flow ODE implementation (together with a corrector step) of
score-based generative modeling. Our analysis is carried out in the wake of
recent results obtaining such guarantees for the SDE-based implementation
(i.e., denoising diffusion probabilistic modeling or DDPM), but requires the
development of novel techniques for studying deterministic dynamics without
contractivity. Through the use of a specially chosen corrector step based on
the underdamped Langevin diffusion, we obtain better dimension dependence than
prior works on DDPM ($O(\sqrt{d})$ vs. $O(d)$, assuming smoothness of the data
distribution), highlighting potential advantages of the ODE framework.

提供了一种基于分数的生成建模的概率流 ODE 实现的首个多项式时间收敛性保证，并通过基于欠阻尼朗之万扰动的特殊校正步骤获得了更好的维度依赖性。

可证明快速的概率流常微分方程

The probability flow ODE is provably fast

We consider the problem of online adaptive control of the linear quadratic
regulator, where the true system parameters are unknown. We prove new upper and
lower bounds demonstrating that the optimal regret scales as
$\widetilde{\Theta}({\sqrt{d_{\mathbf{u}}^2 d_{\mathbf{x}} T}})$, where $T$ is
the number of time steps, $d_{\mathbf{u}}$ is the dimension of the input space,
and $d_{\mathbf{x}}$ is the dimension of the system state. Notably, our lower
bounds rule out the possibility of a $\mathrm{poly}(\log{}T)$-regret algorithm,
which had been conjectured due to the apparent strong convexity of the problem.
Our upper bound is attained by a simple variant of $\textit{{certainty
equivalent control}}$, where the learner selects control inputs according to
the optimal controller for their estimate of the system while injecting
exploratory random noise. While this approach was shown to achieve
$\sqrt{T}$-regret by (Mania et al. 2019), we show that if the learner
continually refines their estimates of the system matrices, the method attains
optimal dimension dependence as well.
Central to our upper and lower bounds is a new approach for controlling
perturbations of Riccati equations called the $\textit{self-bounding ODE
method}$, which we use to derive suboptimality bounds for the certainty
equivalent controller synthesized from estimated system dynamics. This in turn
enables regret upper bounds which hold for $\textit{any stabilizable instance}$
and scale with natural control-theoretic quantities.

在处理未知真实系统参数的在线自适应控制问题中，使用新的上下界结论证明误差的最优性跟时间步数，输入空间和系统状态空间的维度呈现为～(T*d_u^2*d_x)^1/2, 并引入自绑定 ODE 方法控制 Riccati 方程扰动，从而实现任意可控系统实例的回归上界。同时，提出对估计的系统动力学进行合成的确定性等效控制器。