Open Problem: Fast Stochastic Exp-Concave Optimization

Tomer Koren
Proceedings of the 26th Annual Conference on Learning Theory, PMLR 30:1073-1075, 2013.

Abstract

Stochastic exp-concave optimization is an important primitive in machine learning that captures several fundamental problems, including linear regression, logistic regression and more. The exp-concavity property allows for fast convergence rates, as compared to general stochastic optimization. However, current algorithms that attain such rates scale poorly with the dimension n and run in time O(n^4), even on very simple instances of the problem. The question we pose is whether it is possible to obtain fast rates for exp-concave functions using more computationally-efficient algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v30-Koren13, title = {Open Problem: Fast Stochastic Exp-Concave Optimization }, author = {Koren, Tomer}, booktitle = {Proceedings of the 26th Annual Conference on Learning Theory}, pages = {1073--1075}, year = {2013}, editor = {Shalev-Shwartz, Shai and Steinwart, Ingo}, volume = {30}, series = {Proceedings of Machine Learning Research}, address = {Princeton, NJ, USA}, month = {12--14 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v30/Koren13.pdf}, url = {https://proceedings.mlr.press/v30/Koren13.html}, abstract = {Stochastic exp-concave optimization is an important primitive in machine learning that captures several fundamental problems, including linear regression, logistic regression and more. The exp-concavity property allows for fast convergence rates, as compared to general stochastic optimization. However, current algorithms that attain such rates scale poorly with the dimension n and run in time O(n^4), even on very simple instances of the problem. The question we pose is whether it is possible to obtain fast rates for exp-concave functions using more computationally-efficient algorithms. } }
Endnote
%0 Conference Paper %T Open Problem: Fast Stochastic Exp-Concave Optimization %A Tomer Koren %B Proceedings of the 26th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2013 %E Shai Shalev-Shwartz %E Ingo Steinwart %F pmlr-v30-Koren13 %I PMLR %P 1073--1075 %U https://proceedings.mlr.press/v30/Koren13.html %V 30 %X Stochastic exp-concave optimization is an important primitive in machine learning that captures several fundamental problems, including linear regression, logistic regression and more. The exp-concavity property allows for fast convergence rates, as compared to general stochastic optimization. However, current algorithms that attain such rates scale poorly with the dimension n and run in time O(n^4), even on very simple instances of the problem. The question we pose is whether it is possible to obtain fast rates for exp-concave functions using more computationally-efficient algorithms.
RIS
TY - CPAPER TI - Open Problem: Fast Stochastic Exp-Concave Optimization AU - Tomer Koren BT - Proceedings of the 26th Annual Conference on Learning Theory DA - 2013/06/13 ED - Shai Shalev-Shwartz ED - Ingo Steinwart ID - pmlr-v30-Koren13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 30 SP - 1073 EP - 1075 L1 - http://proceedings.mlr.press/v30/Koren13.pdf UR - https://proceedings.mlr.press/v30/Koren13.html AB - Stochastic exp-concave optimization is an important primitive in machine learning that captures several fundamental problems, including linear regression, logistic regression and more. The exp-concavity property allows for fast convergence rates, as compared to general stochastic optimization. However, current algorithms that attain such rates scale poorly with the dimension n and run in time O(n^4), even on very simple instances of the problem. The question we pose is whether it is possible to obtain fast rates for exp-concave functions using more computationally-efficient algorithms. ER -
APA
Koren, T.. (2013). Open Problem: Fast Stochastic Exp-Concave Optimization . Proceedings of the 26th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 30:1073-1075 Available from https://proceedings.mlr.press/v30/Koren13.html.

Related Material