Two-timescale Derivative Free Optimization for Performative Prediction with Markovian Data
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910455958601728 |
|---|---|
| author | Liu, Haitong Li, Qiang Wai, Hoi-To |
| author_facet | Liu, Haitong Li, Qiang Wai, Hoi-To |
| contents | This paper studies the performative prediction problem where a learner aims to minimize the expected loss with a decision-dependent data distribution. Such setting is motivated when outcomes can be affected by the prediction model, e.g., in strategic classification. We consider a state-dependent setting where the data distribution evolves according to an underlying controlled Markov chain. We focus on stochastic derivative free optimization (DFO) where the learner is given access to a loss function evaluation oracle with the above Markovian data. We propose a two-timescale DFO($λ$) algorithm that features (i) a sample accumulation mechanism that utilizes every observed sample to estimate the overall gradient of performative risk, and (ii) a two-timescale diminishing step size that balances the rates of DFO updates and bias reduction. Under a general non-convex optimization setting, we show that DFO($λ$) requires ${\cal O}( 1 /ε^3)$ samples (up to a log factor) to attain a near-stationary solution with expected squared gradient norm less than $ε> 0$. Numerical experiments verify our analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_05792 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Two-timescale Derivative Free Optimization for Performative Prediction with Markovian Data Liu, Haitong Li, Qiang Wai, Hoi-To Optimization and Control This paper studies the performative prediction problem where a learner aims to minimize the expected loss with a decision-dependent data distribution. Such setting is motivated when outcomes can be affected by the prediction model, e.g., in strategic classification. We consider a state-dependent setting where the data distribution evolves according to an underlying controlled Markov chain. We focus on stochastic derivative free optimization (DFO) where the learner is given access to a loss function evaluation oracle with the above Markovian data. We propose a two-timescale DFO($λ$) algorithm that features (i) a sample accumulation mechanism that utilizes every observed sample to estimate the overall gradient of performative risk, and (ii) a two-timescale diminishing step size that balances the rates of DFO updates and bias reduction. Under a general non-convex optimization setting, we show that DFO($λ$) requires ${\cal O}( 1 /ε^3)$ samples (up to a log factor) to attain a near-stationary solution with expected squared gradient norm less than $ε> 0$. Numerical experiments verify our analysis. |
| title | Two-timescale Derivative Free Optimization for Performative Prediction with Markovian Data |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2310.05792 |