Vitaly Feldman

Orcid: 0000-0002-3904-759X

Affiliations:
  • IBM Almaden Research Center


According to our database1, Vitaly Feldman authored at least 106 papers between 2000 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Instance-Optimal Private Density Estimation in the Wasserstein Distance.
CoRR, 2024

Differentially Private Heavy Hitter Detection using Federated Analytics.
Proceedings of the IEEE Conference on Secure and Trustworthy Machine Learning, 2024

Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages.
Proceedings of the Forty-first International Conference on Machine Learning, 2024

Faster Convergence with MultiWay Preferences.
Proceedings of the International Conference on Artificial Intelligence and Statistics, 2024

2023
Federated Learning with Differential Privacy for End-to-End Speech Recognition.
CoRR, 2023

Samplable Anonymous Aggregation for Private Federated Data Analysis.
CoRR, 2023

Stronger Privacy Amplification by Shuffling for Renyi and Approximate Differential Privacy.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Fast Optimal Locally Private Mean Estimation via Random Projections.
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime.
Proceedings of the International Conference on Machine Learning, 2023

Private Online Prediction from Experts: Separations and Faster Rates.
Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022
Private Federated Statistics in an Interactive Setting.
CoRR, 2022

No Free Lunch in "Privacy for Free: How does Dataset Condensation Help Privacy".
CoRR, 2022

Subspace Recovery from Heterogeneous Data with Non-isotropic Noise.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Mean Estimation with User-level Privacy under Data Heterogeneity.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Private frequency estimation via projective geometry.
Proceedings of the International Conference on Machine Learning, 2022

Optimal Algorithms for Mean Estimation under Local Differential Privacy.
Proceedings of the International Conference on Machine Learning, 2022

2021
Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization.
Math. Oper. Res., 2021

Interaction is Necessary for Distributed Learning with Privacy or Communication Constraints.
J. Priv. Confidentiality, 2021

Private Stochastic Convex Optimization: Optimal Rates in 𝓁<sub>1</sub> Geometry.
CoRR, 2021

When is memorization of irrelevant training data necessary for high-accuracy learning?
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Individual Privacy Accounting via a Rényi Filter.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Lossless Compression of Efficient Private Local Randomizers.
Proceedings of the 38th International Conference on Machine Learning, 2021

Private Stochastic Convex Optimization: Optimal Rates in L1 Geometry.
Proceedings of the 38th International Conference on Machine Learning, 2021

Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020
Tight bounds on <i>ℓ</i><sub>1</sub> approximation and learning of self-bounding functions.
Theor. Comput. Sci., 2020

Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation.
CoRR, 2020

Private stochastic convex optimization: optimal rates in linear time.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Does learning require memorization? a short tale about a long tail.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

PAC learning with stable and private predictions.
Proceedings of the Conference on Learning Theory, 2020

2019
Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Locally Private Learning without Interaction Requires Separation.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Private Stochastic Convex Optimization with Optimal Rates.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

The advantages of multiple classes for reducing overfitting from test set reuse.
Proceedings of the 36th International Conference on Machine Learning, 2019

High probability generalization bounds for uniformly stable algorithms with nearly optimal rate.
Proceedings of the Conference on Learning Theory, 2019

Open Problem: How fast can a multiclass test set be overfit?
Proceedings of the Conference on Learning Theory, 2019

Open Problem: Is Margin Sufficient for Non-Interactive Private Distributed Learning?
Proceedings of the Conference on Learning Theory, 2019

2018
On the Complexity of Random Satisfiability Problems with Planted Solutions.
SIAM J. Comput., 2018

Learning without Interaction Requires Separation.
CoRR, 2018

The Everlasting Database: Statistical Validity at a Fair Price.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Generalization Bounds for Uniformly Stable Algorithms.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Privacy Amplification by Iteration.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Calibrating Noise to Variance in Adaptive Data Analysis.
Proceedings of the Conference On Learning Theory, 2018

Privacy-preserving Prediction.
Proceedings of the Conference On Learning Theory, 2018

2017
Statistical Algorithms and a Lower Bound for Detecting Planted Cliques.
J. ACM, 2017

Guilt-free data reuse.
Commun. ACM, 2017

On the Power of Learning from k-Wise Queries.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Generalization for Adaptively-chosen Estimators via Stable Median.
Proceedings of the 30th Conference on Learning Theory, 2017

A General Characterization of the Statistical Query Complexity.
Proceedings of the 30th Conference on Learning Theory, 2017

Tight Bounds on ℓ<sub>1</sub> Approximation and Learning of Self-Bounding Functions.
Proceedings of the International Conference on Algorithmic Learning Theory, 2017

Dealing with Range Anxiety in Mean Estimation via Statistical Queries.
Proceedings of the International Conference on Algorithmic Learning Theory, 2017

2016
Statistical Query Learning.
Encyclopedia of Algorithms, 2016

Hardness of Proper Learning.
Encyclopedia of Algorithms, 2016

Sorting and Selection with Imprecise Comparisons.
ACM Trans. Algorithms, 2016

Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas.
SIAM J. Comput., 2016

Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back.
Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

Conference on Learning Theory 2016: Preface.
Proceedings of the 29th Conference on Learning Theory, 2016

2015
Sample Complexity Bounds on Differentially Private Learning via Communication Complexity.
SIAM J. Comput., 2015

Agnostic learning of disjunctions on symmetric distributions.
J. Mach. Learn. Res., 2015

Statistical Query Algorithms for Stochastic Convex Optimization.
CoRR, 2015

Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy.
Algorithmica, 2015

Preserving Statistical Validity in Adaptive Data Analysis.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Approximate resilience, monotonicity, and the complexity of agnostic learning.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's.
Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Generalization in Adaptive Data Analysis and Holdout Reuse.
Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014
Subsampled Power Iteration: a New Algorithm for Block Models and Planted CSP's.
CoRR, 2014

Nearly Tight Bounds on ℓ<sub>1</sub> Approximation of Self-Bounding Functions.
CoRR, 2014

Learning Coverage Functions and Private Release of Marginals.
Proceedings of The 27th Conference on Learning Theory, 2014

Open Problem: The Statistical Query Complexity of Learning Sparse Halfspaces.
Proceedings of The 27th Conference on Learning Theory, 2014

2013
Structure and learning of valuation functions.
SIGecom Exch., 2013

Learning Coverage Functions
CoRR, 2013

Provenance-based dictionary refinement in information extraction.
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2013

Statistical Active Learning Algorithms.
Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013

Cognitive computing building block: A versatile and efficient digital neuron model for neurosynaptic cores.
Proceedings of the 2013 International Joint Conference on Neural Networks, 2013

Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees.
Proceedings of the COLT 2013, 2013

Learning Using Local Membership Queries.
Proceedings of the COLT 2013, 2013

2012
Agnostic Learning of Monomials by Halfspaces Is Hard.
SIAM J. Comput., 2012

Computational Bounds on Statistical Query Learning.
Proceedings of the COLT 2012, 2012

Learning DNF Expressions from Fourier Spectrum.
Proceedings of the COLT 2012, 2012

A complete characterization of statistical query learning with applications to evolvability.
J. Comput. Syst. Sci., 2012

Statistical Algorithms and a Lower Bound for Planted Clique.
Electron. Colloquium Comput. Complex., 2012

Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces.
Electron. Colloquium Comput. Complex., 2012

The Complexity of Statistical Algorithms
CoRR, 2012

2011
Distribution-Independent Evolvability of Linear Threshold Functions.
Proceedings of the COLT 2011, 2011

2010
Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas.
Electron. Colloquium Comput. Complex., 2010

Distribution-Specific Agnostic Boosting.
Proceedings of the Innovations in Computer Science, 2010

2009
Separating models of learning with faulty teachers.
Theor. Comput. Sci., 2009

On Agnostic Learning of Parities, Monomials, and Halfspaces.
SIAM J. Comput., 2009

Experience-Induced Neural Circuits That Achieve High Capacity.
Neural Comput., 2009

Hardness of approximate two-level logic minimization and PAC learning with membership queries.
J. Comput. Syst. Sci., 2009

Robustness of Evolvability.
Proceedings of the COLT 2009, 2009

2008
Statistical Query Learning.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Hardness of Proper Learning.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

The complexity of properly learning simple concept classes.
J. Comput. Syst. Sci., 2008

On The Power of Membership Queries in Agnostic Learning.
Electron. Colloquium Comput. Complex., 2008

Evolvability from learning algorithms.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

The Learning Power of Evolution.
Proceedings of the 21st Annual Conference on Learning Theory, 2008

2007
Separating Models of Learning with Faulty Teachers.
Proceedings of the Algorithmic Learning Theory, 18th International Conference, 2007

2006
New Results for Learning Noisy Parities and Halfspaces.
Electron. Colloquium Comput. Complex., 2006

On Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions.
Electron. Colloquium Comput. Complex., 2006

Optimal Hardness Results for Maximizing Agreements with Monomials.
Electron. Colloquium Comput. Complex., 2006

2004
Learnability and Automatizability.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2002
On Using Extended Statistical Queries to Avoid Membership Queries.
J. Mach. Learn. Res., 2002

2000
Sealed calls in Java packages.
Proceedings of the 2000 ACM SIGPLAN Conference on Object-Oriented Programming Systems, 2000


  Loading...