Practical large-scale optimization for max-norm regularization

Jason Lee; Benjamin Recht; Ruslan Salakhutdinov; Nathan Srebro; Joel A. Tropp

Practical large-scale optimization for max-norm regularization

Jason Lee, Benjamin Recht, Ruslan Salakhutdinov, Nathan Srebro, Joel A. Tropp

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The max-norm was proposed as a convex matrix regularizer in [1] and was shown to be empirically superior to the trace-norm for collaborative filtering problems. Although the max-norm can be computed in polynomial time, there are currently no practical algorithms for solving large-scale optimization problems that incorporate the max-norm. The present work uses a factorization technique of Burer and Monteiro [2] to devise scalable first-order algorithms for convex programs involving the max-norm. These algorithms are applied to solve huge collaborative filtering, graph cut, and clustering problems. Empirically, the new methods outperform mature techniques from all three areas.

Original language	English (US)
Title of host publication	Advances in Neural Information Processing Systems 23
Subtitle of host publication	24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010
State	Published - Dec 1 2010
Externally published	Yes
Event	24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010 - Vancouver, BC, Canada Duration: Dec 6 2010 → Dec 9 2010

Publication series

Name	Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010

Other

Other	24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010
Country/Territory	Canada
City	Vancouver, BC
Period	12/6/10 → 12/9/10

All Science Journal Classification (ASJC) codes

Information Systems

Cite this

Lee, J., Recht, B., Salakhutdinov, R., Srebro, N., & Tropp, J. A. (2010). Practical large-scale optimization for max-norm regularization. In Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010 (Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010).

Lee, Jason ; Recht, Benjamin ; Salakhutdinov, Ruslan et al. / Practical large-scale optimization for max-norm regularization. Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010. 2010. (Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010).

@inproceedings{952b3ecd0f604a22b28629c5b35f49e2,

title = "Practical large-scale optimization for max-norm regularization",

abstract = "The max-norm was proposed as a convex matrix regularizer in [1] and was shown to be empirically superior to the trace-norm for collaborative filtering problems. Although the max-norm can be computed in polynomial time, there are currently no practical algorithms for solving large-scale optimization problems that incorporate the max-norm. The present work uses a factorization technique of Burer and Monteiro [2] to devise scalable first-order algorithms for convex programs involving the max-norm. These algorithms are applied to solve huge collaborative filtering, graph cut, and clustering problems. Empirically, the new methods outperform mature techniques from all three areas.",

author = "Jason Lee and Benjamin Recht and Ruslan Salakhutdinov and Nathan Srebro and Tropp, {Joel A.}",

year = "2010",

month = dec,

day = "1",

language = "English (US)",

isbn = "9781617823800",

series = "Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010",

booktitle = "Advances in Neural Information Processing Systems 23",

note = "24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010 ; Conference date: 06-12-2010 Through 09-12-2010",

}

Lee, J, Recht, B, Salakhutdinov, R, Srebro, N & Tropp, JA 2010, Practical large-scale optimization for max-norm regularization. in Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010. Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010, 24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010, Vancouver, BC, Canada, 12/6/10.

Practical large-scale optimization for max-norm regularization. / Lee, Jason; Recht, Benjamin; Salakhutdinov, Ruslan et al.

Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010. 2010. (Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Practical large-scale optimization for max-norm regularization

AU - Lee, Jason

AU - Recht, Benjamin

AU - Salakhutdinov, Ruslan

AU - Srebro, Nathan

AU - Tropp, Joel A.

PY - 2010/12/1

Y1 - 2010/12/1

N2 - The max-norm was proposed as a convex matrix regularizer in [1] and was shown to be empirically superior to the trace-norm for collaborative filtering problems. Although the max-norm can be computed in polynomial time, there are currently no practical algorithms for solving large-scale optimization problems that incorporate the max-norm. The present work uses a factorization technique of Burer and Monteiro [2] to devise scalable first-order algorithms for convex programs involving the max-norm. These algorithms are applied to solve huge collaborative filtering, graph cut, and clustering problems. Empirically, the new methods outperform mature techniques from all three areas.

AB - The max-norm was proposed as a convex matrix regularizer in [1] and was shown to be empirically superior to the trace-norm for collaborative filtering problems. Although the max-norm can be computed in polynomial time, there are currently no practical algorithms for solving large-scale optimization problems that incorporate the max-norm. The present work uses a factorization technique of Burer and Monteiro [2] to devise scalable first-order algorithms for convex programs involving the max-norm. These algorithms are applied to solve huge collaborative filtering, graph cut, and clustering problems. Empirically, the new methods outperform mature techniques from all three areas.

UR - http://www.scopus.com/inward/record.url?scp=84860602150&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84860602150&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84860602150

SN - 9781617823800

T3 - Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010

BT - Advances in Neural Information Processing Systems 23

T2 - 24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010

Y2 - 6 December 2010 through 9 December 2010

ER -

Lee J, Recht B, Salakhutdinov R, Srebro N, Tropp JA. Practical large-scale optimization for max-norm regularization. In Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010. 2010. (Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010).

Practical large-scale optimization for max-norm regularization

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this