8 papers
On the Oracle Complexity of Interpolation-Based Gradient Descent
Dongmin Lee, William Lu, Anuran Makur
Recent work on first-order optimizers for empirical risk minimization (ERM) has suggested that smoothness of ERM loss functions in the training data, rather than in the optimizatio…
Doeblin Curves
Dongmin Lee, William Lu, Anuran Makur +1
Recent research on Doeblin coefficients has shed light on their usefulness as a multi-way generalization of the Dobrushin contraction coefficient for TV distance, in a separate vei…
Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries
Dongmin Lee, Anuran Makur, Japneet Singh
Bradley-Terry-Luce (BTL) model estimation is a well-established strategy to rank a collection of items given a dataset of pairwise comparisons. Although the theoretical performance…
Unified High-Probability Analysis of Stochastic Variance-Reduced Estimation
Zhankun Luo, Antesh Upadhyay, M. Berk Sahin +3
Stochastic estimators are fundamental to large-scale optimization, where population quantities must be inferred from noisy oracle observations. Although influential methods such as…
Fair Division Under Inaccurate Preferences
Trung Dang, Daniel Halpern, Anuran Makur +3
The fair allocation of scarce resources is a central problem in mathematics, computer science, operations research, and economics. While much of the fair-division literature assume…
Bounds on Maximal Leakage over Bayesian Networks
Anuran Makur, Japneet Singh
Maximal leakage quantifies the leakage of information from data due to an observation . While fundamental properties of maximal leakage, such as data process…