Tight Complexity Bounds for Optimizing Composite Objectives

Blake Woodworth, Nathan Srebro

Type: Preprint

Publication Date: 2016-01-01

Citations: 19

DOI: https://doi.org/10.48550/arxiv.1605.08003

View Publication

Locations

arXiv (Cornell University) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Tight Complexity Bounds for Optimizing Composite Objectives	2016	Blake Woodworth Nathan Srebro
+	Oracle Complexity Separation in Convex Optimization	2020	Anastasiya Ivanova Evgeniya Vorontsova Dmitry Pasechnyuk Alexander Gasnikov Pavel Dvurechensky Darina Dvinskikh Alexander Tyurin
+	Convex Optimization: Algorithms and Complexity	2014	Sébastien Bubeck
+	Convex Optimization: Algorithms and Complexity	2014	Sébastien Bubeck
+	Minimizing Oracle-Structured Composite Functions	2021	Xinyue Shen Alnur Ali Stephen Boyd
+ PDF Chat	Convex Optimization: Algorithms and Complexity	2015	Sébastien Bubeck
+	An accelerated algorithm for minimizing convex compositions	2016	Dmitriy Drusvyatskiy Courtney Kempton
+	Variance-Reduced Proximal Stochastic Gradient Descent for Non-convex Composite optimization	2016	Xiyu Yu Dacheng Tao
+	Accelerating Rescaled Gradient Descent: Fast Optimization of Smooth Functions	2019	Ashia C. Wilson Lester Mackey Andre Wibisono
+	Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales	2021	Jonathan A. Kelner Annie Marsden Vatsal Sharan Aaron Sidford Gregory Valiant Honglin Yuan
+	Theory of Convex Optimization for Machine Learning.	2014	Sébastien Bubeck
+	Near-Optimal High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise	2021	Eduard Gorbunov М. А. Данилова Innokentiy Shibaev Pavel Dvurechensky Alexander Gasnikov
+	The Sample Complexity of Optimizing a Convex Function	2017	Eric Balkanski Yaron Singer
+	Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes	2012	Ohad Shamir Tong Zhang
+ PDF Chat	On lower complexity bounds for large-scale smooth convex optimization	2014	Cristóbal Guzmán Arkadi Nemirovski
+	Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelization	2022	Benjamin Dubois-Taine Francis Bach Quentin Berthet Adrien Taylor
+ PDF Chat	Proximal Oracles for Optimization and Sampling	2024	Jiaming Liang Yongxin Chen
+	Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization	2020	Khaled Ahmed Othmane Sebbouh Nicolas Loizou Robert M. Gower Peter Richtárik
+	Lower Complexity Bounds for Minimizing Regularized Functions	2022	Nikita Doikov
+	Bayesian Optimization of Composite Functions	2019	Raul Astudillo Peter I. Frazier

Works That Cite This (13)

Action	Title	Year	Authors
+ PDF Chat	The Practicality of Stochastic Optimization in Imaging Inverse Problems	2020	Junqi Tang Karen Egiazarian Mohammad Golbabaee Mike E. Davies
+ PDF Chat	The Limitation and Practical Acceleration of Stochastic Gradient Algorithms in Inverse Problems	2019	Junqi Tang Karen Egiazarian Mike E. Davies
+	Accelerated Doubly Stochastic Gradient Algorithm for Large-scale Empirical Risk Minimization	2017	Zebang Shen Hui Qian Tongzhou Mu Chao Zhang
+	Lower error bounds for the stochastic gradient descent optimization algorithm: Sharp convergence rates for slowly and fast decaying learning rates	2019	Arnulf Jentzen Philippe von Wurstemberger
+	DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization	2022	Adel Nabli Edouard Oyallon
+ PDF Chat	VR-SGD: A Simple Stochastic Variance Reduction Method for Machine Learning	2018	Fanhua Shang Kaiwen Zhou Hongying Liu James Cheng Ivor W. Tsang Lijun Zhang Dacheng Tao Licheng Jiao
+ PDF Chat	Variance-Reduced Methods for Machine Learning	2020	Robert M. Gower Mark Schmidt Francis Bach Peter Richtárik
+ PDF Chat	Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates	2024	Zhuanghua Liu Luo Luo Bryan Kian Hsiang Low
+ PDF Chat	ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm	2024	Junchi Li
+ PDF Chat	Optimal First-Order Methods for Nonconvex Optimization Using the Stochastic Path-Integrated Differential Estimator	2024	Chris Junchi Li

Works Cited by This (0)

Action	Title	Year	Authors