Near-optimal algorithms for online matrix prediction

DOI10.1137/120895731MaRDI QIDQ5737809zbMATH OpenOpenAlexFDO

Authors Elad Hazan, Satyen Kale, Shai Shalev-Shwartz

Publication date 30 May 2017

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.0136

zbMATH Keywords

online learningmatrix multiplicative weightsmatrix prediction

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25)

Abstract: In several online prediction problems of recent interest the comparison class is composed of matrices with bounded entries. For example, in the online max-cut problem, the comparison class is matrices which represent cuts of a given graph and in online gambling the comparison class is matrices which represent permutations over n teams. Another important example is online collaborative filtering in which a widely used comparison class is the set of matrices with a small trace norm. In this paper we isolate a property of matrices, which we call (beta,tau)-decomposability, and derive an efficient online learning algorithm, that enjoys a regret bound of O*(sqrt(beta tau T)) for all problems in which the comparison class is composed of (beta,tau)-decomposable matrices. By analyzing the decomposability of cut matrices, triangular matrices, and low trace-norm matrices, we derive near optimal regret bounds for online max-cut, online gambling, and online collaborative filtering. In particular, this resolves (in the affirmative) an open problem posed by Abernethy (2010); Kleinberg et al (2010). Finally, we derive lower bounds for the three problems and show that our upper bounds are optimal up to logarithmic factors. In particular, our lower bound for the online collaborative filtering problem resolves another open problem posed by Shamir and Srebro (2011).

Recommendations

• Efficient transductive online learning via randomized rounding
• Logarithmic Regret Algorithms for Online Convex Optimization
• Logarithmic regret algorithms for online convex optimization
• Regret in online combinatorial optimization
• Online optimization for max-norm regularization

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 5957285 (Why is no real title available?)
• scientific article; zbMATH DE number 5485455 (Why is no real title available?)
• scientific article; zbMATH DE number 47926 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 3203564 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Efficient algorithms for online decision problems
• Efficient transductive online learning via randomized rounding
• Exact matrix completion via convex optimization
• Learning hurdles for sleeping experts
• Near-optimal algorithms for online matrix prediction
• Prediction, Learning, and Games
• Regret bounds for sleeping experts and bandits
• Regularization techniques for learning with matrices
• The best constants in the Khintchine inequality
• The multiplicative weights update method: a meta-algorithm and applications
• Understanding machine learning. From theory to algorithms

Cited in

(6)

• Near-optimal algorithms for online matrix prediction
• Online learning for min-max discrete problems
• Learning hurdles for sleeping experts
• Efficient transductive online learning via randomized rounding
• Online Forecasting Matrix Factorization
• Online optimization for max-norm regularization

This page was built for publication: Near-optimal algorithms for online matrix prediction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5737809)