ECPv2: Fast, Efficient, and Scalable Global Optimization of Lipschitz Functions

• URL: http://arxiv.org/abs/2511.16575v1
• Date: Thu, 20 Nov 2025 17:30:55 GMT
• Title: ECPv2: Fast, Efficient, and Scalable Global Optimization of Lipschitz Functions
• Authors: Fares Fourati, Mohamed-Slim Alouini, Vaneet Aggarwal,
• Abstract summary: ECPv2 is a scalable and theoretically grounded algorithm for global optimization of Lipschitz-continuous functions with unknown Lipschitzs.<n>We show that ECPv2 retains ECP's no-regret guarantees with optimal-time bounds and expands the acceptance region with these findings.
• Score: 91.31596562378076
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose ECPv2, a scalable and theoretically grounded algorithm for global optimization of Lipschitz-continuous functions with unknown Lipschitz constants. Building on the Every Call is Precious (ECP) framework, which ensures that each accepted function evaluation is potentially informative, ECPv2 addresses key limitations of ECP, including high computational cost and overly conservative early behavior. ECPv2 introduces three innovations: (i) an adaptive lower bound to avoid vacuous acceptance regions, (ii) a Worst-m memory mechanism that restricts comparisons to a fixed-size subset of past evaluations, and (iii) a fixed random projection to accelerate distance computations in high dimensions. We theoretically show that ECPv2 retains ECP's no-regret guarantees with optimal finite-time bounds and expands the acceptance region with high probability. We further empirically validate these findings through extensive experiments and ablation studies. Using principled hyperparameter settings, we evaluate ECPv2 across a wide range of high-dimensional, non-convex optimization problems. Across benchmarks, ECPv2 consistently matches or outperforms state-of-the-art optimizers, while significantly reducing wall-clock time.

Related papers

• Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization [45.99743804547533]
  Two-way partial AUCAUC is a critical performance metric for binary classification with imbalanced data.<n>Existing algorithms for TPAUC optimization remain under-explored.<n>We introduce two innovative double-coordinate block-coordinate algorithms for TPAUC optimization.
  arXiv  Detail & Related papers  (2025-05-28T03:55:05Z)
• Generalized Kernel Inducing Points by Duality Gap for Dataset Distillation [14.979902937312099]
  Duality Gap KIP (DGKIP) is an extension of the Kernel Inducing Points (KIP) method for dataset distillation.<n> Experimental results on standard benchmarks such as MNIST and CIFAR-10 demonstrate that DGKIP retains the efficiency of KIP while offering broader applicability and robust performance.
  arXiv  Detail & Related papers  (2025-02-18T07:43:13Z)
• Every Call is Precious: Global Optimization of Black-Box Functions with Unknown Lipschitz Constants [72.47160195925056]
  We introduce Call Precious (P), a novel approach for global optimization of Lipschitz continuous functions.<n>P eliminates the need to estimate the Lipschitz constant, thereby minimizing additional function.<n>EC guarantees no-regret performance for evaluation budgets.
  arXiv  Detail & Related papers  (2025-02-06T18:34:40Z)
• ReLU to the Rescue: Improve Your On-Policy Actor-Critic with Positive Advantages [37.12048108122337]
  This paper proposes a step toward approximate Bayesian inference in on-policy actor-critic deep reinforcement learning. It is implemented through three changes to the Asynchronous Advantage Actor-Critic (A3C) algorithm.
  arXiv  Detail & Related papers  (2023-06-02T11:37:22Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way Partial AUC (OPAUC) and Two-way Partial AUC (TPAUC) measures the average performance of a binary classifier. Most of the existing methods could only optimize PAUC approximately, leading to inevitable biases that are not controllable. We present a simpler reformulation of the PAUC problem via distributional robust optimization AUC.
  arXiv  Detail & Related papers  (2022-10-08T08:26:22Z)
• 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)
• Certifiable Outlier-Robust Geometric Perception: Exact Semidefinite Relaxations and Scalable Global Optimization [29.738513596063946]
  We propose the first general framework to design cert algorithms for robust geometric perception in the presence of outliers. Our experiments demonstrate that our SDP relaxation is exact with up to outliers across applications.
  arXiv  Detail & Related papers  (2021-09-07T21:42:16Z)
• 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)

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.