-
作者：Comaneci, Andrei; Plastria, Frank
作者单位：Technical University of Berlin; Vrije Universiteit Brussel
摘要：We compute the robustness of Fermat-Weber points with respect to any finite gauge. We show a breakdown point of 1/(1+sigma)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/(1+\sigma )$$\end{document} where sigma\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackag...
-
作者：Del Pia, Alberto; Kaibel, Volker
作者单位：University of Wisconsin System; University of Wisconsin Madison
-
作者：Evens, Brecht; Pas, Pieter; Latafat, Puya; Patrinos, Panagiotis
作者单位：KU Leuven; IMT School for Advanced Studies Lucca
摘要：The proximal point algorithm (PPA) is the most widely recognized method for solving inclusion problems and serves as the foundation for many numerical algorithms. Despite this popularity, its convergence results have been largely limited to the monotone setting. In this work, we study the convergence of (relaxed) preconditioned PPA for a class of nonmonotone problems that satisfy an oblique weak Minty condition. Additionally, we study the (relaxed) Douglas-Rachford splitting (DRS) method in th...
-
作者：Gao, Bin; Peng, Renfeng; Yuan, Ya-xiang
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS
摘要：In the realm of tensor optimization, the low-rank Tucker decomposition is crucial for reducing the number of parameters and for saving storage. We explore the geometry of Tucker tensor varieties-the set of tensors with bounded Tucker rank-which is notably more intricate than the well-explored matrix varieties. We give an explicit parametrization of the tangent cone of Tucker tensor varieties and leverage its geometry to develop provable gradient-related line-search methods for optimization on ...
-
作者：Chandrasekaran, Karthekeyan; Chekuri, Chandra; Fiorini, Samuel; Kulkarni, Shubhang; Weltge, Stefan
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Universite Libre de Bruxelles; Technical University of Munich
摘要：We consider the feedback vertex set problem in undirected graphs (FVS). The input to FVS is an undirected graph G=(V,E) with non-negative vertex costs. The goal is to find a minimum cost subset of vertices S subset of V such that G-S is acyclic. FVS is a well-known NP-hard problem and does not admit a (2-& varepsilon;)-approximation for any fixed & varepsilon;>0 assuming the Unique Games Conjecture. There are combinatorial 2-approximation algorithms (Bafna et al., in: Algorithms and computatio...
-
作者：Wang, Guanghui; Hu, Zihao; Gentile, Claudio; Muthukumar, Vidya; Abernethy, Jacob
作者单位：University System of Georgia; Georgia Institute of Technology; Alphabet Inc.; Google Incorporated; Alphabet Inc.; Google Incorporated; Hong Kong University of Science & Technology
摘要：First-order optimization methods tend to inherently favor certain solutions over others when minimizing an underdetermined training objective that has multiple global optima. This phenomenon, known as implicit bias, plays a critical role in understanding the generalization capabilities of optimization algorithms. Recent research has revealed that in separable binary classification tasks gradient-descent-based methods exhibit an implicit bias for the & ell;2\documentclass[12pt]{minimal} \usepac...
-
作者：Balogh, Janos; Cohen, Ilan Reuven; Epstein, Leah; Levin, Asaf
作者单位：Szeged University; Bar Ilan University; University of Haifa; Technion Israel Institute of Technology
摘要：In this work, we consider online d-dimensional vector bin packing. For this problem, it is known that no algorithm can have a competitive ratio of o(d/log2d)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$o(d/\log <^>2 d)$$\end{document} in the absolute sense, although upper bounds for it are typically presented in...
-
作者：Feng, Fuxiaoyue; Ding, Chao; Li, Xudong
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; Fudan University
摘要：We introduce a quadratically convergent semismooth Newton method for nonlinear semidefinite programming that eliminates the need for the generalized Jacobian regularity, a common yet stringent requirement in existing approaches. Our strategy involves identifying a single nonsingular element within the Bouligand generalized Jacobian, thus avoiding the standard requirement for nonsingularity across the entire generalized Jacobian set, which is often too restrictive for practical applications. Th...
-
作者：Poremba, Joseph; Shepherd, F. Bruce
作者单位：University of British Columbia
摘要：In multicommodity network flows, a supply-demand graph pair (G, H) (called a multiflow topology) is cut-sufficient if, for all capacity and demand weights, the cut condition is enough to guarantee the existence of a feasible multiflow. We characterize cut-sufficiency for two classes of directed 2-commodity flows: roundtrip demands, where H is a 2-cycle, and 2-path demands, where H is a directed path of length two. We then extend these characterizations to some larger demand graphs, namely dire...
