Contact Information

Vitaly Feldman
Research scientist
Almaden Research Center, San Jose, CA, USA

Tab navigation

I'm a research scientist in CS Theory Group at IBM Almaden Research Center.

Before joining IBM in Aug 2007 I spent 5 very enjoyable years at Harvard University as a PhD student advised by Leslie Valiant and as a postdoc. Previously I studied at the Technion from which I received BA and MSc in CS (advised by Nader Bshouty) and worked at IBM Research in Haifa.

I serve on the steering committee of the Association for Computational Learning and as a chair of IBM Almaden's professional interest community (PIC) on Learning


My research interests are primarily in Machine Learning Theory and Computational Complexity. I'm particularly interested in questions in the overlap of these areas. I also work on understanding of natural learning systems: learning by the brain and evolution as learning. This work is based on the models pioneered by Leslie Valiant (brain, evolvability).

Here are some of my recent works, Ph.D. thesis and surveys and complete list of publications.

Recent/upcoming activities:

Recent/upcoming conference program committees:

Slides for some recent talks:

  • Generalization and adaptivity in stochastic convex optimization. @TOCA-SV 2016: slides (with some comments in the notes).
  • From algorithms to lower bounds via the statistical query complexity. @Caltech/UCLA, 2016: slides (with some comments in the notes).
  • Generalization in Adaptive Data Analysis via Max-Information. @Simons Institute workshop on Information Theory, 2016: slides.
  • Preserving Validity in Adaptive Data Analysis. @National Academy of Engineering, 2016: slides.
  • Adaptive Data Analysis without Overfitting. @Workshop on Learning. NUS, 2015: slides.
  • Preserving statistical validity in adaptive data analysis. @STOC 2015: slides.
  • Approximate resilience, monotonicity, and the complexity of agnostic learning. @SODA 2015: slides.
  • Sample complexity bounds on differentially private learning via communication complexity. @COLT 2014 and ITA 2015: slides.
  • Using data privacy for better adaptive predictions. Foundations of Learning Theory workshop @COLT 2014 : slides.
  • On the power and the limits of evolvability. Simons Institute workshop on Computational Theories of Evolution, 2014: slides.
  • Optimal bounds on approximation of submodular and XOS functions by juntas. Simons Institute workshop on Real Analysis at @FOCS 2013 : slides.

Selected and recent works


  1. On the Power of Learning from k-Wise Queries.
    With Badih Ghazi. ITCS 2017 (to appear).
  2. A General Characterization of the Statistical Query Complexity.
    Preprint, Aug. 2016.
  3. Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back.
    NIPS 2016 (oral presentation).
  4. Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization.
    With Cristobal Guzman and Santosh Vempala. SODA 2017.
  5. The reusable holdout: Preserving validity in adaptive data analysis.
    With Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold and Aaron Roth. Science, 2015.
    Based on STOC and NIPS papers below. See also my post on this work at IBM Research blog.
  6. Generalization in Adaptive Data Analysis and Holdout Reuse.
    With Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold and Aaron Roth. NIPS, 2015.
  7. Preserving Statistical Validity in Adaptive Data Analysis.
    With Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold and Aaron Roth. STOC 2015.
    Invited to Comm. of the ACM; Invited to SICOMP special issue on STOC
  8. Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's .
    With Will Perkins and Santosh Vempala. NIPS 2015.
  9. Tight Bounds on Low-degree Spectral Concentration of Submodular and XOS Functions.
    With Jan Vondrak. FOCS 2015 .
  10. On the Complexity of Random Satisfiability Problems with Planted Solutions .
    With Will Perkins and Santosh Vempala. STOC 2015 .
  11. Agnostic Learning of Disjunctions on Symmetric Distributions.
    With Pravesh Kothari. JMLR 2015.
  12. Approximate resilience, monotonicity, and the complexity of agnostic learning .
    With Dana Dachman-Soled, Li-Yang Tan, Andrew Wan and Karl Wimmer. SODA 2015 .
  13. The Statistical Query Complexity of Learning Sparse Halfspaces.
    Open Problem at COLT 2014.
  14. Sample Complexity Bounds on Differentially Private Learning via Communication Complexity .
    With David Xiao. COLT 2014, SICOMP 2015.
  15. Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy.
    With Nina Balcan. NIPS 2013 . Algorithmica. Special Issue on New Theoretical Challenges in Machine Learning
  16. Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas.
    With Jan Vondrak. FOCS 2013 . SICOMP 2016, Special issue on FOCS
  17. Learning using Local Membership Queries.
    With Pranjal Awasthi and Varun Kanade. COLT 2013, Best Student (co-authored) Paper Award
  18. Statistical Algorithms and a Lower Bound for Detecting Planted Cliques.
    With Elena Grigorescu, Lev Reyzin, Santosh Vempala and Ying Xiao. STOC 2013 . JACM (to appear).
  19. Learning DNF Expressions from Fourier Spectrum.
    COLT 2012.
  20. Nearly Optimal Solutions for the Chow Parameters Problem and Low-weight Approximation of Halfspaces.
    With Anindya De, Ilias Diakonikolas and Rocco Servedio. STOC 2012; JACM 2014 .
    IBM Research 2014 Pat Goldberg Math/CS/EE Best Paper Award.
  21. Distribution-Specific Agnostic Boosting.
    ITCS (formerly ICS) 2010.
  22. A Complete Characterization of Statistical Query Learning with Applications to Evolvability.
    FOCS 2009; JCSS 2012 (Special issue on Learning Theory).
  23. Experience-Induced Neural Circuits That Achieve High Capacity..
    With Leslie Valiant. Neural Computation 21:10, 2009.
  24. New Results for Learning Noisy Parities and Halfspaces.
    With Parikshit Gopalan, Subhash Khot, and Ashok Ponnuswami. FOCS 2006; SICOMP 2009, Special issue on FOCS
  25. Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries.
    STOC 2006; JCSS 75(1), 2009 (Special issue on Learning Theory)
  26. Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions.
    COLT 2005, Best Student Paper Award; JMLR 2007, Special issue on COLT
  27. The Complexity of Properly Learning Simple Concept Classes.
    With Misha Alekhnovich, Mark Braverman, Adam Klivans, and Toni Pitassi.
    FOCS 2004; JCSS 74(1), 2008 (Special issue on Learning Theory)

Invited articles and surveys:

  1. Guilt Free Data Reuse.
    With Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold and Aaron Roth. Communications of the ACM. Research Highlights (to appear)
  2. Hardness of Proper Learning.
    The Encyclopedia of Algorithms. Springer-Verlag, 2015 (2nd ed.) and 2008 (1st ed.)
  3. Statistical Query Learning.
    The Encyclopedia of Algorithms. Springer-Verlag, 2015 (2nd ed.) and 2008 (1st ed.)
  4. Structure and Learning of Valuation Functions
    With Jan Vondrak. ACM SIGecom Exchanges 12.2

Unpublished manuscripts:

  1. Dealing with Range Anxiety in Mean Estimation via Statistical Queries.
  2. Nearly Tight Bounds on L1 Approximation of Self-Bounding Functions.
    With Pravesh Kothari and Jan Vondrak.

Ph.D. thesis: Efficiency and Computational Limitations of Learning Algorithms. Harvard University. January 2007

A bit more about me

I spend a lot of time in the wonderful company of Polina, Aviv and Milan. I enjoy mountain biking, photography, ballroom dancing, skiing, drinking tea and visiting Paris.