John Duchi: Publications
John C. Duchi: Publications
Clicking the publication title will (typically)
give an abstract and publication information.
[back home]
Preprints, In Preparation, and Unpublished Notes
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]
Predictive Inference
with Weak Supervision,
Maxime Cauchois, Suyash Gupta, Alnur Ali, John Duchi.
[pdf]
Robust Validation:
Confident Predictions Even When Distributions Shift, Maxime
Cauchois, Suyash Gupta, 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, book chapters, and lecture notes
Introductory Lectures on
Stochastic Convex Optimization,
John C. Duchi. Park City Mathematics Institute, Graduate
Summer School Lectures, July 2016.
Information Theory and Statistics,
John C. Duchi. Lecture Notes for Statistics 311/Electrical Engineering
377, Stanford University. 2015.
Journal Articles
The Right Complexity Measure in Locally Private Estimation:
It is not the Fisher Information,
John Duchi and Feng Ruan.
Annals of Statistics, to appear.
[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,
to appear.
[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 (to appear), 2019.
[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 (to appear), 2019.
[pdf]
[Mathprog copy]
Asymptotic Optimality in Stochastic Optimization,
John Duchi, Feng Ruan. Annals of Statistics (to appear), 2019.
[pdf]
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]
[SIOPT 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,
and 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
Yoram Singer. Journal of Machine Learning Research
(JMLR 2011).
[pdf]
Efficient
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 (NIPS 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]
Conference Proceedings
A Fast Algorithm for
Adaptive Private Mean Estimation, John Duchi, Saminul Haque,
Rohith
Kuditipudi. Conference on Learning Theory (COLT), 2023.
[pdf]
[slides]
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 coming soon]
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).
[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).
[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).
[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).
[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]
[Long 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]
[Long 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]
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]