2019

最新文章

• Variational perspective on local graph clustering AI翻译
  作者：Fountoulakis, Kimon; Roosta-Khorasani, Farbod; Shun, Julian; Cheng, Xiang; Mahoney, Michael W.
  作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley
  摘要：Modern graph clustering applications require the analysis of large graphs and this can be computationally expensive. In this regard, local spectral graph clustering methods aim to identify well-connected clusters around a given seed set of reference nodes without accessing the entire graph. The celebrated Approximate Personalized PageRank (APPR) algorithm in the seminal paper by Andersen et al. (in: FOCS '06 proceedings of the 47th annual IEEE symposium on foundations of computer science, pp 4...
• Incorporating statistical model error into the calculation of acceptability prices of contingent claims AI翻译
  作者：Glanzer, Martin; Pflug, Georg Ch.; Pichler, Alois
  作者单位：University of Vienna; Technische Universitat Chemnitz
  摘要：The determination of acceptability prices of contingent claims requires the choice of a stochastic model for the underlying asset price dynamics. Given this model, optimal bid and ask prices can be found by stochastic optimization. However, the model for the underlying asset price process is typically based on data and found by a statistical estimation procedure. We define a confidence set of possible estimated models by a nonparametric neighborhood of a baseline model. This neighborhood serve...
• Affine reductions for LPs and SDPs AI翻译
  作者：Braun, Gabor; Pokutta, Sebastian; Zink, Daniel
  作者单位：University System of Georgia; Georgia Institute of Technology
  摘要：We define a reduction mechanism for LP and SDP formulations that degrades approximation factors in a controlled fashion. Our reduction mechanism is a minor restriction of classical hardness reductions requiring an additional independence assumption and it allows for reusing many hardness reductions that have been used to show inapproximability in the context of PCP theorems. As a consequence we establish strong linear programming inapproximability (for LPs with a polynomial number of constrain...
• Stochastic quasi-Fejer block-coordinate fixed point iterations with random sweeping II: mean-square and linear convergence AI翻译
  作者：Combettes, Patrick L.; Pesquet, Jean-Christophe
  作者单位：North Carolina State University; Universite Paris Saclay
  摘要：Combettes and Pesquet (SIAM J Optim 25:1221-1248,2015) investigated the almost sure weak convergence of block-coordinate fixed point algorithms and discussed their applications to nonlinear analysis and optimization. This algorithmic framework features random sweeping rules to select arbitrarily the blocks of variables that are activated over the course of the iterations and it allows for stochastic errors in the evaluation of the operators. The present paper establishes results on the mean-sq...
• Distributionally robust expectation inequalities for structured distributions AI翻译
  作者：Van Parys, Bart P. G.; Goulart, Paul J.; Morari, Manfred
  作者单位：Massachusetts Institute of Technology (MIT); University of Oxford; University of Pennsylvania
  摘要：Quantifying the risk of unfortunate events occurring, despite limited distributional information, is a basic problem underlying many practical questions. Indeed, quantifying constraint violation probabilities in distributionally robust programming or judging the risk of financial positions can both be seen to involve risk quantification under distributional ambiguity. In this work we discuss worst-case probability and conditional value-at-risk problems, where the distributional information is ...
• Sample average approximation with sparsity-inducing penalty for high-dimensional stochastic programming AI翻译
  作者：Liu, Hongcheng; Wang, Xue; Yao, Tao; Li, Runze; Ye, Yinyu
  作者单位：State University System of Florida; University of Florida; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Stanford University
  摘要：The theory on the traditional sample average approximation (SAA) scheme for stochastic programming (SP) dictates that the number of samples should be polynomial in the number of problem dimensions in order to ensure proper optimization accuracy. In this paper, we study a modification to the SAA in the scenario where the global minimizer is either sparse or can be approximated by a sparse solution. By making use of a regularization penalty referred to as the folded concave penalty (FCP), we sho...
• An algorithm for nonsmooth optimization by successive piecewise linearization AI翻译
  作者：Fiege, Sabrina; Walther, Andrea; Griewank, Andreas
  作者单位：University of Paderborn; Universidad Yachay Tech
  摘要：We present an optimization method for Lipschitz continuous, piecewise smooth (PS) objective functions based on successive piecewise linearization. Since, in many realistic cases, nondifferentiabilities are caused by the occurrence of abs(), max(), and min(), we concentrate on these nonsmooth elemental functions. The method's idea is to locate an optimum of a PS objective function by explicitly handling the kink structure at the level of piecewise linear models. This piecewise linearization can...
• Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators AI翻译
  作者：Attouch, Hedy; Peypouquet, Juan
  作者单位：Universite de Montpellier; Universidad Tecnica Federico Santa Maria; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universidad de Chile; Universidad de Chile; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI)
  摘要：We study the behavior of the trajectories of a second-order differential equation with vanishing damping, governed by the Yosida regularization of a maximally monotone operator with time-varying index, along with a new Regularized Inertial Proximal Algorithm obtained by means of a convenient finite-difference discretization. These systems are the counterpart to accelerated forward-backward algorithms in the context of maximally monotone operators. A proper tuning of the parameters allows us to...
• Learning in games with continuous action sets and unknown payoff functions AI翻译
  作者：Mertikopoulos, Panayotis; Zhou, Zhengyuan
  作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Inria; Stanford University
  摘要：This paper examines the convergence of no-regret learning in games with continuous action sets. For concreteness, we focus on learning via dual averaging, a widely used class of no-regret learning schemes where players take small steps along their individual payoff gradients and then mirror the output back to their action sets. In terms of feedback, we assume that players can only estimate their payoff gradients up to a zero-mean error with bounded variance. To study the convergence of the ind...
• Quadratic optimization with orthogonality constraint: explicit Lojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods AI翻译
  作者：Liu, Huikang; So, Anthony Man-Cho; Wu, Weijie
  作者单位：Chinese University of Hong Kong; Chinese University of Hong Kong
  摘要：The problem of optimizing a quadratic form over an orthogonality constraint (QP-OC for short) is one of the most fundamental matrix optimization problems and arises in many applications. In this paper, we characterize the growth behavior of the objective function around the critical points of the QP-OC problem and demonstrate how such characterization can be used to obtain strong convergence rate results for iterative methods that exploit the manifold structure of the orthogonality constraint ...