Full list of papers can be found at my DBLP and Google Scholar pages. Papers written before 2022 are below.
Private Stochastic Convex Optimization: Optimal Rates in L1 GeometryH. Asi, V. Feldman, T. Koren and K. Talwar
International Conference on Machine Learning (ICML),
2021.
(Oral Presentation)
Lossless Compression of Efficient Private Local RandomizersV. Feldman and K. Talwar
International Conference on Machine Learning (ICML),
2021.
Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by ShufflingV. Feldman, A. McMillan and K. Talwar
IEEE Symposium on Foundations of Computer Science (FOCS),
2021.
When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?G. Brown, M. Bun, V. Feldman, and A. Smith
ACM Symposium on Theory of Computing (STOC),
2021.
Individual Privacy Accounting via a Renyi FilterV. Feldman and T. Zrnic
Foundations of Responsible Computing (FORC),
2021.
(Non-archival track)Neural Information Processing Systems (NeurIPS),
2021.
What Neural Networks Memorize and Why: Discovering the Long Tail via Influence EstimationV. Feldman and C. Zhang
Neural Information Processing Systems (NeurIPS),
2020.
(Spotlight)
Stability of Stochastic Gradient Descent on Nonsmooth Convex LossesR. Bassily, V. Feldman, C. Guzman and K. Talwar
Neural Information Processing Systems (NeurIPS),
2020.
(Spotlight)
Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical EvaluationU. Erlingsson, V. Feldman, I. Mironov, A. Raghunathan, S. Song, K. Talwar, A. Thakurta
Preprint. Jan., 2020
Interaction is necessary for distributed learning with privacy or communication constraintsY. Dagan and V. Feldman
ACM Symposium on Theory of Computing (STOC),
2020.
Private Stochastic Convex Optimization: Optimal Rates in Linear TimeV. Feldman, T. Koren and K. Talwar
ACM Symposium on Theory of Computing (STOC),
2020.
PAC learning with stable and private predictionsY. Dagan and V. Feldman
Conference on Learning Theory (COLT),
2020.
Does Learning Require Memorization? A Short Tale about a Long TailV. Feldman
ACM Symposium on Theory of Computing (STOC),
2020.
Private Stochastic Convex Optimization with Optimal RatesR. Bassily, V. Feldman, K. Talwar and A. Thakurta
Neural Information Processing Systems (NeurIPS),
2019.
(Spotlight)
High probability generalization bounds for uniformly stable algorithms with nearly optimal rateV. Feldman and J. Vondrak
Conference on Learning Theory (COLT),
2019.
The advantages of multiple classes for reducing overfitting from test set reuseV. Feldman, R. Frostig and M. Hardt
International Conference on Machine Learning (ICML),
2019.
Learning without Interaction Requires SeparationA. Daniely and V. Feldman
Neural Information Processing Systems (NeurIPS),
2019.
Amplification by Shuffling: From Local to Central Differential PrivacyU. Erlingsson, V. Feldman, I. Mironov, A. Raghunathan, K. Talwar, A. Thakurta
ACM-SIAM Symposium on Discrete Algorithms (SODA),
2019.
Generalization Bounds for Uniformly Stable AlgorithmsV. Feldman and J. Vondrak
Neural Information Processing Systems (NIPS),
2018.
(Spotlight)
Privacy Amplification by IterationV. Feldman, I. Mironov, K. Talwar, A. Thakurta
IEEE Symposium on Foundations of Computer Science (FOCS),
2018.
Privacy-preserving PredictionC. Dwork and V. Feldman
Conference on Learning Theory (COLT),
2018.
The Everlasting Database: Statistical Validity at a Fair PriceB. Woodworth, V. Feldman, S. Rosset and N. Srebro
Neural Information Processing Systems (NIPS),
2018.
Calibrating Noise to Variance in Adaptive Data AnalysisV. Feldman and T. Steinke
Conference on Learning Theory (COLT),
2018.
Dealing with Range Anxiety in Mean Estimation via Statistical QueriesV. Feldman
Algorithmic Learning Theory (ALT),
2017.
Nearly Tight Bounds on ℓ1 Approximation of Self-Bounding FunctionsV. Feldman, P. Kothari and J. Vondrak
Algorithmic Learning Theory (ALT),
2017.
Generalization for Adaptively-chosen Estimators via Stable MedianV. Feldman and T. Steinke
Conference on Learning Theory (COLT),
2017.
Guilt Free Data ReuseC. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold and A. Roth
Communications of the ACM
(CACM)
,
2017.
Research Highlights
On the power of learning from k-wise queriesV. Feldman and B. Ghazi
Innovations in Theoretical Computer Science (ITCS),
2017.
A General Characterization of the Statistical Query ComplexityV. Feldman
Conference on Learning Theory (COLT),
2017.
Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes BackV. Feldman
Neural Information Processing Systems (NIPS),
2016.
(Oral)
Statistical Query Algorithms for Mean Estimation and Stochastic Convex OptimizationV. Feldman, C. Guzman and S. Vempala
ACM-SIAM Symposium on Discrete Algorithms (SODA),
2017.
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 ReuseC. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold and A. Roth
Neural Information Processing Systems (NIPS),
2015.
Tight Bounds on Low-degree Spectral Concentration of Submodular and XOS FunctionsV. Feldman and J. Vondrak
IEEE Symposium on Foundations of Computer Science (FOCS),
2015.
Preserving Statistical Validity in Adaptive Data AnalysisC. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold and A. Roth
ACM Symposium on Theory of Computing (STOC),
2015.
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.
The Statistical Query Complexity of Learning Sparse HalfspacesV. Feldman
Open Problem in:
Conference on Learning Theory (COLT),
2014.
Sample Complexity Bounds on Differentially Private Learning via Communication ComplexityV. Feldman and D. Xiao
SIAM Journal on Computing
(SICOMP)
,
2015.
Conference on Learning Theory (COLT),
2014.
Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP'sV. Feldman, W. Perkins and S. Vempala
Neural Information Processing Systems (NIPS),
2015.
On the Complexity of Random Satisfiability Problems with Planted SolutionsV. Feldman, W. Perkins and S. Vempala
ACM Symposium on Theory of Computing (STOC),
2015.
Statistical Active Learning Algorithms for Noise Tolerance and Differential PrivacyM.F. Balcan and V. Feldman
Algorithmica 72(1)
(Special Issue on New Theoretical Challenges in Machine Learning)
: pp. 282-315,
2015.
Neural Information Processing Systems (NIPS),
2013.
Optimal Bounds on Approximation of Submodular and XOS Functions by JuntasV. Feldman and J. Vondrak
SIAM Journal on Computing
(SICOMP)
45(3)
(Special issue on FOCS 2013)
: pp. 1129-1170,
2016.
IEEE Symposium on Foundations of Computer Science (FOCS),
2013.
Agnostic Learning of Disjunctions on Symmetric DistributionsV. Feldman and P. Kothari
Journal of Machine Learning Research
(JMLR)
,
2016.
Learning Coverage Functions and Private Release of MarginalsV. Feldman and P. Kothari
Conference on Learning Theory (COLT),
2014.
Learning Using Local Membership QueriesP. Awasthi, V. Feldman and V. Kanade
Conference on Learning Theory (COLT),
2013.
Best Student Paper award.
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision TreesV. Feldman, P. Kothari and J. Vondrak
Conference on Learning Theory (COLT),
2013.
Provenance-based Dictionary Refinement in Information ExtractionS. 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 CliquesV. Feldman, E. Grigorescu, L. Reyzin, S. Vempala and Y. Xiao
ACM Symposium on Theory of Computing (STOC),
2013.
Journal of the ACM
(JACM)
,
2017.
Computational Bounds on Statistical Query LearningV. Feldman and V. Kanade
Conference on Learning Theory (COLT),
2012.
Nearly Optimal Solutions for the Chow Parameters Problem and Low-weight Approximation of HalfspacesA. De, I. Diakonikolas, V. Feldman and R. Servedio
Journal of the ACM
(JACM)
,
2014.
IBM Research 2014 Pat Goldberg Math/CS/EE Best Paper award.ACM Symposium on Theory of Computing (STOC)
: pp. 729-746,
2012.
Learning DNF Expressions from Fourier SpectrumV. Feldman
Conference on Learning Theory (COLT),
2012.
Distribution-Independent Evolvability of Linear Threshold FunctionsV. Feldman
Conference on Learning Theory (COLT),
2011.
Lower Bounds and Hardness Amplification for Learning Shallow Monotone FormulasV. Feldman, H. Lee and R. Servedio
Conference on Learning Theory (COLT),
2011.
Also available on
ECCC.
Distribution-Specific Agnostic BoostingV. Feldman
Innovations in Computer Science (ICS)
: pp. 241-250,
2010.
Agnostic Learning of Monomials by Halfspaces is HardV. Feldman, V. Guruswami, P. Raghavendra and Yi Wu
SIAM Journal on Computing
(SICOMP)
41(6)
: pp. 1558-1590,
2012.
IEEE Symposium on Foundations of Computer Science (FOCS)
: pp. 385-394,
2009.
A Complete Characterization of Statistical Query Learning with Applications to EvolvabilityV. Feldman
Journal of Computer and System Sciences
(JCSS)
78(5)
(Special issue on Learning Theory in 2009)
: pp. 1444-1459,
2012.
IEEE Symposium on Foundations of Computer Science (FOCS)
: pp. 375-384,
2009.
Sorting and Selection with Imprecise ComparisonsM. Ajtai, V. Feldman, A. Hassidim and J. Nelson
International Colloquium on Automata, Languages and Programming (ICALP) A
: pp. 37-48,
2009.
ACM Transactions on Algorithms
(TALG)
,
2016.
Robustness of EvolvabilityV. Feldman
Conference on Learning Theory (COLT)
: pp. 277-292,
2009.
Experience-Induced Neural Circuits That Achieve High CapacityV. Feldman and L. Valiant
Neural Computation
(NeCo)
21:10
: pp. 2715-2754,
2009.
Also available from
NECO website.
On The Power of Membership Queries in Agnostic LearningV. Feldman
Journal of Machine Learning Research
(JMLR)
10
: pp. 163-182,
2009.
Conference on Learning Theory (COLT)
: pp. 147-156,
2008.
Also available from
JMLR website and
ECCC.
Evolvability from Learning AlgorithmsV. Feldman
ACM Symposium on Theory of Computing (STOC)
: pp. 619-628,
2008.
Separating Models of Learning with Faulty TeachersV. Feldman and S. Shah
Theoretical Computer Science
(TCS)
410(19)
(Special issue on ALT 2007)
: pp. 1903-1912,
2009.
Algorithmic Learning Theory (ALT)
: pp. 94-106,
2007.
Joint with Neal Wadhwa.
On Agnostic Learning of Parities, Monomials and HalfspacesV. Feldman, P. Gopalan, S. Khot, and A. Ponnuswami
SIAM Journal on Computing
(SICOMP)
39(2)
(Special issue on FOCS 2006)
: pp. 606-645,
2009.
Includes the results from:
IEEE Symposium on Foundations of Computer Science (FOCS)
: pp. 563-576,
2006.
Also available on
ECCC.
Optimal Hardness Results for Maximizing Agreement with MonomialsV. Feldman
IEEE Computational Complexity Conference (CCC)
: pp. 226-236,
2006.
Also available on
ECCC. Journal version was merged into the SICOMP paper above.
Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership QueriesV. Feldman
Journal of Computer and System Sciences
(JCSS)
75(1)
(Special issue on Learning Theory in 2006)
: pp. 13-26,
2009.
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 ExpressionsV. Feldman
Journal of Machine Learning Research
(JMLR)
8
(Special issue on COLT 2005)
: pp. 1431-1460,
2007.
Conference on Learning Theory (COLT)
: pp. 576-590,
2005.
Best Student Paper award.Also available from
JMLR.
The Complexity of Properly Learning Simple Concept ClassesM. Alekhnovich, M. Braverman, V. Feldman, A. Klivans, and T. Pitassi
Journal of Computer and System Sciences
(JCSS)
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 QueriesN. Bshouty and V. Feldman
Journal of Machine Learning Research
(JMLR)
2
: pp. 359-395,
2002.
Conference on Computational Learning Theory (COLT)
: pp. 529-545,
2001.
Also available from
JMLR website.
Sealed Calls in Java PackagesA. Zaks, V. Feldman and N. Aizikowitz
ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages & Applications (OOPSLA)
: pp. 83-92,
2000.
Invited articles and surveys:
- Guilt-Free Data Reuse
C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold and A. Roth.
Communications of the ACM (Research Highlights), 2017
- Hardness of Proper Learning.
V. Feldman
The Encyclopedia of Algorithms. Springer-Verlag, 2015 (2nd ed.) and 2008 (1st ed.)
- Statistical Query Learning.
V. Feldman
The Encyclopedia of Algorithms. Springer-Verlag, 2015 (2nd ed.) and 2008 (1st ed.)
- Structure and Learning of Valuation Functions.
V. Feldman and J. Vondrak.
ACM SIGecom Exchanges 12.2