-
作者：Zhou, Danqing; Ma, Shiqian; Yang, Tunfeng
作者单位：Nanjing University; Rice University
摘要：In this paper, we propose AdaBB, an adaptive gradient method based on the Barzilai-Borwein stepsize. The algorithm is line-search-free and parameter-free, and it essentially provides a convergent variant of the Barzilai-Borwein method for general convex optimization problems. We analyze the ergodic convergence of the objective function value and the convergence of the iterates for solving general convex optimization problems. Compared with existing works along this line of research, our algori...
-
作者：Feldman, Moran; Liu, Paul; Norouzi-Fard, Ashkan; Svensson, Ola; Zenklusen, Rico
作者单位：University of Haifa; Stanford University; Alphabet Inc.; Google Incorporated; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：Recent progress in (semi-)streaming algorithms for monotone submodular function maximization has led to tight results for a simple cardinality constraint. However, current techniques fail to give a similar understanding for natural generalizations, including matroid constraints. This paper aims at closing this gap. For a single matroid of rank k (i.e., any solution has cardinality at most k), our main results are a single-pass streaming algorithm that uses Oe(k) memory and achieves an approxim...
-
作者：Han, Shaoning; Cui, Ying; Pang, Jong-Shi
作者单位：National University of Singapore; University of California System; University of California Berkeley; University of Southern California
摘要：The minimization of nonlower semicontinuous functions is a difficult topic that has been minimally studied. Among such functions is a Heaviside composite function that is the composition of a Heaviside function with a possibly nonsmooth multivariate function. Unifying a statistical estimation problem with hierarchical selection of variables and a sample average approximation of composite chance constrained stochastic programs, a Heaviside composite optimization problem is one whose objective a...
-
作者：Gershkov, Alex; Moldovanu, Benny; Shi, Xianwen
作者单位：Hebrew University of Jerusalem; University of Surrey; University of Bonn; Tel Aviv University; University of Toronto
摘要：We study when the voting outcome is independent of the order of issues put up for vote in a spatial multidimensional voting model. Agents equipped with norm-based preferences that use a norm to measure the distance from their ideal policy vote sequentially and issue by issue via simple majority. If the underlying norm is generated by an inner product-such as the Euclidean norm-then the voting outcome is order independent if and only if the issues are orthogonal. If the underlying norm is a gen...
-
作者：Amarante, Massimiliano; Liebrich, Felix-Benedikt; Munari, Cosimo
作者单位：Universite de Montreal; University of Amsterdam; University of Verona
摘要：We revisit Marinacci's uniqueness theorem for convex -ranged probabilities and its applications. Our approach does away with both the countable additivity and the positivity of the charges involved. In the process, we uncover several new equivalent conditions, which lead to a novel set of applications. These include extensions of the classic Fre ' chet-Hoeffding bounds as well as of the automatic Fatou property of law -invariant functionals. We also generalize existing results of the collapse ...
-
作者：Csaji, Gergely; Kiraly, Tamas; Yokoi, Yu
作者单位：Eotvos Lorand University; Institute of Science Tokyo
摘要：This paper considers the problem of finding maximum-size stable matchings in the presence of ties, a well-known NP-hard problem, by extending the existing 32-approximation algorithm to a common generalization of many previously studied and newly introduced models. These include the existence of critical agents, where matching as many of these agents as possible is prioritized; free edges that cannot be blocking edges; and triangle-stabilities, which mean that for an edge to block, the improvem...
-
作者：Chen, Xiaochen; Guan, Guohui; Liang, Zongxia
作者单位：Tsinghua University; Renmin University of China; Renmin University of China
摘要：This paper investigates portfolio selection within a continuous-time financial market with regime switching and beliefs-dependent utilities. The market coefficients and the investor's utility function both depend on the market regime, which is modeled by an observable finite-state continuous-time Markov chain. The optimization problem is formulated by aggregating expected certainty equivalents under different regimes, leading to time inconsistency. Utilizing the equilibrium strategy, we derive...
-
作者：Ghosal, Promit; Nutz, Marcel
作者单位：University of Chicago; Columbia University
摘要：We study Sinkhorn's algorithm for solving the entropically regularized optimal transport problem. Its iterate pi t is shown to satisfy H(pi t|pi*) + H(pi*|pi t) = O(t(-1)), where H denotes relative entropy and pi* denotes the optimal coupling. This holds for a large class of cost functions and marginals, including quadratic cost with sub-Gaussian marginals. We also obtain the rate O(t(-1)) for the dual suboptimality and O(t(-2)) for the marginal entropies. More precisely, we derive nonasymptot...
-
作者：Li, Hanyang; Cui, Ying
作者单位：University of California System; University of California Berkeley
摘要：We investigate a class of composite nonconvex functions, where the outer function is the sum of univariate extended-real-valued convex functions and the inner function is the limit of difference-of-convex functions. A notable feature of this class is that the inner function may fail to be locally Lipschitz continuous. It covers a range of important, yet challenging, applications, including inverse optimal value optimization and problems under value-at-risk constraints. We propose an asymptotic...
-
作者：Yang, Shuoguang; Truong, Van-Anh
作者单位：Hong Kong University of Science & Technology; Columbia University
摘要：We propose the analysis of the online learning problem for independent cascade (IC) models under node-level feedback. These models have widespread applications in modern social networks. Existing works for IC models have only shed light on edge-level feedback models, where the agent knows the explicit outcome of every observed edge. Little is known about node-level feedback models where only combined outcomes for sets of edges are observed; in other words, the realization of each edge is censo...
