A Riemannian Primal-dual Algorithm Based on Proximal Operator and its Application in Metric Learning

• URL: http://arxiv.org/abs/2005.09194v1
• Date: Tue, 19 May 2020 03:31:01 GMT
• Title: A Riemannian Primal-dual Algorithm Based on Proximal Operator and its Application in Metric Learning
• Authors: Shijun Wang, Baocheng Zhu, Lintao Ma, Yuan Qi
• Abstract summary: We propose a primal-dual algorithm to optimize the primal and dual variables iteratively. We prove convergence of the proposed algorithm and show its non-asymptotic convergence rate. Preliminary experimental results on an optimal fund selection problem in fund of funds management showed its efficacy.
• Score: 3.511851311025242
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: In this paper, we consider optimizing a smooth, convex, lower semicontinuous function in Riemannian space with constraints. To solve the problem, we first convert it to a dual problem and then propose a general primal-dual algorithm to optimize the primal and dual variables iteratively. In each optimization iteration, we employ a proximal operator to search optimal solution in the primal space. We prove convergence of the proposed algorithm and show its non-asymptotic convergence rate. By utilizing the proposed primal-dual optimization technique, we propose a novel metric learning algorithm which learns an optimal feature transformation matrix in the Riemannian space of positive definite matrices. Preliminary experimental results on an optimal fund selection problem in fund of funds (FOF) management for quantitative investment showed its efficacy.

Related papers

• Dynamic Incremental Optimization for Best Subset Selection [15.8362578568708]
  Best subset selection is considered the gold standard for many learning problems. An efficient subset-dual algorithm is developed based on the primal and dual problem structures.
  arXiv  Detail & Related papers  (2024-02-04T02:26:40Z)
• Faster Riemannian Newton-type Optimization by Subsampling and Cubic Regularization [3.867143522757309]
  This work is on constrained large-scale non-constrained optimization where the constraint set implies a manifold structure. We propose a new second-order saddleian optimization algorithm, aiming at improving convergence and reducing computational cost.
  arXiv  Detail & Related papers  (2023-02-22T00:37:44Z)
• 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)
• Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares [68.8204255655161]
  We consider potentially non- optimized approximation problems. In this paper, we propose an algorithm that achieves close to optimal a priori computational guarantees.
  arXiv  Detail & Related papers  (2022-04-11T09:37:04Z)
• Sequential Subspace Search for Functional Bayesian Optimization Incorporating Experimenter Intuition [63.011641517977644]
  Our algorithm generates a sequence of finite-dimensional random subspaces of functional space spanned by a set of draws from the experimenter's Gaussian Process. Standard Bayesian optimisation is applied on each subspace, and the best solution found used as a starting point (origin) for the next subspace. We test our algorithm in simulated and real-world experiments, namely blind function matching, finding the optimal precipitation-strengthening function for an aluminium alloy, and learning rate schedule optimisation for deep networks.
  arXiv  Detail & Related papers  (2020-09-08T06:54:11Z)
• Primal-Dual Sequential Subspace Optimization for Saddle-point Problems [3.9582154141918964]
  We introduce a new sequential subspace optimization method for large-scale saddle-point problems. It solves auxiliary saddle-point problems in low-dimensional subspaces, spanned by directions derived from first-order information over the primal emphand dual variables. Experimental results demonstrate significantly better convergence relative to popular first-order methods.
  arXiv  Detail & Related papers  (2020-08-20T18:19:19Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching. We consider two of the most popular random embeddings, namely, Gaussian embeddings and the Subsampled Randomized Hadamard Transform (SRHT)
  arXiv  Detail & Related papers  (2020-06-10T15:00:09Z)
• Riemannian Proximal Policy Optimization [15.532281292327031]
  We employ a generalian proximal optimization algorithm with guaranteed convergence to solve Markov decision process (MDP) problems. To formulate a policy model in the MDP problem, we formulate it as a nondefinite mixture model (GMs)
  arXiv  Detail & Related papers  (2020-05-19T03:37:59Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)

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.