-
作者：Guo, Shaoyan; Xu, Huifu
作者单位：Dalian University of Technology; Chinese University of Hong Kong
摘要：Sample average approximation which is also known as Monte Carlo method has been widely used for solving stochastic programming and equilibrium problems. In a data-driven environment, samples are often drawn from empirical data and hence may be potentially contaminated. Consequently it is legitimate to ask whether statistical estimators obtained from solving the sample average approximated problems are statistically robust, that is, the difference between the laws of the statistical estimators ...
-
作者：Teboulle, Marc; Vaisbourd, Yakov
作者单位：Tel Aviv University; McGill University
摘要：This work presents a novel analysis that allows to achieve tight complexity bounds of gradient-based methods for convex optimization. We start by identifying some of the pitfalls rooted in the classical complexity analysis of the gradient descent method, and show how they can be remedied. Our methodology hinges on elementary and direct arguments in the spirit of the classical analysis. It allows us to establish some new (and reproduce known) tight complexity results for several fundamental alg...
-
作者：Wu, Zijun; Moehring, Rolf H.; Ren, Chunying; Xu, Dachuan
作者单位：Hefei University; Technical University of Berlin; Beijing University of Technology
摘要：We analyze the convergence of the price of anarchy (PoA) of Nash equilibria in atomic congestion games with growing total demand T. When the cost functions are polynomials of the same degree, we obtain explicit rates for a rapid convergence of the PoAs of pure and mixed Nash equilibria to 1 in terms of 1/T and d(max)/T, where d(max) is the maximum demand controlled by an individual. Similar convergence results carry over to the random inefficiency of the random flow induced by an arbitrary mix...
-
作者：Kapelevich, Lea; Coey, Chris; Vielma, Juan Pablo
作者单位：Massachusetts Institute of Technology (MIT); Alphabet Inc.; Google Incorporated; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：Polynomial nonnegativity constraints can often be handled using the sum of squares condition. This can be efficiently enforced using semidefinite programming formulations, or as more recently proposed by Papp and Yildiz (Papp D in SIAM J O 29: 822-851, 2019), using the sum of squares cone directly in an interior point algorithm. Beyond nonnegativity, more complicated polynomial constraints (in particular, generalizations of the positive semidefinite, second order and l(1)-norm cones) can also ...
-
作者：Sun, Shigeng; Nocedal, Jorge
作者单位：Northwestern University; Northwestern University
摘要：Classical trust region methods were designed to solve problems in which function and gradient information are exact. This paper considers the case when there are errors (or noise) in the above computations and proposes a simple modification of the trust region method to cope with these errors. The new algorithm only requires information about the size/standard deviation of the errors in the function evaluations and incurs no additional computational expense. It is shown that, when applied to a...
-
作者：Li, Gen; Wei, Yuting; Chi, Yuejie; Chen, Yuxin
作者单位：University of Pennsylvania; Carnegie Mellon University
摘要：The softmax policy gradient (PG) method, which performs gradient ascent under softmax policy parameterization, is arguably one of the de facto implementations of policy optimization in modern reinforcement learning. For gamma-discounted infinite horizon tabular Markov decision processes (MDPs), remarkable progress has recently been achieved towards establishing global convergence of softmax PG methods in finding a near-optimal policy. However, prior results fall short of delineating clear depe...
-
作者：Garber, Dan
作者单位：Technion Israel Institute of Technology
摘要：We consider convex optimization problems which are widely used as convex relaxations for low-rank matrix recovery problems. In particular, in several important problems, such as phase retrieval and robust PCA, the underlying assumption in many cases is that the optimal solution is rank-one. In this paper we consider a simple and natural sufficient condition on the objective so that the optimal solution to these relaxations is indeed unique and rank-one. Mainly, we show that under this conditio...
-
作者：Josz, Cedric
作者单位：Columbia University
摘要：We consider the gradient method with variable step size for minimizing functions that are definable in o-minimal structures on the real field and differentiable with locally Lipschitz gradients. We prove that global convergence holds if continuous gradient trajectories are bounded, with the minimum gradient norm vanishing at the rate o(1/k) if the step sizes are greater than a positive constant. If additionally the gradient is continuously differentiable, all saddle points are strict, and the ...
-
作者：De Rosa, Antonio; Khajavirad, Aida
作者单位：University System of Maryland; University of Maryland College Park; Lehigh University
摘要：Joint object matching, also known as multi-image matching, namely, the problem of finding consistent partial maps among all pairs of objects within a collection, is a crucial task in many areas of computer vision. This problem subsumes bipartite graph matching and graph partitioning as special cases and is NP-hard, in general. We develop scalable linear programming (LP) relaxations with theoretical performance guarantees for joint object matching. We start by proposing a new characterization o...
-
作者：Yu, Qimeng; Kucukyavuz, Simge
作者单位：Northwestern University
摘要：We study the polyhedral convex hull structure of a mixed-integer set which arises in a class of cardinality-constrained concave submodular minimization problems. This class of problems has an objective function in the form of f (alpha(T)x), where f is a univariate concave function, a is a non-negative vector, and x is a binary vector of appropriate dimension. Such minimization problems frequently appear in applications that involve risk-aversion or economies of scale. We propose three classes ...
