Pushing the Limits of the Reactive Affine Shaker Algorithm to Higher Dimensions

• URL: http://arxiv.org/abs/2502.12877v1
• Date: Tue, 18 Feb 2025 14:06:20 GMT
• Title: Pushing the Limits of the Reactive Affine Shaker Algorithm to Higher Dimensions
• Authors: Roberto Battiti, Mauro Brunato,
• Abstract summary: "Reactive Affine Shaker" (RAS) is a simple algorithm for searching very large-dimensional spaces.<n>Despite its simplicity and its use of only local search, surprisingly the produced results are comparable to and not too far from the state-of-the-art results of BO.
• Score: 0.4143603294943439
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bayesian Optimization (BO) for the minimization of expensive functions of continuous variables uses all the knowledge acquired from previous samples (${\boldsymbol x}_i$ and $f({\boldsymbol x}_i)$ values) to build a surrogate model based on Gaussian processes. The surrogate is then exploited to define the next point to sample, through a careful balance of exploration and exploitation. Initially intended for low-dimensional spaces, BO has recently been modified and used also for very large-dimensional spaces (up to about one thousand dimensions). In this paper we consider a much simpler algorithm, called "Reactive Affine Shaker" (RAS). The next sample is always generated with a uniform probability distribution inside a parallelepiped (the "box"). At each iteration, the form of the box is adapted during the search through an affine transformation, based only on the point $\boldsymbol x$ position and on the success or failure in improving the function. The function values are therefore not used directly to modify the search area and to generate the next sample. The entire dimensionality is kept (no active subspaces). Despite its extreme simplicity and its use of only stochastic local search, surprisingly the produced results are comparable to and not too far from the state-of-the-art results of high-dimensional versions of BO, although with some more function evaluations. An ablation study and an analysis of probability distribution of directions (improving steps and prevailing box orientation) in very large-dimensional spaces are conducted to understand more about the behavior of RAS and to assess the relative importance of the algorithmic building blocks for the final results.

Related papers

• Entangled Mean Estimation in High-Dimensions [36.97113089188035]
  We study the task of high-dimensional entangled mean estimation in the subset-of-signals model.<n>We show that the optimal error (up to polylogarithmic factors) is $f(alpha,N) + sqrtD/(alpha N)$, where the term $f(alpha,N)$ is the error of the one-dimensional problem and the second term is the sub-Gaussian error rate.
  arXiv  Detail & Related papers  (2025-01-09T18:31:35Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Modified Step Size for Enhanced Stochastic Gradient Descent: Convergence and Experiments [0.0]
  This paper introduces a novel approach to the performance of the gradient descent (SGD) algorithm by incorporating a modified decay step size based on $frac1sqrttt. The proposed step size integrates a logarithmic step term, leading to the selection of smaller values in the final iteration. To the effectiveness of our approach, we conducted numerical experiments on image classification tasks using the FashionMNIST, andARAR datasets.
  arXiv  Detail & Related papers  (2023-09-03T19:21:59Z)
• Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs [22.925108493465363]
  We provide an algorithmic framework for gaussianizing data distributions via averaging. We show that it is possible to efficiently construct data sketches that are nearly indistinguishable from sub-gaussian random designs.
  arXiv  Detail & Related papers  (2022-06-21T12:16:45Z)
• Subspace clustering in high-dimensions: Phase transitions \& Statistical-to-Computational gap [24.073221004661427]
  A simple model to study subspace clustering is the high-dimensional $k$-Gaussian mixture model. We provide an exact characterization of the statistically optimal reconstruction error in this model in the high-dimensional regime with extensive sparsity.
  arXiv  Detail & Related papers  (2022-05-26T17:47:35Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  A novel model-free algorithm is proposed to minimize regret in episodic reinforcement learning. The proposed algorithm employs an em early-settled reference update rule, with the aid of two Q-learning sequences. The design principle of our early-settled variance reduction method might be of independent interest to other RL settings.
  arXiv  Detail & Related papers  (2021-10-09T21:13:48Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  We propose a model-free reinforcement learning algorithm inspired by the popular randomized least squares value iteration (RLSVI) algorithm. Our algorithm drives exploration by simply perturbing the training data with judiciously chosen i.i.d. scalar noises. We complement the theory with an empirical evaluation across known difficult exploration tasks.
  arXiv  Detail & Related papers  (2021-06-15T02:23:07Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  We develop a new algorithm for non-critical optimization that finds an $O(epsilon)$epsilon point in the optimal product. We validate our results on a variety of large-scale deep learning benchmarks and architectures.
  arXiv  Detail & Related papers  (2021-03-04T19:01:20Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator) We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$. We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
  arXiv  Detail & Related papers  (2020-05-26T17:53:18Z)
• Efficient Algorithms for Multidimensional Segmented Regression [42.046881924063044]
  We study the fundamental problem of fixed design em multidimensional regression. We provide the first sample and computationally efficient algorithm for this problem in any fixed dimension. Our algorithm relies on a simple merging iterative approach, which is novel in the multidimensional setting.
  arXiv  Detail & Related papers  (2020-03-24T19:39:34Z)
• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration [94.47472987987805]
  We consider the exploration-exploitation dilemma in finite-horizon reinforcement learning (RL) In this paper, we introduce an optimistically-perturbed variant of the popular randomized least-squares value (RLSVI) Under the assumption that the Markov decision process has low-rank transition dynamics, we prove that the frequentist regret of RLSVI is upper-bounded by $widetilde O(d2 H2 sqrtT)$ where $ d $ are the feature dimension, $ H $ is the horizon, and $ T $ is the total number of
  arXiv  Detail & Related papers  (2019-11-01T19:48:57Z)

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.