Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms
with Predictions
- URL: http://arxiv.org/abs/2205.09961v1
- Date: Fri, 20 May 2022 04:49:57 GMT
- Title: Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms
with Predictions
- Authors: Shinsaku Sakaue, Taihei Oki
- Abstract summary: Augmenting algorithms with learned predictions is a promising approach for going beyond worst-case bounds.
We show that a warm start with learned dual solutions can improve the time complexity of the Hungarian method for weighted perfect bipartite matching.
We show the usefulness of our DCA-based framework by applying it to weighted perfect bipartite matching, weighted matroid intersection, and discrete energy minimization.
- Score: 15.191184049312467
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Augmenting algorithms with learned predictions is a promising approach for
going beyond worst-case bounds. Dinitz, Im, Lavastida, Moseley, and
Vassilvitskii~(2021) have demonstrated that a warm start with learned dual
solutions can improve the time complexity of the Hungarian method for weighted
perfect bipartite matching. We extend and improve their framework in a
principled manner via \textit{discrete convex analysis} (DCA), a discrete
analog of convex analysis. We show the usefulness of our DCA-based framework by
applying it to weighted perfect bipartite matching, weighted matroid
intersection, and discrete energy minimization for computer vision. Our
DCA-based framework yields time complexity bounds that depend on the
$\ell_\infty$-distance from a predicted solution to an optimal solution, which
has two advantages relative to the previous $\ell_1$-distance-dependent bounds:
time complexity bounds are smaller, and learning of predictions is more sample
efficient. We also discuss whether to learn primal or dual solutions from the
DCA perspective.
Related papers
- $A^*$ for Graphs of Convex Sets [7.9756690088226145]
We present a novel algorithm that fuses the existing convex-programming based approach with information to find optimality guarantees.
Our method, inspired by $A*$, initiates a best-first-like procedure from a designated subset of vertices and iteratively expands it until further growth is neither possible nor beneficial.
arXiv Detail & Related papers (2024-07-24T16:48:32Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
We show the first tight characterization of the optimal Hessian-dependent sample complexity.
A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances.
The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
arXiv Detail & Related papers (2023-06-21T17:03:22Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications.
This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
arXiv Detail & Related papers (2023-01-30T15:46:39Z) - On the Complexity of a Practical Primal-Dual Coordinate Method [63.899427212054995]
We prove complexity bounds for primal-dual algorithm with random and coordinate descent (PURE-CD)
It has been shown to obtain good extrapolation for solving bi-max performance problems.
arXiv Detail & Related papers (2022-01-19T16:14:27Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network.
We design two optimal algorithms that attain these lower bounds.
We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
arXiv Detail & Related papers (2021-06-08T15:54:44Z) - Distributed Stochastic Consensus Optimization with Momentum for
Nonconvex Nonsmooth Problems [45.88640334610308]
This paper presents a new distributed optimization algorithm for non-smooth problems.
We show that the proposed algorithm can achieve an overcal communication.
Experiments are presented to illustrate the effectiveness of the proposed algorithms.
arXiv Detail & Related papers (2020-11-10T13:12:21Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
We propose two single-timescale single-loop algorithms that require only one data point each step.
Our results are expressed in a form of simultaneous primal and dual side convergence.
arXiv Detail & Related papers (2020-08-23T20:36:49Z) - Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret
Minimization [21.64869023699999]
We study the problem of estimating the mean of a distribution in high dimensions when either the samples are adversarially corrupted or the distribution is heavy-tailed.
We provide a meta-problem and a duality theorem that lead to a new unified view on robust and heavy-tailed mean estimation in high dimensions.
arXiv Detail & Related papers (2020-07-31T04:18:32Z) - Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
Principal component analysis (PCA) is a widely used dimension reduction technique in machine learning and statistics.
Various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis.
We present thresholding as a provably accurate, time, approximation algorithm for the SPCA problem.
arXiv Detail & Related papers (2020-06-23T04:25:36Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.