File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: Efficient Euclidean projections onto the intersection of norm balls
  • Basic View
  • Metadata View
  • XML View
TitleEfficient Euclidean projections onto the intersection of norm balls
 
AuthorsSu, H1
Yu, W
Li, FF
 
KeywordsAuxiliary functions
Bisection algorithms
Building blockes
Classical methods
Empirical studies
 
Issue Date2012
 
PublisherInternational Machine Learning Society.
 
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-440 [How to Cite?]
 
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).
 
ISBN9781450312851
 
DC FieldValue
dc.contributor.authorSu, H
 
dc.contributor.authorYu, W
 
dc.contributor.authorLi, FF
 
dc.date.accessioned2012-09-20T08:12:25Z
 
dc.date.available2012-09-20T08:12:25Z
 
dc.date.issued2012
 
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.description.naturepostprint
 
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
 
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-440 [How to Cite?]
 
dc.identifier.epage440
 
dc.identifier.hkuros209420
 
dc.identifier.isbn9781450312851
 
dc.identifier.scopuseid_2-s2.0-84867132579
 
dc.identifier.spage433
 
dc.identifier.urihttp://hdl.handle.net/10722/164926
 
dc.identifier.volume1
 
dc.languageeng
 
dc.publisherInternational Machine Learning Society.
 
dc.publisher.placeGermany
 
dc.relation.ispartofProceedings of the 29th International Conference on Machine Learning, ICML-12
 
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 balls
 
dc.typeConference_Paper
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Su, H</contributor.author>
<contributor.author>Yu, W</contributor.author>
<contributor.author>Li, FF</contributor.author>
<date.accessioned>2012-09-20T08:12:25Z</date.accessioned>
<date.available>2012-09-20T08:12:25Z</date.available>
<date.issued>2012</date.issued>
<identifier.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</identifier.citation>
<identifier.isbn>9781450312851</identifier.isbn>
<identifier.uri>http://hdl.handle.net/10722/164926</identifier.uri>
<description.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 &#8467; 1 and &#8467; 1,q norm balls (q = 2 or &#8734;) 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 = &#8734;), 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).</description.abstract>
<language>eng</language>
<publisher>International Machine Learning Society.</publisher>
<relation.ispartof>Proceedings of the 29th International Conference on Machine Learning, ICML-12</relation.ispartof>
<rights>Creative Commons: Attribution 3.0 Hong Kong License</rights>
<subject>Auxiliary functions</subject>
<subject>Bisection algorithms</subject>
<subject>Building blockes</subject>
<subject>Classical methods</subject>
<subject>Empirical studies</subject>
<title>Efficient Euclidean projections onto the intersection of norm balls</title>
<type>Conference_Paper</type>
<description.nature>postprint</description.nature>
<identifier.scopus>eid_2-s2.0-84867132579</identifier.scopus>
<identifier.hkuros>209420</identifier.hkuros>
<identifier.volume>1</identifier.volume>
<identifier.spage>433</identifier.spage>
<identifier.epage>440</identifier.epage>
<publisher.place>Germany</publisher.place>
<description.other>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</description.other>
<bitstream.url>http://hub.hku.hk/bitstream/10722/164926/1/Content.pdf</bitstream.url>
</item>
Author Affiliations
  1. Stanford University
  2. The University of Hong Kong