arXiv Analytics

Sign in

arXiv:1811.04905 [math.OC]AbstractReferencesReviewsResources

Algorithmic models of human behavior and stochastic optimization

Maktagali Bektemessov, Alexander Gasnikov, Anastasia Lagunovskaya, Zhanna Ordabayeva

Published 2018-11-12Version 1

In this article we describe the solutions of three problems posed at different time by Yurii Nesterov. First problem is 'Mage vs Experts': Assume that we live in some enviroment that characterized by unobservable convex function $f(x)$. Each day we can observe only the stochastic gradient of $f(x)$ (with heavy tails). We want to know where is a minimum of $f(x)$. What is better to live one long live or to live in parallel many short lives? The second problem is a variant of the previous one (we'd like to find the minimum of convex function $f(x)$) but we can observe only the (noise) value of the function at each day. The additional difficulties here is $f(x)$ isn't necessarily smooth and $x$ belongs to unit simplex. The third problem is to interprete equillibrium in Stable dynamic traffic assignment model (Nesterov-dePalma, 2000) as atractor of the best response dynamic. All these problems required proper generalizations of mirror descent (MD) algorithm. In this paper we collect different special versions of MD to solve the described problems.

Related articles: Most relevant | Search more
arXiv:2306.04174 [math.OC] (Published 2023-06-07)
End-to-End Learning for Stochastic Optimization: A Bayesian Perspective
arXiv:2402.03982 [math.OC] (Published 2024-02-06)
On Convergence of Adam for Stochastic Optimization under Relaxed Assumptions
arXiv:1504.06683 [math.OC] (Published 2015-04-25)
Duality and optimality conditions in stochastic optimization and mathematical finance