🔢 mathematics

A $\sqrt{2}$ -accelerated FISTA for composite strongly convex problems

This paper introduces a novel $\sqrt{2}$ -accelerated forward-backward splitting algorithm for composite strongly convex problems that improves the leading constant in the linear convergence rate by a factor of $\sqrt{2}$ over FISTA, derived from discretizing the continuous-time Information-Theoretic Exact Method (ITEM).

Original authors: Kansei Ushiyama

Published 2026-08-07

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Kansei Ushiyama

Original paper licensed under CC BY 4.0 (http://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

Imagine you are trying to find the lowest point in a vast, foggy valley. This isn't just any valley; it's a mathematical landscape where the ground is made of two different materials. One part is smooth and slippery, like a polished ice rink, while the other part is rough, bumpy, and full of sudden cliffs, like a rocky mountain path. In the world of computer science and data, this "valley" represents a complex problem we need to solve, such as training a smart AI to recognize faces or figuring out the best way to compress a huge image. The smooth part usually represents the data we have, and the rough part represents the rules we must follow, like keeping the solution simple or sparse.

To find the bottom of this valley, computers use a strategy called "gradient descent." Think of it like a hiker who takes a step in the direction that feels most downhill. If the ground is smooth, the hiker can glide quickly. But if the ground is bumpy, the hiker has to stop, feel around carefully, and take a cautious step. For decades, the best hikers (algorithms) known to science could get to the bottom, but they sometimes took a very long time, especially if the valley was tricky. They would zigzag, overshoot, or get stuck in small dips. The big question for researchers has always been: "Can we build a hiker who is not only careful on the bumps but also incredibly fast on the smooth parts, without getting lost?"

This paper introduces a new, super-charged hiker named SR2-FISTA. The author, Kansei Ushiyama, has designed a method that moves through this mixed terrain faster than any previously known technique. They didn't just guess; they built their new hiker by translating a continuous, flowing motion (like a river flowing downhill) into a series of discrete steps a computer can take. Their main finding is that this new algorithm reaches the bottom of the valley significantly quicker than the old champions, especially when the valley has a specific shape that makes it "strongly convex" (meaning it curves upward sharply, guaranteeing a single, clear bottom).

The paper proves mathematically that this new method is faster by a specific factor involving the square root of 2 (about 1.41 times faster in the exponent of its speed). To put it simply, if the old best method took 100 steps to get close to the answer, this new method might get there in fewer steps, or reach a much more precise answer in the same amount of time. The author also shows that their method works even when the "rough" part of the valley is slightly weird or "weakly convex" (a technical way of saying it's not perfectly bumpy but has some gentle curves), which is a common scenario in real-world problems like medical imaging or financial modeling. They didn't just simulate this on a computer; they provided a rigorous mathematical proof that their hiker will always find the bottom, and they even showed how to handle cases where the computer doesn't know exactly how slippery the smooth part is.

The Story of the Paper

The Problem: The Mixed-Terrain Valley
The paper tackles a classic optimization problem: finding the minimum value of a function $f(x)$ that is the sum of two parts, $g(x)$ and $h(x)$ .

$g(x)$ is the "smooth" part. Imagine a smooth, rolling hill. It's easy to slide down, but it might be very wide.
$h(x)$ is the "rough" part. Imagine a field of jagged rocks or a wall. You can't slide down it smoothly; you have to jump or step carefully.
The Goal: Find the absolute lowest point where these two meet.

In the real world, this happens all the time. For example, in LASSO (a method used in statistics), $g(x)$ might be the error between a prediction and the actual data (smooth), while $h(x)$ is a penalty for having too many variables (rough, like a sharp corner). The challenge is that standard methods often struggle to balance speed on the smooth part with caution on the rough part.

The Old Champions and Their Flaws
For years, the "Fast Iterative Shrinkage/Thresholding Algorithm" (FISTA) was the gold standard. It's like a hiker who uses momentum to speed up on the smooth parts but stops to check their footing on the rocks. It's fast, but it has a limit.
There was also a method called ADR (Accelerated Dual Regularization) that claimed to be faster. However, the paper points out that while ADR is good, it isn't the absolute fastest possible. The author notes that previous methods had a "speed limit" determined by a specific formula involving the square root of the ratio of the smoothness to the curvature of the valley.

The New Discovery: SR2-FISTA
The author proposes a new algorithm, which they call SR2-FISTA (Square Root 2 Strongly Convex FISTA).

How they built it: Instead of just tweaking the old steps, they looked at the problem through the lens of physics. They started with a continuous-time model (an equation describing how a particle moves through time) called the ITEM (Information-Theoretic Exact Method). This model describes a particle sliding down a hill with a very specific, changing friction.
The Magic Ingredient: The friction in this model isn't constant; it changes over time in a way described by a hyperbolic cotangent function (a fancy math curve). By carefully "discretizing" (breaking down) this smooth, flowing motion into steps a computer can take, they created a new algorithm.
The Result: The paper proves that this new algorithm converges (reaches the solution) with a rate that is faster than FISTA and ADR. Specifically, the "exponent" in the speed formula is improved by a factor of $\sqrt{2}$ .
- If the old methods were like a car going 100 mph, this new method is like a car going faster in a way that compounds over time, getting to the destination significantly sooner.
- The paper provides a mathematical proof (Theorem 6) showing that the error (the distance to the bottom) shrinks by a factor of roughly $(1 + \sqrt{2q})^{-k}$ per step, where $q$ is a measure of how "strongly" the valley curves. This is faster than the previous best known rate of $(1 + \sqrt{2q} - 6q)^{-k}$ .

Handling the "Weird" Rocks
A unique feature of this paper is that it handles cases where the "rough" part ( $h(x)$ ) isn't perfectly convex. In math terms, $h(x)$ can be "weakly convex" (it might curve slightly the wrong way, but not enough to ruin the whole problem).

Many old methods required the user to rewrite the problem to make the rough part look "nice" (convex) before they could use them.
The author's method works directly on the original problem. They show that even if the rough part is a bit "wobbly," as long as the total sum is still convex (the valley still has a bottom), their algorithm works. This is a big deal because it means you don't have to do extra math homework to use the tool; you can just plug in your messy, real-world problem.

The Proof and the Numbers
The author is very confident in their results. They didn't just run a simulation and say, "Hey, it looks fast." They provided a rigorous mathematical proof (using something called a Lyapunov function, which is like an energy meter that proves the hiker is always getting closer to the bottom).

They proved that for a specific type of problem (composite strongly convex), their method achieves the fastest known convergence rate for the objective value (the height of the valley).
They also ran a numerical experiment (Section 6) with a problem of dimension 10,000 (a very high-dimensional valley). In this test, their algorithm (SR2FISTA) was indeed faster than the old FISTA and the ADR method, confirming their theory in practice.

What They Don't Claim
It's important to note what the paper doesn't say.

They do not claim to have found the absolute fastest possible method for every single scenario. They acknowledge that while their method is the fastest known for the objective value ( $f(x_k) - f^*$ ), there is another method called Prox-ITEM that is faster for the distance to the solution ( $\|x_k - x^*\|^2$ ) in some contexts. However, in the "rough" (nonsmooth) setting of this paper, you can't always translate the distance speed into objective value speed, so their result stands as the best for the value itself.
They don't claim their method works for non-convex problems (where the valley might have multiple bottoms and no clear path). They strictly require the total problem to be convex.

Why This Matters
For a curious teenager or anyone interested in how computers learn, this paper is like upgrading the engine of a race car. It takes a problem that is already solvable and makes the solution arrive faster and more efficiently. In a world where data is growing exponentially, shaving off even a small percentage of the time it takes to train an AI or solve a complex engineering problem can save millions of dollars and hours of computing time. By proving that a specific, mathematically elegant approach (based on continuous-time physics) leads to a faster discrete algorithm, the author has given us a new, powerful tool to tackle some of the most difficult optimization challenges in science and technology.

Technical Summary: A $\sqrt{2}$ -accelerated FISTA for Composite Strongly Convex Problems

Problem Formulation
The paper addresses the minimization of composite convex functions of the form:
$\min_{x \in \mathbb{R}^d} f(x) := g(x) + h(x)$
where $g: \mathbb{R}^d \to \mathbb{R}$ is differentiable with an $L_g$ -Lipschitz continuous gradient and is $\mu_g$ -convex, and $h: \mathbb{R}^d \to \mathbb{R} \cup \{+\infty\}$ is proper, lower semicontinuous, and $\mu_h$ -convex. The author defines $\mu$ -convexity such that a function is $\mu$ -strongly convex if $\mu > 0$ and $(\mu)$ -weakly convex if $\mu < 0$ . The overall objective $f$ is assumed to be convex ( $\mu = \mu_g + \mu_h \geq 0$ ), though individual components may be weakly convex. The proximal operator of $h$ is assumed to be efficiently computable.

This formulation generalizes standard composite optimization by allowing $h$ to be weakly convex (e.g., non-convex regularizers like MCP or SCAD used to reduce bias in sparse recovery) without requiring the overall objective to be reformulated into a standard strongly convex form.

Methodology
The proposed algorithm, termed SR2 Strongly Convex FISTA, is derived by discretizing a continuous-time ordinary differential equation (ODE) model of the Information-Theoretic Exact Method (ITEM).

Continuous-Time Model: The author utilizes the ITEM ODE:
$\ddot{x}(t) + 3\sqrt{\mu} \coth(\sqrt{\mu}t) \dot{x}(t) + 2\nabla f(x(t)) = 0$
This ODE was previously established as an optimal continuous-time model for unconstrained smooth strongly convex minimization. The damping coefficient $3\sqrt{\mu} \coth(\sqrt{\mu}t)$ interpolates between the Triple Momentum Method (TMM) as $t \to \infty$ and the Optimized Gradient Method (OGM) as $\mu \to 0$ .
Discretization Strategy: To extend this to the composite (nonsmooth) setting, the author employs a Weak Discrete Gradient (wDG). Unlike standard discretizations that rely on the chain rule, the wDG provides a discrete surrogate compatible with the $\mu$ -convexity inequality for nonsmooth functions. Specifically, for $f = g + h$ , the discrete gradient is defined as $\nabla f(y, z) = \nabla g(z) + \partial h(y)$ .
Algorithm Construction: By discretizing the ITEM ODE using the wDG and a specific time-stepping scheme defined by a sequence $A_k$ , the author derives an explicit iterative algorithm (Algorithm 1). The step sizes and momentum terms are determined by solving a recurrence relation that ensures the non-increase of a discrete Lyapunov function. The algorithm requires prior knowledge of $L_g$ , $\mu_g$ , and $\mu_h$ , though the author notes that $L_g$ can be selected adaptively via backtracking.

Key Contributions

Novel Algorithm: The paper introduces SR2 FISTA, an accelerated forward-backward splitting method that directly handles weakly convex regularizers without reformulating the problem.
Convergence Rate Improvement: For the composite strongly convex case ( $\mu > 0$ ), the proposed method achieves a linear convergence rate in objective value $f(x_k) - f^\star$ with a geometric factor of $r^{-k}$ , where:
$r = 1 + q_2 + \frac{\sqrt{(q_1 + q_2)(2 - q_1 + q_2)}}{1 - q_1}$
with $q_1 = \mu_g/L_g$ and $q_2 = \mu_h/L_g$ . In the specific case where $g$ is strongly convex and $h$ is convex ( $\mu_g > 0, \mu_h = 0$ ), this factor improves upon the best previously known rate (achieved by ADR [16]) by a factor of $\sqrt{2}$ in the exponent for small condition numbers.
Unified Analysis: The convergence analysis is derived in parallel with the continuous-time analysis of the ITEM ODE, utilizing a discrete Lyapunov function that mirrors the continuous energy function. This approach provides a clear proof structure and extends validity to cases where one component is weakly convex, provided the sum remains convex.
General Convex Case: When $\mu = 0$ , the method recovers the $O(1/k^2)$ convergence rate of standard FISTA.

Results

Theoretical Bounds: The paper establishes that for $\mu > 0$ , the objective gap satisfies:
$f(x_k) - f^\star \leq \min \left( \frac{L_g - \mu_g}{2} r^{-k+1}, \frac{6L_g}{k^2} \right) \|x_0 - x^\star\|^2$
This bound offers both a fast non-asymptotic sublinear rate (useful for small $k$ or small $\mu$ ) and an exponential linear convergence rate.
Numerical Experiments: The author tested the algorithm on a synthetic problem with dimension $d=10,000$ involving a least-squares loss ( $g$ ) and a Minimax Concave Penalty (MCP) regularizer ( $h$ ), where $h$ is weakly convex. The results demonstrate that SR2 FISTA converges slightly faster than existing accelerated methods (FISTA and ADR) and significantly faster than ISTA. The observed convergence aligns with the theoretical predictions, outperforming the reference rate $O(e^{-\sqrt{2q}k})$ in the initial regime.

Significance and Claims
The author claims that, to the best of their knowledge, SR2 FISTA achieves the fastest known convergence rate for composite strongly convex minimization in terms of the objective value $f(x_k) - f^\star$ .

The author is modest regarding the optimality of their rates. They acknowledge that while Prox-ITEM [25] achieves an optimal rate for the distance to the solution ( $\|x_k - x^\star\|^2$ ) in the composite strongly convex setting, it remains unclear whether this translates to an optimal rate for the objective value in the nonsmooth setting. Consequently, the author does not claim their method is "optimal" in the absolute sense for $f(x_k) - f^\star$ , but rather that it improves the leading constant in the exponent of the convergence rate by a factor of $\sqrt{2}$ relative to the previous state-of-the-art (ADR).

The work highlights the utility of the ODE approach for deriving new algorithms and demonstrates that the ITEM ODE framework can be successfully extended to composite problems involving weakly convex regularizers, a setting increasingly relevant for bias reduction in sparse recovery and imaging.

The Story of the Paper

More like this