-
作者：Chatterjee, Krishnendu; Oliu-Barton, Miquel; Saona, Raimundo
作者单位：Institute of Science & Technology - Austria; Centre National de la Recherche Scientifique (CNRS); Universite PSL; Universite Paris-Dauphine
摘要：Matrix games are the most basic model in game theory, and yet robustness with respect to small perturbations of the matrix entries is not fully understood. In this paper, we introduce value positivity and uniform value positivity, two properties that refine the notion of optimality in the context of polynomially perturbed matrix games. The first concept captures how the value depends on the perturbation parameter, and the second consists of the existence of a fixed strategy that guarantees the...
-
作者：Hegde, Vishwajit; Menon, Arvind Satish; Prashanth, L. A.; Tagannathan, Krishna
作者单位：Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Madras; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Madras; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Madras
摘要：Utility-based shortfall risk (UBSR) is a risk metric that is increasingly popular in financial applications, owing to certain desirable properties that it enjoys. We consider the problem of estimating UBSR in a recursive setting, in which samples from the underlying loss distribution are available one at a time. We cast the UBSR estimation problem as a root-finding problem and propose stochastic approximation-based estimation schemes. We derive nonasymptotic bounds on the estimation error in t...
-
作者：Zhang, Penghe; Xiu, Naihua; Luo, Ziyan
作者单位：Beijing Jiaotong University
摘要：We consider the problem of minimizing the sum of a smooth function and a composition of a zero-one loss function with a linear operator, namely the zero-one composite optimization problem (0/1-COP). It has a vast body of applications, including the support vector machine (SVM), calcium dynamics fitting (CDF), one-bit compressive sensing (1-bCS), and so on. However, it remains challenging to design a globally convergent algorithm for the original model of 0/1-COP because of the nonconvex and di...
-
作者：Gast, Nicolas; Gaujal, Bruno; Yan, Chen
作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); INRAE
摘要：We provide a framework to analyze control policies for the restless Markovian bandit model under both finite and infinite time horizons. We show that when the population of arms goes to infinity, the value of the optimal control policy converges to the solution of a linear program (LP). We provide necessary and sufficient conditions for a generic control policy to be (i) asymptotically optimal, (ii) asymptotically optimal with square root convergence rate, and (iii) asymptotically optimal with...
-
作者：Zhang, Jianfeng; Zhu, Zimu
作者单位：University of Southern California; Hong Kong University of Science & Technology (Guangzhou)
摘要：In this paper, we consider a principal-agent problem where the agent is allowed to quit by incurring a cost. When the current agent quits the job, the principal will hire a new one, possibly with a different type. We characterize the principal's dynamic value function, which could be discontinuous at the boundary, as the (unique) minimal solution of an infinite dimensional system of Hamilton-Jacobi-Bellman equations, parameterized by the agent's type. This dynamic problem is time consistent in...
-
作者：Agrawal, Priyank; Balkanski, Eric; Gkatzelis, Vasilis; Ou, Tingting; Tan, Xizhi
作者单位：Columbia University; Drexel University
摘要：In this work, we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in learning augmented algorithms. Aiming to complement the traditional worst-case analysis approach in computer science, this line of work has focused on the design and analysis of algorithms that are enhanced with machine-learned predictions. The algorithms can use the predictions as a guide to inform their decisions, aiming to achieve much stro...
-
作者：Daniilidis, Aris; Tapia, Sebastian
作者单位：Technische Universitat Wien
摘要：Daniilidis and Drusviatskiy, in 2017, extended the celebrated Kurdyka- Lojasiewicz inequality from definable functions to definable multivalued maps by establishing that the coderivative mapping admits a desingularization around every critical value. As was the case in the gradient dynamics, this desingularization yields a uniform control of the lengths of all bounded orbits of the corresponding sweeping process. In this paper, working outside the framework of o-minimal geometry, we characteri...
-
作者：Li, Tianjiao; Wu, Feiyang; Lan, Guanghui
作者单位：University System of Georgia; Georgia Institute of Technology; University System of Georgia; Georgia Institute of Technology
摘要：We study average-reward Markov decision processes (AMDPs) and develop novel first-order methods with strong theoretical guarantees for both policy optimization and policy evaluation. Compared with intensive research efforts in finite sample analysis of policy gradient methods for discounted MDPs, existing studies on policy gradient methods for AMDPs mostly focus on regret bounds under restrictive assumptions, and they often lack guarantees on the overall sample complexities. Toward this end, w...
-
作者：Blanchard, Moise; Zhang, Junhui; Jaillet, Patrick
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We give query complexity lower bounds for convex optimization and the related feasibility problem. We show that quadratic memory is necessary to achieve the optimal oracle complexity for first-order convex optimization. In particular, this shows that center-of-mass cutting-plane algorithms in dimension d , which use O ( d 2 ) memory and O ( d ) queries, are Pareto optimal for both convex optimization and the feasibility problem, up to logarithmic factors. Precisely, building upon techniques in...
-
作者：Lu, Zhaosong; Mei, Sanyou
作者单位：University of Minnesota System; University of Minnesota Twin Cities
摘要：In this paper, we consider a class of monotone inclusion (MI) problems of finding a zero of the sum of two monotone operators, in which one operator is maximal monotone, whereas the other is locally Lipschitz continuous. We propose primal-dual (PD) extrapolation methods to solve them using a point and operator extrapolation technique, whose parameters are chosen by a backtracking line search scheme. The proposed methods enjoy an operation complexity of O(log epsilon-1) and O(epsilon-1log epsil...
