Learning with Submodular Functions: A Convex Optimization Perspective

Francis Bach

Source-linked AI summary

Learning with Submodular Functions: A Convex Optimization Perspective

Francis Bach

arXiv:1111.6453v2Nov 28, 2011cs.LGmath.OC

TL;DR

Submodular functions support both direct combinatorial optimization and machine-learning regularization, motivating a unified convex-analysis treatment. The monograph connects Lovász extensions and associated polyhedra to convex optimization, showing equivalences for submodular minimization and developing algorithms, applications, and experiments. Its methods include practical algorithms and theoretical guarantees, while some iterative approaches remain slow or unstable in particular settings.

Problem
Submodular functions arise in combinatorial optimization and machine-learning regularization, but their discrete structure requires connections to continuous convex optimization.
Method
The monograph develops submodular analysis through Lovász extensions, submodular and base polyhedra, and traditional convex optimization algorithms.
Results
The monograph shows that submodular function minimization is equivalent to convex optimization problems and presents algorithms for approximate or exact solutions with theoretical guarantees and practical illustrations.
Takeaways & Limitations
The convex perspective provides a common framework for combinatorial optimization, structured regularization, and machine-learning applications of submodular functions.
Takeaways & Limitations
The ellipsoid method has iteration cost O(p^3), strong dimension dependence, and is typically slow in practice; Kelley’s method may require many iterations and be unstable.

Abstract

from arXiv · show

Submodular functions are relevant to machine learning for at least two reasons: (1) some problems may be expressed directly as the optimization of submodular functions and (2) the lovasz extension of submodular functions provides a useful set of regularization functions for supervised and unsupervised learning. In this monograph, we present the theory of submodular functions from a convex analysis perspective, presenting tight links between certain polyhedra, combinatorial optimization and convex optimization problems. In particular, we show how submodular function minimization is equivalent to solving a wide variety of convex optimization problems. This allows the derivation of new efficient algorithms for approximate and exact submodular function minimization with theoretical guarantees and good practical performance. By listing many examples of submodular functions, we review various applications to machine learning, such as clustering, experimental design, sensor placement, graphical model structure learning or subset selection, as well as a family of structured sparsity-inducing norms that can be derived and used from submodular functions.

Introduction

The monograph develops submodular analysis through convex geometry, linking set functions, polyhedra, Lovász extensions, and optimization. It presents applications, algorithms, and theoretical connections spanning combinatorial and continuous optimization.

Motivation: Submodular functions are set functions with a role analogous to convex functions, appearing in combinatorial optimization and machine learning.They model problems defined on subsets of a base set or vertices of a hypercube.
Convex perspective: The monograph presents submodular theory self-containedly from first principles of convex analysis rather than traditional combinatorial concepts such as matroids or flows.Its algorithms use methods including simplex, active-set, ellipsoid, cutting-plane, and conditional-gradient procedures.
Lovász extension: The Lovász extension is convex exactly when the underlying set function is submodular, and minimizing the set function is equivalent to minimizing its extension on [0,1]^p.The extension is also the support function of the base polyhedron and can be computed by a greedy algorithm.
Scope and applications: The monograph covers polyhedra, classical submodular examples, non-smooth optimization algorithms, submodular minimization, maximization, differences of submodular functions, and experiments.Applications include cuts, set covers, network flows, entropies, spectral functions, matroids, and machine-learning problems.
Convex relaxation: Submodular functions generate convex regularizers for supports and level sets, naturally relaxing mixed combinatorial/continuous problems through the Lovász extension.A separable optimization formulation is shown equivalent to a sequence of submodular function minimization problems.
Definitions: For normalized submodular functions, subtracting modular gains yields a submodular non-decreasing function, and polymatroid rank functions are characterized using diminishing marginal gains.These transformations and characterizations support the analysis of associated polyhedra.

Lov´asz Extension

The Lovász extension extends set-functions from hypercube vertices to R^p by interpolation over ordered simplices, linking submodularity with convexity, polyhedral support functions, and optimization.

Definition: Every subset A maps to its indicator vector 1_A in {0,1}^p, while the Lovász extension interpolates values across p! simplices of the hypercube.The extension is defined for arbitrary set-functions with F(∅)=0 and extends from [0,1]^p to R^p.
Definition: For p=2, the extension is piecewise affine, with separate formulas determined by whether w1≥w2 or w2≥w1.For the two-node complete-graph cut, F({1,2})=0 and F({1})=F({2})=1, yielding f(w)=|w1−w2|.
Greedy algorithm: The Lovász extension is the support function of the submodular or base polyhedron, and its maximizers can be obtained by the greedy algorithm.Extreme points of the base polyhedron arise from greedy constructions over all component orderings.
Greedy algorithm: For non-decreasing submodular functions, greedy maximization over positive and symmetric submodular polyhedra orders w or |w| and uses successive marginal gains.The positive construction uses zero coefficients for non-positive coordinates, whereas the symmetric construction restores signs after ordering absolute values.
Links between submodularity and convexity: A set-function is submodular if and only if its Lovász extension is convex.This equivalence supplies the central bridge between submodular analysis and convex analysis.
Links between submodularity and convexity: For submodular F, minimizing F over subsets, hypercube vertices, or the continuous cube [0,1]^p gives the same minimum, with continuous minimizers forming the convex hull of discrete minimizers.The extension also provides convex relaxations for imposing structure on supports or level sets in estimation problems.

Properties of Associated Polyhedra

The monograph characterizes support functions, maximizers, faces, and decompositions of submodular polyhedra, linking these structures to Lovász extensions and convex optimization.

Support functions: The support function of the base polyhedron equals the Lovász extension f(w), while the positive polyhedron has finite support only for nonnegative w.For the unrestricted submodular polyhedron, any negative component of w makes the support function unbounded above.
Support functions: Greedy orderings characterize support-function maximizers through tight cumulative level sets, with conditions differing between base and submodular polyhedra.For base polyhedra all relevant level sets must be tight; for positive submodular polyhedra only positive-valued levels are required, with negative coordinates set to zero.
Decomposition and representation: Submodular functions decompose across separable sets, and the submodular polyhedron admits a minimal representation using inseparable subsets.The base polyhedron has non-empty relative interior exactly when the ground set is inseparable.
Facial structure: Faces of the base polyhedron are determined by partitions into inseparable sets whose cumulative constraints are tight.The facial structure is dual to the Lovász-extension sublevel set projected onto the hyperplane w⊤1V = 0.
Symmetric polyhedra: For the symmetric submodular polyhedron, maximizers align signs with w and satisfy tightness on positive absolute-value levels; its dual unit-ball faces have stable non-zero patterns.Defining constraints can be restricted to stable and inseparable sets.
Convex relaxation: For submodular functions, the convex closure equals the Lovász extension, is computable in closed form, and yields an equivalent convex formulation of set-function minimization.Minimizing the convex closure on [0,1]^p is equivalent to minimizing the original function on 2^V.

5.2 Structured sparsity

The monograph develops submodular-function penalties and their Lovász-extension relaxations to encode structured sparsity, connecting support preferences, convex norms, and stable solutions.

Structured sparsity: Structured sparsity favors prescribed nonzero supports or level sets, and submodular penalties provide convex relaxations for both structures.Support-based penalties use F(Supp(w)); level-set penalties target sets such as {w ≥ α} or {w = α}.
Convex relaxation: Non-decreasing submodular support penalties can restrict supports while providing an explicit penalty interpretation beyond merely forbidding disallowed sparsity patterns.The resulting norms therefore combine structured support selection with a direct penalty on the selected support.
Convex relaxation: The Lovász extension Ω∞(w) = f(|w|) is the convex envelope of F(Supp(w)) on the unit ℓ∞-ball.This gives the tightest convex lower bound for the support penalty within [-1,1]^p.
Norms from submodularity: Ω∞ is a norm when F is strictly positive on singletons, and its dual norm can be computed through a sequence of submodular function minimizations.The norm and dual-norm construction links structured sparsity regularization to submodular optimization algorithms.
Stable sparsity: Under invertible XᵀX and continuously distributed responses, least-squares minimization with Ω∞ has a unique solution whose support is stable with probability one.The result relies on the stated full-rank design and absolute-continuity assumptions.

5.5 Shaping level sets∗

The Lovász extension can shape not only supports but also the level sets of predictors, encouraging structured equality patterns through submodular regularization.

For functions F with F(∅) = F(V) = 0, the Lovász extension is the convex envelope of the maximum submodular value over predictor level sets.
Using the Lovász extension directly for symmetric submodular functions affects all sub-level sets, not only the support.
For graph cuts, Lovász-extension regularization yields piecewise-constant vectors whose constant regions are connected graph subsets.
Concave cardinality functions constrain which predictor components can form equal-valued level sets, producing clustering patterns determined by their linearity intervals.
A strongly concave function permits all level-set patterns, whereas a function linear between cardinalities 1 and p separates intermediate variables.
Submodular quadratic functions have the form q⊤1_A + 1/2 1_A⊤Q1_A and are submodular exactly when every off-diagonal entry of Q is non-positive.

6.3 Set covers

Set covers provide submodular functions based on the measure of unions, with equivalent group formulations that encode structured sparsity patterns and admit flow-based algorithms.

The associated structured sparsity norm is Ω∞(w) = f(|w|) = Σ_G D(G)||w_G||∞, yielding grouped ℓ1/ℓ∞ regularization for partition groups.
For q ∈ (1, ∞), Ω_q differs from the overlapping group-Lasso sum unless positively weighted groups form a partition, avoiding its overcounting effect.
A set cover assigns each element k a measurable set S_k, and F(A) measures the union of sets indexed by A.
Set-cover functions are equivalent to sums over groups with non-negative weights, connecting coverage representations to group-based submodular models.
Choosing sequence groups can restrict supports to contiguous segments, while neighborhood groups can prevent isolated variables from being selected.
Flow reinterpretations enable fast proximal algorithms, with network size determined by the number of positively weighted groups and reducible through group containment.

6.5 Entropies

Entropy-based constructions supply submodular objectives for information, design, and clustering problems, while their additional structure makes them narrower than general submodular functions.

Joint entropy is a non-decreasing submodular function because conditioning reduces entropy, and symmetrization yields mutual information across a partition.
Discrete entropies are non-negative and non-decreasing submodular functions, but satisfy additional properties not shared by all submodular functions.
In Gaussian linear models, minimizing posterior entropy after selecting observations is equivalent to maximizing a submodular experimental-design objective.
Semi-supervised clustering can be formulated as minimizing a modular term plus mutual information between variables indexed by A and its complement.
On the two-moons example, mutual information captures cluster structure better than weighted cuts when using interactions beyond second order.
Matroid rank functions are submodular, and for graphic matroids their base polyhedron is the spanning-tree polytope with greedy optimization corresponding to Kruskal’s algorithm.

Non-smooth Convex Optimization

The monograph develops non-smooth convex optimization methods for submodular and related problems, balancing general convergence guarantees against dimension, iteration, and subproblem costs.

The chapter studies convex objectives with non-smooth positively homogeneous terms, covering submodular minimization, separable optimization, and sparsity-based problems.
Generic methods include subgradient, ellipsoid, Kelley cutting-plane, and analytic-center cutting-plane algorithms.
Mirror descent, conditional gradient, bundle, simplicial, and proximal methods exploit stronger convexity or additional operations on the regularizer.
Efficient linear maximization over the relevant polyhedron is a key assumption, with greedy optimization available for base and symmetric submodular polyhedra.
Projected subgradient methods have low iteration cost and dimension-independent stated rates, but converge slowly despite often finding decent solutions quickly in applications.
The ellipsoid method has exponential convergence in iterations but strong dimension dependence and an O(p^3) running time per iteration.
Kelley’s method may require complicated subproblems, many iterations, and can be unstable when local subproblems have multiple minimizers.

7.5 Analytic center cutting planes

The section develops analytic-center and related convex optimization methods for minimizing nonsmooth functions, including submodular objectives. It contrasts convergence guarantees, primal–dual interpretations, and practical requirements across iterative schemes.

7.5 Analytic center cutting planes: Analytic-center cutting planes iteratively shrink a candidate polytope containing all optima and recompute its analytic center.The method adds supporting hyperplanes from subgradients and updates an upper bound on the objective.
7.5 Analytic center cutting planes: Analytic-center methods have non-exponential complexity bounds, while their empirical behavior can be substantially better than their theoretical guarantees.The text contrasts a complexity bound with improved practical performance observed in simulations.
7.6 Mirror descent/conditional gradient: For strongly convex Ψ, the mirror-descent interpretation gives O(1/µt) convergence for averaged primal iterates, dual variables, and one primal iterate.If Ψ* is also strongly convex and the optimum lies in the interior of K, the convergence rate is exponential.
7.6 Mirror descent/conditional gradient: Conditional-gradient methods optimize a smooth dual function over a compact convex set using linear maximization over that set.Each iteration selects a maximizing point and forms a convex combination using a step size or line search.
7.6 Mirror descent/conditional gradient: Line-search conditional-gradient iterates achieve a stated convergence rate, with the natural primal variable attaining a duality gap of the same order.The primal variable is obtained from the gradient of the conjugate, and the resulting gap matches the dual rate.
7.8 Dual simplicial method: The practical applicability of some methods depends on solving each iteration’s minimization accurately, typically restricting them to linear- or quadratic-program representations.Under suitable linear-program representations of Ψ* and K, the algorithm can terminate finitely with an exact minimizer.

7.10 Simplex algorithm for linear programming

The section presents simplex and active-set approaches for linear and quadratic programs, emphasizing vertex or active-set updates, feasibility, termination, and scalability to exponentially large representations. It also records degeneracy, numerical stability, and worst-case complexity limitations.

7.10 Simplex algorithm for linear programming: The simplex method explores vertices of a feasible polyhedron and pivots by introducing a nonbasic variable along a feasible descent direction.The entering direction preserves Ax=b and is determined by the active columns of A.
7.10 Simplex algorithm for linear programming: When reduced costs are nonnegative, the current primal–dual pair is optimal; otherwise, a negative reduced cost identifies a strict descent direction.The step continues until a basic variable reaches zero or the problem is detected as unbounded.
7.10 Simplex algorithm for linear programming: For non-degenerate problems, simplex terminates finitely, but some instances visit exponentially many basic feasible solutions.Combinatorial-optimization linear programs can be degenerate, requiring strategies to avoid cycling.
7.10 Simplex algorithm for linear programming: In this monograph, simplex is applied to submodular minimization through a linear program with exponentially many variables, while greedy steps retain polynomial-time iteration complexity.The approach relies on the greedy algorithm to handle the large representation.
7.10 Simplex algorithm for linear programming: Active-set methods maintain primal feasibility while updating the set of nonzero variables and solving the equality-constrained subproblem.The method uses optimality conditions involving feasibility, stationarity, and complementary slackness.
7.10 Simplex algorithm for linear programming: Active-set quadratic methods can handle exponentially many components, but approximate linear-system solutions may be numerically unstable when the system is ill-conditioned.The text also notes that the unique quadratic solution may have more than m nonzero components.
7.10 Simplex algorithm for linear programming: For sparsity-inducing norms, the dual active-set method can produce large active sets and potential instability because primal sparsity is not exploited.Regularization paths remain affine in λ once the local active set is fixed.

Separable Optimization Problems: Analysis

The section analyzes separable convex problems penalized by Lovász extensions through duality, base-polyhedron optimization, and parameterized submodular minimization. It establishes thresholding, monotonicity, duality-gap decomposition, and quadratic-problem consequences.

Separable Optimization Problems: Analysis: Separable convex optimization penalized by a Lovász extension is dual to maximizing a separable concave function over the submodular function’s base polyhedron.The analysis assumes strictly convex differentiable separable terms and uses convex strong duality.
Separable Optimization Problems: Analysis: The primal and dual optima are linked by sk = −ψ′k(wk), while optimality also requires maximizing w⊤s over the base polyhedron.Under the stated assumptions, both optimal solutions are unique.
Separable Optimization Problems: Analysis: Solving one separable convex problem is equivalent to solving the parameterized submodular minimization problems for every α.This equivalence uses submodularity to establish the monotonicity of the parameterized minimizers.
Separable Optimization Problems: Analysis: If α < β, every minimizer at β is contained in every minimizer at α, so the parameterized solution sets are nested.For the unique convex optimum u, minimal and maximal minimizers are respectively {u > α} and {u ≥ α}.
Separable Optimization Problems: Analysis: The convex duality gap decomposes as an integral over α of the duality gaps of the associated submodular minimization problems.This connects approximate convex solutions to approximate combinatorial solutions.
Separable Optimization Problems: Analysis: For quadratic separable functions, one convex problem yields minimizers of F(A) + λ|A| for every λ, including a minimizer of F by thresholding a base-polyhedron projection.The minimum-norm base-polyhedron point is linked to threshold sets of the quadratic optimum.
Separable Optimization Problems: Analysis: An isotonic-regression formulation improves the choice w = −s and can be solved in O(p) using the pool adjacent violators algorithm.The formulation corresponds geometrically to projecting 0 onto an outer approximation associated with the base polyhedron’s tangent cone.
Separable Optimization Problems: Analysis: Quadratic regularization can produce agglomerative solution paths, and adding an ℓ1 penalty is solved by soft-thresholding the original proximal solution.The agglomerative property means components cluster as λ increases and do not separate.

8.4 Separable problems on other polyhedra∗

Separable optimization on submodular polyhedra can be transferred from the base polyhedron to the submodular, positive, and symmetric variants through primal-dual transformations. For quadratic objectives, these transformations become projection and thresholding operations.

Submodular polyhedron: Given a primal-dual optimum (v,t) on B(F), define w=v+ and adjust each s_k by optimizing over (−∞,t_k]; then (w,s) is optimal on P(F).The proof uses coordinatewise Fenchel duality together with the Lovász-extension optimality condition.
Submodular polyhedron: For projection objectives, projecting onto P(F) is obtained from the projection t onto B(F) by setting s_k=t_k when z_k≥t_k and s_k=z_k otherwise.The resulting operation is illustrated in Figure 8.2.
Submodular polyhedron: Optimal separable solutions on B(F) can be transformed into optimal solutions on P(F), but the reverse direction is unavailable.The transformation can be viewed through primal-only or dual-only variables.
Positive and symmetric polyhedra: For non-decreasing F, positive and symmetric polyhedra extend the same construction by positive-part and sign transformations of the base-polyhedron solution.The positive case uses w=v+ and positive parts of the dual variables; the symmetric case introduces coordinate signs.
Applications: Proximal operators for the sparsity-inducing norm Ω∞(w)=f(|w|) can be obtained from the proximal operator for the Lovász extension, followed by sign and positive-part operations.This applies the symmetric-polyhedron result to quadratic separable objectives.
Divide and conquer: The divide-and-conquer algorithm can split problems unevenly, increasing total complexity to O(p) times one submodular minimization instead of O(log p) for balanced splits.The stated issue is a practical limitation of the splitting strategy.

9.3 Iterative algorithms - Approximate minimization

The section develops iterative convex-optimization methods for approximate submodular minimization, especially conditional-gradient algorithms on the base polyhedron. These methods provide convergence guarantees and computable optimality certificates, while related procedures support line searches and proximal computations.

Conditional gradient: Conditional-gradient iterations minimize a Taylor approximation over B(F), then move toward the selected extreme point using a step size or line search.The method starts from s0∈B(F) and updates st=ρt−1 s̄t−1+(1−ρt−1)st−1.
Conditional gradient: The quantity maxs∈B(F) g′(st)ᵀ(s−st) is a computable optimality certificate that upper-bounds the current suboptimality.Its convergence rate is of the same order as the iterate bound, and isotonic regression can improve the certificate.
Comparison of methods: Min-norm-point and conditional-gradient methods both use greedy extreme points, but the former is finitely convergent while the latter has a convergence rate without finite convergence.Figure 9.2 highlights the conditional-gradient oscillations during line search.
Line search: Line search in P(F) reduces feasibility testing to minimizing submodular functions G−αt, where the resulting concave piecewise-affine function identifies the largest feasible α.When t has strictly positive components, the number of Newton steps is less than p.
Proximal extensions: The line-search procedure also computes dual norms, while related proximal problems connect Lovász-extension minimization with the norms Ωq.For Ω∞, thresholding yields the solution directly from the corresponding quadratic problem.
Minimizer structure: The chapter’s minimizer results include lattice closure under union and intersection and dual characterizations of submodular-function minimization.These structural properties support exact and approximate minimization procedures.

10.4 Ellipsoid method

The ellipsoid and simplex-based approaches solve convex formulations of submodular minimization using cutting-plane or active-set representations. They provide polynomial or per-iteration guarantees, while approximate subgradient approaches offer cheaper iterations and threshold-based certificates.

Ellipsoid method: Applying the ellipsoid method to minw∈[0,1]^p f(w) requires at most O(p^2 log(1/ε)) iterations and has total complexity O(p^5 log(1/ε)).Each ellipsoid iteration has complexity O(p^3), yielding a weakly polynomial bound.
Dual formulation: The dual problem maximizes s−(V) over the convex hull of base-polyhedron extreme points, represented by nonnegative convex weights η.The resulting linear program uses variables η, α, and β with balance and normalization constraints.
Simplex method: Simplex iterations use active constraints and reduced costs to detect violations of w∈[0,1]^p or of the base-polyhedron inequalities.When the box constraints are satisfied, the current solution is globally optimal for the restricted linear model.
Simplex method: Each simplex iteration has complexity O(p^2), and the method can add or remove extreme-point columns through a column-decomposition view.The active basis is partitioned into extreme-point and box-constraint index sets.
Interior-point method: Interior-point analytic centers select subgradients that are empirically better than extreme-point choices in the corresponding Kelley-method limit.The analytic-center subproblem can be solved with Newton’s method from a feasible start.
Minimum-norm-point method: The minimum-norm-point approach obtains all minimizers from negative components of a base-polyhedron solution, but its iteration count has no known upper bound.Each iteration has order O(p^3) operations.
Approximate minimization: Subgradient descent provides certified approximate minimizers by thresholding iterates, requiring at most 4pD^2/ε^2 iterations for an ε-approximate set.A suitable sup-level set of the iterate attains the stated approximation guarantee.

Proposition 10.6 (Submodular function minimization by conditional gradient

The section connects submodular minimization to convex optimization and develops conditional-gradient-based methods with convergence and optimality-certificate guarantees.

After t steps, the conditional-gradient analysis yields an ε-approximate solution whose submodular minimization gap is bounded through thresholding.The bound is obtained from the convergence rate and the thresholding result.
The iterate s_t provides an optimality certificate, bounding the gap between the selected set value and the dual certificate.
Certificate bounds can also constrain minimizers: sufficiently positive coordinates cannot belong to a minimizer, while sufficiently negative coordinates must belong.
For decomposable functions, projection-based methods reduce the dual problem to finding closest points between polytopes and support efficient parallelization.
Smooth approximations of Lovász extensions can improve the minimization guarantee to O(1/t), compared with O(1/√t) in the general nonsmooth case.
Submodular minimization is polynomial-time, whereas maximization is NP-hard; greedy and local-search methods nevertheless provide approximation guarantees in relevant cases.

Experiments

The experiments compare submodular and convex optimization algorithms across datasets and applications, showing distinct trade-offs between primal quality, certificates, speed, and structure exploitation.

Experiments: The experiments evaluate submodular minimization, separable quadratic optimization, sparsity-inducing wavelet estimators, and structured one-dimensional signal recovery.
Submodular function minimization: The study compares simplex, ACCPM, ACCPM-Kelley, ellipsoid, projected-gradient, and conditional-gradient variants using primal and dual optimality measures.
Submodular function minimization: Across datasets, primal values become good much faster than dual certificates, so later iterations primarily sharpen optimality certification.
Submodular function minimization: ACCPM obtains near-optimal primal and dual solutions in all cases, while minimum-norm-point succeeds in most cases but more slowly.
Separable optimization problems: For separable problems, minimum-norm-point achieves the quickest small duality gaps, while line-search conditional gradients outperform decaying-step variants.
Structured sparsity: The hierarchical submodular prior produces lower estimation error with fewer artefacts than ridge regression and Lasso in the wavelet estimator comparison.
Structured sparsity: Dedicated proximal algorithms are most efficient in the tree-structured norm example, while decomposition-based submodular methods outperform generic min-norm-point methods when structure is available.

Appendix A

Appendix A develops the convex-analysis foundations used throughout the monograph, including extended-value functions, conjugacy, duality, norms, gauges, and polars. It also connects these concepts to submodular optimization through affine representations, polyhedral projections, and proximal problems.

Convex-analysis foundations: The appendix reviews extended-value convex functions and assumes throughout that functions are proper and closed.The domain of an extended-value function is convex, and constrained problems can be represented using indicator functions.
Conjugacy and duality: Fenchel conjugates represent convex functions through affine lower bounds, with closed convex functions recovered by their biconjugates.The conjugate is geometrically related to tangent intercepts, while the biconjugate gives the tightest convex closed lower bound when convexity or closedness fails.
Conjugacy and duality: Fenchel duality provides primal-dual optimization pairs and a nonnegative optimality gap that vanishes exactly for Fenchel-dual solutions.Fenchel-Young equality characterizes the corresponding maximizers, and differentiability links primal and dual variables through gradients.
Convex sets and geometric functions: Support functions, norms, gauges, and polar sets connect convex functions with closed convex sets and dual geometric representations.Support functions are conjugates of indicator functions, gauges encode scaled membership, and polar sets produce dual norm balls in the normed case.
Convex optimization: Proximal problems for positively homogeneous convex functions reduce, under strong duality, to orthogonal projection onto a closed convex set.The primal and dual minimizers are related by w = z − s, and the framework extends to more general separable functions.
Connections to submodular optimization: The appendix establishes convex-analysis links that support submodular optimization, including polyhedral descriptions and a function representation as a maximum over affine functions.The supplied passages also include a cut-function definition, but do not provide enough surrounding context to characterize its broader role here.

A.3 Pool-adjacent-violators algorithm

This section derives the pool-adjacent-violators algorithm from the convex formulation of chain-constrained isotonic regression. The method pools adjacent violating blocks, yielding linear-time optimization and preserving that complexity for weighted squared ℓ2 losses.

A.3 Pool-adjacent-violators algorithm: The target problem is isotonic regression with a chain constraint requiring w_t ⩾ w_t+1.The section formulates the problem as minimizing a squared ℓ2 distance from z subject to a non-increasing sequence.
A.3 Pool-adjacent-violators algorithm: The dual formulation uses cumulative-sum constraints, with optimality linking the primal variable and dual variable through w = z − s.Summation by parts converts the chain-ordering constraints into conditions on partial sums of s.
A.3 Pool-adjacent-violators algorithm: Each active-set block receives the average v_i = z(A_i)/|A_i|, so the fitted sequence is constant within blocks.The block values arise from solving the active-set subproblem.
A.3 Pool-adjacent-violators algorithm: When adjacent block values violate the non-increasing order, the algorithm merges those blocks and recomputes their shared average.This is the pooling operation that updates the active set until dual feasibility is restored.
A.3 Pool-adjacent-violators algorithm: O(p) complexity is achievable by ordering pooling operations from the first indices, and the same running time applies to weighted squared ℓ2 losses.The result follows from the active-set interpretation and the adjacent-pooling implementation.
Related submodular constructions: The surrounding appendix relates submodular-function transformations to Lovász extensions and projections of submodular polyhedra.Restriction, contraction, partial minimization, and convolution each preserve submodularity while inducing corresponding polyhedral operations.