We consider convex optimization with non-smooth objective function and
log-concave sampling with non-smooth potential (negative log density). In
particular, we study two specific settings where the convex objective/potential
function is either semi-smooth or in composite form as the finite sum of
semi-smooth components. To overcome the challenges caused by non-smoothness,
our algorithms employ two powerful proximal frameworks in optimization and
sampling: the proximal point framework for optimization and the alternating
sampling framework (ASF) that uses Gibbs sampling on an augmented distribution.
A key component of both optimization and sampling algorithms is the efficient
implementation of the proximal map by the regularized cutting-plane method. We
establish the iteration-complexity of the proximal map in both semi-smooth and
composite settings. We further propose an adaptive proximal bundle method for
non-smooth optimization. The proposed method is universal since it does not
need any problem parameters as input. Additionally, we develop a proximal
sampling oracle that resembles the proximal map in optimization and establish
its complexity using a novel technique (a modified Gaussian integral). Finally,
we combine this proximal sampling oracle and ASF to obtain a Markov chain Monte
Carlo method with non-asymptotic complexity bounds for sampling in semi-smooth
and composite settings.

本文考虑了具有非光滑目标函数和具有非光滑潜势（负对数密度）的凸优化和对数凹取样问题，并研究了两个特定的设置，其中凸目标 / 潜势函数可以是半光滑的，也可以是复合形式，作为半光滑分量的有限和。为了克服非光滑性带来的挑战，我们的算法在优化和取样上使用了两种强大的近端框架：优化的近端点框架和使用增广分布上的 Gibbs 取样的交替取样框架（ASF）。优化和取样算法的关键组成部分是通过正则化割平面法对近端映射的高效实现。我们在半光滑和复合的两种情况下建立了近端映射的迭代复杂性。此外，我们还提出了一种适应性近端捆绑法用于非光滑优化。该方法是通用的，因为它不需要任何问题参数作为输入。此外，我们开发了一个类似于优化中近端映射的近端取样预测器，并使用一种新颖的技术（改进的高斯积分）建立了其复杂性。最后，我们将这个近端取样预测器和 ASF 结合起来，得到了一个在半光滑和复合设置中具有非渐近复杂性界限的马尔可夫链蒙特卡洛方法用于取样。