mlsanityData to 7 Oct 2026

Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning

arXiv 2002.10790 ↗First posted 25 Feb 2020math.OC cs.LG stat.MLcited by 46

Not on the map. Why?

Abstract (arXiv)

Conditional stochastic optimization covers a variety of applications ranging from invariant learning and causal inference to meta-learning. However, constructing unbiased gradient estimators for such problems is challenging due to the composition structure. As an alternative, we propose a biased stochastic gradient descent (BSGD) algorithm and study the bias-variance tradeoff under different structural assumptions. We establish the sample complexities of BSGD for strongly convex, convex, and weakly convex objectives under smooth and non-smooth conditions. Our lower bound analysis shows that the sample complexities of BSGD cannot be improved for general convex objectives and nonconvex objectives except for smooth nonconvex objectives with Lipschitz continuous gradient estimator. For this special setting, we propose an accelerated algorithm called biased SpiderBoost (BSpiderBoost) that matches the lower bound complexity. We further conduct numerical experiments on invariant logistic regression and model-agnostic meta-learning to illustrate the performance of BSGD and BSpiderBoost.

Key facts. Cited by 46 papers in the map (data through 7 Oct 2026). First posted on arXiv 25 Feb 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 9; 2023: 12; 2024: 9; 2025: 5; 2026: 4.

46 papers.

Sort:

By area:

  1. 2023A Guide Through the Zoo of Biased SGDcited by 39
  2. 2021Sinkhorn Distributionally Robust Optimizationcited by 38
  3. 2021Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimizationcited by 32
  4. 2022Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applicationscited by 27
  5. 2022Large-scale Stochastic Optimization of NDCG Surrogates for Deep Learning with Provable Convergencecited by 21
  6. 2022Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimizationcited by 16
  7. 2021Momentum Accelerates the Convergence of Stochastic AUPRC Maximizationcited by 14
  8. 2023Contextual Stochastic Bilevel Optimizationcited by 14
  9. 2022Federated Learning and Meta Learning: Approaches, Applications, and Directionscited by 12
  10. 2022FeDXL: Provable Federated Learning for Deep X-Risk Optimizationcited by 10
  11. 2023Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimizationcited by 10
  12. 2025MPO: An Efficient Post-Processing Framework for Mixing Diverse Preference Alignmentcited by 10
34 more
  1. 2025Advantage Shaping as Surrogate Reward Maximization: Unifying Pass@K Policy Gradientscited by 10
  2. 2023Post-processing Private Synthetic Data for Improving Utility on Selected Measurescited by 9
  3. 2023Wasserstein Distributionally Robust Policy Evaluation and Learning for Contextual Banditscited by 9
  4. 2022A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimizationcited by 8
  5. 2022Algorithmic Foundations of Empirical X-risk Minimizationcited by 7
  6. 2021Memory-Based Optimization Methods for Model-Agnostic Meta-Learning and Personalized Federated Learningcited by 6
  7. 2021KOALA: A Kalman Optimization Algorithm with Loss Adaptivitycited by 6
  8. 2022Constructing unbiased gradient estimators with finite variance for conditional stochastic optimizationcited by 6
  9. 2023Debiasing Conditional Stochastic Optimizationcited by 6
  10. 2021Online Estimation and Optimization of Utility-Based Shortfall Riskcited by 5
  11. 2024CoBo: Collaborative Learning via Bilevel Optimizationcited by 5
  12. 2023Federated Conditional Stochastic Optimizationcited by 4
  13. 2024Non-asymptotic Analysis of Biased Adaptive Stochastic Approximationcited by 4
  14. 2024Non-Convex Robust Hypothesis Testing using Sinkhorn Uncertainty Setscited by 4
  15. 2024Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distancescited by 4
  16. 2024Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Datacited by 4
  17. 2024Deep Learning for Computing Convergence Rates of Markov Chainscited by 4
  18. 2023Provable Multi-instance Deep AUC Maximization with Stochastic Poolingcited by 3
  19. 2023Serverless Federated AUPRC Optimization for Multi-Party Collaborative Imbalanced Data Miningcited by 3
  20. 2023Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimizationcited by 3
  21. 2023A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimizationcited by 3
  22. 2024A Functional Model Method for Nonconvex Nonsmooth Conditional Stochastic Optimizationcited by 3
  23. 2021A Variance Controlled Stochastic Method with Biased Estimation for Faster Non-convex Optimizationcited by 2
  24. 2024Parallel Momentum Methods Under Biased Gradient Estimationscited by 2
  25. 2023Stochastic Nested Compositional Bi-level Optimization for Robust Feature Learningcited by 1
  26. 2024On the KL-Divergence-based Robust Satisficing Modelcited by 1
  27. 2025Iterative Sampling Methods for Sinkhorn Distributionally Robust Optimizationcited by 1
  28. 2026A Geometry-Aware Efficient Algorithm for Compositional Entropic Risk Minimizationcited by 1
  29. 2022Fairness via Adversarial Attribute Neighbourhood Robust Learningcited by 0
  30. 2025Quantum speedup of non-linear Monte Carlo problemscited by 0
  31. 2025Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimizationcited by 0
  32. 2026Convergence Rate of a Functional Learning Method for Contextual Stochastic Optimizationcited by 0
  33. 2026UB-SMoE: Universally Balanced Sparse Mixture-of-Experts for Resource-adaptive Federated Fine-tuning of Foundation Modelscited by 0
  34. 2026Convex Optimization Is Free When Accuracy Is Expensivecited by 0