Search

Your search keyword '"coordinate descent methods"' showing total 2 results
Start Over Descriptor "coordinate descent methods" Topic mathematical optimization
2 results on '"coordinate descent methods"'

1. EFFICIENCY OF THE ACCELERATED COORDINATE DESCENT METHOD ON STRUCTURED OPTIMIZATION PROBLEMS.

Author

NESTEROV, YURII and STICH, SEBASTIAN U.

Subjects
*COMPUTATIONAL complexity, *MATHEMATICAL optimization, *ANALYTIC geometry, *MATHEMATICAL bounds, *ITERATIVE methods (Mathematics), *MATHEMATICAL proofs
Abstract

In this paper we prove a new complexity bound for a variant of the accelerated coordinate descent method [Yu. Nesterov, SIAM J. Optim., 22 (2012), pp. 341{362]. We show that this method often outperforms the standard fast gradient methods (FGM [Yu. Nesterov, Dokl. Akad. Nauk SSSR, 269 (1983), pp. 542{547; Math. Program. (A), 103 (2005), pp. 127{152]) on optimization problems with dense data. In many important situations, the computational expenses of oracle and method itself at each iteration of our scheme are perfectly balanced (both depend linearly on dimensions of the problem). As application examples, we consider unconstrained convex quadratic minimization and the problems arising in the smoothing technique [Nesterov, Math. Program. (A), 103 (2005), pp. 127{152]. On some special problem instances, the provable acceleration factor with respect to FGM can reach the square root of the number of variables. Our theoretical conclusions are confirmed by numerical experiments. [ABSTRACT FROM AUTHOR]

Published
2017
Full Text
View/download PDF

2. First-Order Methods for Convex Optimization

Author

Pavel Dvurechensky, Shimrit Shtern, Mathias Staudigl, RS: FSE DACS, and Dept. of Advanced Computing Sciences

Subjects
FOS: Computer and information sciences, Computer Science - Machine Learning, Mathematical optimization, 90C06, Proximal Mapping, Control and Optimization, Optimization problem, FRANK-WOLFE, Computational complexity theory, Convex Optimization, Computer science, COORDINATE DESCENT METHODS, 90C25, 90C06, 65Y20, PROJECTED SUBGRADIENT METHODS, Management Science and Operations Research, THRESHOLDING ALGORITHM, Mathematical proof, 90C25, 65Y20, Machine Learning (cs.LG), Set (abstract data type), Bregman Divergence, VARIATIONAL-INEQUALITIES, FOS: Mathematics, Numerical Algorithms, Mathematics - Optimization and Control, INTERMEDIATE GRADIENT-METHOD, MIRROR DESCENT, MINIMIZATION ALGORITHM, Class (computer programming), T57-57.97, Applied mathematics. Quantitative methods, Convergence Rate, 90C30, 68Q25, 68W40, QA75.5-76.95, Computational Mathematics, APPROXIMATION ALGORITHMS, Optimization and Control (math.OC), Modeling and Simulation, Electronic computers. Computer science, Convex optimization, Key (cryptography), STOCHASTIC COMPOSITE OPTIMIZATION, Proximal Gradient Methods, Proximity Operator, First-Order Methods, Composite Optimization
Abstract

First-order methods for solving convex optimization problems have been at the forefront of mathematical optimization in the last 20 years. The rapid development of this important class of algorithms is motivated by the success stories reported in various applications, including most importantly machine learning, signal processing, imaging and control theory. First-order methods have the potential to provide low accuracy solutions at low computational complexity which makes them an attractive set of tools in large-scale optimization problems. In this survey, we cover a number of key developments in gradient-based optimization methods. This includes non-Euclidean extensions of the classical proximal gradient method, and its accelerated versions. Additionally we survey recent developments within the class of projection-free methods, and proximal versions of primal-dual schemes. We give complete proofs for various key results, and highlight the unifying aspects of several optimization algorithms.

Published
2021
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results