Education
Work Experience
- 2007-present: Senior Research Scientist. Yahoo! Research Machine Learning Group.
- Yahoo Team Superstar Awards in 2010 (for guaranteed delivery advertising) and 2011 (for anti-abuse), the company's highest honor.
- Built a component in C++ that reduced spam to US Yahoo! Mail clients by 30%. Key element was an unorthodox source of labeled data.
- Posed an NP-hard problem that provided the foundation of the architecture of Yahoo's guaranteed delivery advertising system.
- Designed the frequency capping component of Yahoo's guaranteed delivery advertising system. Designed simple heuristics and theoretically principled approaches. Patent application submitted on principled approaches, and simple heuristics are currently in production.
- Established theoretical foundations for the multi-core and cloud machine learning algorithms of John Langford and Alex Smola. Established how stochastic gradient descent handled delayed updates in the context of text, and proved theoretical bounds for when the algorithm was run in parallel and then averaged, a problem that, despite its clear relevance, stayed open for three years.
- Designed "classification-scale focused" learning systems for anti-abuse in Java, currently in staging. Designed learning algorithms which scale with data rate and data dynamics as opposed to data size.
- Came up with new methods for viewing comments. Designed a method for partitioning commenting users into villages: structured heterogeneous groups with mechanisms for protecting each other from abuse. Also, designed new ways to view comments based on the nature of the discussion.
- To study machines learning when to cooperate and with whom, started the Lemonade Stand Game Competition, based on a small three player, twelve action repeated location game I designed, which had no computational component and was in the game theoretic sense "unsolvable", forcing the agents to distinguish themselves by hypothesizing and learning about the behavior of the other agents. Now in its fourth iteration, with competitors from Europe, North America, Middle East, and Australia.
- 2005-2007: Postdoctoral Research Fellow, University of Alberta. Mentor: Michael Bowling.
- Designed an algorithm that was used to build the first program to beat the world's best humans at Texas Hold'em heads-up limit poker. Implemented the prototype in C++. Featured in Wired and The Economist.
- Started the Annual Computer Poker Competition, now in its seventh year. The 2011 competition had 42 agents in three competitions submitted by 13 universities and a variety of individual hobbyists from 16 countries around the world. Built the competition infrastructure in Java that was used for the first four years.
- Found tricks to make the best response computation in the full game of heads-up limit poker (with over 1017 states) feasible. For the first time, people could know exactly how exploitable their strategies were, providing the first absolute metric of quality in the history of computer poker.
- 2004-2005: Postdoctoral Research Associate, Brown University. Computer Science Department. Mentor: Amy Greenwald.
- Summer 1999: Lockheed Martin, Intern.
- Summer 1998: Datacor, Inc., Programmer.
From Microsoft Academic Search (March 2012): Publications: 41 | Citations: 570 | G-Index: 23 | H-Index: 12
Representative Publications
- M. Zinkevich. Online Convex Programming and Generalized Infinitesimal Gradient Ascent. ICML 2003.
- M. Zinkevich, M. Weimer, A. Smola, L. Li. Parallelized Stochastic Gradient Descent. NIPS 2010.
- M. Zinkevich, A. Smola and J. Langford. Slow Learners are Fast. NIPS 2009.
- B. Rubinstein, A. Ghosh, S. Vassilvitski, M. Zinkevich. Adaptive Bidding for Display Advertising. WWW 2009.
- M. Zinkevich, M. Bowling, M. Johanson, C. Piccione. Regret Minimization in Games with Incomplete Information. NIPS 2007.
- A. Blum, T. Sandholm, and M. Zinkevich. Online algorithms for Market Clearing. In Journal of the ACM, Vol. 53, No. 5, Sept. 2006. A previous version appeared in Symposium on Discrete Algorithms, 2002.
Invited Publications
Service
- ICML Area Chair 2009-2011
- NSF Grant Panels 2012, 2011
- DOE Grant Panel 2009, Mathematics for Analysis of Petascale Data
- Ran LSG Competition 2009-2012: Ran panel and session as part of TADA at ACM EC 2010, and was an affiliated competition with TAC presented at TADA at IJCAI 2011.
- Chair, AAAI Computer Poker Competition 2007
- Lead Programmer, AAAI Computer Poker Competition 2006 (M. Littman served as arbiter)
- Reviewing at Yahoo: conferences: AAMAS 2011, AAAI 2008,2011, AISTATS 2009,2011, COLT 2008-2010, FOCS 2008, ICML 2008,2012, NIPS 2008-2010, SAGT 2009, TIST 2010, Canadian AI 2011, Techpulse 2009,2011, workshops: WINE 2008, BigLearn Workshop at NIPS 2011, journals: Algorithmica 2010, ICGA 2008, JAAMAS 2010-2011, JAIR 2010-2011, Journal of GEB 2008, JMLR 2010, Machine Learning 2011
References
Refereed Publications
- S. Zilles, S. Lange, R. Holte, M. Zinkevich.Models of Cooperative Teaching and Learning. JMLR 2011. An earlier version appeared in COLT 2008.
- M. Johanson, K. Waugh, M. Bowling, M. Zinkevich. Accelerating Best Response Calculation in Large Extensive Games. IJCAI 2011.
- W. Chu, M. Zinkevich, L. Li, A. Thomas, B Tseng. Unbiased Online Active Learning in Data Streams. KDD 2011.
- S. Pandey. M. Aly. A. Bagherjeiran. A. Hatch. P. Ciccolo. A. Ratnaparkhi. M. Zinkevich. Learning to Target: What Works for Behavioral Targeting. CIKM 2011.
- M. Zinkevich, M. Weimer, A. Smola, L. Li. Parallelized Stochastic Gradient Descent. NIPS 2010.
- M. Zinkevich, A. Smola and J. Langford. Slow Learners are Fast. NIPS 2009.
- M. Lanctot, K. Waugh, M. Zinkevich, M. Bowling. Monte Carlo Sampling for Regret Minimization in Extensive Games. NIPS 2009.
- B. Rubinstein, A. Ghosh, S. Vassilvitski, M. Zinkevich. Adaptive Bidding for Display Advertising. WWW 2009.
- J. Attenberg, K. Weinberger, A. Dasgupta, A. Smola, M. Zinkevich. Collaborative Email-Spam Filtering with the Hashing Trick. CEAS 2009.
- M. Zinkevich, M. Bowling, M. Johanson, C. Piccione. Regret Minimization in Games with Incomplete Information. NIPS 2007.
- M. Johanson, M. Zinkevich, and M. Bowling. Computing robust
counter-strategies. NIPS 2007.
- M. Zinkevich, M. Bowling, N. Burch. A New Algorithm for Generating Equilibria in Massive Zero-Sum Games. AAAI 2007.
- N. Ratliff, D. Bagnell, M. Zinkevich. Subgradient Methods for Structured Prediction. AISTATS 2007.
- A. Blum, T. Sandholm, and M. Zinkevich. Online algorithms for market clearing. In Journal of the ACM, Vol. 53, No. 5, Sept. 2006. A previous version appeared in SODA, 2002.
- M. Littman, N. Ravi, A. Talwar, M. Zinkevich. An Efficient Optimal-Equilibrium Algorithm for Two-Player Game Trees. UAI 2006.
- M. Zinkevich, M. Bowling, N. Bard, M. Kan, and D. Billings. Optimal Unbiased Estimators for Evaluating Agent
Performance.
AAAI 2006.
- A. Rettinger, M. Zinkevich, and M. Bowling.
Boosting Expert Ensembles for Rapid Concept Recall.
AAAI 2006.
-
N. Sturtevant, M. Zinkevich, and M. Bowling.
ProbMaxn: Opponent Modeling in N-Player Games.
AAAI 2006.
- N. Ratliff, J. Bagnell, M. Zinkevich. Maximum Margin Planning.
ICML 2006. A previous version
appeared in
NIPS, Workshop on Machine Learning
Based Robotics in Unstructured Environments.
- M. Zinkevich, A. Greenwald, and M. Littman.
Cyclic equilibria in markov games.
In NIPS 2005.
-
M. Zinkevich.
Theoretical guarantees for algorithms in multiagent
settings.
PhD thesis, Carnegie Mellon University, 2004.
- A. Blum, J. Jackson, T. Sandholm, and M. Zinkevich. Preference elicitation and query learning. JMLR 2004. A previous version appeared in COLT 2003.
- M. Zinkevich, A. Blum, and T. Sandholm.On polynomial-time preference elicitation with value queries. In ACM-EC 2003.
- M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In ICML 2003.
- J. Langford, M. Zinkevich, and S. Kakade. Competitive analysis of the explore/exploit tradeoff. In ICML 2002.
- T. Balch and M. Zinkevich. Symmetry in markov decision processes and its implications for single agent and multiagent learning. In ICML 2001.
Working Papers