Vitaly Feldman  Vitaly Feldman photo       

contact information

Research scientist
Almaden Research Center, San Jose, CA, USA
  +1dash408dash927dash1013

links




Generalization for Adaptively-chosen Estimators via Stable Median.
V. Feldman and T. Steinke.

Conference on Learning Theory (COLT), 2017.
Also available on arXiv.


Guilt Free Data Reuse.
C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold and A. Roth.

Communications of the ACM, 2017. Research Highlights


A General Characterization of the Statistical Query Complexity.
V. Feldman.

Conference on Learning Theory (COLT), 2017.
Also available on arXiv.


On the power of learning from k-wise queries..
V. Feldman and B. Ghazi.

Innovations in Theoretical Computer Science (ITCS), 2017.
Also available on arXiv.


Dealing with Range Anxiety in Mean Estimation via Statistical Queries.
V. Feldman.

Algorithmic Learning Theory (ALT), 2017.
Also available on arXiv.


Nearly Tight Bounds on ℓ1 Approximation of Self-Bounding Functions.
V. Feldman, P. Kothari and J. Vondrak.

Algorithmic Learning Theory (ALT), 2017.
Available on arXiv.


Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back.
V. Feldman.

Neural Information Processing Systems (NIPS), 2016.
Also available on arXiv.


Statistical Query Algorithms for Mean Estimation and Stochastic Convex Optimization.
V. Feldman, C. Guzman and S. Vempala.

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017.
Also available on arXiv.


The reusable holdout: Preserving validity in adaptive data analysis.
C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold and A. Roth.

Science 349(6248) : pp. 636-638, 2015. IBM Research 2015 Pat Goldberg Math/CS/EE Best Paper award.
Available directly from Science (unfortunately paywalled; email me for a copy). Supplemental Material (with corrections) and code.
Detailed versions appear on arXiv: part I and part II.


Generalization in Adaptive Data Analysis and Holdout Reuse.
C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold and A. Roth.

Neural Information Processing Systems (NIPS), 2015.
Also available on arXiv.


Tight Bounds on Low-degree Spectral Concentration of Submodular and XOS Functions.
V. Feldman and J. Vondrak.

IEEE Symposium on Foundations of Computer Science (FOCS), 2015.
Also available on arXiv.


Preserving Statistical Validity in Adaptive Data Analysis.
C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold and A. Roth.

ACM Symposium on Theory of Computing (STOC), 2015.
Also available on arXiv.


Approximate resilience, monotonicity, and the complexity of agnostic learning .
D. Dachman-Soled, V. Feldman, L. Tan, A. Wan and K. Wimmer .

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.
Also available on arXiv.


The Statistical Query Complexity of Learning Sparse Halfspaces.
V. Feldman.

Open Problem in: Conference on Learning Theory (COLT), 2014.


Sample Complexity Bounds on Differentially Private Learning via Communication Complexity.
V. Feldman and D. Xiao.

Conference on Learning Theory (COLT), 2014.
SIAM Journal on Computing, 2015.
Also available on arXiv.


Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's.
V. Feldman, W. Perkins and S. Vempala.

Neural Information Processing Systems (NIPS), 2015.
Also available on arXiv.


On the Complexity of Random Satisfiability Problems with Planted Solutions.
V. Feldman, W. Perkins and S. Vempala.

ACM Symposium on Theory of Computing (STOC), 2015.
Also available on arXiv.


Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy.
M.F. Balcan and V. Feldman.

Neural Information Processing Systems (NIPS), 2013.
Algorithmica 72(1) (Special Issue on New Theoretical Challenges in Machine Learning) : pp. 282-315, 2015.
Also available on arXiv.


Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas.
V. Feldman and J. Vondrak.

IEEE Symposium on Foundations of Computer Science (FOCS), 2013.
SIAM Journal on Computing 45(3) (Special issue on FOCS 2013) : pp. 1129-1170, 2016.
Also available on arXiv.


Agnostic Learning of Disjunctions on Symmetric Distributions.
V. Feldman and P. Kothari.

Journal of Machine Learning Research, 2016.
Also available on arXiv.


Learning Coverage Functions and Private Release of Marginals.
V. Feldman and P. Kothari.

Conference on Learning Theory (COLT), 2014.
Also available on arXiv.


Learning Using Local Membership Queries.
P. Awasthi, V. Feldman and V. Kanade.

Conference on Learning Theory (COLT), 2013. Best Student Paper award.
Also available on arXiv.


Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees.
V. Feldman, P. Kothari and J. Vondrak.

Conference on Learning Theory (COLT), 2013.
Also available on arXiv.


Provenance-based Dictionary Refinement in Information Extraction.
S. Roy, L. Chiticariu, V. Feldman, F. Reiss and H. Zhu.

ACM SIGMOD International Conference on Management of Data (SIGMOD), 2013.


Statistical Algorithms and a Lower Bound for Detecting Planted Cliques.
V. Feldman, E. Grigorescu, L. Reyzin, S. Vempala and Y. Xiao.

ACM Symposium on Theory of Computing (STOC), 2013.
Journal of the ACM, 2017.
Also available on arXiv and ECCC.


Computational Bounds on Statistical Query Learning.
V. Feldman and V. Kanade.

Conference on Learning Theory (COLT), 2012.


Nearly Optimal Solutions for the Chow Parameters Problem and Low-weight Approximation of Halfspaces.
A. De, I. Diakonikolas, V. Feldman and R. Servedio.

ACM Symposium on Theory of Computing (STOC) : pp. 729-746, 2012.
Journal of the ACM, 2014. IBM Research 2014 Pat Goldberg Math/CS/EE Best Paper award.
Also available on arXiv and ECCC.


Learning DNF Expressions from Fourier Spectrum.
V. Feldman.

Conference on Learning Theory (COLT), 2012.
Also available on arXiv.


Distribution-Independent Evolvability of Linear Threshold Functions.
V. Feldman.

Conference on Learning Theory (COLT), 2011.
Also available on arXiv.


Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas.
V. Feldman, H. Lee and R. Servedio.

Conference on Learning Theory (COLT), 2011.
Also available on ECCC.


Distribution-Specific Agnostic Boosting.
V. Feldman.

Innovations in Computer Science (ICS) : pp. 241-250, 2010.
Also available on arXiv.


Agnostic Learning of Monomials by Halfspaces is Hard.
V. Feldman, V. Guruswami, P. Raghavendra and Yi Wu.

IEEE Symposium on Foundations of Computer Science (FOCS) : pp. 385-394, 2009.
SIAM Journal on Computing 41(6) : pp. 1558-1590, 2012.
Also available on arXiv and ECCC.


A Complete Characterization of Statistical Query Learning with Applications to Evolvability.
V. Feldman.

Journal of Computer and System Sciences (Special issue on Learning Theory in 2009) .
Preliminary version in: IEEE Symposium on Foundations of Computer Science (FOCS) : pp. 375-384, 2009.
Also available on arXiv and ECCC.


Sorting and Selection with Imprecise Comparisons.
M. Ajtai, V. Feldman, A. Hassidim and J. Nelson.

Preliminary version in: International Colloquium on Automata, Languages and Programming (ICALP) A : pp. 37-48, 2009.
ACM Transactions on Algorithms, 2016.
Also available on arXiv


Robustness of Evolvability.
V. Feldman.

Conference on Learning Theory (COLT) : pp. 277-292, 2009.


Experience-Induced Neural Circuits That Achieve High Capacity.
V. Feldman and L. Valiant.

Neural Computation 21:10 : pp. 2715-2754, 2009.
Also available from NECO website.


On The Power of Membership Queries in Agnostic Learning.
V. Feldman.

Journal of Machine Learning Research 10 : pp. 163-182, 2009.
Earlier version in: Conference on Learning Theory (COLT) : pp. 147-156, 2008.
Also available from JMLR website and ECCC.


Evolvability from Learning Algorithms.
V. Feldman.

Earlier version in: ACM Symposium on Theory of Computing (STOC) : pp. 619-628, 2008.


Separating Models of Learning with Faulty Teachers.
V. Feldman and S. Shah.

Theoretical Computer Science 410(19) (Special issue on ALT 2007) : pp. 1903-1912, 2009.
Earlier version in: Algorithmic Learning Theory (ALT) : pp. 94-106, 2007. Joint with Neal Wadhwa.


New Results for Learning Noisy Parities and Halfspaces.
V. Feldman, P. Gopalan, S. Khot, and A. Ponnuswami.

IEEE Symposium on Foundations of Computer Science (FOCS) : pp. 563-576, 2006.
Full version of the first two results appears in: On Agnostic Learning of Parities, Monomials and Halfspaces. SIAM Journal on Computing 39(2) (Special issue on FOCS 2006) : pp. 606-645, 2009.
Also available on ECCC.


Optimal Hardness Results for Maximizing Agreement with Monomials.
V. Feldman.

In IEEE Computational Complexity Conference (CCC) : pp. 226-236, 2006.
Journal version is included in: V. Feldman, P. Gopalan, S. Khot, and A. Ponnuswami. On Agnostic Learning of Parities, Monomials and Halfspaces. SIAM Journal on Computing 39(2) : pp. 606-645, 2009.
Also available on ECCC.


Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries.
V. Feldman.

Journal of Computer and System Sciences 75(1) (Special issue on Learning Theory in 2006) : pp. 13-26, 2009.
Earlier version in: ACM Symposium on Theory of Computing (STOC) : pp. 363-372, 2006.
Also available on ECCC.


Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions.
V. Feldman.

Journal of Machine Learning Research 8 (Special issue on COLT 2005) : pp. 1431-1460, 2007.
Earlier version in: Conference on Learning Theory (COLT) : pp. 576-590, 2005. Best Student Paper award.
Also available from JMLR.


The Complexity of Properly Learning Simple Concept Classes.
M. Alekhnovich, M. Braverman, V. Feldman, A. Klivans, and T. Pitassi.

Journal of Computer and System Sciences 74(1) (Special issue on Learning Theory in 2004) : pp. 16-34, 2008.
Earlier version: Learnability and Automizability. IEEE Symposium on Foundations of Computer Science (FOCS) : pp. 521-530, 2004.


On Using Extended Statistical Queries to Avoid Membership Queries.
N. Bshouty and V. Feldman.

Journal of Machine Learning Research 2 : pp. 359-395, 2002.
Earlier version in: Conference on Computational Learning Theory (COLT) : pp. 529-545, 2001.
Also available from JMLR website.


Sealed Calls in Java Packages.
A. Zaks, V. Feldman and N. Aizikowitz.

ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages & Applications (OOPSLA) : pp. 83-92, 2000.