Block Coordinate Update (BCU) methods enjoy low per-update computational complexity because every time only one or a few block variables would need to be updated among possibly a large number of blocks. They are also easily parallelized and thus have been particularly popular for solving problems involving large-scale …
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “Block Updating”
In this paper we consider the problem of minimizing a convex function using a randomized block coordinate descent method. One of the key steps at each iteration of the algorithm is determining the update to a block of variables. Existing algorithms assume that in order to compute the update, a particular subproblem is …
We consider convex SGD updates with a block-cyclic structure, i.e. where each cycle consists of a small number of blocks, each with many samples from a possibly different, block-specific, distribution. This situation arises, e.g., in Federated Learning where the mobile devices available for updates at different times d…
Core-Halo solves large-scale fixed-point problems by decentralizing updates.
problem Large-scale fixed-point equations with block dependencies.
method Core-Halo decomposition separates write ownership from read-only context, aligning with block-dependence structure.
result Core-Halo achieves near-centralized performance while retaining parallelism.
The stochastic gradient (SG) method can minimize an objective function composed of a large number of differentiable functions, or solve a stochastic optimization problem, to a moderate accuracy. The block coordinate descent/update (BCD) method, on the other hand, handles problems with multiple blocks of variables by up…
Nonnegative matrix factorization (NMF) has attracted much attention in the last decade as a dimension reduction method in many applications. Due to the explosion in the size of data, naturally the samples are collected and stored distributively in local computational nodes. Thus, there is a growing need to develop algo…
Alternating Direction Method of Multipliers (ADMM) has become a widely used optimization method for convex problems, particularly in the context of data mining in which large optimization problems are often encountered. ADMM has several desirable properties, including the ability to decompose large problems into smalle…
Coordinate ascent variational inference is an important algorithm for inference in probabilistic models, but it is slow because it updates only a single variable at a time. Block coordinate methods perform inference faster by updating blocks of variables in parallel. However, the speed and stability of these algorithms…
In this paper we propose a randomized primal-dual proximal block coordinate updating framework for a general multi-block convex optimization model with coupled objective function and linear constraints. Assuming mere convexity, we establish its convergence rate in terms of the objective value and feasibility m…
Recent years have witnessed the rapid development of block coordinate update (BCU) methods, which are particularly suitable for problems involving large-sized data and/or variables. In optimization, BCU first appears as the coordinate descent method that works well for smooth problems or those with separable nonsmooth …
This paper is concerned with improving the empirical convergence speed of block-coordinate descent algorithms for approximate nonnegative tensor factorization (NTF). We propose an extrapolation strategy in-between block updates, referred to as heuristic extrapolation with restarts (HER). HER significantly accelerates t…
Second-order methods for neural network optimization have several advantages over methods based on first-order gradient descent, including better scaling to large mini-batch sizes and fewer updates needed for convergence. But they are rarely applied to deep learning in practice because of high computational cost and th…
Paper proposes a new pipeline for few-shot classification using forget-update module and channel vector sequence.
problem Few-shot classification with limited support samples.
method Channel vector sequence construction module and forget-update module.
result Pipeline achieves state-of-the-art results on various datasets.
DiffusionBlocks trains neural networks by breaking them into independent blocks, reducing memory usage.
problem Memory bottlenecks in end-to-end neural network training.
method Transforming transformer-based networks into independent trainable blocks via a denoising process.
result Independent block-wise training matches end-to-end training performance while reducing memory requirements.
A new graph neural network (NBA-GNN) avoids revisiting nodes to improve accuracy.
problem Redundancy in graph neural network updates causes over-squashing and inaccurate recognition.
method Proposes non-backtracking graph neural networks (NBA-GNN) that update messages without revisiting nodes.
result The NBA-GNN alleviates over-squashing and improves performance on graph benchmarks.
The problem of outlier detection is extremely challenging in many domains such as text, in which the attribute values are typically non-negative, and most values are zero. In such cases, it often becomes difficult to separate the outliers from the natural variations in the patterns in the underlying data. In this paper…
In this paper we consider a general matrix factorization model which covers a large class of existing models with many applications in areas such as machine learning and imaging sciences. To solve this possibly nonconvex, nonsmooth and non-Lipschitz problem, we develop a non-monotone alternating updating method based o…
Accelerated Block Coordinate Proximal Gradients with Applications in High Dimensional Statisticsmath.OC
Nonconvex optimization problems arise in different research fields and arouse lots of attention in signal processing, statistics and machine learning. In this work, we explore the accelerated proximal gradient method and some of its variants which have been shown to converge under nonconvex context recently. We show th…
Test-time training adapts a pretrained model to each prompt via parameter updates, improving accuracy under pretraining-to-test distribution shifts.
problem Improving accuracy of pretrained models under distribution shifts.
method Explaining TTT behavior through a decision-theoretic lens.
result TTT reduces prediction error when updates are spectrally matched to the prompt's signal-to-noise ratio and aligned with query-relevant eigen-directions.
Randomized block-diagonal preconditioning improves parallel learning convergence.
problem Improving convergence of gradient-based optimization methods in parallel settings.
method Randomization of coordinates during optimization to repartition tasks.
result Randomization significantly improves convergence of block-diagonal preconditioned methods.
Recent several years have witnessed the surge of asynchronous (async-) parallel computing methods due to the extremely big data involved in many modern applications and also the advancement of multi-core machines and computer clusters. In optimization, most works about async-parallel methods are on unconstrained proble…
A new method for efficient neural network fine-tuning using queryable low-rank update atoms.
problem Rigidity of static low-rank adaptation methods when input and depth-wise computation vary.
method A shared queryable memory of low-rank update atoms, allowing dynamic and context-sensitive adaptation.
result Improves final test performance and training stability compared to standard low-rank adaptation.
Convergence of the Stochastic Heavy Ball Method With Approximate Gradients and/or Block Updatingmath.OC
Paper proves SHB convergence with biased gradients and approximate step sizes.
problem Establishing convergence of SHB with biased gradients and approximate step sizes.
method Generalizes SHB convergence conditions for biased gradients, approximate step sizes, and block updating.
result Proves convergence of SHB with new conditions for biased gradients and approximate step sizes.
LoCo learns local representations without end-to-end synchronization, improving performance on complex tasks.
problem Learning local representations without end-to-end synchronization constraints.
method Overlap local blocks to increase decoder depth and allow feedback from upper to lower layers.
result LoCo closes the performance gap between local learning and end-to-end contrastive learning.
Training large machine learning (ML) models with many variables or parameters can take a long time if one employs sequential procedures even with stochastic updates. A natural solution is to turn to distributed computing on a cluster; however, naive, unstructured parallelization of ML algorithms does not usually lead t…
We consider a generic convex-concave saddle point problem with separable structure, a form that covers a wide-ranged machine learning applications. Under this problem structure, we follow the framework of primal-dual updates for saddle point problems, and incorporate stochastic block coordinate descent with adaptive st…
New algorithm speeds up large-scale statistical inference.
problem Efficiently solving large-scale mean-field variational inference problems.
method Developed a novel primal-dual algorithm (PD-VI) and a block-preconditioned extension (PD-VI) for mean-field variational inference.
result PD-VI and PD-VI achieve faster convergence and better solution quality compared to existing methods.
The method of block coordinate gradient descent (BCD) has been a powerful method for large-scale optimization. This paper considers the BCD method that successively updates a series of blocks selected according to a Markov chain. This kind of block selection is neither i.i.d. random nor cyclic. On the other hand, it is…
New taxonomy and improved solvers for discrete energy minimization.
problem Maximum-a-posteriori inference in discrete graphical models.
method Dual block-coordinate ascent rule, theoretical analysis, new solver variants.
result Improved state-of-the-art solver outperforming existing methods on all test instances.
We consider convex-concave saddle point problems with a separable structure and non-strongly convex functions. We propose an efficient stochastic block coordinate descent method using adaptive primal-dual updates, which enables flexible parallel optimization for large-scale problems. Our method shares the efficiency an…
Traditional learning methods for training Markov random fields require doing inference over all variables to compute the likelihood gradient. The iteration complexity for those methods therefore scales with the size of the graphical models. In this paper, we propose \emph{block belief propagation learning} (BBPL), whic…
This note presents in a technical though hopefully pedagogical way the three most common forms of neural network architectures: Feedforward, Convolutional and Recurrent. For each network, their fundamental building blocks are detailed. The forward pass and the update rules for the backpropagation algorithm are then der…
We develop parallel and distributed Frank-Wolfe algorithms; the former on shared memory machines with mini-batching, and the latter in a delayed update framework. Whenever possible, we perform computations asynchronously, which helps attain speedups on multicore machines as well as in distributed environments. Moreover…
Multi-block Min-max Bilevel Optimization with Applications in Multi-task Deep AUC Maximizationmath.OC
Paper tackles multi-block min-max optimization with applications in deep AUC maximization.
problem Multi-block min-max bilevel optimization with non-convex strongly-concave upper level and strongly convex lower level.
method Single-loop randomized stochastic algorithm for constant number of blocks per iteration.
result Sample complexity of O(1/ε^4) for finding ε-stationary point, matching optimal complexity.
New optimizer designs respect symmetry, improving deep learning models.
problem Optimizers lack respect for symmetry in neural networks.
method Introduce symmetry-compatible principle for optimizer design.
result Symmetry-compatible optimizers improve model performance.
Fast Convolutive Nonnegative Matrix Factorization Through Coordinate and Block Coordinate Updatescs.LG
Identifying recurring patterns in high-dimensional time series data is an important problem in many scientific domains. A popular model to achieve this is convolutive nonnegative matrix factorization (CNMF), which extends classic nonnegative matrix factorization (NMF) to extract short-lived temporal motifs from a long …
This paper focuses on coordinate update methods, which are useful for solving problems involving large or high-dimensional datasets. They decompose a problem into simple subproblems, where each updates one, or a small block of, variables while fixing others. These methods can deal with linear and nonlinear mappings, sm…
Many popular distributed optimization methods for training machine learning models fit the following template: a local gradient estimate is computed independently by each worker, then communicated to a master, which subsequently performs averaging. The average is broadcast back to the workers, which use it to perform a…
Paper improves recommendation systems by optimizing sequence of items for clicks.
problem Improving recommendation systems robustness against bots and clicks.
method Minimizing pairwise ranking loss over sequences of items, with thresholds to prevent bot influence.
result The proposed algorithms converge and outperform existing methods in various ranking measures.
Unified learning-rate scale for CNNs and ResNets, avoiding depth imbalance.
problem Challenges in choosing an appropriate learning rate for deep networks, especially as depth increases.
method Introduces Arithmetic-Mean P (AM-P), constraining network-wide average pre-activation second moment to a constant scale, combined with residual-aware He fan-in initialization.
result Demonstrates a scaling law for learning rates across depths, enabling zero-shot learning-rate transfer.
Improved tensor GLM estimation for complex data.
problem Complex tensor data in GLMs leads to high-dimensional, ill-posed estimation.
method Proposed LSRTR-M algorithm using Muon updates for faster convergence and lower errors.
result LSRTR-M converges faster and achieves lower errors than LSRTR.
We propose a new optimization method for training feed-forward neural networks. By rewriting the activation function as an equivalent proximal operator, we approximate a feed-forward neural network by adding the proximal operators to the objective function as penalties, hence we call the lifted proximal operator machin…
Adaptive gradient approaches that automatically adjust the learning rate on a per-feature basis have been very popular for training deep networks. This rich class of algorithms includes Adagrad, RMSprop, Adam, and recent extensions. All these algorithms have adopted diagonal matrix adaptation, due to the prohibitive co…
Speeding up Markov Chain Monte Carlo (MCMC) for datasets with many observations by data subsampling has recently received considerable attention. A pseudo-marginal MCMC method is proposed that estimates the likelihood by data subsampling using a block-Poisson estimator. The estimator is a product of Poisson estimators,…
We propose inertial versions of block coordinate descent methods for solving non-convex non-smooth composite optimization problems. Our methods possess three main advantages compared to current state-of-the-art accelerated first-order methods: (1) they allow using two different extrapolation points to evaluate the grad…
Bayesian models predict Collatz stopping times with high accuracy.
problem Predicting the total stopping time of Collatz sequences.
method Developed two complementary models: a hierarchical Negative Binomial regression and a mechanistic generative approximation.
result Bayesian models outperform generative approximations in predicting Collatz stopping times.
Sharp pseudospectral bounds prevent transient amplification in coupled gradient descent.
problem Transient amplification in coupled gradient descent systems.
method Developed a sharp pseudospectral theory for block-triangular Jacobians, proving Kreiss constant bounds and matching minimax lower bounds.
result Obtained a finite-horizon iteration-complexity bound of for stochastic coupled descent.
New algorithms improve machine learning performance with explicit regret bounds.
problem Improving machine learning performance with explicit regret bounds.
method Projection-based linear regression algorithms with a focus on modern machine-learning models and their algorithmic performance.
result Established a priori regret bounds with explicit λ-dependence.