-
作者：Dey, Santanu; Singh, Mohit; Williamson, David P.
作者单位：University System of Georgia; Georgia Institute of Technology; Cornell University
-
作者：Cui, Shisheng; Shanbhag, Uday, V; Yousefian, Farzad
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Rutgers University System; Rutgers University New Brunswick
摘要：Mathematical programs with equilibrium constraints (MPECs) represent a class of hierarchical programs that allow for modeling problems in engineering, economics, finance, and statistics. While stochastic generalizations have been assuming increasing relevance, there is a pronounced absence of efficient first/zeroth-order schemes with non-asymptotic rate guarantees for resolving even deterministic variants of such problems. We consider a subclass of stochastic MPECs (SMPECs) where the parametri...
-
作者：Arjevani, Yossi; Carmon, Yair; Duchi, John C.; Foster, Dylan J.; Srebro, Nathan; Woodworth, Blake
作者单位：Hebrew University of Jerusalem; Tel Aviv University; Stanford University; Microsoft; Inria
摘要：We lower bound the complexity of finding epsilon-stationary points (with gradient norm at most epsilon) using stochastic first-order methods. In a well-studied model where algorithms access smooth, potentially non-convex functions through queries to an unbiased stochastic gradient oracle with bounded variance, we prove that (in the worst case) any algorithm requires at least epsilon(-4) queries to find an epsilon-stationary point. The lower bound is tight, and establishes that stochastic gradi...
-
作者：Aissi, Hassene; Chen, Da Qi; Ravi, R.
作者单位：Universite PSL; Universite Paris-Dauphine; Carnegie Mellon University; Carnegie Mellon University
摘要：We consider the problem of interdicting a directed graph by deleting nodes with the goal of minimizing the local edge connectivity of the remaining graph from a given source to a sink. We introduce and study a general downgrading variant of the interdiction problem where the capacity of an arc is a function of the subset of its endpoints that are downgraded, and the goal is to minimize the downgraded capacity of a minimum source-sink cut subject to a node downgrading budget. This models the ca...
-
作者：Basu, Amitabh; Conforti, Michele; Di Summa, Marco; Jiang, Hongyi
作者单位：Johns Hopkins University; University of Padua
摘要：We investigate the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms for mixed-integer optimization. In particular, we study the relative efficiency of BB and CP, when both are based on the same family of disjunctions. We extend a result of Dash (International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 145-160, 2002) to the nonlinear setting which shows that for convex 0/1 problems, CP does at least as well as BB, with variable ...
-
作者：Combettes, Cyrille W.; Pokutta, Sebastian
作者单位：University System of Georgia; Georgia Institute of Technology; Technical University of Berlin; Zuse Institute Berlin
摘要：The approximate Caratheodory theorem states that given a compact convex set C subset of R-n and p is an element of[2,+infinity[, each point x*is an element of C can be approximated to epsilon-accuracy in the l(p)-norm as the convex combination of O(pD(p)(2)/epsilon(2)) vertices of C, where D-p is the diameter of C in the l(p)-norm. A solution satisfying these properties can be built using probabilistic arguments or by applying mirror descent to the dual problem. We revisit the approximate Cara...
-
作者：Poon, Clarice; Peyre, Gabriel
作者单位：University of Bath; Centre National de la Recherche Scientifique (CNRS)
摘要：Non-smooth optimization is a core ingredient of many imaging or machine learning pipelines. Non-smoothness encodes structural constraints on the solutions, such as sparsity, group sparsity, low-rank and sharp edges. It is also the basis for the definition of robust loss functions and scale-free functionals such as square-root Lasso. Standard approaches to deal with non-smoothness leverage either proximal splitting or coordinate descent. These approaches are effective but usually require parame...
-
作者：Xu, Zi; Zhang, Huiling; Xu, Yang; Lan, Guanghui
作者单位：Shanghai University; University System of Georgia; Georgia Institute of Technology
摘要：Much recent research effort has been directed to the development of efficient algo-rithms for solving minimax problems with theoretical convergence guarantees due to the relevance of these problems to a few emergent applications. In this paper, we propose a unified single-loop alternating gradient projection (AGP) algorithm for solving smooth nonconvex-(strongly) concave and (strongly) convex-nonconcave minimax problems. AGP employs simple gradient projection steps for updating the primal and ...
-
作者：Barre, Mathieu; Taylor, Adrien B.; Bach, Francis
作者单位：Universite PSL; Ecole Normale Superieure (ENS); Universite PSL; Ecole Normale Superieure (ENS); Inria
摘要：Proximal operations are among the most common primitives appearing in both practical and theoretical (or high-level) optimization methods. This basic operation typically consists in solving an intermediary (hopefully simpler) optimization problem. In this work, we survey notions of inaccuracies that can be used when solving those intermediary optimization problems. Then, we show that worst-case guarantees for algorithms relying on such inexact proximal operations can be systematically obtained...
-
作者：Tsuchiya, Takashi; Lourenco, Bruno F.; Muramatsu, Masakazu; Okuno, Takayuki
作者单位：National Graduate Institute for Policy Studies; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; University of Electro-Communications - Japan; Seikei University
摘要：We consider primal-dual pairs of semidefinite programs and assume that they are singular, i.e., both primal and dual are either weakly feasible or weakly infeasible. Under such circumstances, strong duality may break down and the primal and dual might have a nonzero duality gap. Nevertheless, there are arbitrary small perturbations to the problem data which would make them strongly feasible thus zeroing the duality gap. In this paper, we conduct an asymptotic analysis of the optimal value as t...
