Technical Summary: Projection-Free Functional Constrained Optimization for Risk Aversion and Sparsity Control

1. Problem Formulation

The paper addresses the functional constrained optimization problem:
$$\begin{aligned} f^* := \min_{x} \quad & f(x) \\ \text{s.t.} \quad & h_i(x) \le 0, \quad i = 1, \dots, m, \\ & x \in X, \end{aligned} \tag{1.1}$$
where $X \subseteq \mathbb{R}^n$ is a nonempty, compact, convex set. The functions $h_i$ are proper, lower semicontinuous, and convex. The objective $f$ is studied in two regimes:

1. Convex Setting: $f$ is convex (possibly nonsmooth).
2. Nonconvex Setting: $f$ is differentiable with Lipschitz continuous gradients.

This framework models applications where risk-aware criteria and sparsity constraints appear simultaneously, such as portfolio optimization (minimizing underperformance risk with asset limits) and intensity-modulated radiation therapy (IMRT) planning (minimizing overdose/underdose with sparse beam selection).

Challenge: Standard projection-based methods (e.g., penalty, augmented Lagrangian, primal-dual) require repeated projections onto $X$, which can be computationally expensive and destroy sparse structures inherent in the solution. Existing projection-free methods either handle only simple constraints or have complexity bounds dependent on the magnitude of optimal dual Lagrange multipliers, which can be arbitrarily large.

2. Methodology

The authors propose projection-free algorithms that replace projections with calls to a Linear Minimization Oracle (LMO) over $X$. The core innovation is a Level-Set Outer Loop combined with a Conditional Gradient Oracle (CGO) for saddle-point subproblems.

2.1 Convex Setting: Level Conditional Gradient (LCG)

For the convex case, the problem is reduced to finding the root of a value function $\phi(l) = \min_{x \in X} \max \{ f(x) - l, h_1(x), \dots, h_m(x) \}$.

• Outer Loop: An approximate Newton method updates the level estimate $l_k$. Instead of exact gradients, it uses a lower bound $L_k$ and an approximate subgradient derived from the inner oracle.
• Inner Loop (CGO): A specialized Conditional Gradient Oracle solves the saddle-point subproblem $\min_{x \in X} \max_{z \in Z} [f(x) - l_k] + \langle h(x), z \rangle$.
  • The oracle returns a primal iterate $x_k$ and a certificate interval $[L_k, U_k]$.
  • Crucially, the dual set $Z$ is the standard simplex, ensuring the method does not depend on the magnitude of optimal Lagrange multipliers.
  • The gap $U_k - L_k$ drives the stopping rule and level updates.
• Nonsmooth Extension: For structured nonsmooth functions (max-structure), the method employs Nesterov smoothing within the CGO framework, maintaining the same complexity order.

2.2 Nonconvex Setting: Inexact Proximal Point LCG (IPP-LCG)

For nonconvex $f$, the method reduces the problem to a sequence of convex subproblems via proximal point regularization:
$$\min_{x \in X} f(x) + L_f \|x - x_{j-1}\|^2 \quad \text{s.t.} \quad h_i(x) \le 0.$$

• Mechanism: The LCG method from the convex setting is used as an inexact solver for each proximal subproblem.
• Output: The algorithm selects the iterate that minimizes the objective decrease across the sequence.
• Guarantee: Under Slater's condition and smoothness assumptions, the method computes an $(\epsilon, \epsilon)$-near-KKT point.

3. Key Contributions

1. LCG for Convex Functional Constraints:

   • Proposes the Level Conditional Gradient (LCG) method.
   • Achieves an iteration complexity of $O(\epsilon^{-2} \log(\epsilon^{-1}))$ for obtaining an $\epsilon$-optimal and $\epsilon$-feasible solution.
   • Significance: The complexity bound is independent of the magnitude of the optimal dual Lagrange multiplier, a limitation present in prior projection-free works (e.g., Lan et al., 2021).

2. IPP-LCG for Smooth Nonconvex Objectives:

   • Develops the Inexact Proximal Point LCG (IPP-LCG) method.
   • Solves a sequence of convex subproblems using LCG, keeping all inner solves projection-free.
   • Achieves an iteration complexity of $O(\epsilon^{-3} \log(\epsilon^{-1}))$ for computing an $(\epsilon, \epsilon)$-near-KKT point.

3. Certificate Mechanism:

   • The CGO returns explicit lower and upper certificates ($L_k, U_k$) that drive the level-set updates and stopping rules, avoiding the need for exact saddle-point solutions.

4. Numerical Results

The authors evaluate the methods on two application domains:

4.1 Portfolio Selection

• Setup: Risk-averse portfolio optimization with step-risk objectives (convexified via CVaR or smoothed nonconvex surrogates) and sparsity constraints (limiting the number of assets).
• Baselines: Compared against CoexDurCG (projection-free), FISTA, PGD, and various sparsity-oriented heuristics (Greedy+Refit, IRL1, etc.) under a fixed 5-second wall-clock budget.
• Findings:
  • Convex Model: LCG achieved the best feasible out-of-sample step-risk on 5 of 6 datasets while strictly meeting sparsity targets.
  • Nonconvex Model: IPP-LCG achieved the best feasible step-risk on 4 of 6 datasets.
  • Trade-off: The methods successfully navigated the accuracy-sparsity trade-off, often outperforming projection-based baselines in feasible risk reduction within the same time budget.

4.2 Intensity-Modulated Radiation Therapy (IMRT)

• Setup: Treatment planning with group-sparsity constraints (limiting the number of beam angles) and clinical dose-volume constraints.
• Findings:
  • Convex: LCG improved constraint satisfaction compared to CoexDurCG at similar runtimes.
  • Nonconvex: A "warm-start" strategy was tested where a sparse convex LCG plan initialized the nonconvex IPP-LCG refinement.
  • Result: The warm-started IPP-LCG significantly reduced the maximum constraint violation (from 0.8438 to 0.1675) compared to a cold-start IPP-LCG, while preserving a clinically sparse treatment structure (7 angles, 20 apertures). Cold-start nonconvex optimization failed to find clinically viable plans due to severe target underdose.

5. Significance and Claims

The paper claims that its primary contribution lies in extending projection-free methods to general functional constraints without relying on the magnitude of dual multipliers for complexity guarantees. By combining a level-set outer loop with a compact saddle-point oracle, the authors retain the sparse representation benefits of conditional gradient methods (iterates as convex combinations of extreme points) while handling complex nonlinear constraints.

The numerical results suggest that:

1. LCG is effective for convex risk-sparsity problems, offering competitive or superior performance to existing projection-free and projection-based methods.
2. IPP-LCG is most effective not as a standalone solver from a random start, but as a refinement mechanism when initialized with a high-quality sparse convex solution.

The authors conclude that these methods are particularly suitable for large-scale applications where projections are expensive and sparse structural representations are desirable. Future work directions identified include developing lighter nonconvex schemes, relaxing Slater-type assumptions, and designing application-specific LMOs for implicit feasible sets.