-
作者：Lu, Zhaosong; Li, Xiaorui
作者单位：Simon Fraser University
摘要：In the context of sparse recovery, it is known that most of the existing regularizers such as l(1) suffer from some bias incurred by some leading entries (in magnitude) of the associated vector. To neutralize this bias, we propose a class of models with partial regularizers for recovering a sparse solution of a linear system. We show that every local minimizer of these models is substantially sparse or the magnitude of all of its nonzero entries is above a uniform constant depending only on th...
-
作者：Nissim, Kobbi; Smorodinsky, Rann; Tennenholtz, Moshe
作者单位：Georgetown University; Technion Israel Institute of Technology
摘要：Data-driven segmentation is the powerhouse behind the success of online advertising. Various underlying challenges for successful segmentation have been studied by the academic community, with one notable exception-consumers' incentives have been typically ignored. This lacuna is troubling, as consumers have much control over the data being collected. Missing or manipulated data could lead to inferior segmentation. The current work proposes a model of prior-free segmentation, inspired by model...
-
作者：Ma, Will
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We study the multi-armed bandit problem with arms which are Markov chains with rewards. In the finite-horizon setting, the celebrated Gittins indices do not apply, and the exact solution is intractable. We provide approximation algorithms for the general model of Markov decision processes with nonunit transition times. When preemption is allowed, we provide a (1/2 - epsilon)-approximation, along with an example showing this is tight. When preemption isn't allowed, we provide a 1/12-approximati...
-
作者：Han, Deren; Sun, Defeng; Zhang, Liwei
作者单位：Nanjing Normal University; Hong Kong Polytechnic University; Dalian University of Technology
摘要：In this paper, we aim to prove the linear rate convergence of the alternating direction method of multipliers (ADMM) for solving linearly constrained convex composite optimization problems. Under a mild calmness condition, which holds automatically for convex composite piecewise linear-quadratic programming, we establish the global Q-linear rate of convergence for a general semi-proximal ADMM with the dual step-length being taken in (0, (1 + 5(1/2))/2). This semi-proximal ADMM, which covers th...
-
作者：Bansal, Nikhil; Kamphorst, Bart; Zwart, Bert
作者单位：Eindhoven University of Technology
摘要：For a GI/GI/1 queue, we show that the average sojourn time under the (blind) Randomized Multilevel Feedback algorithm is no worse than that under the Shortest Remaining Processing Time algorithm times a logarithmic function of the system load. Moreover, it is verified that this bound is tight in heavy traffic, up to a constant multiplicative factor. We obtain this result by combining techniques from two disparate areas: competitive analysis and applied probability.
-
作者：Murota, Kazuo
作者单位：Tokyo Metropolitan University
摘要：The multiple exchange property for matroid bases is generalized for valuated matroids and M-natural concave set functions. The proof is based on the Fenchel-type duality theorem in discrete convex analysis. The present result has an implication in economics: The strong no complementarities condition of Gul and Stacchetti is, in fact, equivalent to the gross substitutes condition of Kelso and Crawford.
-
作者：Cohen-Hillel, Tamar; Yedidsion, Liron
作者单位：Technion Israel Institute of Technology
摘要：In this paper, we study the long-standing open question regarding the computational complexity of one of the core problems in supply chains management, the periodic joint replenishment problem. This problem has received a lot of attention over the years, and many heuristic and approximation algorithms have been suggested. However, in spite of the vast effort, the complexity of the problem remains unresolved. In this paper, we provide a proof that the problem is indeed strongly NP-hard.
-
作者：Lu, Zhaosong; Chen, Xiaojun
作者单位：Simon Fraser University; Hong Kong Polytechnic University
摘要：The conjugate gradient (CG) method is an efficient iterative method for solving large-scale strongly convex quadratic programming (QP). In this paper, we propose some generalized CG (GCG) methods for solving the l(1)-regularized (possibly not strongly) convex QP that terminate at an optimal solution in a finite number of iterations. At each iteration, our methods first identify a face of an orthant and then either perform an exact line search along the direction of the negative projected minim...
-
作者：Sorin, Sylvain
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite Paris Cite; Sorbonne Universite
摘要：We consider two-person zero-sum games where the players control, at discrete times {t(n)} induced by a partition Pi of R+, a continuous time Markov process. We prove that the limit of the values v(Pi) exist as the mesh of Pi goes to 0. The analysis covers the cases of (1) stochastic games (where both players know the state), and (2) games with unknown state and symmetric signals. The proof is by reduction to deterministic differential games.
-
作者：Kraetschmer, Volker; Ladkau, Marcel; Laeven, Roger J. A.; Schoenmakers, John G. M.; Stadjed, Mitja
作者单位：University of Duisburg Essen; Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics; University of Amsterdam; Ulm University; Ulm University
摘要：This paper studies the optimal stopping problem in the presence of model uncertainty (ambiguity). We develop a numerically implementable method to solve this problem in a general setting, allowing for general time-consistent ambiguity-averse preferences and general payoff processes driven by jump diffusions. Our method consists of three steps. First, we construct a suitable Doob martingale associated with the solution to the optimal stopping problem using backward stochastic calculus. Second, ...
