Mathematical Programming

最新文章

• Submodular functions: from discrete to continuous domains AI翻译
  作者：Bach, Francis
  作者单位：Universite PSL; Ecole Normale Superieure (ENS)
  摘要：Submodular set-functions have many applications in combinatorial optimization, as they can be minimized and approximately maximized in polynomial time. A key element in many of the algorithms and analyses is the possibility of extending the submodular set-function to a convex function, which opens up tools from convex optimization. Submodularity goes beyond set-functions and has naturally been considered for problems with multiple labels or for functions defined on continuous domains, where it...
• A distributed one-step estimator AI翻译
  作者：Huang, Cheng; Huo, Xiaoming
  作者单位：University System of Georgia; Georgia Institute of Technology
  摘要：Distributed statistical inference has recently attracted enormous attention. Many existing work focuses on the averaging estimator, e.g., Zhang and Duchi (J Mach Learn Res 14:3321-3363, 2013) together with many others. We propose a one-step approach to enhance a simple-averaging based distributed estimator by utilizing a single Newton-Raphson updating. We derive the corresponding asymptotic properties of the newly proposed estimator. We find that the proposed one-step estimator enjoys the same...
• A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo-Tseng error bound property AI翻译
  作者：Yue, Man-Chung; Zhou, Zirui; So, Anthony Man-Cho
  作者单位：Imperial College London; Hong Kong Baptist University; Chinese University of Hong Kong
  摘要：We propose a new family of inexact sequential quadratic approximation (SQA) methods, which we call the inexact regularized proximal Newton (IRPN) method, for minimizing the sum of two closed proper convex functions, one of which is smooth and the other is possibly non-smooth. Our proposed method features strong convergence guarantees even when applied to problems with degenerate solutions while allowing the inner minimization to be solved inexactly. Specifically, we prove that when the problem...
• Run-and-Inspect Method for nonconvex optimization and global optimality bounds for R-local minimizers AI翻译
  作者：Chen, Yifan; Sun, Yuejiao; Yin, Wotao
  作者单位：Tsinghua University; University of California System; University of California Los Angeles
  摘要：Many optimization algorithms converge to stationary points. When the underlying problem is nonconvex, they may get trapped at local minimizers or stagnate near saddle points. We propose the Run-and-Inspect Method, which adds an inspect phase to existing algorithms that helps escape from non-global stationary points. It samples a set of points in a radius R around the current point. When a sample point yields a sufficient decrease in the objective, we resume an existing algorithm from that poin...
• Enhanced proximal DC algorithms with extrapolation for a class of structured nonsmooth DC minimization AI翻译
  作者：Lu, Zhaosong; Zhou, Zirui; Sun, Zhe
  作者单位：Simon Fraser University; Hong Kong Baptist University; Jiangxi Normal University
  摘要：In this paper we consider a class of structured nonsmooth difference-of-convex (DC) minimization in which the first convex component is the sum of a smooth and nonsmooth functions while the second convex component is the supremum of possibly infinitely many convex smooth functions. We first propose an inexact enhanced DC algorithm for solving this problem in which the second convex component is the supremum of finitely many convex smooth functions, and show that every accumulation point of the...
• Behavior of accelerated gradient methods near critical points of nonconvex functions AI翻译
  作者：O'Neill, Michael; Wright, Stephen J.
  作者单位：University of Wisconsin System; University of Wisconsin Madison
  摘要：We examine the behavior of accelerated gradient methods in smooth nonconvex unconstrained optimization, focusing in particular on their behavior near strict saddle points. Accelerated methods are iterative methods that typically step along a direction that is a linear combination of the previous step and the gradient of the function evaluated at a point at or near the current iterate. (The previous step encodes gradient information from earlier stages in the iterative process). We show by mean...
• 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...