Overview
Mirror Descent is an optimization method that updates candidate solutions using objective values, gradients, constraints, or local models. It is useful when the objective landscape, constraints, or update cost fit the method's assumptions.
SpecializedSource checked
Mirror Descent
Mirror Descent improves candidate solutions according to an objective function.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Optimization
- Difficulty
- Intermediate
- Family
- Optimization
- Tier
- Specialized
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
Core Concepts
objective functionsearch directionconstraint handlingcandidate updatestopping rule
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(t)
Average
O(t c)
Worst
O(t c)
Space
O(n)
When to Use
- Use Mirror Descent when the objective, gradients, constraints, or local model fit its update rule.
- Use it when progress diagnostics can be logged during the search.
When Not to Use
- Avoid when the objective cannot be evaluated reliably.
- Avoid when constraints or non-smooth behavior violate the update assumptions.
What It Does
- Evaluates candidate solutions
- Updates parameters or search regions
- Seeks a lower-cost or higher-reward result
Use Cases
- Model fitting
- Operations planning
- Parameter tuning
Inputs
- Objective function
- Parameters or candidate solution
- Constraints or step settings
Outputs
- Improved parameters
- Objective value
- Convergence status
Key Formulas (1)
Mirror descent update
xnext = argminx(η · <g, x> + Dφ(x, xcurrent))
x_next = argmin_x(eta * <g, x> + D_phi(x, x_current))Updates parameters in a geometry defined by a Bregman divergence.
Pseudocode
- 1.Initialize candidate parameters
- 2.Evaluate the objective, gradient, constraint, or local model
- 3.Choose a step, search direction, or candidate update
- 4.Repeat until convergence or budget is reached
- 5.Return the best candidate found
Canonical Example
- Input
- objective J(x), initial x = 0
- Output
- improved candidate x
- Explanation
- Mirror Descent evaluates the objective and updates the candidate according to its search rule.
Implementation Notes
- Log objective values, constraint residuals, and step sizes.
- Use safeguards for failed line searches, invalid gradients, or stalled progress.
Common Pitfalls
- Using a fixed step rule without monitoring progress can diverge.
- Comparing methods only by final value hides constraint violations or instability.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow candidate points moving across the objective landscape.
Step 1 of 5: Initialize candidate parameters
optimizationNotes
Mirror Descent operates in O(t c) time and O(n) space within the Optimization family. Key governing relation: x_next = argmin_x(eta * <g, x> + D_phi(x, x_current)). Often compared with Gradient Descent and Newton's Method.
Sources (1)
What each reference supports for this entry.
Boyd and Vandenberghe Convex Optimization
BookConvex optimization reference for constrained or nonsmooth methods related to Mirror Descent.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageConceptual neighborGradient Descent
Mirror Descent and Gradient Descent address nearby optimization problems but make different implementation tradeoffs.
Related Algorithms
Tags
Optimization