提出高阶光滑凸优化新算法，支持非欧几里得空间与不精确求解。
Non-Euclidean High-Order Smooth Convex Optimization
- 基于高阶原语设计非欧几何下的加速近端点方法
- 在ℓ_p空间中达到近乎最优的收敛速度，适用于任意q≥1阶光滑
- 适合处理结构化函数和不精确球形优化的场景
我们为具有霍尔德连续q阶导数的凸目标函数设计了优化算法，使用q阶原语（q ≥ 1）。算法在一般范数下有效，包括ℓ_p空间（1≤p≤∞）。通过引入非精确均匀凸正则项，我们发展了一种非欧几里得的不精确加速近端点方法，可处理结构化函数中不精确实现非欧球优化原语的情形。我们证明了一个针对一般范数的下界，表明在黑盒原语模型下，我们的算法在高维ℓ_p设置中对所有q≥1几乎最优，即使在随机和并行环境下也成立。该下界在首阶光滑情况下解决了并行凸优化中的一个开放问题。
原文摘要 · Abstract (English)
We develop algorithms for the optimization of convex objectives that have Hölder continuous $q$-th derivatives by using a $q$-th order oracle, for any $q \geq 1$. Our algorithms work for general norms under mild conditions, including the $\ell_p$-settings for $1\leq p\leq \infty$. We can also optimize structured functions that allow for inexactly implementing a non-Euclidean ball optimization oracle. We do this by developing a non-Euclidean inexact accelerated proximal point method that makes use of an \emph{inexact uniformly convex regularizer}. We show a lower bound for general norms that demonstrates our algorithms are nearly optimal in high-dimensions in the black-box oracle model for $\ell_p$-settings and all $q \geq 1$, even in randomized and parallel settings. This new lower bound, when applied to the first-order smooth case, resolves an open question in parallel convex optimization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。