Near-optimal algorithms for online matrix prediction

DOI10.1137/120895731zbMATH Open1370.68253arXiv1204.0136OpenAlexW1773217197MaRDI QIDQ5737809FDOQ5737809

Authors: Elad Hazan, Satyen Kale, Shai Shalev-Shwartz 

Publication date: 30 May 2017

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

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).

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

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

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)

Cites Work

• Title not available (Why is that?)
• Prediction, Learning, and Games
• Title not available (Why is that?)
• Exact matrix completion via convex optimization
• Understanding machine learning. From theory to algorithms
• Title not available (Why is that?)
• The best constants in the Khintchine inequality
• Efficient algorithms for online decision problems
• The multiplicative weights update method: a meta-algorithm and applications
• Title not available (Why is that?)
• Regularization techniques for learning with matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Regret bounds for sleeping experts and bandits
• Title not available (Why is that?)
• Near-optimal algorithms for online matrix prediction
• Learning hurdles for sleeping experts
• Efficient transductive online learning via randomized rounding

Cited In (6)

• Near-optimal algorithms for online matrix prediction
• Efficient transductive online learning via randomized rounding
• Online learning for min-max discrete problems
• Learning hurdles for sleeping experts
• 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)