Vitaly Feldman

Local Pan-privacy for Federated Analytics ICML 2025 Trade-offs in Data Memorization via Strong Data Processing Inequalities COLT 2025 Instance-Optimal Private Density Estimation in the Wasserstein Distance NIPS 2024 Private and Personalized Frequency Estimation in a Federated Setting NIPS 2024 Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages ICML 2024 Faster Convergence with MultiWay Preferences AISTATS 2024 Fast Optimal Locally Private Mean Estimation via Random Projections NIPS 2023 Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime ICML 2023 Private Online Prediction from Experts: Separations and Faster Rates COLT 2023 Optimal Algorithms for Mean Estimation under Local Differential Privacy ICML 2022 Private frequency estimation via projective geometry ICML 2022 Subspace Recovery from Heterogeneous Data with Non-isotropic Noise NIPS 2022 Mean Estimation with User-level Privacy under Data Heterogeneity NIPS 2022 Algorithmic Learning Theory 2021: Preface ALT 2021 Lossless Compression of Efficient Private Local Randomizers ICML 2021 Individual Privacy Accounting via a Rényi Filter NIPS 2021 Private Stochastic Convex Optimization: Optimal Rates in L1 Geometry ICML 2021 PAC learning with stable and private predictions COLT 2020 What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation NIPS 2020 Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses NIPS 2020 Private Stochastic Convex Optimization with Optimal Rates NIPS 2019 Locally Private Learning without Interaction Requires Separation NIPS 2019 High probability generalization bounds for uniformly stable algorithms with nearly optimal rate COLT 2019 Open Problem: Is Margin Sufficient for Non-Interactive Private Distributed Learning? COLT 2019 Open Problem: How fast can a multiclass test set be overfit? COLT 2019 The advantages of multiple classes for reducing overfitting from test set reuse ICML 2019 The Everlasting Database: Statistical Validity at a Fair Price NIPS 2018 Calibrating Noise to Variance in Adaptive Data Analysis COLT 2018 Privacy-preserving Prediction COLT 2018 Generalization Bounds for Uniformly Stable Algorithms NIPS 2018 Generalization for Adaptively-chosen Estimators via Stable Median COLT 2017 Tight Bounds on $\ell_1$ Approximation and Learning of Self-Bounding Functions ALT 2017 A General Characterization of the Statistical Query Complexity COLT 2017 Dealing with Range Anxiety in Mean Estimation via Statistical Queries ALT 2017 Conference on Learning Theory 2016: Preface COLT 2016 Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back NIPS 2016 Agnostic Learning of Disjunctions on Symmetric Distributions JMLR 2015 Generalization in Adaptive Data Analysis and Holdout Reuse NIPS 2015 Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's NIPS 2015 Open Problem: The Statistical Query Complexity of Learning Sparse Halfspaces COLT 2014 Learning Coverage Functions and Private Release of Marginals COLT 2014 Sample Complexity Bounds on Differentially Private Learning via Communication Complexity COLT 2014 Statistical Active Learning Algorithms NIPS 2013 Learning Using Local Membership Queries COLT 2013 Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees COLT 2013 Computational Bounds on Statistical Query Learning COLT 2012 Learning DNF Expressions from Fourier Spectrum COLT 2012 Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas COLT 2011 Distribution-Independent Evolvability of Linear Threshold Functions COLT 2011 On The Power of Membership Queries in Agnostic Learning JMLR 2009 Attribute-Efficient and Non-adaptive Learning of Parities and DNF Expressions JMLR 2007 On Using Extended Statistical Queries to Avoid Membership Queries JMLR 2002