Package {MMAD}

MMAD: Minorization-Maximization via Assembly-Decomposition Technology

Description

Tools for maximizing a target function via the MM algorithm, built around three layers:

Details

• a symbolic expression tree (mmad_expr) constructed via the formula interface or operator overloads on mmad_var();

• disciplined-convex-programming inference of curvature, sign, and monotonicity (curvature(), sign_of(), is_dcp());

• a surrogate construction (minorize_at()) that uses only Jensen's inequality and the supporting hyperplane, plus a top-level driver (mmad()) that maximizes the surrogate via block-coordinate Newton.

The formula interface accepts theta[i] indexing or named parameters, eager-evaluates theta-free sub-expressions in data, and recognizes sum() over observations together with X %*% theta, so standard statistical likelihoods can be written in one line. See mmad() for the headline example and Function_check() for a pre-flight diagnostic.

Author(s)

Maintainer: Jiaqi Gu jiaqigu@usf.edu

Authors:

• Jiaqi Gu jiaqigu@usf.edu

• Xifen Huang xf_yellow@126.com

• Jinfeng Xu jinfenxu@cityu.edu.hk

Diagnose an mmad_expr (or formula) before optimization

Description

Runs curvature inference, top-level summand decomposition, domain check at init, and a dry-run of minorize_at(). Returns a structured report with a print() method intended as a quick health check before invoking mmad().

Usage

Function_check(expr, init, data = NULL, tree = FALSE)

Arguments

Details

The is_dcp flag reflects strict DCP composition rules and may be FALSE even for expressions that are fully minorizable by MMAD's extended rules (e.g. log(1 + exp(theta)) or exp(log(theta1) + log(theta2))). The operationally relevant criterion is is_separable: if that is TRUE, mmad() will optimise the expression successfully.

The print() method renders a full expression tree in which every node is annotated with ⁠[curvature | sign | minorizable?]⁠.

Value

A list with class "mmad_check" and components target_curvature, target_sign, is_dcp, is_minorizable, summands, domain_ok, domain_message, is_separable, non_separable_indices, expr_tree, show_tree.

Examples

chk <- Function_check(~ log(theta[1] + theta[2]) - theta[1],
                      init = c(1, 1))
print(chk)
print(chk, tree = TRUE)   # show the expression tree

Mathematical functions for mmad_expr

Description

log(), exp(), and sqrt() (the latter as (.)^(1/2)).

Usage

## S3 method for class 'mmad_expr'
Math(x, ...)

Arguments

Value

An mmad_expr.

Arithmetic operators for mmad_expr

Description

Lets users write expressions naturally: 2 * theta1 - log(theta1 + theta2) becomes a properly-typed expression tree.

Usage

## S3 method for class 'mmad_expr'
Ops(e1, e2)

Arguments

Details

Restrictions enforced at construction time:

• expr * expr is rejected (one side must be a numeric scalar) – products of two parameter-dependent expressions are non-DCP.

• numeric / expr is rejected – division by an expression is non-DCP.

• expr ^ expr is rejected – the exponent must be a numeric scalar.

Value

An mmad_expr.

Convert a formula or expression into an mmad_expr

Description

Convert a formula or expression into an mmad_expr

Usage

as_mmad_expr(x, init = NULL, data = NULL)

Arguments

Value

An mmad_expr.

Examples

expr <- as_mmad_expr(~ log(theta[1] + theta[2]), init = c(0, 0))
evaluate_expr(expr, c(1, 2))$value

Inferred curvature of an mmad_expr

Description

Returns the DCP curvature of the expression as one of "affine", "convex", "concave", or "unknown". "unknown" means the DCP rule set could not prove a definite curvature; this is a refusal, not a claim of non-convexity.

Usage

curvature(expr)

Arguments

Value

A length-1 character.

Examples

curvature(log(mmad_var(1) + 1))                      # "concave"
curvature(exp(mmad_var(1)))                          # "convex"
curvature(2 * mmad_var(1) + 3 * mmad_var(2))         # "affine"
curvature(exp(mmad_var(1)) - exp(mmad_var(2)))       # "unknown"

Evaluate an mmad_expr at a parameter vector

Description

Computes the value, gradient, and Hessian of the expression at theta, all with respect to theta. The gradient is a numeric vector of length length(theta); the Hessian is a length(theta) by length(theta) numeric matrix.

Usage

evaluate_expr(expr, theta)

Arguments

Details

This is the Phase 1 replacement for Function_evaluation() – it works on the new expression tree. The legacy function continues to work on the old list representation; legacy_to_expr() bridges between them.

Value

A list with components value, gradient, and hessian.

Examples

expr <- log(mmad_var(1) + mmad_var(2))
evaluate_expr(expr, c(1, 1))

Whether an expression's curvature is provably one of affine/convex/concave

Description

Convenience predicate: TRUE exactly when curvature() is not "unknown".

Usage

is_dcp(expr)

Arguments

Value

TRUE or FALSE.

Examples

is_dcp(log(mmad_var(1) + 1))                       # TRUE
is_dcp(exp(mmad_var(1)) - exp(mmad_var(2)))        # FALSE

Build a surrogate of an mmad_expr at a current iterate

Description

Given a target expr and a current iterate theta_0, construct a surrogate S(theta | theta_0) that lower-bounds expr(theta) and is tangent to it at theta_0. The surrogate is constructed to be as separable across the coordinates of theta as the structure permits; anything that resists clean minorization is preserved as-is in a fallback bucket so that value/gradient/Hessian computations on the full surrogate remain available.

Usage

minorize_at(expr, theta_0)

Arguments

Details

Construction uses only Jensen's inequality and the supporting hyperplane; no per-atom tight surrogates are applied.

Value

A list with components

expr

the full surrogate as an mmad_expr

constant

the additive constant of the surrogate

per_coord

a list of length length(theta_0) whose j-th entry is the 1-d surrogate term in theta[j], or NULL if no term touches that coordinate

non_separable

an mmad_expr representing the multi-coordinate residue we could not minorize, or NULL if every leaf was minorized or extracted

is_separable

TRUE iff non_separable is NULL

Examples

expr <- log(0.5 * mmad_var(1) + 0.5 * mmad_var(2))
surr <- minorize_at(expr, c(2, 1))
surr$is_separable
evaluate_expr(surr$expr, c(2, 1))$value     # tangent at theta_0

Minorization-Maximization driver for an mmad_expr target

Description

Given a target expression expr and an initial parameter vector init, this iteratively maximizes expr by constructing a separable surrogate at the current iterate (via minorize_at()), taking Newton steps on the separable and entangled blocks, and line-searching on the target to enforce ascent.

Usage

mmad(
  expr,
  init,
  data = NULL,
  tol = 1e-06,
  max_iter = 1000,
  line_search_max = 30,
  track_history = FALSE,
  verbose = FALSE
)

Arguments

Value

A list with components

estimate

the final parameter vector (named if init was named)

value

the target value at estimate

iterations

number of iterations actually run

converged

TRUE iff both convergence criteria were met

history

per-iteration diagnostics (data frame), or NULL

message

character: short status string

Examples

fit <- mmad(~ log(theta[1] + theta[2]) - theta[1] - theta[2] + 2,
            init = c(2, 2))
fit$estimate

# Poisson regression via sum() and X %*% theta:
set.seed(1); n <- 50; p <- 2
X <- matrix(rnorm(n * p, sd = 0.5), nrow = n)
y <- rpois(n, exp(X %*% c(0.3, -0.2)))
mmad(~ sum(y * (X %*% theta) - exp(X %*% theta)),
     init = rep(0, p), data = list(X = X, y = y))

Names of currently registered atoms

Description

Names of currently registered atoms

Usage

mmad_atom_names()

Value

A character vector.

Examples

mmad_atom_names()

Construct an atom-application expression node

Description

Internal constructor; not normally called by users. Validates that the atom name is registered (see mmad_atom_names()) and that all child expressions are themselves mmad_expr.

Usage

mmad_call(op, args, params = list())

Arguments

Value

An object of class mmad_expr (subclass mmad_call).

Construct a numeric-constant expression node

Description

Construct a numeric-constant expression node

Usage

mmad_const(value)

Arguments

Value

An object of class mmad_expr (subclass mmad_const).

Examples

mmad_const(2.5)

Construct a parameter reference theta[i]

Description

Construct a parameter reference theta[i]

Usage

mmad_var(i, sign = "unknown")

Arguments

Value

An object of class mmad_expr (subclass mmad_var).

Examples

mmad_var(1)
mmad_var(2, sign = "positive")

Register a primitive atom in the mmad_expr framework

Description

Register a primitive atom in the mmad_expr framework

Usage

register_atom(name, arity, value, grad, hess, dcp_info = NULL)

Arguments

Value

Invisibly NULL. Called for its side effect on the registry.

Examples

## Not run: 
# Register a custom 'tanh' atom (advanced; rarely needed):
register_atom("tanh",
  arity = 1L,
  value = function(args, params) tanh(args[1]),
  grad  = function(args, params) 1 - tanh(args[1])^2,
  hess  = function(args, params) matrix(-2 * tanh(args[1]) * (1 - tanh(args[1])^2), 1, 1))

## End(Not run)

Inferred sign of an mmad_expr

Description

Inferred sign of an mmad_expr

Usage

sign_of(expr)

Arguments

Value

One of "positive", "nonneg", "zero", "nonpos", "negative", "unknown".

Examples

sign_of(exp(mmad_var(1)))                # "positive"
sign_of(mmad_var(1) ^ 2)                 # "nonneg"

Algebraically simplify an mmad_expr

Description

Applies identities E3 (log(exp(h)) = h), E4 (exp(log(h)) = h when h > 0), and E5 (log(h^c) = c * log(h) when h > 0) in a single bottom-up pass. Used internally by minorize_at() before dispatching to the minorization rules.

Usage

simplify_expr(expr)

Arguments

Value

An mmad_expr that is algebraically equivalent to expr.