-
作者：Baas, Stef; Boucherie, Richard J.; Braaksma, Aleida
作者单位：University of Twente
摘要：A sampling-based method is introduced to approximate the Gittins index for a general family of alternative bandit processes. The approximation consists of a truncation of the optimization horizon and support for the immediate rewards, an optimal stopping value approximation, and a stochastic approximation procedure. Finite-time error bounds are given for the three approximations, leading to a procedure to construct a confidence interval for the Gittins index using a finite number of Monte Carl...
-
作者：Backhoff-Veraguas, Julio; Zhang, Xin
作者单位：University of Vienna; New York University; New York University Tandon School of Engineering
摘要：Defining a divergence between the laws of continuous martingales is a delicate task, owing to the fact that these laws tend to be singular to each other. An important idea, by Gantert, is to instead consider a scaling limit of the relative entropy between such continuous martingales sampled over a finite time grid. This gives rise to the concept of specific relative entropy. In order to develop a general theory of divergences between continuous martingales, it is natural to replace the role of...
-
作者：Yu, Di; Henderson, Shane G.; Pasupathy, Raghu
作者单位：Purdue University System; Purdue University; Cornell University
摘要：Motivated by applications in emergency response and experimental design, we consider smooth stochastic optimization problems over probability measures supported on compact subsets of the Euclidean space. With the influence function as the variational object, we construct a deterministic Frank-Wolfe (dFW) recursion for probability spaces. The dFW recursion is made especially possible by a lemma that identifies the solution to the infinite-dimensional Frank-Wolfe subproblem as a Dirac measure co...
-
作者：Huang, Chien-Chung; Sellier, Francois
作者单位：Universite PSL; Centre National de la Recherche Scientifique (CNRS); Ecole Normale Superieure (ENS); Universite PSL; Ecole Normale Superieure (ENS); Universite PSL; MINES ParisTech
摘要：Matroid intersection is a classical optimization problem where given two matroids over the same ground set, the goal is to find the largest common independent set. In this paper, we show that there exists a certain sparsifer: a subset of elements of size O(|Sopt| 1/E), where Sopt denotes the optimal solution, that is guaranteed to contain a 3/2 + E approximation while guaranteeing certain robustness properties. We call such a small subset a density constrained subset, which is inspired by the ...
-
作者：Okuno, Takayuki
作者单位：Seikei University
摘要：We study properties of the central path underlying a nonlinear semidefinite optimization problem, called an NSDP for short. The latest radical work on this topic was contributed by Yamashita and Yabe [Yamashita H, Yabe H (2012) Local and superlinear convergence of a primal-dual interior point method for nonlinear semidefinite programming. Mathematical Programming 132(1-2):1-30]: they proved that the Jacobian of a certain equation system derived from the Karush-Kuhn-Tucker (KKT) conditions of t...
-
作者：Jezequel, Remi; Ostrovskii, Dmitrii; Gaillard, Pierre
作者单位：Inria; Universite PSL; Ecole Normale Superieure (ENS); University System of Georgia; Georgia Institute of Technology; Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); Inria; Institut National Polytechnique de Grenoble
摘要：In the problem of online portfolio selection as formulated by Cover [Cover TM (1991) Universal portfolios. Math. Finance 1(1):1-29], the trader repeatedly distributes the trader's capital over d assets in each of T > 1 rounds with the goal of maximizing the total return. Cover proposed an algorithm, termed universal portfolios, that performs nearly as well as the best (in hindsight) static assignment of a portfolio with an O(d log(T)) logarithmic regret. Without imposing any restrictions on th...
-
作者：Zhao, Renbo
作者单位：University of Iowa
摘要：We present and analyze an away-step Frank-Wolfe method for the convex optimization problem minx is an element of Xf(Ax) + < c , x > , where f is a theta-logarithmically homogeneous self-concordant barrier, A is a linear operator that may be noninvertible, < c , > is a linear function, and X is a nonempty polytope. The applications of primary interest include D-optimal design, inference of multivariate Hawkes processes, and total variationregularized Poisson image deblurring. We establish affin...
-
作者：Kim, Kyoung-Kuk; Kim, Taeho; Fu, Michael C.
作者单位：Korea Advanced Institute of Science & Technology (KAIST); Hong Kong University of Science & Technology; University System of Maryland; University of Maryland College Park; University System of Maryland; University of Maryland College Park
摘要：We consider the problem of estimating a multivariate distribution based on multiple data sources, which include both joint and marginal-only data. Specifically, we introduce a nonparametric approach called Ensemble Copula Coupling (ECC), which can be viewed as a data fusion approach that combines joint and marginal information. The particular setting of interest is input modeling for output analysis of simulated stochastic systems. We apply an ECC-based input model to address uncertainty quant...
-
作者：Bolte, Jerome; Le, Quoc-Tung; Pauwels, Edouard; Vaiter, Samuel
作者单位：Communaute d'universites et etablissements de Toulouse (Comue); Universite Toulouse 1 Capitole; Toulouse School of Economics; Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); Inria; Institut National Polytechnique de Grenoble; Centre National de la Recherche Scientifique (CNRS); Universite Cote d'Azur
摘要：We introduce the Morse parametric qualification condition for bilevel programming. Generic semialgebraic functions are Morse parametric in a piecewise sense. Thus, bilevel programs with a Morse parametric lower level constitute a relevant intermediate class between strongly convex and fully generic lower levels. In this framework, we study bilevel gradient algorithms with two strategies: the single-step multistep strategy, which involves a sequence of steps on the lower-level problems followed...
-
作者：Tabri, Rami
作者单位：Monash University
摘要：Relative entropy minimization is a widely used method in decisions and operations research that incorporates information through constraints on the underlying probability model. The solution is called information projection, and we present new results for its existence, exponential family representation, and approximation in the infinite-dimensional setting for moment inequality constraint sets, nesting both conditional and unconditional moments and allowing for an infinite number of such ineq...
