Guzman’s COLT 2015 open problem on nondual Lipschitz optimization

For $1\le p<q\le\infty$ , let $B_p^n=\{x\in\mathbb{R}^n:\|x\|_p\le 1\}$ . For the class of convex functions $f:B_p^n\to\mathbb{R}$ that are $L$ -Lipschitz with respect to $\|\cdot\|_q$ , determine whether a first-order black-box method can achieve a worst-case optimization error after $T$ oracle queries that is asymptotically better than the classical nonsmooth rate $O(L/\sqrt{T})$ , without relying on dual structure.

References

Primary source

arXiv

Additional references

The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings — arXiv — David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán, Mathieu Molina

Posted 2 weeks ago · edited 2 weeks ago

Progress summary

Refreshed 2 weeks ago

Claimed solved

A new unrefereed paper claims the nonsmooth version is solved up to logarithmic factors, but the claim has not been independently verified.

Guzmán posed this COLT 2015 question about whether faster-than-classical first-order rates are possible for Lipschitz optimization without relying on dual structure. The nonsmooth case is the version addressed by the latest work.

September 17, 2026 preprint

David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán, and Mathieu Molina claim that prior lower bounds are matched up to logarithmic factors in broad nondual settings, affirmatively resolving the nonsmooth question. Their analysis also identifies an online-learning quantity governing the complexity; the preprint is unrefereed.

Current status (as of September 2026): The nonsmooth version is claimed solved up to logarithmic factors by an unrefereed preprint, while independent verification is not recorded.

Sources

No solutions have been posted yet.