-
作者：Simchi-Levi, David; Xu, Yunzong
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We consider the general (stochastic) contextual bandit problem under the realizability assumption, that is, the expected reward, as a function of contexts and actions, belongs to a general function class F. We design a fast and simple algorithm that achieves the statistically optimal regret with only O(log T) calls to an offline regression oracle across all T rounds. The number of oracle calls can be further reduced to O(log log T) if T is known in advance. Our results provide the first univer...
-
作者：Abdi, Ahmed; Cornuejols, Gerard; Lee, Dabeen
作者单位：University of London; London School Economics & Political Science; Carnegie Mellon University; Institute for Basic Science - Korea (IBS)
摘要：Ideal matrices and clutters are prevalent in combinatorial optimization, ranging from balanced matrices, clutters of T-joins, to clutters of rooted arborescences. Most of the known examples of ideal clutters are combinatorial in nature. In this paper, rendered by the recently developed theory of cuboids, we provide a different class of ideal clutters, one that is geometric in nature. The advantage of this new class of ideal clutters is that it allows for infinitely many ideal minimally nonpack...
-
作者：De Angelis, Tiziano; Gensbittel, Fabien; Villeneuve, Stephane
作者单位：University of Leeds; Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics
摘要：This paper studies a two-player zero-sum Dynkin game arising from pricing an option on an asset whose rate of return is unknown to both players. Using filtering techniques, we first reduce the problem to a zero-sum Dynkin game on a bidimensional diffusion (X,Y). Then we characterize the existence of a Nash equilibrium in pure strategies in which each player stops at the hitting time of (X,Y) to a set with a moving boundary. A detailed description of the stopping sets for the two players is pro...
-
作者：Oliu-Barton, Miquel
作者单位：Universite PSL; Universite Paris-Dauphine
摘要：Zero-sum stochastic games, henceforth stochastic games, are a classical model in game theory in which two opponents interact and the environment changes in response to the players' behavior. The central solution concepts for these games are the discounted values and the value, which represent what playing the game is worth to the players for different levels of impatience. In the present manuscript, we provide algorithms for computing exact expressions for the discounted values and for the val...
-
作者：Zhang, Hui; Dai, Yu-Hong; Guo, Lei; Peng, Wei
作者单位：National University of Defense Technology - China; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; East China University of Science & Technology
摘要：We introduce a unified algorithmic framework, called the proximal-like incremental aggregated gradient (PLIAG) method, for minimizing the sum of a convex function that consists of additive relatively smooth convex components and a proper lower semicontinuous convex regularization function over an abstract feasible set whose geometry can be captured by using the domain of a Legendre function. The PLIAG method includes many existing algorithms in the literature as special cases, such as the prox...
-
作者：Grishchenko, Dmitry; Iutzeler, Franck; Malick, Jerome
作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Inria; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Centre National de la Recherche Scientifique (CNRS)
摘要：Many applications in machine learning or signal processing involve nonsmooth optimization problems. This nonsmoothness brings a low-dimensional structure to the optimal solutions. In this paper, we propose a randomized proximal gradient method harnessing this underlying structure. We introduce two key components: (i) a random subspace proximal gradient algorithm; and (ii) an identification-based sampling of the subspaces. Their interplay brings a significant performance improvement on typical ...
-
作者：Duetting, Paul; Kesselheim, Thomas; Tardos, Eva
作者单位：University of London; London School Economics & Political Science; University of Bonn; Cornell University
摘要：Many algorithms that are originally designed without explicitly considering incentive properties are later combined with simple pricing rules and used as mechanisms. A key question is therefore to understand which algorithms, or, more generally, which algorithm design principles, when combined with simple payment rules such as pay your bid, yield mechanisms with a small price of anarchy. Our main result concerns mechanisms that are based on the relax-and-round paradigm. It shows that oblivious...
-
作者：Ye, Heng-Qing; Yao, David D.
作者单位：Hong Kong Polytechnic University; Columbia University
摘要：In a prior study [Ye HQ, Yao DD (2016) Diffusion limit of fair resource control- Stationary and interchange of limits. Math. Oper. Res. 41(4):1161-1207.] focusing on a class of stochastic processing network with fair resource control, we justified the diffusion approximation (in the context of the interchange of limits) provided that the pth moment of the workloads are bounded. To this end, we introduced the so-called bounded workload condition, which requires the workload process be bounded b...
-
作者：Facchinei, Francisco; Kungurtsev, Vyacheslav; Lampariello, Lorenzo; Scutari, Gesualdo
作者单位：Sapienza University Rome; Czech Technical University Prague; Roma Tre University; Purdue University System; Purdue University
摘要：We consider nonconvex constrained optimization problems and propose a new approach to the convergence analysis based on penalty functions. We make use of classical penalty functions in an unconventional way, in that penalty functions only enter in the theoretical analysis of convergence while the algorithm itself is penalty free. Based on this idea, we are able to establish several new results, including the first general analysis for diminishing stepsize methods in nonconvex, constrained opti...
-
作者：Callegaro, Giorgla; Grasselli, Martino; Pages, Gilles
作者单位：University of Padua; Universite Paris Cite; Sorbonne Universite
摘要：We solve a family of fractional Riccati equations with constant (possibly complex) coefficients. These equations arise, for example, in fractional Heston stochastic volatility models, which have received great attention in the recent financial literature because of their ability to reproduce a rough volatility behavior. We first consider the case of a zero initial value corresponding to the characteristic function of the log-price. Then we investigate the case of a general starting value assoc...
