-
作者：Ilandarideva, Sasila; Juditsky, Anatoli; Lan, Guanghui; Li, Tianjiao
作者单位：Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); University System of Georgia; Georgia Institute of Technology
摘要：We consider a class of stochastic smooth convex optimization problems under rather general assumptions on the noise in the stochastic gradient observation. As opposed to the classical problem setting in which the variance of noise is assumed to be uniformly bounded, herein we assume that the variance of stochastic gradients is related to the sub-optimality of the approximate solutions delivered by the algorithm. Such problems naturally arise in a variety of applications, in particular, in the ...
-
作者：Wei, Ningji; Walteros, Jose L.
作者单位：Texas Tech University System; Texas Tech University; State University of New York (SUNY) System; University at Buffalo, SUNY
摘要：Supervalid inequalities are a specific type of constraints often used within the branch-and-cut framework to strengthen the linear relaxation of mixed-integer programs. These inequalities share the particular characteristic of potentially removing feasible integer solutions as long as they are already dominated by an incumbent solution. This paper focuses on supervalid inequalities for solving binary interdiction games. Specifically, we provide a general characterization of inequalities that a...
-
作者：de Meijer, Frank; Sotirov, Renata
作者单位：Delft University of Technology; Tilburg University
摘要：In this paper we study the well-known Chvatal-Gomory (CG) procedure for the class of integer semidefinite programs (ISDPs). We prove several results regarding the hierarchy of relaxations obtained by iterating this procedure. We also study different formulations of the elementary closure of spectrahedra. A polyhedral description of the elementary closure for a specific type of spectrahedra is derived by exploiting total dual integrality for SDPs. Moreover, we show how to exploit (strengthened)...
-
作者：Borst, Sander; Dadush, Daniel; Huiberts, Sophie; Kashaev, Danish
作者单位：Centrum Wiskunde & Informatica (CWI); Utrecht University; Columbia University
摘要：Explorable heap selection is the problem of selecting the nth smallest value in a binary heap. The key values can only be accessed by traversing through the underlying infinite binary tree, and the complexity of the algorithm is measured by the total distance traveled in the tree (each edge has unit cost). This problem was originally proposed as a model to study search strategies for the branch-and-bound algorithm with storage restrictions by Karp, Saks andWidgerson (FOCS '86), who gave determ...
-
作者：Gupta, Anupam; Moseley, Benjamin; Zhou, Rudy
作者单位：New York University; Carnegie Mellon University
摘要：This paper considers approximation algorithms for generalized k-median problems. This class of problems can be informally described as k-median with a constant number of extra constraints, and includes k-median with outliers, and knapsack median. Our first contribution is a pseudo-approximation algorithm for generalized k-median that outputs a 6.387-approximate solution, with a constant number of fractional variables. The algorithm builds on the iterative rounding framework introduced by Krish...
-
作者：Munoz, Gonzalo; Salas, David; Svensson, Anton
摘要：We study linear bilevel programming problems whose lower-level objective is given by a random cost vector with known distribution. We consider the case where this distribution is nonatomic, allowing to reformulate the problem of the leader using the Bayesian approach in the sense of Salas and Svensson (SIAM J Optim 33(3):2311-2340, 2023), with a decision-dependent distribution that concentrates on the vertices of the feasible set of the follower's problem. We call this a vertex-supported belie...
-
作者：Dvorak, Martin; Kolmogorov, Vladimir
作者单位：Institute of Science & Technology - Austria
摘要：Given a fixed finite metric space (V,mu)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(V,\mu )$$\end{document}, the minimum 0-extension problem, denoted as 0-Ext[mu]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{ma...
-
作者：Bartan, Burak; Pilanci, Mert
作者单位：Stanford University
摘要：The training of two-layer neural networks with nonlinear activation functions is an important non-convex optimization problem with numerous applications and promising performance in layerwise deep learning. In this paper, we develop exact convex optimization formulations for two-layer neural networks with second degree polynomial activations based on dual relaxations and semidefinite programming. Remarkably, we show that our semidefinite relaxations are always tight. Therefore, the computation...
-
作者：Pesenti, Silvana M.; Wang, Qiuqi; Wang, Ruodu
作者单位：University of Toronto; University System of Georgia; Georgia State University; University of Waterloo
摘要：Optimization of distortion riskmetrics with distributional uncertainty has wide applications in finance and operations research. Distortion riskmetrics include many commonly applied risk measures and deviation measures, which are not necessarily monotone or convex. One of our central findings is a unifying result that allows to convert an optimization of a non-convex distortion riskmetric with distributional uncertainty to a convex one induced from the concave envelope of the distortion functi...
-
作者：Bach, Francis
作者单位：Inria; Universite PSL; Ecole Normale Superieure (ENS)
摘要：We consider min-max optimization problems for polynomial functions, where a multivariate polynomial is maximized with respect to a subset of variables, and the resulting maximal value is minimized with respect to the remaining variables. When the variables belong to simple sets (e.g., a hypercube, the Euclidean hypersphere, or a ball), we derive a sum-of-squares formulation based on a primal-dual approach. In the simplest setting, we provide a convergence proof when the degree of the relaxatio...
