2025

最新文章

• Inexact subgradient methods for semialgebraic functions AI翻译
  作者：Bolte, Jerome; Le, Tam; Moulines, Eric; Pauwels, Edouard
  作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Inria; Institut Polytechnique de Paris; Ecole Polytechnique; Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics
  摘要：Motivated by the extensive application of approximate gradients in machine learning and optimization, we investigate inexact subgradient methods subject to persistent additive errors. Within a nonconvex semialgebraic framework, assuming boundedness or coercivity, we establish that the method yields iterates that eventually fluctuate near the critical set at a proximity characterized by an O(& varepsilon;rho)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{ams...
• Low solution rank of the matrix LASSO under RIP with consequences for rank-constrained algorithms AI翻译
  作者：McRae, Andrew D.
  作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
  摘要：We show that solutions to the popular convex matrix LASSO problem (nuclear-norm-penalized linear least-squares) have low rank under similar assumptions as required by classical low-rank matrix sensing error bounds. Although the purpose of the nuclear norm penalty is to promote low solution rank, a proof has not yet (to our knowledge) been provided outside very specific circumstances. Furthermore, we show that this result has significant theoretical consequences for nonconvex rank-constrained o...
• A nearly optimal randomized algorithm for explorable heap selection AI翻译
  作者：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...
• Structural iterative rounding for generalized k-median problems AI翻译
  作者：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...
• Exploiting the polyhedral geometry of stochastic linear bilevel programming AI翻译
  作者：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...
• Generalized minimum 0-extension problem and discrete convexity AI翻译
  作者：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...
• Non-asymptotic global convergence rates of BFGS with exact line search AI翻译
  作者：Jin, Qiujiang; Jiang, Ruichen; Mokhtari, Aryan
  作者单位：University of Texas System; University of Texas Austin
  摘要：In this paper, we explore the non-asymptotic global convergence rates of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method implemented with exact line search. Notably, due to Dixon's equivalence result, our findings are also applicable to other quasi-Newton methods in the convex Broyden class employing exact line search, such as the Davidon-Fletcher-Powell (DFP) method. Specifically, we focus on problems where the objective function is strongly convex with Lipschitz continuous gradient and He...
• Optimizing over path-length matrices of unrooted binary trees AI翻译
  作者：Catanzaro, Daniele; Pesenti, Raffaele; Sapucaia, Allan; Wolsey, Laurence
  作者单位：Universite Catholique Louvain; Universita Ca Foscari Venezia
  摘要：Path-Length Matrices (PLMs) form a tree encoding scheme that is often used in the context of optimization problems defined over Unrooted Binary Trees (UBTs). Determining the conditions that a symmetric integer matrix of order n >= 3 must satisfy to encode the PLM of a UBT with n leaves is central to these applications. Here, we show that a certain subset of known necessary conditions is also sufficient to characterize the set Theta(n) of PLMs induced by the set of UBTs with n leaves. We also i...
• Neural spectrahedra and semidefinite lifts: global convex optimization of degree-two polynomial activation neural networks in polynomial-time AI翻译
  作者：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...
• Optimizing distortion riskmetrics with distributional uncertainty AI翻译
  作者：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...