Warm Starting Optimization via Progressive Approximation

This direction is merged into another direction: warm-start optimization (temporal warm-starting). Its last version stays readable and citable here.

Version 1 of 117 papers19 conceptsfrozen 2026-10-04

In large-scale machine learning, we typically solve optimization problems by picking a starting point—often zero or a random guess—and iteratively moving toward a solution. This "cold start" approach is computationally expensive because the optimizer must navigate the entire loss landscape from a position of total ignorance.

A more efficient paradigm has emerged across various domains: Progressive Approximation. Instead of tackling the full-scale problem immediately, these methods solve a sequence of increasingly complex approximations. By using the solution of a simpler problem to "warm start" the next, researchers can bypass the most expensive phases of optimization.

The Sample Size Ladder

The most intuitive form of progressive approximation is the Adaptive Sample Size strategy. If you have a dataset of a million points, the optimal solution for the first 1,000 points is likely very close to the optimal solution for the full million.

Aryan Mokhtari and Alejandro Ribeiro formalized this in First-Order Adaptive Sample Size Methods to Reduce Complexity of Empirical Risk Minimization. They demonstrate that by geometrically increasing the sample size and using the previous stage's solution as the next stage's starting point, one can reach the global optimum with significantly fewer total gradient evaluations.

This idea was extended to second-order methods by Majid Jahani and colleagues in their DANCE algorithm. By starting small and "growing" the sample size, they ensure the optimizer stays within the "local neighborhood" of the optimum, where Newton-type methods converge much faster. Farha AlBreiki further proved that this adaptive sampling is particularly effective for algorithms with sub-linear convergence, as it avoids wasting expensive iterations on the full dataset when the model is still far from the goal.

Incremental Model Complexity

Progressive approximation isn't limited to data volume; it also applies to the rank or complexity of the model itself. In matrix factorization, finding a high-rank representation is computationally taxing.

Tianyi Zhou and Dacheng Tao introduced the Greedy Bilateral (GreB) paradigm, which builds low-rank solutions incrementally. By using a rank-$k$ solution to initialize a rank-$(k+1)$ search, they achieved speedups of up to 100x over standard SVD-based methods. Similarly, Yan Yan and collaborators applied this to Maximum Margin Matrix Factorization, using Riemannian manifold optimization to "expand" the active subspace only as needed. This ensures that the search for new latent factors is always grounded in the representations already learned.

Divide, Conquer, and Concatenate

When the dataset is too large to process even in subsets, the strategy shifts to spatial approximation. Cho-Jui Hsieh and Inderjit S Dhillon pioneered this for Kernel SVMs. Their approach solves independent subproblems on data partitions and concatenates the results to form a high-quality global initialization.

This hierarchical logic is also central to the Scalable Optimal Margin Distribution Machine by Yilin Wang and colleagues. By treating the solutions of smaller partitions as "anchors" for the global problem, they enable the processing of massive datasets that would otherwise crash standard solvers.

Why It Works: The Neighborhood Effect

The success of progressive approximation rests on a single intuitive principle: the statistical consistency of the problem.

Whether you are looking at 10% of the data (Mokhtari & Ribeiro), a 1D version of a transport problem (marco cuturi and James Thornton in Rethinking Initialization of the Sinkhorn Algorithm), or a representative sub-problem (Y.H. Long in Kernel Inverse Optimization), the underlying structure remains similar.

By solving the "easy" version first, you place the optimizer in the local neighborhood of the global solution. In this neighborhood:

  1. The gradient points more accurately toward the goal.
  2. The curvature (Hessian) is more stable.
  3. The "distance" the optimizer must travel is drastically reduced.

By the time the algorithm reaches the full-scale, high-rank, or global problem, the "hard work" of finding the right region of the search space is already done. The final iterations become a matter of refinement rather than discovery.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_warm_starting_optimization_via_progressi_854f1415,
  title = {Warm Starting Optimization via Progressive Approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/warm-starting-optimization-via-progressive-approximation/rdr_854f1415244f472ea2a4ece2459d0a97},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_warm_starting_optimization_via_progressi_854f1415_v1,
  title = {Warm Starting Optimization via Progressive Approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/warm-starting-optimization-via-progressive-approximation/rdr_854f1415244f472ea2a4ece2459d0a97/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}