BIBLIOS

  Sistema de Gestão de Referências Bibliográficas de Ciências

Modo Visitante (Login)
Need help?


Voltar

Detalhes Referência

Tipo
Artigos em Conferência

Tipo de Documento
Artigo Completo

Título
Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness

Participantes na publicação
Ankit Garg (Author)
Robin Kothari (Author)
Praneeth Netrapalli (Author)
Suhail Sherif (Author)
Dep. Matemática

Resumo
We study the complexity of optimizing highly smooth convex functions. For a positive integer p, we want to find an approximate minimum of a convex function f, given oracle access to the function and its first p derivatives, assuming that the pth derivative of f is Lipschitz. Recently, three independent research groups (Jiang et al., PMLR 2019; Gasnikov et al., PMLR 2019; Bubeck et al., PMLR 2019) developed a new algorithm for this problem. This algorithm is known to be optimal (up to log factors) for deterministic algorithms, but known lower bounds for randomized algorithms do not match this bound. We prove a new lower bound that matches this bound (up to log factors), and holds not only for randomized algorithms, but also for quantum algorithms.

Editor
M. Ranzato and A. Beygelzimer and Y. Dauphin and P.S. Liang and J. Wortman Vaughan

Data de Aceitação
2021-10-27
Data de Publicação
2021-11-09

Evento
Advances in Neural Information Processing Systems 34 (NeurIPS 2021)

Identificadores da Publicação
ISBN - 9781713845393

Número de Páginas
11

Identificadores de Qualidade
CORE A* (2023) - 4611 - Machine learning

Download

Exportar referência

APA
Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif, (2021). Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness. Advances in Neural Information Processing Systems 34 (NeurIPS 2021), -

IEEE
Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif, "Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness" in Advances in Neural Information Processing Systems 34 (NeurIPS 2021), , 2021, pp. -, doi:

BIBTEX
@InProceedings{60204, author = {Ankit Garg and Robin Kothari and Praneeth Netrapalli and Suhail Sherif}, title = {Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness}, booktitle = {Advances in Neural Information Processing Systems 34 (NeurIPS 2021)}, year = 2021, pages = {-}, address = {}, publisher = {} }