Vitaly Feldman

According to our database, Vitaly Feldman authored at least 104 papers between 2000 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2023

Faster Convergence with Multiway Preferences.

Aadirupa Saha, Vitaly Feldman, Tomer Koren, Yishay Mansour

CoRR, 2023

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

Martin Pelikan, Sheikh Shams Azam, Vitaly Feldman, Jan Honza Silovsky, Kunal Talwar, Tatiana Likhomanenko

CoRR, 2023

Samplable Anonymous Aggregation for Private Federated Data Analysis.

Kunal Talwar, Shan Wang, Audra McMillan, Vojta Jina, Vitaly Feldman, Bailey Basile, Áine Cahill, Yi Sheng Chan, Mike Chatzidakis, Junye Chen, Oliver Chick, Mona Chitnis, Suman Ganta, Yusuf Goren, Filip Granqvist, Kristine Guo, Frederic Jacobs, Omid Javidbakht, Albert Liu, Richard Low, Dan Mascenik, Steve Myers, David Park, Wonhee Park, Gianni Parsa, Tommy Pauly, Christian Priebe, Rehan Rishi, Guy N. Rothblum, Michael Scaria, Linmao Song, Congzheng Song, Karl Tarbe, Sebastian Vogt, Luke Winstrom, Shundong Zhou

CoRR, 2023

Differentially Private Heavy Hitter Detection using Federated Analytics.

Karan N. Chadha, Junye Chen, John C. Duchi, Vitaly Feldman, Hanieh Hashemi, Omid Javidbakht, Audra McMillan, Kunal Talwar

CoRR, 2023

Stronger Privacy Amplification by Shuffling for Renyi and Approximate Differential Privacy.

Vitaly Feldman, Audra McMillan, Kunal Talwar

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Fast Optimal Locally Private Mean Estimation via Random Projections.

Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar

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.

Hilal Asi, Vitaly Feldman, Tomer Koren, Kunal Talwar

Proceedings of the International Conference on Machine Learning, 2023

Private Online Prediction from Experts: Separations and Faster Rates.

Hilal Asi, Vitaly Feldman, Tomer Koren, Kunal Talwar

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Private Federated Statistics in an Interactive Setting.

Audra McMillan, Omid Javidbakht, Kunal Talwar, Elliot Briggs, Mike Chatzidakis, Junye Chen, John C. Duchi, Vitaly Feldman, Yusuf Goren, Michael Hesse, Vojta Jina, Anil Katti, Albert Liu, Cheney Lyford, Joey Meyer, Alex Palmer, David Park, Wonhee Park, Gianni Parsa, Paul Pelzl, Rehan Rishi, Congzheng Song, Shan Wang, Shundong Zhou

CoRR, 2022

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

Nicholas Carlini, Vitaly Feldman, Milad Nasr

CoRR, 2022

Subspace Recovery from Heterogeneous Data with Non-isotropic Noise.

John C. Duchi, Vitaly Feldman, Lunjia Hu, Kunal Talwar

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.

Rachel Cummings, Vitaly Feldman, Audra McMillan, Kunal Talwar

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.

Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar

Proceedings of the International Conference on Machine Learning, 2022

Optimal Algorithms for Mean Estimation under Local Differential Privacy.

Hilal Asi, Vitaly Feldman, Kunal Talwar

Proceedings of the International Conference on Machine Learning, 2022

2021

Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization.

Vitaly Feldman, Cristóbal Guzmán, Santosh Srinivas Vempala

Math. Oper. Res., 2021

Interaction is Necessary for Distributed Learning with Privacy or Communication Constraints.

Yuval Dagan, Vitaly Feldman

J. Priv. Confidentiality, 2021

Private Stochastic Convex Optimization: Optimal Rates in 𝓁₁ Geometry.

Hilal Asi, Vitaly Feldman, Tomer Koren, Kunal Talwar

CoRR, 2021

When is memorization of irrelevant training data necessary for high-accuracy learning?

Gavin Brown, Mark Bun, Vitaly Feldman, Adam D. Smith, Kunal Talwar

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Individual Privacy Accounting via a Rényi Filter.

Vitaly Feldman, Tijana Zrnic

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.

Vitaly Feldman, Kunal Talwar

Proceedings of the 38th International Conference on Machine Learning, 2021

Private Stochastic Convex Optimization: Optimal Rates in L1 Geometry.

Hilal Asi, Vitaly Feldman, Tomer Koren, Kunal Talwar

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.

Vitaly Feldman, Audra McMillan, Kunal Talwar

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Tight bounds on <i>ℓ</i>₁ approximation and learning of self-bounding functions.

Vitaly Feldman, Pravesh Kothari, Jan Vondrák

Theor. Comput. Sci., 2020

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

Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Shuang Song, Kunal Talwar, Abhradeep Thakurta

CoRR, 2020

Private stochastic convex optimization: optimal rates in linear time.

Vitaly Feldman, Tomer Koren, Kunal Talwar

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Does learning require memorization? a short tale about a long tail.

Vitaly Feldman

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.

Vitaly Feldman, Chiyuan Zhang

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.

Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, Kunal Talwar

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.

Yuval Dagan, Vitaly Feldman

Proceedings of the Conference on Learning Theory, 2020

2019

Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity.

Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, Abhradeep Thakurta

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Locally Private Learning without Interaction Requires Separation.

Amit Daniely, Vitaly Feldman

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.

Raef Bassily, Vitaly Feldman, Kunal Talwar, Abhradeep Guha Thakurta

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.

Vitaly Feldman, Roy Frostig, Moritz Hardt

Proceedings of the 36th International Conference on Machine Learning, 2019

High probability generalization bounds for uniformly stable algorithms with nearly optimal rate.

Vitaly Feldman, Jan Vondrák

Proceedings of the Conference on Learning Theory, 2019

Open Problem: How fast can a multiclass test set be overfit?

Vitaly Feldman, Roy Frostig, Moritz Hardt

Proceedings of the Conference on Learning Theory, 2019

Open Problem: Is Margin Sufficient for Non-Interactive Private Distributed Learning?

Amit Daniely, Vitaly Feldman

Proceedings of the Conference on Learning Theory, 2019

2018

Learning without Interaction Requires Separation.

Amit Daniely, Vitaly Feldman

CoRR, 2018

The Everlasting Database: Statistical Validity at a Fair Price.

Blake E. Woodworth, Vitaly Feldman, Saharon Rosset, Nati Srebro

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.

Vitaly Feldman, Jan Vondrák

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Privacy Amplification by Iteration.

Vitaly Feldman, Ilya Mironov, Kunal Talwar, Abhradeep Thakurta

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Calibrating Noise to Variance in Adaptive Data Analysis.

Vitaly Feldman, Thomas Steinke

Proceedings of the Conference On Learning Theory, 2018

Privacy-preserving Prediction.

Cynthia Dwork, Vitaly Feldman

Proceedings of the Conference On Learning Theory, 2018

2017

Statistical Algorithms and a Lower Bound for Detecting Planted Cliques.

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, Ying Xiao

J. ACM, 2017

Guilt-free data reuse.

Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth

Commun. ACM, 2017

On the Power of Learning from k-Wise Queries.

Vitaly Feldman, Badih Ghazi

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Generalization for Adaptively-chosen Estimators via Stable Median.

Vitaly Feldman, Thomas Steinke

Proceedings of the 30th Conference on Learning Theory, 2017

A General Characterization of the Statistical Query Complexity.

Vitaly Feldman

Proceedings of the 30th Conference on Learning Theory, 2017

Tight Bounds on ℓ₁ Approximation and Learning of Self-Bounding Functions.

Vitaly Feldman, Pravesh Kothari, Jan Vondrák

Proceedings of the International Conference on Algorithmic Learning Theory, 2017

Dealing with Range Anxiety in Mean Estimation via Statistical Queries.

Vitaly Feldman

Proceedings of the International Conference on Algorithmic Learning Theory, 2017

2016

Statistical Query Learning.

Vitaly Feldman

Encyclopedia of Algorithms, 2016

Hardness of Proper Learning.

Vitaly Feldman

Encyclopedia of Algorithms, 2016

Sorting and Selection with Imprecise Comparisons.

Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson

ACM Trans. Algorithms, 2016

Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas.

Vitaly Feldman, Jan Vondrák

SIAM J. Comput., 2016

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

Vitaly Feldman

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.

Vitaly Feldman, Alexander Rakhlin

Proceedings of the 29th Conference on Learning Theory, 2016

2015

Sample Complexity Bounds on Differentially Private Learning via Communication Complexity.

Vitaly Feldman, David Xiao

SIAM J. Comput., 2015

Agnostic learning of disjunctions on symmetric distributions.

Vitaly Feldman, Pravesh Kothari

J. Mach. Learn. Res., 2015

Statistical Query Algorithms for Stochastic Convex Optimization.

Vitaly Feldman, Cristóbal Guzmán, Santosh S. Vempala

CoRR, 2015

Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy.

Maria-Florina Balcan, Vitaly Feldman

Algorithmica, 2015

Preserving Statistical Validity in Adaptive Data Analysis.

Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Leon Roth

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Approximate resilience, monotonicity, and the complexity of agnostic learning.

Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan, Andrew Wan, Karl Wimmer

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.

Vitaly Feldman, Will Perkins, Santosh S. Vempala

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.

Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth

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.

Vitaly Feldman, Jan Vondrák

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces.

Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio

J. ACM, 2014

On the Complexity of Random Satisfiability Problems with Planted Solutions.

Vitaly Feldman, Will Perkins, Santosh S. Vempala

Electron. Colloquium Comput. Complex., 2014

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

Vitaly Feldman, Will Perkins, Santosh S. Vempala

CoRR, 2014

Nearly Tight Bounds on ℓ₁ Approximation of Self-Bounding Functions.

Vitaly Feldman, Pravesh Kothari, Jan Vondrák

CoRR, 2014

Learning Coverage Functions and Private Release of Marginals.

Vitaly Feldman, Pravesh Kothari

Proceedings of The 27th Conference on Learning Theory, 2014

Open Problem: The Statistical Query Complexity of Learning Sparse Halfspaces.

Vitaly Feldman

Proceedings of The 27th Conference on Learning Theory, 2014

2013

Structure and learning of valuation functions.

Vitaly Feldman, Jan Vondrák

SIGecom Exch., 2013

Learning Coverage Functions

Vitaly Feldman, Pravesh Kothari

CoRR, 2013

Provenance-based dictionary refinement in information extraction.

Sudeepa Roy, Laura Chiticariu, Vitaly Feldman, Frederick Reiss, Huaiyu Zhu

Proceedings of the ACM SIGMOD International Conference on Management of Data, 2013

Statistical Active Learning Algorithms.

Maria-Florina Balcan, Vitaly Feldman

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.

Andrew S. Cassidy, Paul Merolla, John V. Arthur, Steven K. Esser, Bryan L. Jackson, Rodrigo Alvarez-Icaza, Pallab Datta, Jun Sawada, Theodore M. Wong, Vitaly Feldman, Arnon Amir, Daniel Ben Dayan Rubin, Filipp Akopyan, Emmett McQuinn, William P. Risk, Dharmendra S. Modha

Proceedings of the 2013 International Joint Conference on Neural Networks, 2013

Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees.

Vitaly Feldman, Pravesh Kothari, Jan Vondrák

Proceedings of the COLT 2013, 2013

Learning Using Local Membership Queries.

Pranjal Awasthi, Vitaly Feldman, Varun Kanade

Proceedings of the COLT 2013, 2013

2012

Computational Bounds on Statistical Query Learning.

Vitaly Feldman, Varun Kanade

Proceedings of the COLT 2012, 2012

Learning DNF Expressions from Fourier Spectrum.

Vitaly Feldman

Proceedings of the COLT 2012, 2012

A complete characterization of statistical query learning with applications to evolvability.

Vitaly Feldman

J. Comput. Syst. Sci., 2012

Statistical Algorithms and a Lower Bound for Planted Clique.

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, Ying Xiao

Electron. Colloquium Comput. Complex., 2012

The Complexity of Statistical Algorithms

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala

CoRR, 2012

2011

Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas.

Vitaly Feldman, Homin K. Lee, Rocco A. Servedio

Proceedings of the COLT 2011, 2011

Distribution-Independent Evolvability of Linear Threshold Functions.

Vitaly Feldman

Proceedings of the COLT 2011, 2011

2010

Agnostic Learning of Monomials by Halfspaces is Hard.

Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu

Electron. Colloquium Comput. Complex., 2010

Distribution-Specific Agnostic Boosting.

Vitaly Feldman

Proceedings of the Innovations in Computer Science, 2010

2009

Separating models of learning with faulty teachers.

Vitaly Feldman, Shrenik Shah

Theor. Comput. Sci., 2009

On Agnostic Learning of Parities, Monomials, and Halfspaces.

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami

SIAM J. Comput., 2009

Experience-Induced Neural Circuits That Achieve High Capacity.

Vitaly Feldman, Leslie G. Valiant

Neural Comput., 2009

On The Power of Membership Queries in Agnostic Learning.

Vitaly Feldman

J. Mach. Learn. Res., 2009

Hardness of approximate two-level logic minimization and PAC learning with membership queries.

Vitaly Feldman

J. Comput. Syst. Sci., 2009

Robustness of Evolvability.

Vitaly Feldman

Proceedings of the COLT 2009, 2009

2008

Statistical Query Learning.

Vitaly Feldman

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Hardness of Proper Learning.

Vitaly Feldman

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

The complexity of properly learning simple concept classes.

Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi

J. Comput. Syst. Sci., 2008

Evolvability from learning algorithms.

Vitaly Feldman

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

The Learning Power of Evolution.

Vitaly Feldman, Leslie G. Valiant

Proceedings of the 21st Annual Conference on Learning Theory, 2008

2007

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

Vitaly Feldman

J. Mach. Learn. Res., 2007

Separating Models of Learning with Faulty Teachers.

Vitaly Feldman, Shrenik Shah, Neal Wadhwa

Proceedings of the Algorithmic Learning Theory, 18th International Conference, 2007

2006

New Results for Learning Noisy Parities and Halfspaces.

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami

Electron. Colloquium Comput. Complex., 2006

Optimal Hardness Results for Maximizing Agreements with Monomials.

Vitaly Feldman

Electron. Colloquium Comput. Complex., 2006

2004

Learnability and Automatizability.

Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2002

On Using Extended Statistical Queries to Avoid Membership Queries.

Nader H. Bshouty, Vitaly Feldman

J. Mach. Learn. Res., 2002

2000

Sealed calls in Java packages.

Ayal Zaks, Vitaly Feldman, Nava Aizikowitz

Proceedings of the 2000 ACM SIGPLAN Conference on Object-Oriented Programming Systems, 2000