File Download
There are no files associated with this item.
Supplementary
-
Citations:
- Appears in Collections:
Conference Paper: Even faster accelerated coordinate descent using non-uniform sampling
Title | Even faster accelerated coordinate descent using non-uniform sampling |
---|---|
Authors | |
Issue Date | 2016 |
Publisher | MIT Press. The Journal's web site is located at http://mitpress.mit.edu/jmlr |
Citation | The 33 rd International Conference on Machine Learning (ICML 2016), New York, NY., 19-24 June 2016. In JMLR: Workshop and Conference Proceedings, 2016, v. 48, p. 1-10 How to Cite? |
Abstract | Accelerated coordinate descent is widely used in optimization due to its cheap per-iteration cost and scalability to large-scale problems. Up to a primal-dual transformation, it is also the same as accelerated stochastic gradient descent that is one of the central methods used in machine learning. In this paper, we improve the best known running time of accelerated coordinate descent by a factor up to square root of n. Our improvement is based on a clean, novel non-uniform sampling that selects each coordinate with a probability proportional to the square root of its smoothness parameter. Our proof technique also deviates from the classical estimation sequence technique used in prior work. Our speed-up applies to important problems such as empirical risk minimization and solving linear systems, both in theory and in practice. |
Description | This journal vol. entitled: Proceedings of the 33 rd International Conference on Machine Learning, ICML 2016 The full version of this paper can be found on http://arxiv.org/abs/1512.09103 |
Persistent Identifier | http://hdl.handle.net/10722/235017 |
ISSN | 2021 Impact Factor: 5.177 2020 SCImago Journal Rankings: 1.240 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Allen-Zhu, Z | - |
dc.contributor.author | Qu, Z | - |
dc.contributor.author | Richtarik, P | - |
dc.contributor.author | Yuan, Y | - |
dc.date.accessioned | 2016-10-14T13:50:44Z | - |
dc.date.available | 2016-10-14T13:50:44Z | - |
dc.date.issued | 2016 | - |
dc.identifier.citation | The 33 rd International Conference on Machine Learning (ICML 2016), New York, NY., 19-24 June 2016. In JMLR: Workshop and Conference Proceedings, 2016, v. 48, p. 1-10 | - |
dc.identifier.issn | 1532-4435 | - |
dc.identifier.uri | http://hdl.handle.net/10722/235017 | - |
dc.description | This journal vol. entitled: Proceedings of the 33 rd International Conference on Machine Learning, ICML 2016 | - |
dc.description | The full version of this paper can be found on http://arxiv.org/abs/1512.09103 | - |
dc.description.abstract | Accelerated coordinate descent is widely used in optimization due to its cheap per-iteration cost and scalability to large-scale problems. Up to a primal-dual transformation, it is also the same as accelerated stochastic gradient descent that is one of the central methods used in machine learning. In this paper, we improve the best known running time of accelerated coordinate descent by a factor up to square root of n. Our improvement is based on a clean, novel non-uniform sampling that selects each coordinate with a probability proportional to the square root of its smoothness parameter. Our proof technique also deviates from the classical estimation sequence technique used in prior work. Our speed-up applies to important problems such as empirical risk minimization and solving linear systems, both in theory and in practice. | - |
dc.language | eng | - |
dc.publisher | MIT Press. The Journal's web site is located at http://mitpress.mit.edu/jmlr | - |
dc.relation.ispartof | Journal of Machine Learning Research | - |
dc.rights | Journal of Machine Learning Research. Copyright © MIT Press. | - |
dc.rights | Author holds the copyright | - |
dc.title | Even faster accelerated coordinate descent using non-uniform sampling | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Qu, Z: zhengqu@hku.hk | - |
dc.identifier.authority | Qu, Z=rp02096 | - |
dc.description.nature | published_or_final_version | - |
dc.identifier.hkuros | 269839 | - |
dc.identifier.volume | 48 | - |
dc.identifier.spage | 1 | - |
dc.identifier.epage | 10 | - |
dc.publisher.place | United States | - |
dc.customcontrol.immutable | sml 161017 - full text embargo till 170601 | - |
dc.identifier.issnl | 1532-4435 | - |