Publications

Note: This webpage is often slightly out of date. An overhaul of this webpage also accidentally removed all copies of slide presentations. I'm working on it.

Preprints and unpublished notes

• Distribution free M-estimation, Felipe Areces and John Duchi. (pdf)

• A Few Observations on Sample-Conditional Coverage in Conformal Prediction, John Duchi. (pdf)

• On Privately Estimating a Single Parameter, Hilal Asi, John Duchi, Kunal Talwar. (pdf)

• A fast and slightly robust covariance estimator John Duchi, Saminul Haque, Rohith Kuditipudi. (pdf)

• Geometry, Computation, and Optimality in Stochastic Optimization, Chen Cheng, John C. Duchi, Daniel Levy. (pdf)

• Resampling methods for private statistical inference, Karan Chadha, John Duchi, Rohith Kuditipudi. (pdf)

• PPI++: Efficient Prediction-Powered Inference, Anastasios N. Angelopoulos, John C. Duchi, Tijana Zrnic. (pdf)

• How many labelers do you have? A closer look at gold-standard labels, Chen Cheng, Hilal Asi, John Duchi. (pdf), (slides)

• Query-Adaptive Predictive Inference with Partial Labels, Maxime Cauchois and John Duchi. (pdf)

• The Lifecycle of a Statistical Model: Model Failure Detection, Identification, and Refitting, Alnur Ali, Maxime Cauchois, John C. Duchi. (pdf)

• A comment and erratum on “Excess Optimism: How Biased is the Apparent Error of an Estimator Tuned by SURE?”, Maxime Cauchois, Alnur Ali, John Duchi (pdf)

• Near Instance-Optimality in Differential Privacy, Hilal Asi and John Duchi. (pdf)

• Protection Against Reconstruction and Its Applications in Private Federated Learning, Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, Ryan Rogers. (pdf)

• Local Minimax Complexity of Stochastic Convex Optimization, Yuancheng Zhu, Sabyasachi Chatterjee, John C. Duchi, John Lafferty. (pdf)

• Privacy and Statistical Risk: Formalisms and Minimax Bounds, Rina F. Barber and John C. Duchi. (pdf)

Books, expository writing, and lecture notes

• Information Theory and Statistics, John Duchi. Lecture Notes for Statistics 311/Electrical Engineering 377, Stanford University. 2025.

• Introductory Lectures on Stochastic Convex Optimization, John C. Duchi. Park City Mathematics Institute, Graduate Summer School Lectures, July 2016.

Journal Articles

• Robust Validation: Confident Predictions Even When Distributions Shift, Maxime Cauchois, Suyash Gupta, Alnur Ali, John Duchi. Journal of the American Statistical Association 119(548): pages 3033–3044. 2024. (pdf, doi)

• Predictive Inference in Multi-environment Scenarios, John C. Duchi, Suyash Gupta, Kuanhao Jiang, Pragya Sur. Statistical Science, to appear. 2025. (pdf)

• Predictive Inference with Weak Supervision, Maxime Cauchois, Suyash Gupta, Alnur Ali, John Duchi. Journal of Machine Learning Research 25(118): pages 1–45. 2024. (pdf)

• The Right Complexity Measure in Locally Private Estimation: It is not the Fisher Information, John Duchi and Feng Ruan. Annals of Statistics 52(1): pages 1–51. 2024. (pdf)

• Distributionally Robust Losses for Latent Covariate Mixtures, John Duchi, Tatsunori Hashimoto, and Hongseok Namkoong. Operations Research, 71(2): pages 649-664. 2022. (pdf)

• Lower Bounds for Non-Convex Stochastic Optimization, Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, Blake Woodworth. Mathematical Programming, Series A, 199: pages 165–214. 2023. (pdf)

• Bounds on the conditional and average treatment effect in the presence of unobserved confounders, Steve Yadlowsky, Hongseok Namkoong, Sanjay Basu, John Duchi, and Lu Tian. Annals of Statistics 50(5), pages 2587-2615, 2022. (pdf)

• Mean Estimation from One-Bit Measurements, Alon Kipnis, John Duchi. IEEE Transactions on Information Theory, 68(9), pages 6276-6296, 2022. (pdf)

• Knowing what you know: valid and validated confidence sets in multiclass and multilabel prediction, Maxime Cauchois, Suyash Gupta, John Duchi. Journal of Machine Learning Research, 22(81), pages 1-42, 2021. (pdf)

• Learning Models with Uniform Performance via Distributionally Robust Optimization, John Duchi and Hongseok Namkoong. Annals of Statistics, 49(3), pages 1378-1406, 2021. (pdf)

• Statistics of Robust Optimization: a Generalized Empirical Likelihood Approach, John Duchi, Peter Glynn, Hongseok Namkoong. Mathematics of Operations Research, 46(3), pages 946-969, 2021. (pdf)

• First-Order Methods for Nonconvex Quadratic Minimization, Yair Carmon and John Duchi. SIAM Review, 62(2), pages 395-436, May 2020. SIGEST Award Paper. (pdf)

• The importance of better models in stochastic optimization, Hilal Asi and John Duchi. Proceedings of the National Academy of Sciences (PNAS) 116 (46), pages 22924-22930, 2019. (pdf), (PNAS copy), (slides)

• Lower Bounds for Finding Stationary Points II: First-Order Methods, Yair Carmon, John Duchi, Oliver Hinder, Aaron Sidford. Mathematical Programming, Series A 185, pages 315-355, 2021. (pdf), (Mathprog copy)

• Comments on Michael Jordan's essay “Artificial Intelligence: The revolution hasn't happened yet”, Emmanuel Candes, John Duchi, and Chiara Sabatti. Harvard Data Science Review, Issue 1, 2019. (pdf)

• Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity, Hilal Asi and John Duchi. SIAM Journal on Optimization 29(3), pp. 2257–2290, 2019. (pdf) (SIAM copy)

• Lower Bounds for Finding Stationary Points I, Yair Carmon, John Duchi, Oliver Hinder, Aaron Sidford. Mathematical Programming, Series A 184: pages 71–120. 2020. (pdf) (Mathprog copy)

• Asymptotic Optimality in Stochastic Optimization, John Duchi, Feng Ruan. Annals of Statistics 49(1): pages 21–48. 2021. (pdf, Annals copy)

• Gradient Descent Finds the Cubic-Regularized Nonconvex Newton Step, Yair Carmon, John Duchi. SIAM Journal on Optimization 29(3), pp. 2146–2178, 2019 (pdf) (SIAM copy)

• Variance-based regularization with convex objectives, John Duchi, Hongseok Namkoong. Journal of Machine Learning Research 20(68), pages 1–55, 2019. (pdf)

• Stochastic Methods for Composite and Weakly Convex Optimization Problems, John Duchi and Feng Ruan. SIAM Journal on Optimization, 28(4), pages 3229–3259, 2018. (pdf)

• Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval, John Duchi, Feng Ruan. Information and Inference, a Journal of the IMA iay015, 2018. (pdf) (slides) (code)

• Accelerated Methods for Non-Convex Optimization, Yair Carmon, John Duchi, Oliver Hinder, Aaron Sidford. SIAM Journal on Optimization 28(2), pages 1751–1772, 2018. (pdf)

• Multiclass Classification, Information, Divergence, and Surrogate Risk, John C. Duchi, Khashayar Khosravi, and Feng Ruan. Annals of Statistics 46(6b), pages 3246–3275, 2018. (pdf)

• Minimax Optimal Procedures for Locally Private Estimation, John C. Duchi, Michael I. Jordan, Martin J. Wainwright. Journal of the American Statistical Association (with discussion) 113, pages 182–201. 2018. (pdf) (code and data)

• Optimal rates for zero-order optimization: the power of two function evaluations, John C. Duchi, Michael I. Jordan, Martin J. Wainwright, Andre Wibisono. IEEE Transactions on Information Theory 61(5): 2788–2806, 2015. (pdf) (slides)

• Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates, Yuchen Zhang, John C. Duchi, and Martin J. Wainwright. Journal of Machine Learning Research, 2015. (pdf)

• Privacy Aware Learning, John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Journal of the Association for Computing Machinery, 2014. (pdf)

• The Asymptotics of Ranking Algorithms, John C. Duchi, Lester Mackey, Michael I. Jordan. Annals of Statistics 41(5):2292–2323, 2013. (pdf)

• Communication-Efficient Algorithms for Statistical Optimization, Yuchen Zhang, John C. Duchi, and Martin Wainwright. Journal of Machine Learning Research 14(Nov):3321–3363, 2013. (pdf)

• The Generalization Ability of Online Algorithms for Dependent Data, Alekh Agarwal and John C. Duchi. IEEE Transactions on Information Theory (2013). (pdf)

• Ergodic Mirror Descent, John C. Duchi, Alekh Agarwal, Mikael Johansson, Michael I. Jordan. SIAM Journal on Optimization (SIOPT), 2012. (pdf)

• Randomized Smoothing for Stochastic Optimization, John Duchi, Peter L. Bartlett, and Martin Wainwright. SIAM Journal on Optimization (SIOPT), 2012. (pdf)

• Dual Averaging for Distributed Optimization: Convergence and Network Scaling, John Duchi, Alekh Agarwal, and Martin Wainwright. IEEE Transactions on Automatic Control (March 2012). (pdf)

• Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, John Duchi, Elad Hazan, and and Yoram Singer. Journal of Machine Learning Research (JMLR 2011). (pdf)

• Online and Batch Learning using Forward Backward Splitting, John Duchi and Yoram Singer. Journal of Machine Learning Research (JMLR 2009) and Neural Information Processing Systems (NeurIPS 2009). (pdf)

Ph.D. Thesis

• Multiple Optimality Guarantees in Statistical Learning, John C. Duchi. Ph.D. Thesis, Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, 2014. (pdf) Association for Computing Machinery Dissertation Award (honorable mention)

Conference Proceedings

• Online Conformal Prediction via Online Optimization, Felipe Areces, Christopher Mohri, Tatsunori Hashimoto, John Duchi. Fourty-Second International Conference on Machine Learning (ICML), 2025.

• Universally Instance-Optimal Mechanisms for Private Statistical Estimation, Hilal Asi, John C. Duchi, Saminul Haque, Zewei Li, Feng Ruan. Conference on Learning Theory (COLT) 37, 2024.

• Two fundamental limits for uncertainty quantification in predictive inference, Felipe Areces, Chen Cheng, John Duchi, Rohith Kuditipudi. Conference on Computational Learning Theory (COLT) 37, 2024.

• Collaboratively Learning Linear Models with Structured Missing Data, Chen Cheng, Gary Cheng, John Duchi. Neural Information Processing Systems 23, 2023.

• Differentially private heavy hitter detection using federated analytics, Karan Chadha, Junye Chen, John Duchi, Vitaly Feldman, Hanieh Hashemi, Omid Javidbakht, Audra McMillan, Kunal Talwar. Proceedings of the 39th International Conference on Machine Learning, 2023.

• A Fast Algorithm for Adaptive Private Mean Estimation, John Duchi, Saminul Haque, Rohith Kuditipudi. Conference on Learning Theory (COLT), 2023. (pdf) Winner of best student paper award.

• Federated Asymptotics: a model to compare federated learning algorithms, Gary Cheng, Karan Chadha, John Duchi. Artificial Intelligence and Statistics (AISTATS), 2023. (pdf)

• Subspace Recovery from Heterogeneous Data with Non-isotropic Noise, John Duchi, Vitaly Feldman, Lunjia Hu, Kunal Talwar. Neural Information Processing Systems (NeurIPS), 2022. (pdf)

• Private optimization in the interpolation regime: faster rates and hardness results, Hilal Asi, Karan Chadha, Gary Cheng, John Duchi. International Conference on Machine Learning (ICML), 2022. (pdf)

• Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization, Karan Chadha, Gary Cheng, John Duchi. International Conference on Machine Learning (ICML), 2022. (pdf)

• Memorize to Generalize: on the Necessity of Interpolation in High Dimensional Linear Regression“, Chen Cheng, John Duchi, Rohith Kuditipudi, Conference on Learning Theory (COLT), 2022. (pdf)

• Adapting to Function Difficulty and Growth Conditions in Private Optimization, Hilal Asi, Daniel Levy, John Duchi. Advances in Neural Information Processing Systems (NeurIPS) 35, 2021. (pdf)

• Private adaptive gradient methods for convex optimization, Hilal Asi, John Duchi, Alireza Fallah, Omid Javidbakht, Kunal Talwar. International Conference on Machine Learning (ICML), 2021. (pdf)

• On Misspecification in Prediction Problems and Robustness via Improper Learning, John Duchi, Annie Marsden, Gregory Valiant. Artificial Intelligence and Statistics (AISTATS), 2021. (pdf) Selected for oral presentation.

• A constrained risk inequality for general losses, John Duchi and Feng Ruan. Artificial Intelligence and Statistics (AISTATS), 2021. (pdf) Selected for oral presentation.

• Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms, Hilal Asi and John Duchi. Neural Information Processing Systems (NeurIPS), 2020. (pdf)

• Minibatch Stochastic Approximate Proximal Point Methods, Hilal Asi, Karan Chadha, Gary Cheng, John C. Duchi. Neural Information Processing Systems (NeurIPS), 2020. (pdf)

• Neural Bridge Sampling for Evaluating Safety-Critical Autonomous Systems, Aman Sinha, Matthew O'Kelly, Russ Tedrake, John C. Duchi. Neural Information Processing Systems (NeurIPS), 2020. (pdf)

• Conic Descent and its Application to Memory-efficient Optimization over Positive Semidefinite Matrices, John C. Duchi, Oliver Hinder, Andrew Naber, Yinyu Ye. Neural Information Processing Systems (NeurIPS), 2020. (pdf)

• Large-Scale Methods for Distributionally Robust Optimization, Daniel Levy, Yair Carmon, John C. Duchi. Neural Information Processing Systems (NeurIPS), 2020. (pdf)

• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations, Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Ayush Sekhari, and Karthik Sridharan. Conference on Learning Theory (COLT) 2020 (pdf)

• FormulaZero: Distributionally Robust Online Adaptation via Offline Population Synthesis, Aman Sinha, Matthew O'Kelly, Hongrui Zheng, Rahul Mangharam, John Duchi, Russ Tedrake. International Conference on Machine Learning (ICML) 2020. (pdf)

• Understanding and Mitigating the Tradeoff Between Robustness and Accuracy, Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John Duchi, Percy Liang. International Conference on Machine Learning (ICML) 2020. (pdf)

• Necessary and Sufficient Geometries for Adaptive Gradient Algorithms, John Duchi and Daniel Levy. Neural Information Processing Systems (NeurIPS) 2019. (pdf) Selected for oral presentation.

• Unlabeled Data Improves Adversarial Robustness, Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, Percy Liang, John Duchi. Neural Information Processing Systems (NeurIPS) 2019. (pdf)

• A Rank-1 Sketch for Matrix Multiplicative Weights, Yair Carmon, John Duchi, Aaron Sidford, Kevin Tian. Conference on Learning Theory (COLT) 2019. (pdf)

• Lower Bounds for Locally Private Estimation via Communication Complexity, John Duchi and Ryan Rogers. Conference on Learning Theory (COLT) 2019. (pdf)

• Modeling simple structures and geometry for better stochastic optimization algorithms, Hilal Asi and John Duchi. Artificial Intelligence and Statistics (AISTATS) 2019. (pdf)

• Analysis of Krylov Subspace Solutions of Regularized Nonconvex Quadratic Problems, Yair Carmon and John Duchi. Neural Information Processing Systems (NeurIPS) 2018. (pdf) Selected for oral presentation.

• Generalizing to Unseen Domains via Adversarial Data Augmentation, Riccardo Volpi, Hongseok Namkoong, Ozan Sener, John Duchi, Vittorio Murino, and Silvio Savarese. Neural Information Processing Systems (NeurIPS) 2018. (pdf)

• Scalable End-to-End Autonomous Vehicle Testing via Rare-event Simulation, Matthew O'Kelly, Aman Sinha, Hongseok Namkoong, Russ Tedrake, and John Duchi. Neural Information Processing Systems (NeurIPS) 2018. (pdf)

• Minimax Bounds on Stochastic Batched Convex Optimization, John Duchi, Feng Ruan, and Chulhee Yun. 31st Annual Conference on Learning Theory (COLT), 2018. (pdf)

• Certifying Some Distributional Robustness with Principled Adversarial Training, Aman Sinha, Hongseok Namkoong, John C. Duchi. Sixth International Conference on Learning Representations (ICLR 2018). (pdf) Selected for oral presentation.

• Derivative free optimization via repeated classification, Tatsunori B. Hashimoto, Steve Yadlowsky, John C. Duchi. 22nd International Conference on Artificial Intelligence and Statistics (AISTATS 2018). (pdf)

• Variance-based regularization with convex objectives, Hongseok Namkoong, John Duchi. Neural Information Processing Systems (NeurIPS) 2017. (pdf) Winner of best paper award.

• Unsupervised Transformation Learning via Convex Relaxations, Tatsunori B. Hashimoto, John C. Duchi, Percy Liang. Neural Information Processing Systems (NeurIPS) 2017. (pdf)

• “Convex until proven guilty” Dimension-free acceleration of gradient descent on non-convex functions, Yair Carmon, John Duchi, Oliver Hinder, Aaron Sidford. International Conference on Machine Learning (ICML) 2017. (conference pdf), (arXiv)

• Adaptive Sampling Probabilities for Non-Smooth Optimization Hongseok Namkoong, Aman Sinha, Steve Yadlowsky, John C. Duchi. International Conference on Machine Learning (ICML) 2017. (pdf)

• Learning Kernels with Random Features, Aman Sinha, John Duchi. Neural Information Processing Systems (NeurIPS 2016) (pdf)

• Stochastic Gradient Methods for Distributionally Robust Optimization with f-Divergences, Hongseok Namkoong, John Duchi. Neural Information Processing Systems (NeurIPS 2016). (pdf)

• Local Minimax Complexity of Stochastic Convex Optimization, Sabyasachi Chatterjee, John Duchi, John Lafferty, Yuancheng Zhu. Neural Information Processing Systems (NeurIPS 2016). (pdf)

• Estimation from Indirect Supervision with Linear Moments, Aditi Ragunathan, Roy Frostig, John Duchi, Percy Liang. International Conference on Learning Theory (ICML) 2016. (pdf)

• Asynchronous Stochastic Convex Optimization: the noise is in the noise and SGD don't care, John Duchi, Sorathan Chaturapruek, and Christopher Re. Neural Information Processing Systems (NeurIPS) 2016. (pdf) (long version)

• Minimax Rates for Memory-Constrained Sparse Linear Regression, Jacob Steinhardt, John Duchi. Conference on Learning Theory (COLT) 2015. (pdf)

• Estimation, Optimization, and Parallelism when Data is Sparse, John C. Duchi, Michael I. Jordan, and Brendan McMahan. Neural Information Processing Systems (NeurIPS 2013). (long pdf)

• Information-theoretic lower bounds for distributed statistical estimation with communication constraints, Yuchen Zhang, John C. Duchi, Michael I. Jordan, and Martin Wainwright. Neural Information Processing Systems (NeurIPS 2013). (NeurIPS versoin) (pdf)

• Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation, John C. Duchi, Michael I. Jordan, and Martin Wainwright. Neural Information Processing Systems (NeurIPS 2013). (pdf)

• Local Privacy and Statistical Minimax Rates, John C. Duchi, Michael I. Jordan, and Martin Wainwright. 54th Annual Symposium on Foundations of Computer Science (FOCS 2013). (pdf)

• Divide and Conquer Kernel Ridge Regression, Yuchen Zhang, John C. Duchi, and Martin Wainwright. Conference on Learning Theory (COLT 2013). (long pdf)

• Privacy Aware Learning, John C. Duchi, Michael I. Jordan, and Martin Wainwright. Neural Information Processing Systems (NeurIPS 2012). (pdf) Selected for oral presentation.

• Communication-Efficient Algorithms for Statistical Optimization, Yuchen Zhang, John C. Duchi, and Martin Wainwright. Neural Information Processing Systems (NeurIPS 2012). (pdf)

• Finite Sample Convergence Rates of Zero-Order Stochastic Optimization Methods, John C. Duchi, Michael I. Jordan, Martin Wainwright, and Andre Wibisono. Neural Information Processing Systems (NeurIPS 2012). (NeurIPS pdf)

• Randomized Smoothing for (Parallel) Stochastic Optimization, John Duchi, Peter L. Bartlett, and Martin Wainwright. International Conference on Machine Learning (ICML 2012) . Presented but not included in proceedings. (pdf)

• Distributed Delayed Stochastic Optimization, Alekh Agarwal and John Duchi. Neural Information Processing Systems (NeurIPS 2011). (pdf)

• Ergodic Subgradient Descent, John Duchi Alekh Agarwal, Mikael Johansson, Michael I. Jordan. Allerton Conference on Communications, Control, and Computing 2011. (pdf)

• Oracle Inequalities for Computationally Budgeted Model Selection, Alekh Agarwal, John Duchi, Peter L. Bartlett, Clement Levrard. Conference on Learning Theory (COLT 2011). (pdf)

• Distributed Dual Averaging in Networks, John Duchi, Alekh Agarwal, and Martin Wainwright. Neural Information Processing Systems (NeurIPS 2010). (pdf)

• On the Consistency of Ranking Algorithms, John Duchi, Lester Mackey, and Michael Jordan. International Conference on Machine Learning (ICML 2010). (pdf) Winner of best student paper award.

• Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, John Duchi, Elad Hazan, and Yoram Singer. Conference on Learning Theory (COLT 2010). (pdf)

• Composite Objective Mirror Descent, John Duchi, Shai Shalev-Shwartz, Yoram Singer, Ambuj Tewari. Conference on Learning Theory (COLT 2010). (pdf)

• Efficient Learning using Forward Backward Splitting, John Duchi and Yoram Singer. Neural Information Processing Systems (NeurIPS 2009). (pdf) Selected for oral presentation.

• Boosting with Structural Sparsity, John Duchi and Yoram Singer. International Conference on Machine Learning (ICML 2009). (pdf)

• Efficient Projections onto the L1-Ball for Learning in High Dimensions, John Duchi, Shai Shalev-Shwartz, Yoram Singer, and Tushar Chandra. International Conference on Machine Learning (ICML 2008). (pdf)

• Constrained Approximate Maximum Entropy Learning of Markov Random Fields,Varun Ganapathi, David Vickrey, John Duchi, and Daphne Koller. Conference on Uncertainty in Artificial Intelligence (UAI 2008). (pdf)

• Projected Subgradient Methods for Learning Sparse Gaussians, John Duchi, Stephen Gould and Daphne Koller. Conference on Uncertainty in Artificial Intelligence (UAI 2008). (pdf)

• Using Combinatorial Optimization within Max-Product Belief Propagation, John Duchi, Danny Tarlow, Gal Elidan, and Daphne Koller. Neural Information Processing Systems (NeurIPS 2006). (pdf)

Miscellaneous notes and long versions of some conference papers

• Asynchronous Stochastic Convex Optimization, John C. Duchi and Sorathan Chaturapruek. (pdf)

• Oracle Inequalities for Computationally Adaptive Model Selection, Alekh Agarwal, Peter L. Bartlett, and John C. Duchi. (pdf)

• Distance-based and continuum Fano inequalities with applications to statistical estimation, John C. Duchi, and Martin J. Wainwright. (pdf)