# Minimax Excess Risk of First-Order Methods for Statistical Learning with Data-Dependent Oracles

arXiv: https://arxiv.org/abs/2307.04679 · HTML: https://mlsanity.com/paper/2307.04679/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 38 references that are in the map.
- First posted on arXiv 10 Jul 2023.

## Builds on (most cited first, 17 of 17)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [A survey on domain adaptation theory: learning bounds and theoretical guarantees](https://mlsanity.com/paper/2004.11829/) (2020)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Information-Theoretic Generalization Bounds for Stochastic Gradient Descent](https://mlsanity.com/paper/2102.00931/) (2021)
- [Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers](https://mlsanity.com/paper/1703.04940/) (2017)
- [Stability of SGD: Tightness Analysis and Improved Bounds](https://mlsanity.com/paper/2102.05274/) (2021)
- [A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descent](https://mlsanity.com/paper/1709.06617/) (2017)
- [Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyond](https://mlsanity.com/paper/2202.13441/) (2022)
- [Generalization Properties and Implicit Regularization for Multiple Passes SGM](https://mlsanity.com/paper/1605.08375/) (2016)
- [Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimization](https://mlsanity.com/paper/1802.06903/) (2018)
- [On the oracle complexity of smooth strongly convex minimization](https://mlsanity.com/paper/2101.09740/) (2021)
- [Tight Risk Bounds for Gradient Descent on Separable Data](https://mlsanity.com/paper/2303.01135/) (2023)

## Built on by (most cited first, 2 of 2)

- [Learning with Locally Private Examples by Inverse Weierstrass Private Stochastic Gradient Descent](https://mlsanity.com/paper/2602.16436/) (2026)
- [Adaptive Personalized Federated Learning via Multi-task Averaging of Kernel Mean Embeddings](https://mlsanity.com/paper/2603.02233/) (2026)

## Abstract (arXiv)

In this paper, our aim is to analyse the generalization capabilities of first-order methods for statistical learning in multiple, different yet related, scenarios including supervised learning, transfer learning, robust learning and federated learning. To do so, we provide sharp upper and lower bounds for the minimax excess risk of strongly convex and smooth statistical learning when the gradient is accessed through partial observations given by a data-dependent oracle. This novel class of oracles can query the gradient with any given data distribution, and is thus well suited to scenarios in which the training data distribution does not match the target (or test) distribution. In particular, our upper and lower bounds are proportional to the smallest mean square error achievable by gradient estimators, thus allowing us to easily derive multiple sharp bounds in the aforementioned scenarios using the extensive literature on parameter estimation.