Title | ||
---|---|---|
On the Solution of Stochastic Optimization and Variational Problems in Imperfect Information Regimes |
Abstract | ||
---|---|---|
We consider the minimization of a convex expectation-valued objective E[f(x;theta*,xi)] over a closed and convex set $X$ in a regime where theta* is unavailable and theta* is a suitably defined random variable. Instead, theta* may be obtained through the solution of a learning problem that requires minimizing a metric E[g(x;theta*,eta)] in theta* over a closed and convex set theta*. To resolve the absence of convergent efficient schemes, we present a coupled stochastic approximation scheme which simultaneously solves both the computational and the learning problems. The obtained schemes are shown to be equipped with almost sure convergence properties in regimes when the function f is either strongly convex or merely convex. Importantly, the scheme displays the optimal rate for both strongly convex and convex problems where the rate statement in the latter regime necessitates the use of averaging. In the second part of the paper, we extend these statements to a class of stochastic variational inequality problems, an object that unifies stochastic convex optimization problems and a range of stochastic equilibrium problems. Analogous almost-sure convergence statements are provided in strongly monotone and merely monotone regimes, the latter facilitated by using an iterative Tikhonov regularization. Again, we note that the schemes admit the optimal rate in strongly monotone and monotone settings, where the latter result requires the additional assumption of weak sharpness. Preliminary numerics demonstrate the performance of the prescribed schemes. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1137/140955495 | SIAM JOURNAL ON OPTIMIZATION |
Keywords | Field | DocType |
sochastic optimization,stochastic variational inequality,stochastic approximation,learning | Discrete mathematics,Convergence of random variables,Stochastic optimization,Random variable,Convex set,Regular polygon,Minification,Convex function,Stochastic approximation,Mathematics | Journal |
Volume | Issue | ISSN |
26 | 4 | 1052-6234 |
Citations | PageRank | References |
6 | 0.48 | 27 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jiang Hao | 1 | 15 | 2.01 |
Uday V. Shanbhag | 2 | 403 | 35.53 |