Proximal Oracles for Optimization and Sampling
<|reference_start|>Proximal Oracles for Optimization and Sampling: 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.<|reference_end|>
@article{liang2024proximal,
    title={Proximal Oracles for Optimization and Sampling},
    author={Jiaming Liang and Yongxin Chen},
    journal={arXiv preprint arXiv:2404.02239},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.02239},
    primaryClass={math.OC cs.LG}
}