-
作者：Lim, Dong-Young; Neufeld, Ariel; Sabanis, Sotirios; Zhang, Ying
作者单位：Ulsan National Institute of Science & Technology (UNIST); Nanyang Technological University; University of Edinburgh; Alan Turing Institute; National Technical University of Athens; Hong Kong University of Science & Technology (Guangzhou)
摘要：We introduce a new Langevin dynamics based algorithm, called the extended tamed hybrid epsilon-order polygonal unadjusted Langevin algorithm (e-TH epsilon O POULA), to solve optimization problems with discontinuous stochastic gradients, which naturally appear in real-world applications such as quantile estimation, vector quantization, conditional value at risk (CVaR) minimization, and regularized optimization problems involving rectified linear unit (ReLU) neural networks. We demonstrate both ...
-
作者：Bellon, Antonio; Henrion, Didier; Kungurtsev, Vyacheslav; Marec, Jakub
作者单位：Czech Technical University Prague; Universite de Toulouse; Centre National de la Recherche Scientifique (CNRS)
摘要：In many applications, solutions of convex optimization problems are updated on-line, as functions of time. In this paper, we consider parametric semidefinite programs, which are linear optimization problems in the semidefinite cone whose coefficients (input data) depend on a time parameter. We are interested in the geometry of the solution (output data) trajectory, defined as the set of solutions depending on the parameter. We propose an exhaustive description of the geometry of the solution t...
-
作者：Davies, Sami; Moseley, Benjamin; Newman, Heather
作者单位：University of California System; University of California Berkeley; Carnegie Mellon University; Vassar College
摘要：We design the first purely combinatorial O(1)-factor algorithms for correlation clustering with respect to the fp-norm of the disagreement vector. Our main technical contribution is the construction of a novel semimetric on the set of vertices, which we call the correlation metric, that indicates to our clustering algorithms whether pairs of nodes should be in the same cluster. The power of the correlation metric allows us to design an algorithm that outputs a single clustering solution that i...
-
作者：Li, Shukai; Mehrotra, Sanjay
作者单位：Northwestern University
摘要：This paper develops a new method for computing the stationary distribution and steady-state performance measures of stochastic systems that can be described as a continuous-state Markov chain supported on R. The balance equations are solved by constructing a proxy Markov chain with finite states. We show the consistency of an approximate solution and provide deterministic nonasymptotic error bounds under the supremum norm. Our method is near optimal among all approximation methods using discre...
-
作者：Ahn, Hyun-Soo; Ryan, Christopher Thomas; Uichanco, Joline; Zhang, Mengzhenyu
作者单位：University of Michigan System; University of Michigan; University of British Columbia; University of London; University College London
摘要：When underlying demand follows a complex stochastic process, pricing problems are difficult to solve. In such cases, certainty equivalent (CE) policies, based on the solution to the deterministic relaxation of the stochastic pricing problem, can be used as practical alternatives. CE policies have lighter computational and informational requirements compared with solving the problem to optimality. Although the effectiveness of CE pricing policies has been theoretically studied when demands are ...
-
作者：Black, Alexander E.; De Loera, Jestis A.; Kafer, Sean; Sanita, Laura
作者单位：University of California System; University of California Davis; University System of Georgia; Georgia Institute of Technology; Bocconi University
摘要：We present three new pivot rules for the Simplex method for Linear Programs over 0/1-polytopes. We show that the number of nondegenerate steps taken using these three rules is strongly polynomial, linear in the number of variables, and linear in the dimension. Our bounds on the number of steps are asymptotically optimal on several well-known combinatorial polytopes. Our analysis is based on the geometry of 0/1 -polytopes and novel modifications to the classical steepest -edge and shadow -verte...
-
作者：Yu, Qimeng; Kucukyavuz, Simge
作者单位：Universite de Montreal; Northwestern University
摘要：Diminishing returns (DR)-submodular functions encompass a broad class of functions that are generally nonconvex and nonconcave. We study the problem of minimizing any DR-submodular function with continuous and general integer variables under box constraints and, possibly, additional monotonicity constraints. We propose valid linear inequalities for the epigraph of any DR-submodular function under the constraints. We further provide the complete convex hull of such an epigraph, which, surprisin...
-
作者：Li, Yuan; Goldberg, David A.
作者单位：Amazon.com
摘要：We consider the FCFS GI/GI/n queue, and prove the first simple and explicit bounds that scale as( 1)/(1-rho) under only the assumption that inter-arrival times have finite second moment, and service times have finite 2+& varepsilon; moment for some & varepsilon;>0. Here rho denotes the corresponding traffic intensity. Conceptually, our results can be viewed as a multi-server analogue of Kingman's bound. Our main results are bounds for the tail of the steady-state queue length and the steady-st...
-
作者：Hua, Zheng; Qu, Zheng
作者单位：University of Hong Kong; Shenzhen University
摘要：In this paper, we address the effective degree bound problem for Lasserre's hierarchy of moment-sum-of-squares (SOS) relaxations in polynomial optimization involving n variables. We assume that the first n equality constraint polynomials g1, ... ,gn do not share any nontrivial common complex zero locus at infinity and that the optimal solutions are nonsingular. Under these conditions, we derive an effective degree bound for the exactness of Lasserre's hierarchy. Importantly, the assumption of ...
-
作者：Li, Zanyu; Bao, Chenglong
作者单位：Tsinghua University; Tsinghua University; Yanqi Lake Beijing Institute of Mathematical Sciences & Applications
摘要：Anderson mixing (AM) method is a popular approach for accelerating fixedpoint iterations by leveraging historical information from previous steps. In this paper, we introduce the Riemannian Anderson mixing (RAM) method, an extension of AM to Riemannian manifolds, and analyze its local linear convergence under reasonable assumptions. Unlike other extrapolation-based algorithms on Riemannian manifolds, RAM does not require computing the inverse retraction or inverse exponential mapping and has a...
