A Gradient Sampling Method With Complexity Guarantees for Lipschitz Functions in High and Low Dimensions

Damek Davis; Dmitriy Drusvyatskiy; Yin Tat Lee; Swati Padmanabhan; Guanghao Ye

A Gradient Sampling Method With Complexity Guarantees for Lipschitz Functions in High and Low Dimensions

Damek Davis, Dmitriy Drusvyatskiy, Yin Tat Lee, Swati Padmanabhan, Guanghao Ye

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

Abstract

Zhang, Lin, Jegelka, Sra, and Jadbabaie [1] introduce a method for minimizing Lipschitz functions with an efficiency guarantee of O(ε^-4). Their method is a novel modification of Goldstein's classical subgradient method. Their work, however, makes use of a nonstandard subgradient oracle model and requires the function to be directionally differentiable. Our first contribution in this paper is to show that both of these assumptions can be dropped by simply adding a small random perturbation in each step of their algorithm. The resulting method works on any Lipschitz function whose value and gradient can be evaluated at points of differentiability. Our second contribution is a new cutting plane algorithm that achieves better efficiency in low dimensions: O(dε^-3) for Lipschitz functions and O(dε^-2) for those that are weakly convex.

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

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

Find It

Find It at U of M Libraries

Cite this

Davis, D., Drusvyatskiy, D., Lee, Y. T., Padmanabhan, S., & Ye, G. (2022). A Gradient Sampling Method With Complexity Guarantees for Lipschitz Functions in High and Low Dimensions. 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.

A Gradient Sampling Method With Complexity Guarantees for Lipschitz Functions in High and Low Dimensions. / Davis, Damek; Drusvyatskiy, Dmitriy; Lee, Yin Tat et al.
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

Davis, D, Drusvyatskiy, D, Lee, YT, Padmanabhan, S & Ye, G 2022, A Gradient Sampling Method With Complexity Guarantees for Lipschitz Functions in High and Low Dimensions. 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.

Davis D, Drusvyatskiy D, Lee YT, Padmanabhan S, Ye G. A Gradient Sampling Method With Complexity Guarantees for Lipschitz Functions in High and Low Dimensions. 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).

Davis, Damek ; Drusvyatskiy, Dmitriy ; Lee, Yin Tat et al. / A Gradient Sampling Method With Complexity Guarantees for Lipschitz Functions in High and Low Dimensions. 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{fdc4ee9d5fcc4861a916ccf3b30bf888,

title = "A Gradient Sampling Method With Complexity Guarantees for Lipschitz Functions in High and Low Dimensions",

abstract = "Zhang, Lin, Jegelka, Sra, and Jadbabaie [1] introduce a method for minimizing Lipschitz functions with an efficiency guarantee of O(ε-4). Their method is a novel modification of Goldstein's classical subgradient method. Their work, however, makes use of a nonstandard subgradient oracle model and requires the function to be directionally differentiable. Our first contribution in this paper is to show that both of these assumptions can be dropped by simply adding a small random perturbation in each step of their algorithm. The resulting method works on any Lipschitz function whose value and gradient can be evaluated at points of differentiability. Our second contribution is a new cutting plane algorithm that achieves better efficiency in low dimensions: O(dε-3) for Lipschitz functions and O(dε-2) for those that are weakly convex.",

author = "Damek Davis and Dmitriy Drusvyatskiy and Lee, \{Yin Tat\} and Swati Padmanabhan and Guanghao Ye",

note = "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 - A Gradient Sampling Method With Complexity Guarantees for Lipschitz Functions in High and Low Dimensions

AU - Davis, Damek

AU - Drusvyatskiy, Dmitriy

AU - Lee, Yin Tat

AU - Padmanabhan, Swati

AU - Ye, Guanghao

PY - 2022

Y1 - 2022

N2 - Zhang, Lin, Jegelka, Sra, and Jadbabaie [1] introduce a method for minimizing Lipschitz functions with an efficiency guarantee of O(ε-4). Their method is a novel modification of Goldstein's classical subgradient method. Their work, however, makes use of a nonstandard subgradient oracle model and requires the function to be directionally differentiable. Our first contribution in this paper is to show that both of these assumptions can be dropped by simply adding a small random perturbation in each step of their algorithm. The resulting method works on any Lipschitz function whose value and gradient can be evaluated at points of differentiability. Our second contribution is a new cutting plane algorithm that achieves better efficiency in low dimensions: O(dε-3) for Lipschitz functions and O(dε-2) for those that are weakly convex.

AB - Zhang, Lin, Jegelka, Sra, and Jadbabaie [1] introduce a method for minimizing Lipschitz functions with an efficiency guarantee of O(ε-4). Their method is a novel modification of Goldstein's classical subgradient method. Their work, however, makes use of a nonstandard subgradient oracle model and requires the function to be directionally differentiable. Our first contribution in this paper is to show that both of these assumptions can be dropped by simply adding a small random perturbation in each step of their algorithm. The resulting method works on any Lipschitz function whose value and gradient can be evaluated at points of differentiability. Our second contribution is a new cutting plane algorithm that achieves better efficiency in low dimensions: O(dε-3) for Lipschitz functions and O(dε-2) for those that are weakly convex.

UR - https://www.scopus.com/pages/publications/85149365164

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

M3 - Conference contribution

AN - SCOPUS:85149365164

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 -

A Gradient Sampling Method With Complexity Guarantees for Lipschitz Functions in High and Low Dimensions

Abstract

Publication series

Conference

Bibliographical note

Find It

Other files and links

Fingerprint

Cite this