File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Efficient Euclidean projections onto the intersection of norm balls

TitleEfficient Euclidean projections onto the intersection of norm balls
Authors
KeywordsAuxiliary functions
Bisection algorithms
Building blockes
Classical methods
Empirical studies
Issue Date2012
PublisherInternational Machine Learning Society.
Citation
The 29th International Conference on Machine Learning (ICML 2012). Edinburgh, Scotland, UK., 27 June-3 July 2012 In Proceedings of the 29th International Conference on Machine Learning, ICML-12, 2012, v. 1, p. 433-440 How to Cite?
Abstract
Using sparse-inducing norms to learn robust models has received increasing attention from many fields for its attractive properties. Projection-based methods have been widely applied to learning tasks constrained by such norms. As a key building block of these methods, an efficient operator for Euclidean projection onto the intersection of ℓ 1 and ℓ 1,q norm balls (q = 2 or ∞) is proposed in this paper. We prove that the projection can be reduced to finding the root of an auxiliary function which is piecewise smooth and monotonic. Hence, a bisection algorithm is sufficient to solve the problem. We show that the time complexity of our solution is O(n + g log g) for q = 2 and O(n log n) for q = ∞), where n is the dimensionality of the vector to be projected and g is the number of disjoint groups; we confirm this complexity by experimentation. Empirical study reveals that our method achieves significantly better performance than classical methods in terms of running time and memory usage. We further show that embedded with our efficient projection operator, projection-based algorithms can solve regression problems with composite norm constraints more efficiently than other methods and give superior accuracy. Copyright 2012 by the author(s)/owner(s).
Persistent Identifierhttp://hdl.handle.net/10722/164926
ISBN

 

Author Affiliations
  1. Stanford University
  2. The University of Hong Kong
DC FieldValueLanguage
dc.contributor.authorSu, Hen_US
dc.contributor.authorYu, Wen_US
dc.contributor.authorLi, FFen_US
dc.date.accessioned2012-09-20T08:12:25Z-
dc.date.available2012-09-20T08:12:25Z-
dc.date.issued2012en_US
dc.identifier.citationThe 29th International Conference on Machine Learning (ICML 2012). Edinburgh, Scotland, UK., 27 June-3 July 2012 In Proceedings of the 29th International Conference on Machine Learning, ICML-12, 2012, v. 1, p. 433-440en_US
dc.identifier.isbn9781450312851-
dc.identifier.urihttp://hdl.handle.net/10722/164926-
dc.description.abstractUsing sparse-inducing norms to learn robust models has received increasing attention from many fields for its attractive properties. Projection-based methods have been widely applied to learning tasks constrained by such norms. As a key building block of these methods, an efficient operator for Euclidean projection onto the intersection of ℓ 1 and ℓ 1,q norm balls (q = 2 or ∞) is proposed in this paper. We prove that the projection can be reduced to finding the root of an auxiliary function which is piecewise smooth and monotonic. Hence, a bisection algorithm is sufficient to solve the problem. We show that the time complexity of our solution is O(n + g log g) for q = 2 and O(n log n) for q = ∞), where n is the dimensionality of the vector to be projected and g is the number of disjoint groups; we confirm this complexity by experimentation. Empirical study reveals that our method achieves significantly better performance than classical methods in terms of running time and memory usage. We further show that embedded with our efficient projection operator, projection-based algorithms can solve regression problems with composite norm constraints more efficiently than other methods and give superior accuracy. Copyright 2012 by the author(s)/owner(s).-
dc.languageengen_US
dc.publisherInternational Machine Learning Society.en_US
dc.relation.ispartofProceedings of the 29th International Conference on Machine Learning, ICML-12en_US
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectAuxiliary functions-
dc.subjectBisection algorithms-
dc.subjectBuilding blockes-
dc.subjectClassical methods-
dc.subjectEmpirical studies-
dc.titleEfficient Euclidean projections onto the intersection of norm ballsen_US
dc.typeConference_Paperen_US
dc.identifier.emailSu, H: haosu@cs.stanford.edu-
dc.identifier.emailYu, W: wyu@cs.hku.hk-
dc.identifier.emailLi, FF: feifeili@cs.stanford.edu-
dc.description.naturepostprint-
dc.identifier.scopuseid_2-s2.0-84867132579-
dc.identifier.hkuros209420en_US
dc.identifier.volume1-
dc.identifier.spage433-
dc.identifier.epage440-
dc.publisher.placeGermany-
dc.description.otherThe 29th International Conference on Machine Learning (ICML 2012). Edinburgh, Scotland, UK., 27 June-3 July 2012 In Proceedings of the 29th International Conference on Machine Learning, ICML-12, 2012, v. 1, p. 433-440-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats