A De-singularity Subgradient Approach for the Extended Weber Location Problem

• URL: http://arxiv.org/abs/2405.06965v1
• Date: Sat, 11 May 2024 09:22:44 GMT
• Title: A De-singularity Subgradient Approach for the Extended Weber Location Problem
• Abstract summary: We establish a de-singularity subgradient approach for the extended Weber location problem. We show that the proposed approach solves the problem, produces the same results as in the non-singularity cases, and shows a reasonable rate of linear convergence.
• Score: 12.263117303066831
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The extended Weber location problem is a classical optimization problem that has inspired some new works in several machine learning scenarios recently. However, most existing algorithms may get stuck due to the singularity at the data points when the power of the cost function $1\leqslant q<2$, such as the widely-used iterative Weiszfeld approach. In this paper, we establish a de-singularity subgradient approach for this problem. We also provide a complete proof of convergence which has fixed some incomplete statements of the proofs for some previous Weiszfeld algorithms. Moreover, we deduce a new theoretical result of superlinear convergence for the iteration sequence in a special case where the minimum point is a singular point. We conduct extensive experiments in a real-world machine learning scenario to show that the proposed approach solves the singularity problem, produces the same results as in the non-singularity cases, and shows a reasonable rate of linear convergence. The results also indicate that the $q$-th power case ($1<q<2$) is more advantageous than the $1$-st power case and the $2$-nd power case in some situations. Hence the de-singularity subgradient approach is beneficial to advancing both theory and practice for the extended Weber location problem.

Related papers

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• De-singularity Subgradient for the $q$-th-Powered $\ell_p$-Norm Weber Location Problem [14.506533458989853]
  The gradient of the objective does not exist at a considerable set of singular points. In this paper, we establish the de-singularity subgradient for the $q$-th-powered $ell_p$-norm case with $1leqslant p$ and $1leqslant p2$. We develop a $q$-th-powered $ell_p$-norm Weiszfeld Algorithm without Singularity ($q$P$p$NWAWS) for this problem, which ensures convergence and the descent property of the objective function.
  arXiv  Detail & Related papers  (2024-12-20T04:12:08Z)
• A quantum-classical performance separation in nonconvex optimization [7.427989325451079]
  We prove that the recently proposed Quantum Hamiltonian (QHD) algorithm is able to solve any $d$dimensional queries from this family. On the other side, a comprehensive empirical study suggests that representative state-of-the-art classical algorithms/solvers would require a superpolynomial time to solve such queries.
  arXiv  Detail & Related papers  (2023-11-01T19:51:00Z)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  This work studies problems with zero-order noisy oracle information under the assumption that the objective function is highly smooth. We consider two kinds of zero-order projected gradient descent algorithms.
  arXiv  Detail & Related papers  (2023-06-03T17:05:13Z)
• Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
  We show that Adam converges to $epsilon$-stationary points with $O(epsilon-4)$ gradient complexity under far more realistic conditions. We also propose a variance-reduced version of Adam with an accelerated gradient complexity of $O(epsilon-3)$.
  arXiv  Detail & Related papers  (2023-04-27T06:27:37Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
  Yang et al. (2023) recently showed how to use first-order gradient methods to solve general variational inequalities. We prove the convergence of this method and show that the gap function of the last iterate of the method decreases at a rate of $O(frac1sqrtK)$ when the operator is $L$-Lipschitz and monotone.
  arXiv  Detail & Related papers  (2022-10-27T17:59:09Z)
• A globally convergent fast iterative shrinkage-thresholding algorithm with a new momentum factor for single and multi-objective convex optimization [0.0]
  We show that our proposed method also has a global convergence rate of $O(1/k2)$ for any $(a,b)$. We report numerical results with various $(a,b)$, showing that some of these choices give better results than the classical momentum factors.
  arXiv  Detail & Related papers  (2022-05-11T04:26:00Z)
• Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning [99.34907092347733]
  We analyze the problem of estimating optimal $Q$-value functions for a discounted Markov decision process with discrete states and actions. Using a local minimax framework, we show that this functional arises in lower bounds on the accuracy on any estimation procedure. In the other direction, we establish the sharpness of our lower bounds, up to factors logarithmic in the state and action spaces, by analyzing a variance-reduced version of $Q$-learning.
  arXiv  Detail & Related papers  (2021-06-28T00:38:54Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)
• Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step [2.0196229393131726]
  We analyze inexact and versions of the CGALP algorithm developed in the authors' previous paper. This allows one to compute some gradients, terms, and/or linear minimization oracles in an inexact fashion. We show convergence of the Lagrangian to an optimum and feasibility of the affine constraint.
  arXiv  Detail & Related papers  (2020-05-11T14:52:16Z)
• Efficient algorithms for multivariate shape-constrained convex regression problems [9.281671380673306]
  We prove that the least squares estimator is computable via solving a constrained convex programming (QP) problem with $(n+1)d$ variables and at least $n(n-1)$ linear inequality constraints. For solving the generally very large-scale convex QP, we design two efficient algorithms, one is the symmetric Gauss-Seidel based alternating direction method of multipliers (tt sGS-ADMM), and the other is the proximal augmented Lagrangian method (tt pALM) with the subproblems solved by the semismooth Newton method (t
  arXiv  Detail & Related papers  (2020-02-26T11:18:43Z)
• Better Theory for SGD in the Nonconvex World [2.6397379133308214]
  Large-scale non optimization problems are ubiquitous in modern machine learning. We perform experiments on the effects of a wide array of synthetic minibatch sizes on the Gradient Descent (SG) problem.
  arXiv  Detail & Related papers  (2020-02-09T09:56:06Z)

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.