Doo

DOOConfig

Configuration for DOO algorithm.

Fields:

• delta::Function: Diameter function δ(h) providing upper bound on cell diameter at depth h. Should be a decreasing function of depth. NOTE: User will define this based on specific problem structure.
• degree::Int: Number of coordinates refined by each expansion (default: 1)
• strict::Bool: If true, use the coordinate-wise cell decomposition (default: false)
• value_transform::Function: Transform loss to value for maximization (default: loss -> -loss)

Theoretical Notes:

• DOO convergence depends on how well δ(h) bounds the actual cell diameters
• δ(h) should decrease at rate matching the partition refinement
• For binary splits: δ(h) = 0.5^h is typical
• For p-adic polydiscs: δ(h) depends on prime and radius shrinkage. In strict degree-d mode, use δ_d(h) = δ(binomial(n - 1, d - 1) * floor(h / binomial(n, d))). The factor binomial(n - 1, d - 1) is the number of d-subsets containing any fixed coordinate in one full cycle through all d-subsets.

Note: DOO does not need an explicit max_depth parameter. The tree search naturally terminates when the polydisc children() function returns empty at the precision boundary of the p-adic field.

DOONode{S,T,N}

Node in the DOO (Deterministic Optimistic Optimization) tree.

Fields:

• polydisc::ValuationPolydisc{S,T,N}: Region represented by this node
• depth::Int: Depth in tree (root has depth 0)
• position::Int: Position index among siblings
• parent::Union{DOONode{S,T,N}, Nothing}: Parent node reference
• children::Vector{DOONode{S,T,N}}: Expanded children
• value::Union{Float64, Nothing}: Evaluated function value (after value_transform)
• is_expanded::Bool: Whether node has been expanded

DOOState{S,T,N}

State for DOO optimization.

Fields:

• root::DOONode{S,T,N}: Root of search tree
• total_samples::Int: Total function evaluations performed
• next_branch::Int: Starting subset index for strict mode
• step_count::Int: Number of optimization steps taken
• leaves::PriorityQueue{DOONode{S,T,N}, Tuple{Float64,Int}}: Unexpanded leaf nodes, prioritized by maximum b-value and deterministic insertion order
• branch_sets::Vector{Vector{Int}}: Precomputed strict-mode degree-d coordinate subsets
• leaf_insertion_order::Int: Monotone counter for breaking leaf-priority ties
• best_node::Union{DOONode{S,T,N}, Nothing}: Best evaluated node seen so far

b_value(node::DOONode, config::DOOConfig)

Compute the b-value (optimistic upper bound) for a node.

Formula: b(h,j) = value + δ(h)

where:

• value = value_transform(loss) is the transformed function value at the node
• δ(h) is the diameter bound at depth h. In strict degree-d mode this uses δ(binomial(n - 1, d - 1) * floor(h / binomial(n, d))).

The b-value represents the best possible value that could be achieved within the node's region, assuming the function could vary by at most δ(h).

Returns: Float64 b-value (Inf for unexplored nodes)

doo_bound_depth(node::DOONode, config::DOOConfig)

Depth argument used in the DOO optimism term.

For the usual simultaneous cell decomposition this is the node depth h. In strict degree-d mode, one full cycle through all binomial(n, d) d-subsets refines every coordinate binomial(n - 1, d - 1) times.

doo_descent(loss::Loss, param::ValuationPolydisc{S,T,N},
            state::DOOState{S,T,N}, config::DOOConfig) where {S,T,N}

Perform one step of DOO optimization.

Algorithm:

1. Select leaf with maximum b-value (optimistic upper bound)
2. Remove selected leaf from the leaves priority queue
3. Expand selected leaf (generate and evaluate children)
4. Update state (step count)
5. If it has no children, report convergence
6. Add new children to the leaves priority queue
7. Return best-valued node's polydisc as new parameter

Returns: (new_param::ValuationPolydisc, updated_state::DOOState, converged::Bool).

doo_descent_init(param::ValuationPolydisc{S,T}, loss::Loss,
                 next_branch::Int, config::DOOConfig) where {S,T}

Initialize DOO optimizer.

Creates the initial search tree with root node, evaluates root, and returns an OptimSetup configured for DOO optimization.

Arguments:

• param: Initial parameter polydisc (becomes root of search tree)
• loss: Loss function with eval and grad methods
• next_branch: Starting subset index for strict mode
• config: DOO configuration

Returns: OptimSetup instance ready for optimization via step!()

expand_node!(node::DOONode, loss::Loss, config::DOOConfig, state::DOOState)

Expand a node by generating and evaluating its children.

Algorithm:

1. Generate child polydiscs (using children() or childrenalongbranch())
2. Create child nodes
3. Evaluate loss on the children
4. Transform loss to value
5. Update parent's children list
6. Increment sample counter

Returns: Vector of newly created child nodes (empty if node cannot be expanded)

get_all_leaves(state::DOOState)

Get all leaf nodes (expanded or not) in the tree by traversing from root.

This differs from state.leaves which only tracks unexpanded leaves.

get_best_value(state::DOOState)

Get the best value found so far (after value_transform).

get_leaf_count(state::DOOState)

Get number of unexpanded leaf nodes currently in the leaves priority queue.

get_tree_size(state::DOOState)

Get total number of nodes in the DOO tree (including root and all descendants).

strict_branch_indices(node::DOONode, state::DOOState)

Coordinate to refine for the coordinate-wise strict DOO tree.

The coordinate subset is a function of node depth rather than global step count: root children use state.next_branch as the starting subset index, and deeper nodes cycle through the deterministic d-subset enumeration.

strict_branch_sets(::Val{N}, degree::Int) where N

Deterministic enumeration of coordinate subsets for strict degree-d DOO.