Sample-Efficient "Clustering and Conquer" Procedures for Parallel Large-Scale Ranking and Selection

Zishi Zhang; Yijie Peng

stat.MEFeb 3, 2024

Sample-Efficient "Clustering and Conquer" Procedures for Parallel Large-Scale Ranking and Selection

Authors: Zishi Zhang, Yijie Peng

Organizations: Guanghua School of Management, Peking University, Beijing 100871, China · School of Management and Engineering, Nanjing University, Nanjing 210008, China

Abstract

This work aims to improve the sample efficiency of parallel large-scale ranking and selection (R&S) problems by leveraging correlation information. We modify the commonly used "divide and conquer" framework in parallel computing by adding a correlation-based clustering step, transforming it into "clustering and conquer". Theoretically, we develop a novel gradient-based analysis framework and show that this seemingly simple modification substantially improves the performance of large-scale R&S procedures. Our approach enjoys two key advantages: (1) it does not require highly accurate correlation estimation or precise clustering, and (2) it can be seamlessly integrated with various existing fixed-precision and fixed-budget R&S procedures while achieving optimal sample complexity. We also introduce a new parallel clustering algorithm tailored to large-scale settings. Finally, in large-scale AI applications such as neural architecture search, our methods demonstrate superior performance.

Figures & tables

Figure 1: Parallel correlation clustering and conquer.

Figure 2: An illustrative example with 7 alternatives, where the top 3 alternatives $[1]$ , $[2]$ and $[3]$ exhibit high mean performances, and $[5]$ , $[6]$ and $[7]$ exhibit low mean performances.

G_{n}(j)=\arg\max_{i\in\{1,2,\dots,k\}}\hat{r}_{\tau_{i},j}^{n}.

Algorithm 2 Few-shot Alternative Clustering

\mathcal{AC}^{+}

Panel of Table 1 — Table 1: $\text{PCS}(1)$ and $\text{PCS}(5)$ with Different $x$ and $y$ ( $N=50$ ).

Figure 3: Required total sample size as a function of the number of alternatives $p$ . The vertical axis reports the total number of samples, and the horizontal axis is $p$ .

Panel of Table 2 — Table 2: Wall-clock running time (in seconds) for different procedures under varying numbers of alternatives $p$ .

Figure 4: Comparison of $\mathrm{PCC}_{\mathcal{A}\mathcal{C}^{+}}$ with different support set sizes $p_{s}$ .

Figure 5: Comparison of R&S procedures under different total sample sizes in the NAS experiment. The vertical axis reports the traditional probability of correct selection, $\mathrm{PCS}_{\mathrm{trad}}$ , while the horizontal axis shows the total sample size (scaled by $10^{7}$ ).

Panel of Table 3 — Table 3: Wall-clock running time (in seconds) of different procedures under varying total sample sizes in the NAS experiment.

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 342 papers

Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction
May 9, 2026Zhirayr Tovmasyan, Artavazd Maranjyan, Peter RichtárikStochastic Optimization Distributed Optimization
KAUST
Sampling Parallelism for Fast and Efficient Bayesian Learning
Apr 6, 2026Asena Karolin Özdemir, Lars H. Heyen, Arvid Weyrauch +3Bayesian Neural Networks Memory-Efficient Training
Karlsruhe Institute of Technology Karlsruhe, Germany · Helmholtz AI
Share More, Search Less: Collaborative Parallel Thinking for Efficient Test-Time Scaling
May 26, 2026Xinglin Wang, Hao Lin, Shaoxiong Feng +9Inference-Time Search Test-Time Scaling
School of Computer Science, Beijing Institute of Technology · Xiaohongshu Inc

May 9, 2026J/K move · Enter open · S save

Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction

Zhirayr Tovmasyan, Artavazd Maranjyan, Peter Richtárik

KAUST

Stochastic Optimization Distributed Optimization Nonconvex Stochastic Optimization Variance Reduction

Open paper AskPDF arXiv

Large-scale machine learning models are trained on clusters of machines that exhibit heterogeneous performance due to hardware variability, network delays, and system-level instabilities. In such environments, time complexity rather than iteration complexity becomes the relevant performance metric for optimization algorithms. Recent work by Tyurin and Richtárik (2023) established the first time complexity analysis for parallel first-order stochastic optimization, proposing Rennala SGD as a time-optimal method for smooth nonconvex optimization. However, Rennala SGD is fundamentally a modification of SGD, and variance reduction techniques are known to improve the iteration complexity of SGD. In this work, we investigate whether variance reduction can also improve time complexity in heterogeneous systems. We show that, under a mean-squared smoothness assumption, variance reduction can improve time complexity in relevant parameter regimes. To this end, we propose Rennala MVR, a variance-reduced extension of Rennala SGD based on momentum-based variance reduction, and analyze its oracle and time complexity. We establish lower bounds for time complexity under these assumptions. On a stochastic quadratic benchmark, experiments with the exact method support the theory, while neural-network experiments with a practical inexact variant show similar empirical gains over Rennala SGD.

Abstract

Clustering

Explore similar work

Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction

Sampling Parallelism for Fast and Efficient Bayesian Learning

Share More, Search Less: Collaborative Parallel Thinking for Efficient Test-Time Scaling