Kavli Affiliate: Jia Liu
| First 5 Authors: Tian Xie, Tian Xie, , ,
| Summary:
Performative prediction (PP) is an algorithmic framework for optimizing
machine learning (ML) models where the model’s deployment affects the
distribution of the data it is trained on. Compared to traditional ML with
fixed data, designing algorithms in PP converging to a stable point — known as
a stationary performative stable (SPS) solution — is more challenging than the
counterpart in conventional ML tasks due to the model-induced distribution
shifts. While considerable efforts have been made to find SPS solutions using
methods such as repeated gradient descent (RGD) and greedy stochastic gradient
descent (SGD-GD), most prior studies assumed a strongly convex loss until a
recent work established $O(1/sqrtT)$ convergence of SGD-GD to SPS solutions
under smooth, non-convex losses. However, this latest progress is still based
on the restricted bounded variance assumption in stochastic gradient estimates
and yields convergence bounds with a non-vanishing error neighborhood that
scales with the variance. This limitation motivates us to improve convergence
rates and reduce error in stochastic optimization for PP, particularly in
non-convex settings. Thus, we propose a new algorithm called stochastic
performative prediction with variance reduction (SPRINT) and establish its
convergence to an SPS solution at a rate of $O(1/T)$. Notably, the resulting
error neighborhood is independent of the variance of the stochastic gradients.
Experiments on multiple real datasets with non-convex models demonstrate that
SPRINT outperforms SGD-GD in both convergence rate and stability.
| Search Query: ArXiv Query: search_query=au:”Jia Liu”&id_list=&start=0&max_results=3