Home . Bio . Publications . Teaching

Publications

Conference Papers

• Better Rates for Any Adversarial Deterministic MDPs (with Ofer Dekel)
  The 30th International Conference on Machine Learning (ICML 2013)

• Online Learning for Time Series Prediction (with Oren Anava, Shie Mannor and Ohad Shamir)
  The 26th conference on learning theory (COLT 2013)

• A Polylog Pivot Steps Simplex Algorithm for Classification (with Z. Karnin)
  Twenty-Sixth Annual Conference on Neural Information Processing Systems (NIPS 2012)

• Linear Regression with Limited Observation. (with T. Koren)
  The 29th International Conference on Machine Learning (ICML 2012)
  ICML 2012 Best Student Paper Runner Up

• Projection-free Online Learning. (with S. Kale)
  The 29th International Conference on Machine Learning (ICML 2012)

• (weak) Calibration is Computationally Hard. (with S. Kakade)
  The 25th conference on learning theory (COLT 2012)

• Near-Optimal Algorithms for Online Matrix Prediction. (with S. Kale and S. Shalev-Shwartz)
  The 25th conference on learning theory (COLT 2012)

• Newtron: an Efficient Bandit algorithm for Online Multiclass Prediction. (with S. Kale)
  Advances in Neural Information Processing Systems (NIPS) 24 2011

• Beating SGD: Learning SVMs in Sublinear Time. (with T. Koren and N. Srebro)
  Advances in Neural Information Processing Systems (NIPS) 24 2011

• Approximating Semidefinite Programs in Sublinear Time. (with D. Garber). Advances in Neural Information Processing Systems (NIPS) 24 2011

• Blackwell Approachability and No-Regret Learning are Equivalent. (with J. Abernethy and P. Bartlett). The 24th Annual Conference on Learning Theory (COLT 2011)

• Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization. (with S. Kale). The 24th Annual Conference on Learning Theory (COLT 2011)

• Learning rotations with little regret. (with S. Kale and M. Warmuth). The 23rd Annual Conference on Learning Theory (COLT 2010). Corrigendum.

• Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. (with J. Duchi and Y. Singer).
  The 23rd Annual Conference on Learning Theory (COLT 2010).

• Efficient learning algorithms for changing environments. (with C. Seshadhri)
  The 26th International Conference on Machine Learning (ICML 2009).

• On Stochastic and Worst-case Models for Investing. (with S. Kale)
  Advances in Neural Information Processing Systems (NIPS) 22, December 2009.

• Online Submodular Minimization. (with S. Kale)
  Advances in Neural Information Processing Systems (NIPS) 22, December 2009.

• How hard is it to approximate the best Nash equilibrium? (with R. Krauthgamer)
  ACM-SIAM Symposium on Discrete Algorithms (SODA09).

• Better Algorithms for Benign Bandits. (with S. Kale)
  ACM-SIAM Symposium on Discrete Algorithms (SODA09).

• An Efficient Algorithm for Bandit Linear Optimization. (with J. Abernethy and A. Rakhlin)
  The 21st Annual Conference on Learning Theory (COLT 2008).
  COLT 2008 Machine Learning Journal Best Student Paper Award

• Sparse Approximate Solutions to Semidefinite Programs.
  LATIN 2008.

• Adaptive Online Gradient Descent. (with P. Bartlett and A. Rakhlin)
  Proceedings of the Twenty-First Annual Conference on Neural Information Processing Systems, (NIPS) 2007.

• Computational Equivalence of Fixed Points and No Regret Algorithms, and Convergence to Equilibria. (with Satyen Kale)
  Proceedings of the Twenty-First Annual Conference on Neural Information Processing Systems, (NIPS) 2007.

• Online Learning with Prior Information.(with N. Megiddo)
  Proceedings of 20th Annual Conference on Learning Theory, (COLT) 2007.

• Algorithms for Portfolio Management based on the Newton Method. (with A. Agarwal, S. Kale and R. E. Schapire)
  The 23rd International Conference on Machine Learning (ICML 2006).

• A Fast Random Sampling Algorithm for Sparsifying Matrices. (with S. Arora and S. Kale)
  APPROX 2006

• Fast Algorithms for Approximate Semidefinite Programming using the Multiplicative Weights Update Method. (with S. Arora and S. Kale)
  Proceedings of the 46th Annual Symposium on the Foundations of Computer Science, (FOCS) 2005

• On Non-Approximability for Quadratic Programs (with S. Arora, E. Berger, G. Kindler, and S. Safra)
  Proceedings of the 46th Annual Symposium on the Foundations of Computer Science, (FOCS) 2005

• (√(log n)) approximation to SPARSEST CUT can be found in Õ(n²) time. (with S. Arora and S. Kale)
  Proceedings of the 46th Annual Symposium on the Foundations of Computer Science (FOCS), 238-247, 2004.

• On the Complexity of Approximating k-Dimensional Matching. (with S. Safra and O. Schwartz)
  RANDOM-APPROX 2003: 83-97

Journal Articles

• Sublinear Optimization for Machine Learning. (with K. Clarkson and D. Woodruff)
  Journal of the ACM (JACM), Volume 59 Issue 5, October 2012.
  

• Universal MMSE Filtering With Logarithmic Adaptive Regret. (with D. Garber)
  to appear IEEE Transactions on Signal Processing.
  

• Online Submodular Minimization. (with S. Kale)
  Journal of Machine Learning Research (JMLR) 13 (2012) 2903-2922.

• The Multiplicative Weights Update Method: A Meta-Algorithm and Applications. (with S. Arora and S. Kale)
  Theory of Computing, Volume 8 (2012) Article 6 pp. 121-164

• Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. (with J. Duchi and Y. Singer)
  Journal of Machine Learning Research (JMLR) Volume 12, 2/1/2011 Pages 2121-2159 .

• On Stochastic and Worst-case Models for Investing. (with S. Kale)
  to appear in Mathematical Finance.

• How hard is it to approximate the best Nash equilibrium? (with Robert Krauthgamer)
  SIAM Journal on Computing (SICOMP) 40(1): 79-91 (2011).

• Better Algorithms for Benign Bandits. (with S. Kale)
  Journal of Machine Learning Research (JMLR) 12, 1287-1311 (2011).

• Interior-Point Methods for Full-Information and Bandit Online Learning. (with Jacob Abernethy and Alexander Rakhlin)
  IEEE Transactions on Information Theory 58(7): 4164-4175 (2012)
  IBM 2008 Pat Goldberg Memorial Best Paper Award
  

• Extracting Certainty from Uncertainty: Regret Bounded by Variation in Costs. (with Satyen Kale)
  Machine Learning Journal 80(2-3): 165-188 (2010) .

• Logarithmic Regret Algorithms for Online Convex Optimization. (with Amit Agarwal and Satyen Kale)
  Machine Learning Journal Volume 69 , Issue 2-3 Pages: 169 - 192 (December 2007)

• (√(log n)) approximation to SPARSEST CUT can be found in Õ(n²) time. (with S. Arora and S. Kale)
  SIAM Journal on Computing (SICOMP) 39(5): 1748-1771 (2010).

• HAPLOFREQ - Estimating Haplotype Frequencies Efficiently(with E. Halperin)
  Journal of Computational Biology, March 2006, Vol. 13, No. 2: 481-500.

• On the Complexity of Approximating k-Set Packing. (with S. Safra and O. Schwartz)
  Computational Complexity 15(1): 20-39 (2006).