CS Paper Radar

Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult

Alexander Tyurin

cs.LG math.OC ·submitted 2026-09-15 17:24 UTC · v1

Abstract

Modern large-scale machine learning tasks often require multiple workers, devices, CPUs, or GPUs to compute stochastic gradients in parallel and asynchronously to train model weights. Theoretical results typically distinguish between two settings: (i) the homogeneous setting, where all workers have access to the same data distribution, and (ii) the heterogeneous setting, where each worker operates on different data distributions. Known optimal time complexities in these settings reveal a significant gap, with far more pessimistic guarantees in the heterogeneous case. In this work, we investigate whether these pessimistic optimal time complexities can be overcome under different assumptions. Surprisingly, we show that improvement is provably impossible under widely used first- and second-order similarity assumptions for any randomized algorithm. We then turn to the interpolation regime and demonstrate that the weak interpolation assumption alone is also insufficient. Finally, we introduce a minimal combination of irreducible assumptions, strong interpolation and the local Polyak-Lojasiewicz condition, to derive a new time complexity bound that matches the dependence on worker computation times in the best-known result in the homogeneous setting, without requiring identical data distributions.

Closest papers

Nearest neighbours by meaning across the whole index.

High-Probability Convergence of SGD via Batched Updates

cs.LG math.OCeess.SY ·2026-09-11 ·Feng Zhu, Robert W. Heath, Aritra Mitra
published similarity 0.63
Abstract · To appear at the 65th IEEE Conference on Decision and Control

Stochastic gradient descent (SGD) is the primary workhorse for large-scale optimization. While the average behavior of its iterates, typically characterized by mean-squared error bounds, is well-understood, obtaining high-probability guarantees for the last iterate remains challenging. Prior approaches to this problem have either imposed restrictive assumptions (such as bounded domains or gradients) or relied on complex proofs involving auxiliary sequences. In this work, we propose Batched SGD, a simple variant that partitions online samples into epochs and performs a single update per epoch using a refined, low-variance gradient estimate. Our main contribution demonstrates that this batching mechanism enables a surprisingly simple high-probability analysis that avoids both restrictive assumptions and auxiliary sequences. Under standard smoothness and norm-sub-Gaussian noise assumptions, we establish near-optimal rates for both strongly convex and non-convex objectives. Furthermore, we show that our batching idea extends naturally to federated learning (FL). We provide the first high-probability guarantees for FL, achieving logarithmic communication complexity, linear speedup in the number of agents, and resilience to data heterogeneity.

0.31

New Multiple Descent Phenomena Induced by Heterogeneous Data

cs.LG stat.ML ·2026-10-27 ·Mark-Anthony Moisescu-Pareja, Elvis Dohmatob
similarity 0.61
Abstract

Modern machine learning models are often trained on large datasets assembled from many different sources, whose statistical properties can differ substantially. Understanding how this heterogeneity affects generalization performance is therefore important for explaining how model performance changes as model size increases. In this work, we study this question in linear random-feature models and show that mixtures of datasets with different covariance structures can give rise to a range of multiple-descent phenomena. We derive exact asymptotic expressions for the test error of each data source in the high-dimensional regime, and show how heterogeneity in covariance scale and spectral structure can introduce additional, group-dependent interpolation thresholds as model size increases. These phenomena arise even with noiseless labels and linear activations, showing that neither label noise nor activation nonlinearity is necessary for multiple-descent. Our results therefore provide a different perspective from classical explanations of multiple descent. More broadly, our results have potential implications for algorithmic fairness by showing that model scaling can affect different data groups unevenly, amplifying disparities in their generalization errors. We validate our theoretical results on synthetic Gaussian mixtures and real-world datasets, including MNIST and CIFAR-10.

0.11

Distribution of hitting times for dissipative random dynamical systems on $\mathbb{R}^d$, with application to stochastic gradient descent

cs.LG stat.MLmath.DS ·2026-08-11 ·Stéphane Galatolo, Stéphane Chrétien
similarity 0.61
Abstract · 24 pages

Machine Learning and more specifically Deep Learning involves solving large scale nonconvex optimization problems. Several algorithms have been proposed in the literature, that seem to achieve satisfactory practical efficiency for difficult instances, the Stochastic Gradient Method being the most rudimentary, while still outperforming more recent algorithms at a number of learning tasks. A major open question about the current methods used in deep learning is to understand their convergence properties. Following a line of previous works about the long time behavior of gradient-type algorithms, %and in particular the recent contributions from Azizian et al., we present a new approach for studying the asymptotic properties of a wide family of methods from an ergodic theoretical viewpoint. Our main results include a study of the expected time for a stochastic optimisation algorithm to reach a certain small neighborhood of a minimizer and show that this reaching time distributes exponentially around its average, which is given by the inverse of the stationary measure of the target. The assumptions on the Stochastic Gradient noise include the Gaussian and the Sub-Exponential assumptions.

0.10

Coordinating Boundaries: Improved Approximation Algorithms for Unweighted Non-Preemptive Throughput Maximization

cs.DS ·2026-10-26 ·Weitian Tong, Yao Xu
similarity 0.61
Abstract · 34 pages, 8 figures

We study unweighted nonpreemptive throughput maximization: given jobs with processing times, release times, and deadlines, schedule a maximum-cardinality subset on identical machines. For every fixed $\varepsilon>0$, we give randomized algorithms with expected approximation ratios $17/13+\varepsilon$ in polynomial time and $21/17+\varepsilon$ in pseudopolynomial time. These improve the respective $4/3+\varepsilon$ and $5/4+\varepsilon$ guarantees of Armbruster, Grandoni, Tinguely, and Wiese [STOC'26]. Both results hold for an arbitrary number of identical machines. Our algorithms build on their configuration-LP and matching framework, which partitions time into blocks. For a job whose window meets multiple blocks, its boundary blocks are the first and last such blocks. Crossing boundary pairs, whose endpoints strictly interleave, permit additional assignments to sampled execution slots, while a noncrossing family can be coordinated using consistent joint distributions on at most three blocks. The exchange analysis accounts for fractional job assignments that must be erased before inserting an additional job. For the pseudopolynomial implementation, we project configurations onto selected job identities and use separate configuration distributions with common placement marginals. This retains efficient pricing while enforcing the correlations needed for coordination.

0.15

Continuous-Time Machine Learning: A Unified Mathematical Perspective

cs.LG cs.AI ·2026-09-15 ·Waleed Razzaq, Yun-Sheng Zhao, Yun-Bo Zhao
surveybenchmark similarity 0.59
Abstract

Continuous-time (CT) machine learning has emerged as a principled framework for modeling temporal dynamics as a continuous process, particularly when observations are sampled at arbitrary time points or span long-range horizons. However, major branches of CT machine learning have matured in separate research communities, leaving their mathematical relationships and design trade-offs insufficiently characterized. In this survey, we develop a unified, concept-driven view of major CT machine learning branches through a taxonomy that organizes families according to their underlying base mathematical formulations. We present a canonical mathematical formulation that relates these families through different architectural choices of vector-field parameterization, stochasticity, memory mechanisms, and discretization. We compare training algorithms, optimization strategies, and failure modes, highlighting the trade-offs across families. We further provide a comparative analysis of theoretical computational complexity alongside an illustrative architecture-controlled benchmark analysis on representative architectures from each family. We also review software ecosystems supporting their implementation. Finally, we identify open challenges in approximation theory, training stability, hardware-efficient implementations, benchmarking, foundation models, and scientific machine learning, and discuss an agenda for future research.

0.21

Partition-Aware Scheduling for Mobile Heterogeneous Inference Co-Execution

cs.DC cs.LGcs.PF ·2026-09-13 ·Zhuojin Li, Marco Paolieri, Leana Golubchik
published similarity 0.58
Abstract · Accepted for publication in the Performance Evaluation journal (presented at IFIP Performance 2026, in Ghent, Belgium)

Modern mobile inference runs on heterogeneous platforms combining mobile GPUs with multiple CPU core clusters. Existing optimizations typically exploit either inter-operator parallelism, by assigning entire operators to CPU cores or to the GPU, or intra-operator parallelism, by partitioning each operator for CPU-GPU co-execution. We consider these two forms of parallelism together, to improve inference latency of tasks that can be represented by a static DAG of operators with predefined input/output tensor shapes (e.g., CNNs or vision transformers). We define the problem of partition-aware DAG scheduling for mobile heterogeneous inference, illustrating that the best strategy depends on the structure of the inference DAG, thus motivating a joint formulation capturing operator partition choices, device assignment, and execution order. We propose an online iterative search framework, which decomposes large DAGs into stages, focuses search on critical operators, and uses latency predictors to estimate partitioned execution without exhaustive profiling. Across representative mobile inference workloads, our approach achieves latency close to an offline solution while keeping scheduling overhead to a fraction of the model initialization cost, allowing platform-specific scheduling at deployment time.

0.29

A QPTAS for Stochastic Scheduling of Bernoulli Jobs

cs.DS cs.CCmath.OC ·2026-10-08 ·Junho Hwang
benchmark similarity 0.58
Abstract · 23 pages, 1 figure

We study the classical problem of scheduling jobs with random processing times on $m$ identical machines to minimize the expected sum of completion times, for Bernoulli jobs: job $j$ takes time $p_j$ with probability $q_j$ and time $0$ otherwise, and its outcome is revealed when it starts. The benchmark is an optimal adaptive policy. We give a quasi-polynomial-time approximation scheme for every number of machines. Previously, quasi-polynomial time was known to give an $O(\log N)$-approximation, and approximation schemes were known only for a constant number of distinct sizes. The scheme rests on a simple observation: it suffices to round the times at which machines become free, rather than the times at which jobs start, to a grid whose width is proportional to the job size, and an optimal policy stretched by a factor close to one already respects such grids. We also show that every policy that fixes the order of the jobs in advance loses a factor $Ω(\log N)$, already on two machines, so a constant factor requires adapting the order to the observed outcomes. Further results include a polynomial-time adaptive rule with ratio $\min\{m,1+\sum_j q_j\}$, a simpler approximation scheme for a constant number of sizes, and #P-hardness of computing the optimal expected cost on two machines.

0.25

Learning Rate Decay Can Exponentially Accelerate SGD for Global Optimization of Nonconvex Functions

cs.DS math.OCcs.LG ·2026-11-09 ·Guneykan Ozgul, Dylan Herman, Junhyung Lyle Kim, Shree Hari Sureshbabu, Shouvanik Chakrabarti
benchmarktheory similarity 0.58
Abstract

Stochastic Gradient Descent (SGD) is a workhorse algorithm for continuous optimization. It is a folk belief among deep learning practitioners that learning rate decay in SGD substantially improves performance. However, it has remained unclear whether learning rate decay offers an asymptotic advantage for global nonconvex optimization. We answer this question in the affirmative by demonstrating a natural class of nonconvex functions for which, we prove that SGD with learning rate decay requires exponentially fewer gradient queries for global optimization than SGD with any fixed learning rate in the small-step size regime. To the best of our knowledge, this is the first exponential advantage that has been demonstrated for learning rate decay. The class of functions we consider includes many popular benchmark nonconvex functions. Our results provide a robust explanatory theory for the empirically observed benefits of learning rate decay for global optimization. We show that annealing performs the non-logconcave sampling task associated to the optimization problem in polynomial time, via a novel application of weak Poincaré inequalities.

0.10