On lower complexity bounds for large-scale smooth convex optimization

Cristóbal Guzmán, Arkadi Nemirovski

Type: Article

Publication Date: 2014-08-13

Citations: 61

DOI: https://doi.org/10.1016/j.jco.2014.08.003

View Publication

Download PDF

Locations

Journal of Complexity - View
arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Reduced complexity methods for large-scale convex optimization	2012	Anatoli Juditsky Arkadi Nemirovski
+	The exact information-based complexity of smooth convex minimization	2016	Yoel Drori
+	On lower and upper bounds in smooth and strongly convex optimization	2016	ArjevaniYossi Shalev-ShwartzShai ShamirOhad
+	On the softplus penalty for large-scale convex optimization	2023	Meng Li Paul Grigas Alper Atamtürk
+	Accelerated first-order methods for large-scale convex optimization: nearly optimal complexity under strong convexity	2019	Masoud Ahookhosh
+	First-Order Methods for Large Scale Convex Optimization	2016	Zi Wang
+ PDF Chat	Convex Optimization: Algorithms and Complexity	2015	Sébastien Bubeck
+	On the Limits of Computation in Non-convex Optimization	2018	Pãnos M. Pardalos
+	Efficient and cheap bounds for (standard) quadratic optimization	2005	Immanuel M. Bomze Marco Locatelli Fabio Tardella
+	A Rigorous Lower Bound for the Optimal Value of Convex Optimization Problems	2003	Christian Jansson
+	Large-scale Nonseparable Convex Optimization	1995	박구현
+	Convex Optimization and Extensions, with a View Toward Large-Scale Problems	2020	Wenbo Gao
+ PDF Chat	Refining asymptotic complexity bounds for nonconvex optimization methods, including why steepest descent is $o(\epsilon^{-2})$ rather than $\mathcal{O}(\epsilon^{-2})$	2024	Serge Gratton Chee-Khian Sim Philippe L. Toint
+	Achieving Optimal Complexity Guarantees for a Class of Bilevel Convex Optimization Problems	2024	Sepideh Samadi Daniel Burbano Farzad Yousefian
+	Large Scale Convex Quadratic Programming.	1975	Edward Joseph Gainer
+	On large-scale unconstrained optimization and arbitrary regularization	2021	J. M. Martı́nez Lúcio T. Santos
+	Iterative Methods for Large Scale Convex Optimization	2017	Thomas Katsekpor
+	On duality bound methods for nonconvex global optimization	2006	Hoàng Tụy
+	Approximation accuracy, gradient methods, and error bound for structured convex optimization	2010	Paul Tseng
+	Convex Optimization Algorithms	2015	Dimitri P. Bertsekas

Works That Cite This (52)

Action	Title	Year	Authors
+ PDF Chat	An Adaptive Proximal Method for Variational Inequalities	2019	Alexander Gasnikov Pavel Dvurechensky Fedor Stonyakin A. Titov
+	On the oracle complexity of smooth strongly convex minimization	2021	Yoel Drori Adrien Taylor
+	Universal Method for Stochastic Composite Optimization Problems	2018	Alexander Gasnikov Yu. E. Nesterov
+	Universal gradient descent	2017	Alexander Gasnikov
+	Path Length Bounds for Gradient Descent and Flow	2019	Chirag Gupta Sivaraman Balakrishnan Aaditya Ramdas
+ PDF Chat	Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization	2021	Vitaly Feldman Cristóbal Guzmán Santosh Vempala
+ PDF Chat	Об адаптивном проксимальном методе для некоторого класса вариационных неравенств и смежных задач	2019	Ф. С. Стонякин
+	Inexact Model: A Framework for Optimization and Variational Inequalities	2019	Fedor Stonyakin Alexander Gasnikov Alexander Tyurin Dmitry Pasechnyuk Artem Agafonov Pavel Dvurechensky Darina Dvinskikh Alexey Kroshnin Victorya Piskunova
+ PDF Chat	Optimal complexity and certification of Bregman first-order methods	2021	Radu-Alexandru Dragomir Adrien Taylor Alexandre d’Aspremont Jérôme Bolte
+	On the Adaptive Proximal Method for a Class of Variational Inequalities and Related Problems	2020	Fedor Stonyakin

Works Cited by This (22)

Action	Title	Year	Authors
+	Sparse convex optimization methods for machine learning	2011	Martin Jaggi
+	Modern mathematical methods of optimization	1993	Karl‐Heinz Elster
+	Fundamentals of Convex Analysis	2001	Jean‐Baptiste Hiriart‐Urruty Claude Lemaréchal
+	The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle	2013	Guanghui Lan
+	The Volume of Convex Bodies and Banach Space Geometry	1989	Gilles Pisier
+ PDF Chat	Universal gradient methods for convex optimization problems	2014	Yu. Nesterov
+	Optimal methods of smooth convex minimization	1985	Arkadi Nemirovski Yu. E. Nesterov
+ PDF Chat	Conditional gradient algorithms for norm-regularized smooth convex optimization	2014	Zaïd Harchaoui Anatoli Juditsky Arkadi Nemirovski
+	On optimality of Krylov's information when solving linear operator equations	1991	Arkadi Nemirovsky
+ PDF Chat	Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization	2012	Alekh Agarwal Peter L. Bartlett Pradeep Ravikumar Martin J. Wainwright