Vitaly Feldman
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 Geometry
H. Asi, V. Feldman, T. Koren and K. Talwar
International Conference on Machine Learning (ICML), 2021. (Oral Presentation)
Lossless Compression of Efficient Private Local Randomizers
V. 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 Shuffling
V. 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 Filter
V. 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 Estimation
V. Feldman and C. Zhang
Neural Information Processing Systems (NeurIPS), 2020. (Spotlight)
Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
R. Bassily, V. Feldman, C. Guzman and K. Talwar
Neural Information Processing Systems (NeurIPS), 2020. (Spotlight)
Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation
U. 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 constraints
Y. Dagan and V. Feldman
ACM Symposium on Theory of Computing (STOC), 2020.
Private Stochastic Convex Optimization: Optimal Rates in Linear Time
V. Feldman, T. Koren and K. Talwar
ACM Symposium on Theory of Computing (STOC), 2020.
PAC learning with stable and private predictions
Y. Dagan and V. Feldman
Conference on Learning Theory (COLT), 2020.
Does Learning Require Memorization? A Short Tale about a Long Tail
V. Feldman
ACM Symposium on Theory of Computing (STOC), 2020.
Private Stochastic Convex Optimization with Optimal Rates
R. 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 rate
V. Feldman and J. Vondrak
Conference on Learning Theory (COLT), 2019.
The advantages of multiple classes for reducing overfitting from test set reuse
V. Feldman, R. Frostig and M. Hardt
International Conference on Machine Learning (ICML), 2019.
Learning without Interaction Requires Separation
A. Daniely and V. Feldman
Neural Information Processing Systems (NeurIPS), 2019.
Amplification by Shuffling: From Local to Central Differential Privacy
U. Erlingsson, V. Feldman, I. Mironov, A. Raghunathan, K. Talwar, A. Thakurta
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019.
Generalization Bounds for Uniformly Stable Algorithms
V. Feldman and J. Vondrak
Neural Information Processing Systems (NIPS), 2018. (Spotlight)
Privacy Amplification by Iteration
V. Feldman, I. Mironov, K. Talwar, A. Thakurta
IEEE Symposium on Foundations of Computer Science (FOCS), 2018.
Privacy-preserving Prediction
C. Dwork and V. Feldman
Conference on Learning Theory (COLT), 2018.
The Everlasting Database: Statistical Validity at a Fair Price
B. Woodworth, V. Feldman, S. Rosset and N. Srebro
Neural Information Processing Systems (NIPS), 2018.
Calibrating Noise to Variance in Adaptive Data Analysis
V. Feldman and T. Steinke
Conference on Learning Theory (COLT), 2018.
Dealing with Range Anxiety in Mean Estimation via Statistical Queries
V. Feldman
Algorithmic Learning Theory (ALT), 2017.
Nearly Tight Bounds on ℓ1 Approximation of Self-Bounding Functions
V. Feldman, P. Kothari and J. Vondrak
Algorithmic Learning Theory (ALT), 2017.
Generalization for Adaptively-chosen Estimators via Stable Median
V. Feldman and T. Steinke
Conference on Learning Theory (COLT), 2017.
Guilt Free Data Reuse
C. 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 queries
V. Feldman and B. Ghazi
Innovations in Theoretical Computer Science (ITCS), 2017.
A General Characterization of the Statistical Query Complexity
V. Feldman
Conference on Learning Theory (COLT), 2017.
Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back
V. Feldman
Neural Information Processing Systems (NIPS), 2016. (Oral)
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.
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.
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.
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.
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 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
SIAM Journal on Computing (SICOMP) , 2015.
Conference on Learning Theory (COLT), 2014.
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.
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.
Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy
M.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 Juntas
V. 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 Distributions
V. Feldman and P. Kothari
Journal of Machine Learning Research (JMLR) , 2016.
Learning Coverage Functions and Private Release of Marginals
V. Feldman and P. Kothari
Conference on Learning Theory (COLT), 2014.
Learning Using Local Membership Queries
P. 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 Trees
V. Feldman, P. Kothari and J. Vondrak
Conference on Learning Theory (COLT), 2013.
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 (JACM) , 2017.
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
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 Spectrum
V. Feldman
Conference on Learning Theory (COLT), 2012.
Distribution-Independent Evolvability of Linear Threshold Functions
V. Feldman
Conference on Learning Theory (COLT), 2011.
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.
Agnostic Learning of Monomials by Halfspaces is Hard
V. 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 Evolvability
V. 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 Comparisons
M. 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 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 (NeCo) 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 (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 Algorithms
V. Feldman
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 (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 Halfspaces
V. 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 Monomials
V. 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 Queries
V. 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 Expressions
V. 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 Classes
M. 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 Queries
N. 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 Packages
A. 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