Proximal Oracles for Optimization and Sampling
Jiaming Liang Yongxin Chen
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.