-
作者：Borodin, Allan; Macrury, Calum
作者单位：University of Toronto; Columbia University
摘要：We consider the classical online bipartite matching problem in the probe-commit model. In this problem, when an online vertex arrives, its edges must be probed to determine if they exist, based on known edge probabilities. A probing algorithm must respect commitment, meaning that if a probed edge exists, it must be used in the matching. Additionally, each online vertex has a patience constraint which limits the number of probes that can be made to its adjacent edges. We introduce a new configu...
-
作者：Lasserre, Jean B.
作者单位：Centre National de la Recherche Scientifique (CNRS); Communaute d'universites et etablissements de Toulouse (Comue); Universite Toulouse 1 Capitole; Toulouse School of Economics
摘要：Given two measures mu,nu\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mu ,\nu $$\end{document} on Rd\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \...
-
作者：Kilinc-Karzan, Fatma; Sun, Shengding
作者单位：Carnegie Mellon University; University of Cambridge
摘要：We study quadratic programs with m ball constraints, and the strength of a lifted convex relaxation for it recently proposed by Burer (2024). Burer shows this relaxation is exact when m=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m=2$$\end{document}. For general m, Burer (2024) provides numerical evidence that...
-
作者：Brahmachari, Shrigyan; Rubboli, Roberto; Tomamichel, Marco
作者单位：National University of Singapore; Duke University; National University of Singapore
摘要：We develop a fixed-point iterative algorithm that computes the matrix projection with respect to the Bures distance on the set of positive definite matrices that are invariant under some symmetry. We prove that the fixed-point iteration algorithm converges exponentially fast to the optimal solution in the number of iterations. Moreover, it numerically shows fast convergence compared to the off-the-shelf semidefinite program solvers. Our algorithm, for the specific case of Bures-Wasserstein bar...
-
作者：Davis, Damek; Drusvyatskiy, Dmitriy; Jiang, Liwei
作者单位：University of Pennsylvania; University of Washington; University of Washington Seattle; Purdue University System; Purdue University
摘要：A prevalent belief among optimization specialists is that linear convergence of gradient descent is contingent on the function growing quadratically away from its minimizers. In this work, we argue that this belief is inaccurate. We show that gradient descent with an adaptive stepsize converges at a local (nearly) linear rate on any smooth function that merely exhibits fourth-order growth away from its minimizer. The adaptive stepsize we propose arises from an intriguing decomposition theorem:...
-
作者：Lou, Mengqi; Verchand, Kabir Aladin; Pananjady, Ashwin
作者单位：University System of Georgia; Georgia Institute of Technology; University of Southern California; University System of Georgia; Georgia Institute of Technology
摘要：Motivated by the desire to understand stochastic algorithms for nonconvex optimization that are robust to their hyperparameter choices, we analyze a mini-batched prox-linear iterative algorithm for the canonical problem of recovering an unknown rank-1 matrix from rank-1 Gaussian measurements corrupted by noise. We derive a deterministic recursion that predicts the error of this method and show, using a non-asymptotic framework, that this prediction is accurate for any batch-size and a large ra...
-
作者：Csendes, Tibor; Toth, Boglarka G.; Locatelli, Marco
作者单位：Szeged University; University of Parma
-
作者：Li, Jiajin; Zhu, Linglingzhi; So, Anthony Man-Cho
作者单位：University of British Columbia; University System of Georgia; Georgia Institute of Technology; Chinese University of Hong Kong
摘要：Nonconvex-nonconcave minimax optimization has gained widespread interest over the last decade. However, most existing works focus on variants of gradient descent-ascent (GDA) algorithms, which are only applicable to smooth nonconvex-concave settings. To address this limitation, we propose a novel algorithm named smoothed proximal linear descent-ascent (smoothed PLDA), which can effectively handle a broad range of structured nonsmooth nonconvex-nonconcave minimax problems. Specifically, we cons...
-
作者：Aragon-Artacho, Francisco J.; Perez-Aros, Pedro; Torregrosa-Belen, David
作者单位：Universitat d'Alacant; Universidad de Chile; Universidad de Chile
摘要：In this paper we introduce the Boosted Double-proximal Subgradient Algorithm (BDSA), a novel splitting algorithm designed to address general structured nonsmooth and nonconvex mathematical programs expressed as sums and differences of composite functions. BDSA exploits the combined nature of subgradients from the data and proximal steps, and integrates a linesearch procedure to enhance its performance. While BDSA encompasses existing schemes proposed in the literature, it extends its applicabi...
-
作者：Hoppenot, Pierre; Martin, Mathis; Szigeti, Zoltan
作者单位：Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA)
