Constrained Langevin Algorithms with L-mixing External Random Variables

Yuping Zheng; Andrew Lamperski

Constrained Langevin Algorithms with L-mixing External Random Variables

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Langevin algorithms are gradient descent methods augmented with additive noise, and are widely used in Markov Chain Monte Carlo (MCMC) sampling, optimization, and machine learning. In recent years, the non-asymptotic analysis of Langevin algorithms for non-convex learning has been extensively explored. For constrained problems with non-convex losses over a compact convex domain with IID data variables, the projected Langevin algorithm achieves a deviation of O(T ^-1/4(log T)^1/2) from its target distribution [27] in 1-Wasserstein distance. In this paper, we obtain a deviation of O(T ^-1/2 log T) in 1-Wasserstein distance for non-convex losses with L-mixing data variables and polyhedral constraints (which are not necessarily bounded). This improves on the previous bound for constrained problems and matches the best-known bound for unconstrained problems.

Original language	English (US)
Title of host publication	Advances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022
Editors	S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, A. Oh
Publisher	Neural information processing systems foundation
ISBN (Electronic)	9781713871088
State	Published - 2022
Externally published	Yes
Event	36th Conference on Neural Information Processing Systems, NeurIPS 2022 - New Orleans, United States Duration: Nov 28 2022 → Dec 9 2022

Publication series

Name	Advances in Neural Information Processing Systems
Volume	35
ISSN (Print)	1049-5258

Conference

Conference	36th Conference on Neural Information Processing Systems, NeurIPS 2022
Country/Territory	United States
City	New Orleans
Period	11/28/22 → 12/9/22

Bibliographical note

Funding Information:
This work was supported in part by NSF CMMI-2122856. The authors thank the reviewers for helpful suggestions for improving the paper.

Publisher Copyright:
© 2022 Neural information processing systems foundation. All rights reserved.

Find It

Find It at U of M Libraries

Cite this

Zheng, Y., & Lamperski, A. (2022). Constrained Langevin Algorithms with L-mixing External Random Variables. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, & A. Oh (Eds.), Advances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022 (Advances in Neural Information Processing Systems; Vol. 35). Neural information processing systems foundation.

Constrained Langevin Algorithms with L-mixing External Random Variables. / Zheng, Yuping; Lamperski, Andrew.
Advances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022. ed. / S. Koyejo; S. Mohamed; A. Agarwal; D. Belgrave; K. Cho; A. Oh. Neural information processing systems foundation, 2022. (Advances in Neural Information Processing Systems; Vol. 35).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Zheng, Y & Lamperski, A 2022, Constrained Langevin Algorithms with L-mixing External Random Variables. in S Koyejo, S Mohamed, A Agarwal, D Belgrave, K Cho & A Oh (eds), Advances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022. Advances in Neural Information Processing Systems, vol. 35, Neural information processing systems foundation, 36th Conference on Neural Information Processing Systems, NeurIPS 2022, New Orleans, United States, 11/28/22.

Zheng Y, Lamperski A. Constrained Langevin Algorithms with L-mixing External Random Variables. In Koyejo S, Mohamed S, Agarwal A, Belgrave D, Cho K, Oh A, editors, Advances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022. Neural information processing systems foundation. 2022. (Advances in Neural Information Processing Systems).

Zheng, Yuping ; Lamperski, Andrew. / Constrained Langevin Algorithms with L-mixing External Random Variables. Advances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022. editor / S. Koyejo ; S. Mohamed ; A. Agarwal ; D. Belgrave ; K. Cho ; A. Oh. Neural information processing systems foundation, 2022. (Advances in Neural Information Processing Systems).

@inproceedings{010aa6e51516401e90a201a35f38fbbd,

title = "Constrained Langevin Algorithms with L-mixing External Random Variables",

abstract = "Langevin algorithms are gradient descent methods augmented with additive noise, and are widely used in Markov Chain Monte Carlo (MCMC) sampling, optimization, and machine learning. In recent years, the non-asymptotic analysis of Langevin algorithms for non-convex learning has been extensively explored. For constrained problems with non-convex losses over a compact convex domain with IID data variables, the projected Langevin algorithm achieves a deviation of O(T -1/4(log T)1/2) from its target distribution [27] in 1-Wasserstein distance. In this paper, we obtain a deviation of O(T -1/2 log T) in 1-Wasserstein distance for non-convex losses with L-mixing data variables and polyhedral constraints (which are not necessarily bounded). This improves on the previous bound for constrained problems and matches the best-known bound for unconstrained problems.",

author = "Yuping Zheng and Andrew Lamperski",

note = "Funding Information: This work was supported in part by NSF CMMI-2122856. The authors thank the reviewers for helpful suggestions for improving the paper. Publisher Copyright: {\textcopyright} 2022 Neural information processing systems foundation. All rights reserved.; 36th Conference on Neural Information Processing Systems, NeurIPS 2022 ; Conference date: 28-11-2022 Through 09-12-2022",

year = "2022",

language = "English (US)",

series = "Advances in Neural Information Processing Systems",

publisher = "Neural information processing systems foundation",

editor = "S. Koyejo and S. Mohamed and A. Agarwal and D. Belgrave and K. Cho and A. Oh",

booktitle = "Advances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022",

}

TY - GEN

T1 - Constrained Langevin Algorithms with L-mixing External Random Variables

AU - Zheng, Yuping

AU - Lamperski, Andrew

N1 - Funding Information: This work was supported in part by NSF CMMI-2122856. The authors thank the reviewers for helpful suggestions for improving the paper. Publisher Copyright: © 2022 Neural information processing systems foundation. All rights reserved.

PY - 2022

Y1 - 2022

N2 - Langevin algorithms are gradient descent methods augmented with additive noise, and are widely used in Markov Chain Monte Carlo (MCMC) sampling, optimization, and machine learning. In recent years, the non-asymptotic analysis of Langevin algorithms for non-convex learning has been extensively explored. For constrained problems with non-convex losses over a compact convex domain with IID data variables, the projected Langevin algorithm achieves a deviation of O(T -1/4(log T)1/2) from its target distribution [27] in 1-Wasserstein distance. In this paper, we obtain a deviation of O(T -1/2 log T) in 1-Wasserstein distance for non-convex losses with L-mixing data variables and polyhedral constraints (which are not necessarily bounded). This improves on the previous bound for constrained problems and matches the best-known bound for unconstrained problems.

AB - Langevin algorithms are gradient descent methods augmented with additive noise, and are widely used in Markov Chain Monte Carlo (MCMC) sampling, optimization, and machine learning. In recent years, the non-asymptotic analysis of Langevin algorithms for non-convex learning has been extensively explored. For constrained problems with non-convex losses over a compact convex domain with IID data variables, the projected Langevin algorithm achieves a deviation of O(T -1/4(log T)1/2) from its target distribution [27] in 1-Wasserstein distance. In this paper, we obtain a deviation of O(T -1/2 log T) in 1-Wasserstein distance for non-convex losses with L-mixing data variables and polyhedral constraints (which are not necessarily bounded). This improves on the previous bound for constrained problems and matches the best-known bound for unconstrained problems.

UR - http://www.scopus.com/inward/record.url?scp=85144266141&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85144266141&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85144266141

T3 - Advances in Neural Information Processing Systems

BT - Advances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022

A2 - Koyejo, S.

A2 - Mohamed, S.

A2 - Agarwal, A.

A2 - Belgrave, D.

A2 - Cho, K.

A2 - Oh, A.

PB - Neural information processing systems foundation

T2 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022

Y2 - 28 November 2022 through 9 December 2022

ER -

Constrained Langevin Algorithms with L-mixing External Random Variables

Abstract

Publication series

Conference

Bibliographical note

Find It

Other files and links

Fingerprint

Cite this