Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows bandit and contextual bandit online learning can sequentially tune the SOR relaxation parameter (and CG/SSOR variants) across linear systems, with regret guarantees using only iteration counts as feedback.
Problem
Choosing the relaxation parameter omega of SOR (and related solvers like preconditioned CG) is instance-dependent and expensive to optimize, yet many related linear systems are solved in sequence; the goal is end-to-end learning guarantees for tuning these parameters.
Approach
Treat omega selection as a bandit problem with iteration count as feedback; bound the number of iterations by a learnable surrogate U(omega) based on the asymptotic convergence rate, and run Tsallis-INF for a fixed comparator, or discretized Tsallis-INF / a Chebyshev-regression SquareCB for instance-optimal policies in the diagonally shifted setting.
Key results
- Tsallis-INF over an omega grid achieves expected cost approaching the best fixed omega with regret O(T^{2/3}) for semi-Lipschitz surrogate losses.
- In the diagonally shifted setting, discretized Tsallis-INF attains O(T^{3/4}) regret w.r.t. the instance-optimal policy; the SSOR Chebyshev-regression ChebCB attains O~(T^{9/11} sqrt n) regret.
- Empirically ChebCB reportedly converges to an instance-optimal policy much faster than the Tsallis-INF-based method.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use contextual bandit (ChebCB, SquareCB with Chebyshev regression) instead of discretized Tsallis-INF for diagonal shifts | SSOR parameter selection in diagonally shifted setting · semi-stochastic diagonal shifts | regret w.r.t. instance-optimal policy (theoretical exponent): O(T^{9/11}sqrt n) vs O(T^{3/4}) worse bound, but converges to instance-optimal policy faster empirically | Mixed |
Limitations
- Dependence on dimension n and precision is large in the semi-stochastic bounds; only near-asymptotic results give reasonable instance counts.
- Upper bounds are loose for suboptimal omega and for preconditioned CG; ChebCB has worse guarantees than Tsallis-INF.
- Requires knowledge of spectral bounds (beta_max, alpha_max) to set grid size and normalization.
Experimental setup
Datasets: discrete Laplacian of 100x100 square domain (synthetic) 2D heat equation with time-varying diffusion coefficient (synthetic)
Benchmarks: synthetic diagonally shifted SOR instances 2D heat equation SSOR-preconditioned CG
Metrics: total solver iterations regret
Baselines: best fixed omega instance-optimal policy Tsallis-INF randomized block-Krylov spectral radius approximation Exp3
Builds on: Tsallis-INF SquareCB algorithms with predictions Exp3
Closest papers by meaning
- Universal Sequence Preconditioning (NeurIPS 2025 · similarity 0.87)
- A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems (NeurIPS 2026 · similarity 0.86)
- Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics (ICLR 2025 · similarity 0.86)
- The Power of Second Order Methods for Sequence Preconditioning (NeurIPS 2026 · similarity 0.86)
- Solver-Free Decision-Focused Learning for Linear Optimization Problems (NeurIPS 2025 · similarity 0.85)
- Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.