Projected subgradient methods for paraconvex optimization: Application to robust low-rank matrix recovery

This paper establishes the convergence properties and rates of projected subgradient methods for paraconvex optimization under various step-size rules and error bound conditions, demonstrating their effectiveness through numerical experiments on diverse robust low-rank matrix recovery problems.

The Gist

Imagine you are trying to find the lowest point in a vast, foggy, and incredibly bumpy landscape. This landscape represents a complex mathematical problem where you want to minimize an "error" or "cost."

In the world of math, this is called optimization. Usually, if the landscape is a smooth bowl (convex), finding the bottom is easy. But in real life—like fixing a blurry photo, filling in missing parts of a movie rating database, or recognizing faces—the landscape is full of jagged cliffs, hidden valleys, and tricky "saddle points" (hills that look like a pass between two peaks but aren't the bottom). This is non-smooth, non-convex optimization.

This paper introduces a new, smarter way to navigate this messy terrain using a method called Projected Subgradient Methods. Here is the breakdown in simple terms:

1. The Problem: The "Bumpy" Terrain

Most standard navigation tools (algorithms) assume the ground is smooth. If you try to roll a ball down a jagged, rocky mountain, it might get stuck or bounce around wildly.

• The Challenge: The authors are dealing with a specific type of rocky terrain called Paraconvex. It's not perfectly smooth, but it's not totally chaotic either. It has a "structure" that allows us to predict how it behaves, even if it's rough.
• The Goal: Find the absolute lowest point (the global minimum) without getting stuck in a local dip or a saddle point.

2. The Tool: The "Blind Hiker" with a Compass

The method they use is like a Blind Hiker.

• How it works: The hiker can't see the whole mountain. They can only feel the ground directly under their feet (the "subgradient").
• The Move: Based on that feeling, they take a step in the direction that seems to go down.
• The "Projection": Sometimes, the hiker might step off the edge of a cliff or into a forbidden zone (like trying to make a negative number of pixels in an image). The "Projection" part is like an invisible wall that gently bounces them back onto the safe path, ensuring they stay within the rules of the problem.

3. The Secret Sauce: The "Hölderian Error Bound"

How does the hiker know they are getting close to the bottom?

• The Analogy: Imagine you are in a dark room looking for a light switch. In some rooms, the closer you get to the switch, the brighter the room gets (this is a "sharp" switch). In others, the light gets brighter very slowly.
• The Paper's Insight: The authors prove that for these specific "Paraconvex" problems, there is a reliable relationship between how far you are from the bottom and how much "downhill" you can still go. They call this the Hölderian Error Bound. It's like having a magical compass that tells you, "You are X meters away from the goal, and the ground slopes down at least Y degrees." This guarantee allows the hiker to take bigger, more confident steps.

4. The Step-Size: How Big Should the Steps Be?

The most critical part of the hiker's journey is deciding how long each step should be. The paper tests five different strategies:

1. Constant Step: Taking the same size step forever. (Good for getting close, but you might overshoot the very bottom).
2. Diminishing Step: Taking smaller and smaller steps as you get tired. (Safe, but very slow).
3. Geometric Decay: Taking steps that shrink by a fixed percentage each time (like a bouncing ball losing height). (Very fast convergence).
4. Scaled Polyak's Step: This is the Star of the Show.
   • The Analogy: Imagine the hiker looks at how far they are from the bottom (the "residual") and adjusts their step size dynamically. If they are far away, they take a huge leap. As they get closer, they take tiny, precise tiptoes.
   • The Result: The paper shows this method is incredibly efficient. It converges to the solution much faster than the others, almost like it has a sixth sense for the terrain.

5. Real-World Applications: Fixing the World

The authors didn't just do math on paper; they tested their "Blind Hiker" on real-world disasters:

• Robust Matrix Completion (MovieLens): Imagine Netflix has a database of movie ratings, but 80% of the data is missing or corrupted by trolls. The algorithm fills in the blanks to recommend movies, ignoring the bad data.
• Image Inpainting: Imagine a photo where 40% of the pixels are scratched out or covered in noise. The algorithm reconstructs the missing parts, effectively "healing" the image.
• Face Recognition: Breaking down a face into its basic parts (eyes, nose, mouth) to identify people, even if the photo is noisy or low-quality.
• Image Deblurring: Taking a photo of a moving car that looks like a smear and turning it back into a sharp image.

The Bottom Line

This paper is a guidebook for navigating the roughest, most confusing optimization problems. It proves that if you understand the specific "shape" of the problem (Paraconvexity) and use the right "compass" (Hölderian Error Bound), you can find the best solution quickly.

The Takeaway: Their new "Scaled Polyak" step-size strategy is like giving the hiker a GPS that updates in real-time. It consistently outperformed older methods in their experiments, making it a powerful new tool for fixing blurry photos, completing missing data, and solving complex machine learning puzzles.

Technical Summary

Here is a detailed technical summary of the paper "Projected subgradient methods for paraconvex optimization: Application to robust low-rank matrix recovery."

1. Problem Statement

The paper addresses the challenge of solving nonsmooth and nonconvex optimization problems of the form:
$$\min_{x \in X} f(x)$$
where $f: \mathbb{R}^n \to \mathbb{R}$ is a proper, nonsmooth, and nonconvex function, and $X$ is a nonempty, closed, and convex set.

The specific focus is on a class of functions known as $\nu$-paraconvex functions (where $\nu \in (0, 1]$). These functions generalize weakly convex functions (which correspond to the case $\nu=1$) and include many nonconvex objectives arising in signal processing, machine learning, and image reconstruction that do not satisfy standard convexity assumptions. The authors aim to analyze the convergence of Projected Subgradient Methods (PSMs) for this broader class of functions under the Hölderian Error Bound (HEB) condition.

2. Methodology

2.1 Theoretical Framework: $\nu$-Paraconvexity

The authors establish fundamental properties of $\nu$-paraconvex functions:

• Definition: A function $h$ is $\nu$-paraconvex if it satisfies an inequality involving a perturbation term $\rho \min\{\lambda, 1-\lambda\} \|x-y\|^{1+\nu}$.
• Characterization: They prove that the $\min\{\lambda, 1-\lambda\}$ term can be removed for equivalent definitions and that continuous midpoint $\nu$-paraconvexity implies full $\nu$-paraconvexity.
• Relation to Weak Convexity: They demonstrate that on compact convex sets, $\nu$-paraconvexity coincides with $\nu$-weak convexity.
• Properties: The class admits local Lipschitz continuity, ensuring the existence of Clarke subdifferentials. Crucially, they show that under the HEB condition, there exists a neighborhood around the optimal set that contains no extraneous saddle points, facilitating global convergence.

2.2 The Algorithm: Projected Subgradient Method (PSM)

The core algorithm iterates as follows:

1. Select a subgradient $\zeta_k \in \partial f(x_k)$.
2. Update: $x_{k+1} = \text{proj}_X \left( x_k - \alpha_k \frac{\zeta_k}{\|\zeta_k\|} \right)$.

The paper analyzes the convergence of this algorithm under five distinct step-size strategies:

1. Constant Step-size: $\alpha_k = \alpha$.
2. Nonsummable Diminishing (ND): $\alpha_k \to 0$, $\sum \alpha_k = \infty$.
3. Square-Summable but Not Summable (SSNS): $\sum \alpha_k = \infty$, $\sum \alpha_k^2 < \infty$.
4. Geometrically Decaying (GD): $\alpha_k = \lambda q^k$ with $0 < q < 1$.
5. Scaled Polyak's Step-size: $\alpha_k = \frac{f(x_k) - f^*}{\sigma \|\zeta_k\|}$ (requires knowledge of the optimal value $f^*$).

2.3 Convergence Analysis

The analysis relies on the Hölderian Error Bound (HEB) condition:
$$\mu \cdot \text{dist}^{1/\delta}(x; X^*) \leq f(x) - f^*$$
where $\delta \in (0, 1]$.

• Constant Step-size: Proves linear convergence of the distance to the optimal set up to a specific tolerance threshold.
• Diminishing/SSNS: Establishes subsequential and global convergence to the optimal solution.
• Geometrically Decaying & Scaled Polyak: Proves linear convergence (Q-linear) to the optimal set. Specifically, for the Scaled Polyak step-size, the rate is linear if $\delta=1$ and sublinear if $1/(1+\nu) < \delta < 1$.

3. Key Contributions

1. Theoretical Extension: The paper extends the convergence theory of subgradient methods from weakly convex functions to the broader class of $\nu$-paraconvex functions.
2. Characterization of Paraconvexity: Provides new characterizations, including the equivalence of midpoint paraconvexity and the relationship between paraconvexity and the convexity of perturbed functions ($x \mapsto f(x) + \rho \|x\|^{1+\nu}$).
3. Saddle Point Avoidance: Identifies a region around the global minimizer (under HEB) that is free of saddle points, justifying the use of local methods for global optimization in this setting.
4. Comprehensive Step-size Analysis: Derives convergence rates for five different step-size schemes, with a novel theoretical and numerical focus on the Scaled Polyak step-size in the context of paraconvex optimization.
5. Application to Robust Low-Rank Recovery: Successfully applies the theory to Robust Low-Rank Matrix Recovery, a problem class known for being nonconvex and nonsmooth.

4. Numerical Results and Applications

The authors validated their theoretical findings on several robust low-rank matrix recovery problems using Python on a MacBook Pro. The applications included:

• Robust Matrix Completion (MovieLens Dataset):

  • Result: The Scaled Polyak and Polyak strategies achieved the lowest Root Mean Squared Error (RMSE) compared to diminishing and decaying strategies.
  • Observation: Scaled Polyak converged faster and more stably, achieving an RMSE of 1.254 (vs. 1.656 for diminishing).

• Image Inpainting:

  • Result: Scaled Polyak and Polyak strategies significantly outperformed others in Peak Signal-to-Noise Ratio (PSNR) and Signal-to-Noise Ratio (SNR).
  • Observation: For the "Man" image, Scaled Polyak achieved a PSNR of 26.47 dB, while diminishing and decaying methods struggled with artifacts and lower quality.

• Robust Nonnegative Matrix Factorization (RNMF) for Face Recognition:

  • Result: Using the Olivetti Faces dataset, the Polyak step-size strategy showed the highest classification accuracy (92.5% for $k=1$) and robustness across different neighborhood sizes ($k=1, 3, 5$).
  • Observation: Polyak-based methods maintained stability as problem complexity increased, whereas decaying methods showed clear limitations.

• Robust Image Deblurring:

  • Result: Using a GMCP (Generalized Minimax Concave Penalty) regularizer, the Polyak and Scaled Polyak methods produced visually sharper reconstructions with higher PSNR (~29 dB) compared to the over-smoothed results from the diminishing rule.

5. Significance

• Bridging Theory and Practice: The paper provides a rigorous theoretical foundation for using simple, first-order subgradient methods on complex, nonconvex, and nonsmooth problems that were previously thought to require more sophisticated (and expensive) algorithms.
• Efficiency: The results demonstrate that Projected Subgradient Methods, particularly with Scaled Polyak step-sizes, are highly efficient for large-scale problems where function evaluations are costly or splitting algorithms are inapplicable.
• Robustness: The methods show superior robustness to noise and outliers in matrix recovery tasks, making them suitable for real-world applications like image processing and data mining where data is often corrupted.
• Novelty: This is the first work to provide a theoretical convergence analysis and numerical validation of the Scaled Polyak step-size specifically for $\nu$-paraconvex optimization.

In conclusion, the paper successfully argues that under the Hölderian error bound condition, simple projected subgradient methods can achieve linear convergence and high accuracy for a wide class of nonconvex problems, offering a practical and theoretically sound alternative for robust low-rank matrix recovery.