# STIMULUS: Achieving Fast Convergence and Low Sample Complexity in Stochastic Multi-Objective Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 43 references that are in the map.
- First posted on arXiv 24 Jun 2025.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Multi-Task Learning as Multi-Objective Optimization](https://mlsanity.com/paper/1810.04650/) (2018)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Dynamic Routing Between Capsules](https://mlsanity.com/paper/1710.09829/) (2017)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Pareto Multi-Task Learning](https://mlsanity.com/paper/1912.12854/) (2019)
- [Learning with Average Precision: Training Image Retrieval with a Listwise Loss](https://mlsanity.com/paper/1906.07589/) (2019)
- [The stochastic multi-gradient algorithm for multi-objective optimization and its application to supervised machine learning](https://mlsanity.com/paper/1907.04472/) (2019)
- [Uncertainty-Aware Search Framework for Multi-Objective Bayesian Optimization](https://mlsanity.com/paper/2204.05944/) (2022)
- [Pairwise Learning for Neural Link Prediction](https://mlsanity.com/paper/2112.02936/) (2021)
- [Deep Attentive Ranking Networks for Learning to Order Sentences](https://mlsanity.com/paper/2001.00056/) (2019)
- [Multi-Task Video Captioning with Video and Entailment Generation](https://mlsanity.com/paper/1704.07489/) (2017)
- [Mitigating Gradient Bias in Multi-objective Learning: A Provably Convergent Stochastic Approach](https://mlsanity.com/paper/2210.12624/) (2022)
- [Multi-Label Learning to Rank through Multi-Objective Optimization](https://mlsanity.com/paper/2207.03060/) (2022)

## Abstract (arXiv)

Recently, multi-objective optimization (MOO) has gained attention for its broad applications in ML, operations research, and engineering. However, MOO algorithm design remains in its infancy and many existing MOO methods suffer from unsatisfactory convergence rate and sample complexity performance. To address this challenge, in this paper, we propose an algorithm called STIMULUS( stochastic path-integrated multi-gradient recursive eulstimator), a new and robust approach for solving MOO problems. Different from the traditional methods, STIMULUS introduces a simple yet powerful recursive framework for updating stochastic gradient estimates to improve convergence performance with low sample complexity. In addition, we introduce an enhanced version of STIMULUS, termed STIMULUS-M, which incorporates a momentum term to further expedite convergence. We establish O(1/T) convergence rates of the proposed methods for non-convex settings and O (exp-μ T) for strongly convex settings, where T is the total number of iteration rounds. Additionally, we achieve the state-of-the-art O left(n+√nε-1right) sample complexities for non-convex settings and Oleft(n+ √n ln (μ/ε)right) for strongly convex settings, where ε>0 is a desired stationarity error. Moreover, to alleviate the periodic full gradient evaluation requirement in STIMULUS and STIMULUS-M, we further propose enhanced versions with adaptive batching called STIMULUS+/ STIMULUS-M+ and provide their theoretical analysis.