Stochastic methods for <i>l</i>₁ regularized loss minimization Export

@inproceedings{citeulike:5695616, abstract = {We describe and analyze two stochastic methods for l 1 regularized loss minimization problems, such as the Lasso. The first method updates the weight of a single feature at each iteration while the second method updates the entire weight vector but only uses a single training example at each iteration. In both methods, the choice of feature/example is uniformly at random. Our theoretical runtime analysis suggests that the stochastic methods should outperform state-of-the-art deterministic approaches, including their deterministic counterparts, when the size of the problem is large. We demonstrate the advantage of stochastic methods by experimenting with synthetic and natural data sets.}, address = {New York, NY, USA}, author = {Shwartz, Shai S. and Tewari, Ambuj}, booktitle = {ICML '09: Proceedings of the 26th Annual International Conference on Machine Learning}, citeulike-article-id = {5695616}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1553493}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1553374.1553493}, doi = {10.1145/1553374.1553493}, isbn = {978-1-60558-516-1}, keywords = {l1, online, regularisation, scd, sgd}, location = {Montreal, Quebec, Canada}, pages = {929--936}, posted-at = {2009-09-01 08:19:33}, priority = {5}, publisher = {ACM}, title = {Stochastic methods for <i>l</i>₁ regularized loss minimization}, url = {http://dx.doi.org/10.1145/1553374.1553493}, year = {2009} }

TY - CONF ID - citeulike:5695616 L3 - citeulike-article-id:5695616 N2 - We describe and analyze two stochastic methods for l 1 regularized loss minimization problems, such as the Lasso. The first method updates the weight of a single feature at each iteration while the second method updates the entire weight vector but only uses a single training example at each iteration. In both methods, the choice of feature/example is uniformly at random. Our theoretical runtime analysis suggests that the stochastic methods should outperform state-of-the-art deterministic approaches, including their deterministic counterparts, when the size of the problem is large. We demonstrate the advantage of stochastic methods by experimenting with synthetic and natural data sets. CY - Montreal, Quebec, Canada SN - 978-1-60558-516-1 AD - New York, NY, USA EP - 936 TI - Stochastic methods for <i>l</i>₁ regularized loss minimization PB - ACM T2 - ICML '09: Proceedings of the 26th Annual International Conference on Machine Learning SP - 929 KW - l1 KW - online KW - regularisation KW - scd KW - sgd AU - Shwartz, Shai AU - Tewari, Ambuj PY - 2009/// UR - http://dx.doi.org/10.1145/1553374.1553493 ER -