Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures

• URL: http://arxiv.org/abs/2506.00165v1
• Date: Fri, 30 May 2025 19:11:03 GMT
• Title: Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
• Authors: Jie Gao, Rajesh Jayaram, Benedikt Kolbe, Shay Sapir, Chris Schwiegelshohn, Sandeep Silwal, Erik Waingarten,
• Abstract summary: We show that the effect of dimension reduction is intimately tied to the emphdoubling dimension $lambda_X$ of the underlying dataset $X$.<n>Specifically, we prove that a target dimension of $O(lambda_X)$ suffices to approximately preserve the value of any near-optimal solution.
• Score: 15.600580592567738
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Randomized dimensionality reduction is a widely-used algorithmic technique for speeding up large-scale Euclidean optimization problems. In this paper, we study dimension reduction for a variety of maximization problems, including max-matching, max-spanning tree, max TSP, as well as various measures for dataset diversity. For these problems, we show that the effect of dimension reduction is intimately tied to the \emph{doubling dimension} $\lambda_X$ of the underlying dataset $X$ -- a quantity measuring intrinsic dimensionality of point sets. Specifically, we prove that a target dimension of $O(\lambda_X)$ suffices to approximately preserve the value of any near-optimal solution,which we also show is necessary for some of these problems. This is in contrast to classical dimension reduction results, whose dependence increases with the dataset size $|X|$. We also provide empirical results validating the quality of solutions found in the projected space, as well as speedups due to dimensionality reduction.

Related papers

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• The signaling dimension in generalized probabilistic theories [48.99818550820575]
  The signaling dimension of a given physical system quantifies the minimum dimension of a classical system required to reproduce all input/output correlations of the given system. We show that it suffices to consider extremal measurements with rayextremal effects, and we bound the number of elements of any such measurement in terms of the linear dimension. For systems with a finite number of extremal effects, we recast the problem of characterizing the extremal measurements with ray-extremal effects.
  arXiv  Detail & Related papers  (2023-11-22T02:09:16Z)
• Symmetries and Dimension Reduction in Quantum Approximate Optimization Algorithm [1.3469999282609788]
  We focus on the generalized formulation of optimization problems defined on the sets of $n-element $d$-ary strings. Our main contribution encompasses dimension for the originally proposed QAOA. Restricting the algorithm to spaces of smaller dimension may lead to significant acceleration of both quantum and classical simulation of circuits.
  arXiv  Detail & Related papers  (2023-09-25T00:35:40Z)
• Linearly-scalable learning of smooth low-dimensional patterns with permutation-aided entropic dimension reduction [0.0]
  In many data science applications, the objective is to extract appropriately-ordered smooth low-dimensional data patterns from high-dimensional data sets. We show that when selecting the Euclidean smoothness as a pattern quality criterium, both of these problems can be efficiently solved numerically.
  arXiv  Detail & Related papers  (2023-06-17T08:03:24Z)
• First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces [93.35384756718868]
  min-max algorithms have been analyzed in the Euclidean setting. We prove that the extraiteient (RCEG) method corrected lastrate convergence at a linear rate.
  arXiv  Detail & Related papers  (2022-06-04T18:53:44Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering [13.208510864854894]
  Random dimensionality reduction is a versatile tool for speeding up algorithms for high-dimensional problems. We study its application to two clustering problems: the facility location problem, and the single-linkage hierarchical clustering problem.
  arXiv  Detail & Related papers  (2021-07-05T05:55:26Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  We introduce new generalized data reduction and transformation rules for the maximum weight independent set problem. Surprisingly, these so-called increasing transformations can simplify the problem and also open up the reduction space to yield even smaller irreducible graphs later in the algorithm. Our algorithm computes significantly smaller irreducible graphs on all except one instance, solves more instances to optimality than previously possible, is up to two orders of magnitude faster than the best state-of-the-art solver, and finds higher-quality solutions than solvers DynWVC and HILS.
  arXiv  Detail & Related papers  (2020-08-12T08:52:50Z)
• 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)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  We develop a convex analytic approach to analyze finite width two-layer ReLU networks. We show that an optimal solution to the regularized training problem can be characterized as extreme points of a convex set. In higher dimensions, we show that the training problem can be cast as a finite dimensional convex problem with infinitely many constraints.
  arXiv  Detail & Related papers  (2020-02-25T23:05:33Z)

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.