🔢 mathematics

Cost-sensitive spectral sampling algorithms for randomized block Kaczmarz methods

This paper formulates the selection of an optimal static sampling distribution for randomized block Kaczmarz methods as a cost-sensitive E-optimal design problem solvable via semidefinite programming, and proposes two certified algorithms that significantly outperform standard uniform or norm-based sampling by accounting for both row-space redundancy and varying computational costs.

Original authors: Shreyhaan Sarkar

Published 2026-06-24

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Shreyhaan Sarkar

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Solving a Puzzle with a Budget

Imagine you have a giant, complicated puzzle (a system of linear equations) that you need to solve. You can't see the whole picture at once, so you have to fix it piece by piece. This is what the Kaczmarz method does: it takes a current guess, looks at a few pieces of the puzzle (a "block" of equations), and adjusts the guess to fit those pieces better.

The problem is that you have a catalogue of different groups of pieces you could pick from. Some groups are small and easy to check (low cost), while others are huge and take a long time to process (high cost). Also, some groups of pieces give you a lot of new information, while others are just repeating what you already know (redundant).

The author, Shreyhaan Sarkar, asks a simple but tricky question: "If I have to pick a group of pieces to check over and over again, which specific mix of groups should I choose to solve the puzzle the fastest, considering both how much information they give and how long they take to check?"

The Problem with "Random" or "Expensive" Choices

The paper argues that common ways of picking these groups often fail because they ignore two things:

Redundancy: Picking a group that tells you nothing new.
Cost: Picking a group that takes forever to check, even if it gives good information.

Analogy 1: The Redundant Map
Imagine you are trying to find your way in a city. You have a map that shows the whole city (high cost, high info) and 100 tiny maps that only show one single street you already know (low cost, zero new info).

Uniform Sampling (The Naive Approach): You pick a map at random. You might pick one of the 100 tiny maps 99% of the time. You waste all your time looking at streets you already know.
The Paper's Solution: The algorithm figures out that you should ignore the 100 tiny maps and focus your time on the few maps that actually show new streets. It balances the "new info" against the "time to read."

Analogy 2: The Expensive Chef
Imagine you are cooking a meal and need to taste the soup to see if it needs salt.

Option A: A tiny spoonful (cheap, fast, but maybe not enough to tell if it's perfect).
Option B: A giant ladle (expensive, slow to scoop, but very accurate).
The Mistake: If you always use the giant ladle because it's "more accurate," you might run out of time before the meal is ready. If you only use the tiny spoon, you might never get it right.
The Paper's Solution: It calculates the perfect ratio. Maybe you use the giant ladle once, and the tiny spoon ten times. It finds the mix that gets the soup tasting perfect in the least amount of total time.

The "Magic" of the Solution

The paper doesn't just guess; it uses a mathematical framework called Optimal Design (specifically "E-optimal design") to find the perfect mix.

Think of the "blocks" of equations as ingredients in a recipe. The goal is to mix them so that the "flavor" (the solution) improves the fastest per dollar spent.

The "Cost-Sensitive" Part: The algorithm knows that some ingredients are expensive. It won't just pick the tastiest ingredient if it costs a fortune; it picks the best value.
The "Spectral" Part: This is a fancy way of saying the algorithm looks at the "shape" of the information. It checks if the ingredients are covering all the angles of the problem or if they are all pointing in the same direction (redundant).

How They Found the Answer (The Algorithms)

The paper proposes two ways to find this perfect mix:

Method 1: The "Exact Exchange" (The Careful Editor)
Imagine you are editing a book. You start with a few chapters. You solve the problem with just those chapters. Then, you look at the whole library of chapters to see if swapping one out for a new one would make the story better. If it does, you swap it. You keep doing this until no single swap can improve the story. This guarantees you have the absolute best mix, but it takes a bit of computing power.
Method 2: The "Frank-Wolfe" (The Quick Sketch)
This is like drawing a picture. You start with a rough sketch. You look at the part of the picture that is "weakest" (the part that needs the most work). You then find the single best brushstroke (block) that fixes that specific weakness. You add that stroke, look again, and repeat. It's faster and doesn't require solving the whole problem at every step, but it still gives you a very good result with a guarantee that you are close to the best possible.

The Results: Why It Matters

The author ran tests to prove this works.

Test 1 (The Redundant City): When there were 60 copies of the same "street map" and only a few unique ones, standard methods wasted time on the copies. The new method ignored the copies and focused on the unique ones, solving the puzzle 6 times faster.
Test 2 (The Expensive Chef): When there were very expensive "giant ladles" and cheap "tiny spoons," standard methods either picked the expensive ones (too slow) or the cheap ones (too inaccurate). The new method found a mix that used the expensive ones just enough to be accurate, but mostly used the cheap ones, resulting in the fastest total time.

The Bottom Line

This paper provides a "smart shopping list" for solving math problems. Instead of picking puzzle pieces randomly or just picking the biggest pieces, it calculates the perfect combination of pieces to solve the problem in the least amount of time, accounting for how hard each piece is to check.

It is an offline rule, meaning you do the math to figure out the best mix before you start solving the puzzle. Once you have the mix, you just follow it. It is most useful when you have to solve the same type of puzzle many times, or when some parts of the puzzle are much harder to check than others.

Technical Summary: Cost-sensitive spectral sampling algorithms for randomized block Kaczmarz methods

Problem Statement
The paper addresses the offline design problem for randomized block Kaczmarz methods used to solve consistent linear systems $Ax=b$. While randomized block Kaczmarz methods project iterates onto randomly selected blocks of equations, their certified convergence rate depends heavily on the sampling distribution. A critical practical constraint is that different blocks of equations may incur vastly different computational costs (e.g., due to memory layout, communication overhead, or block size).

Existing approaches often prescribe heuristics (norm-proportional, paving-based), adapt to current residuals, or optimize cost-free quantities. The specific problem addressed here is: given a fixed, finite catalogue of admissible blocks with associated positive costs, which static probability distribution over these blocks maximizes the certified exponential convergence rate per unit of expected computational work?

Methodology and Theoretical Framework
The authors formalize the problem by representing each block $B$ via its orthogonal projector $P_B$ onto the row space of the block and a cost $c_B$ .

Work-Normalized Certificate: The standard convergence certificate is governed by the smallest eigenvalue $\mu(p)$ of the expected projector $H_p = \sum p_B P_B$ restricted to the range of $A^T$ . The expected work per step is $\bar{c}(p) = \sum p_B c_B$ . The objective is to maximize the ratio $\eta(p) = \mu(p) / \bar{c}(p)$ .
Optimal Design Formulation: By introducing a change of variables $w_B = p_B / \bar{c}(p)$ , the problem is transformed into maximizing the minimum eigenvalue of a weighted sum of cost-scaled projectors $G_B/c_B$ (where $G_B$ is the projector restricted to the row space). This is identified as a cost-sensitive E-optimal design problem.
Semidefinite Programming (SDP): The problem is formulated as an SDP:
$\max t \quad \text{s.t.} \quad \sum w_B G_B \succeq t I_r, \quad \sum w_B c_B = 1, \quad w_B \ge 0$
where $r = \text{rank}(A)$ .
Dual Certificate: The paper derives a dual formulation involving a "hard-direction" certificate. The optimal value $\eta^*$ is the minimum over trace-one positive semidefinite matrices $Z$ of the maximum cost-normalized directional efficiency $\langle G_B, Z \rangle / c_B$ across the catalogue. This provides a rigorous a posteriori gap for any candidate design.
Sparse Support: A theorem based on Carathéodory's theorem establishes that an optimal design exists with support on at most $r(r+1)/2 + 1$ blocks.

Algorithmic Contributions
The paper proposes two certified algorithms to compute the optimal static distribution:

Exact Exchange Method: A column-generation scheme that maintains a small active set of blocks. It solves a restricted master SDP to find a candidate distribution and a dual certificate, then performs a "pricing" step over the full catalogue to identify a new block that improves the certificate. This method provides rigorous optimality gaps.
Frank-Wolfe-type Spectral Design: A first-order conditional gradient method applied to the cost-normalized convex hull of the projectors. It iteratively selects the block with the highest directional efficiency against the current weakest eigendirection (the supergradient of the minimum eigenvalue function). This method avoids solving restricted SDPs and uses the same quantity for both block selection and gap certification.

Results and Diagnostic Tests
The paper presents diagnostic numerical tests rather than large-scale benchmarks to isolate specific mechanisms:

Redundancy (Test A): In a catalogue with many redundant blocks for a few directions, uniform and norm-based sampling perform poorly because they waste probability mass on redundancy. The spectral design correctly concentrates mass on independent directions, improving the certificate by a factor of $(N+1)/2$ .
Cost Heterogeneity (Test B): In a setting with cheap singleton blocks and expensive large blocks, cost-blind spectral design (ignoring costs) selects the expensive blocks, achieving high per-iteration gain but poor work-normalized performance. The cost-sensitive design correctly favors the cheaper blocks, yielding a significantly lower total work to reach a target error.
Sparse Non-Diagonal Case (Test C): Using a sparse matrix with blocks of varying sizes and costs (modeled by a cubic cost function), the cost-sensitive design again outperforms uniform, norm-based, and cost-blind spectral baselines. The empirical median work observed in 20 runs closely matched the ordering predicted by the theoretical work-normalized certificate.

Significance and Claims
The paper claims to provide a complementary perspective to existing randomized projection theory. It does not introduce a new projection step or claim to optimize the exact mean-square trajectory. Instead, its significance lies in:

Formal Identification: Explicitly identifying the offline block selection problem as a cost-sensitive E-optimal design problem.
Certified Algorithms: Providing two algorithms with explicit a posteriori certificates (gaps) that quantify how close a static distribution is to the optimal work-normalized rate.
Practical Insight: Demonstrating that standard heuristics (uniform, norm-based) can be substantially suboptimal when row-space information is redundant or block costs are unbalanced.
Scope: The method is positioned as an offline static rule, most suitable for scenarios where a block catalogue is reused across many right-hand sides, or where block costs vary significantly. It is not intended for single-solve scenarios where the design cost exceeds the solve cost, nor does it replace adaptive residual-based methods which solve a different online problem.