Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Optimization

2,311 missions · 1,728 completed

Missions

Open583Completed1728All2311
🏆Completed
Control TheoryOptimal TransportStatistics·Captain: mikedeng1

Wasserstein Distributionally Robust Kalman Filtering 1: Minimax MMSE Estimation over a Gaussian Wasserstein Ball Is a Finite Convex SDP with an Affine Robust EstimatorResearch Paper

The Kalman filter estimates the hidden state of a linear system from noisy observations. At every step it solves a minimum mean square error (MMSE) estimation problem: given a joint normal distribution of a signal xxx and an observation yyy, find the estimator ψ(y)\psi(y)ψ(y) minimizing E[∥x−ψ(y)∥2]\mathbb E[\|x-\psi(y)\|^2]E[∥x−ψ(y)∥2]. The answer, the conditional mean, is optimal only if…

18 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimal Transport·Captain: mikedeng1

Wasserstein Distributionally Robust Kalman Filtering 2: The Bisection Algorithm Returns a Feasible, ε-Suboptimal Solution of the Frank–Wolfe Direction-Finding SubproblemResearch Paper

A Kalman filter estimates the hidden state xxx of a linear system from observations yyy, assuming the joint law of z=(x,y)z = (x, y)z=(x,y) is a known Gaussian. When that law is only approximately known, Shafieezadeh-Abadeh, Nguyen, Kuhn and Mohajerin Esfahani (arXiv:1809.08830v3, NeurIPS 2018) replace it by the worst Gaussian within a 2-Wasserstein ball of radius ρ\rhoρ around…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationDynamical Systems·Captain: mikedeng1

Fast Convergence of Inertial Dynamics and Algorithms with Asymptotic Vanishing Viscosity 1: For α > 3 Every Trajectory of ẍ + (α/t)ẋ + ∇Φ(x) = 0 Converges Weakly to a Minimizer of ΦResearch Paper

Nesterov's accelerated gradient method and its proximal variant FISTA minimize a smooth convex function with a value gap of order O(1/k2)O(1/k^2)O(1/k2) after kkk iterations, against O(1/k)O(1/k)O(1/k) for plain gradient descent. They are among the most widely used first-order methods in large-scale optimization, signal processing and machine learning. Su, Boyd and Candès (JMLR 2016)…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical Analysis·Captain: mikedeng1

First-Order Optimization Algorithms via Inertial Systems with Hessian Driven Damping VI: For µ-Strongly Convex f, (IGAHD-SC) Satisfies f(x_k) − min f = O(q^k) and ‖x_k − x⋆‖ = O(q^{k/2})Research Paper

First-order methods use function gradients to minimize an objective without solving a second-order subproblem at each iteration. Inertial methods also use the previous iterate, which can improve the convergence rate but complicates the choice of momentum and step size. Attouch, Chbani, Fadili, and Riahi study a family of such methods derived from continuous…

9 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimal TransportProbability·Captain: mikedeng1

Optimal Transport-Based Distributionally Robust Optimization: Structural Properties and Iterative Schemes 4: A Worst-Case Distribution Is the Law of X + √δ G A(X)⁻¹β, Spending the Whole Budget δResearch Paper

Distributionally robust optimization (DRO) replaces the expected loss EP0[ℓ(βTX)]E_{P_0}[\ell(\beta^{\mathsf T}X)]EP0​​[ℓ(βTX)] of a linear decision rule β\betaβ by its worst case over all data laws PPP within transport distance δ\deltaδ of the baseline P0P_0P0​. When P0P_0P0​ is an empirical distribution this covers regularized regression and classification (Blanchet, Kang, Murthy 2019; Esfahani,…

15 thms3 active usersReviewed
🏆Completed
Convex Optimization·Captain: mikedeng1

The Direct Extension of ADMM for Multi-block Convex Minimization Problems is Not Necessarily Convergent II: On a Three-Block Linear System the Extended ADMM Diverges for Every β > 0Research Paper

The alternating direction method of multipliers (ADMM) solves linearly constrained problems whose objective splits into separately treatable blocks. For two blocks, min⁡{θ1(x1)+θ2(x2):A1x1+A2x2=b}\min\{\theta_1(x_1)+\theta_2(x_2) : A_1x_1+A_2x_2=b\}min{θ1​(x1​)+θ2​(x2​):A1​x1​+A2​x2​=b}, it alternates one minimisation of the augmented Lagrangian in each block with a multiplier update. Its convergence for closed convex …

7 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

From Data to Decisions: Distributionally Robust Optimization Is Optimal 2: The Relative-Entropy Robust Predictor–Prescriptor Pair Is Strongly Optimal among Data-Driven PairsResearch Paper

A decision maker wants to choose xxx in a compact set X⊆RnX\subseteq\mathbb R^nX⊆Rn to minimize an expected cost c(x,P⋆)=EP⋆[γ(x,ξ)]c(x,\mathbb P^\star)=\mathbb E_{\mathbb P^\star}[\gamma(x,\xi)]c(x,P⋆)=EP⋆​[γ(x,ξ)], but the distribution P⋆\mathbb P^\starP⋆ of ξ\xiξ is unknown; only independent samples ξ1,…,ξT\xi_1,\dots,\xi_Tξ1​,…,ξT​ are available. The standard remedy, minimizing the cost under the empirical distribution, is…

9 thms3 active usersReviewed
Convex OptimizationOperations ResearchOptimal Transport·Captain: mikedeng1

Optimal Transport-Based Distributionally Robust Optimization: Structural Properties and Iterative Schemes 3: The Dual Objective Is √δκ₁-Strongly Convex in (β, λ) Near the Dual OptimizersResearch Paper

A decision based on observed data can change when the data law differs from the one used to choose it. Distributionally robust optimization addresses this by evaluating each decision against a family of nearby probability laws. Optimal transport gives one way to define “nearby”: a candidate law is admissible when probability mass can be moved from the…

17 thms3 active usersReviewed
🏆Completed
Complexity TheoryLinear OptimizationOperations Research+1·Captain: mikedeng1

A Comment on "Computational Complexity of Stochastic Programming Problems" 3: An ε-Optimal Decision of the Random-Recourse Program (11) Decides the Integer Feasibility ProblemResearch Paper

A linear two-stage stochastic program chooses a first-stage decision xxx before an uncertain parameter ξ~\tilde\xiξ~​ is revealed, and pays the optimal value Q(x,ξ)Q(x,\xi)Q(x,ξ) of a second-stage linear program once the realization ξ\xiξ is known. Such programs are the basic model of planning under uncertainty in operations research, and their computational complexity…

8 thms3 active usersReviewed
🏆Completed
AnalysisOperations Research·Captain: mikedeng1

Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programs 1: Every Cluster Point of the e-PSG Iterates Is a Lifted Stationary PointResearch Paper

A fractional program minimizes a ratio f(x)/g(x)f(x)/g(x)f(x)/g(x) over a set SSS. Nonconvex, nonsmooth ratios arise in the scale-invariant sparse signal recovery model min⁡∥x∥1/∥x∥2\min\|x\|_1/\|x\|_2min∥x∥1​/∥x∥2​ over a polyhedron, in robust Sharpe-ratio optimization in finance, and in the Rayleigh quotient x⊤Ax/x⊤Bxx^\top Ax/x^\top Bxx⊤Ax/x⊤Bx over a sphere; with g≡1g\equiv1g≡1 and S=HS=HS=H the problem reduces to composite…

13 thms3 active usersReviewed
Numerical AnalysisOperations Research·Captain: mikedeng1

The Proximal Alternating Direction Method of Multipliers in the Nonconvex Setting: Convergence Analysis and Rates 2: Finite, Linear or Sublinear Rates for the Iterates Under the Łojasiewicz PropertyResearch Paper

The alternating direction method of multipliers (ADMM) is one of the standard splitting methods for problems of the form min⁡x{g(Ax)+h(x)}\min_x\{g(Ax) + h(x)\}minx​{g(Ax)+h(x)}, in which a nonsmooth term acts on a linear image of the variable. It is used in signal and image processing, statistical learning and matrix completion, and in many of these applications ggg or hhh is nonconvex:…

14 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical Analysis·Captain: mikedeng1

First-Order Optimization Algorithms via Inertial Systems with Hessian Driven Damping V: For µ-Strongly Convex f, (IPAHD-SC) Satisfies f(x_k) − min f ≤ E₁q^{k−1}, q = 1/(1 + ½√(µs))Research Paper

Many first-order optimization methods are discretizations of second-order differential equations. In the continuous system the velocity carries the momentum, and the damping terms decide how fast the trajectory settles at a minimizer. Attouch, Chbani, Fadili and Riahi study inertial systems with Hessian driven damping: a friction term proportional to …

11 thms3 active usersReviewed
Convex Optimization·Captain: mikedeng1

The Direct Extension of ADMM for Multi-block Convex Minimization Problems is Not Necessarily Convergent I: When A₁ᵀA₃ = 0 the Extended ADMM Is Contractive and Converges to a KKT PointResearch Paper

The alternating direction method of multipliers (ADMM) solves a constrained optimization problem by minimizing an augmented Lagrangian over one block of variables at a time and then updating a multiplier. Its two-block version had established convergence results. Applying the same cycle to three or more blocks was natural in models whose objective separates…

9 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimal Transport·Captain: mikedeng1

Optimal Transport-Based Distributionally Robust Optimization: Structural Properties and Iterative Schemes 2: The Dual Objective f_δ(β, λ) = E_P0[ℓ_rob(β, λ; X)] Is Proper and ConvexResearch Paper

Distributionally robust optimization (DRO) replaces the expected loss EP0[ℓ(βTX)]E_{P_0}[\ell(\beta^{\mathsf T}X)]EP0​​[ℓ(βTX)] of a decision β\betaβ under a baseline distribution P0P_0P0​ by its worst case over all distributions PPP that are close to P0P_0P0​. When closeness is measured by an optimal transport cost, the worst case over this infinite-dimensional ball has a one-dimensional dual:…

9 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

From Data to Decisions: Distributionally Robust Optimization Is Optimal 1: The Relative-Entropy Robust Predictor Is the Least Conservative Predictor Whose Disappointment Decays at Rate rResearch Paper

A decision maker who must choose xxx before observing an uncertain outcome ξ\xiξ usually does not know the distribution of ξ\xiξ; only past observations ξ1,…,ξT\xi_1,\dots,\xi_Tξ1​,…,ξT​ are available. Data-driven optimization replaces the unknown expected cost by an estimate computed from the data. The simplest estimate, the sample average, is optimistically biased: the cost…

13 thms3 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryOperations Research+1·Captain: mikedeng1

A Comment on "Computational Complexity of Stochastic Programming Problems" 2: The Expected Recourse Value of (10) Is 1 − Vol(P(S; ⪯)), and a 1/(2k!)-Accurate Value Counts Linear ExtensionsResearch Paper

A two-stage stochastic program chooses a first action before uncertainty is observed and then takes a recourse action after the observation. Evaluating the expected optimal recourse value can be difficult even when the recourse problem for each fixed observation is a small linear program. This mission isolates the example in Section 3 of Hanasusanto, Kuhn…

8 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

Constrained Assortment Optimization for the Nested Logit Model 7: Under Space Constraints, for Every α > 1, O(⌈α/(α−1)⌉ n^(⌈α/(α−1)⌉+2)) Candidate Assortments Include an α-Approximate SolutionResearch Paper

A retailer that sells products in categories must decide which products to offer in each category. When customers choose among the offered products according to the nested logit model, the expected revenue depends on the offered assortment in a nonlinear way, and the retailer's shelf space adds a knapsack constraint in every category. Gallego and Topaloglu (…

9 thms3 active usersReviewed
🏆Completed
Complexity TheoryOperations ResearchProbability+1·Captain: mikedeng1

A Comment on "Computational Complexity of Stochastic Programming Problems" 1: δ-Accurate Expected Recourse Values of Problem (2) Determine the #Parity Count of a Knapsack PolytopeResearch Paper

A two-stage stochastic program chooses a decision before uncertainty is observed and a recourse decision afterward. Its objective can involve the expected optimal value of the recourse problem. Even with linear constraints, evaluating that expectation can be difficult when the random input has many coordinates. Dyer and Stougie's 2006 complexity paper studie…

10 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOperations Research·Captain: mikedeng1

The Proximal Alternating Direction Method of Multipliers in the Nonconvex Setting: Convergence Analysis and Rates 1: Bounded Iterates Converge to a KKT Point with Finite Length Under the KL PropertyResearch Paper

Many problems in signal processing, statistics and machine learning are of the form min⁡x{g(Ax)+h(x)}\min_x \{g(Ax)+h(x)\}minx​{g(Ax)+h(x)}: a smooth data-fitting term hhh, plus a possibly nonsmooth and nonconvex regularizer ggg applied to a linear image AxAxAx of the variable. Examples are total-variation-type penalties with nonconvex potentials, ℓ0\ell_0ℓ0​-type sparsity terms, and constraints Ax∈CAx\in CAx∈C…

16 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical Analysis·Captain: mikedeng1

First-Order Optimization Algorithms via Inertial Systems with Hessian Driven Damping II: The Inertial Proximal Algorithm (IPAHD) Satisfies f(x_k) − min f = O(1/δ_k)Research Paper

Accelerated first-order methods, such as Nesterov's method and FISTA, reach a convergence rate of O(1/k2)\mathcal O(1/k^2)O(1/k2) on the objective values of a smooth convex function, against O(1/k)\mathcal O(1/k)O(1/k) for plain gradient descent. Since the work of Su, Boyd and Candès (arXiv:1503.01243), these methods are studied through their continuous-time limits, second-order…

9 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical Analysis·Captain: mikedeng1

First-Order Optimization Algorithms via Inertial Systems with Hessian Driven Damping III: The Inertial Gradient Algorithm (IGAHD) Satisfies f(x_k) − min f = O(1/k²) and Σ k²‖∇f(x_k)‖² < ∞Research Paper

Accelerated gradient methods use information from earlier iterates to reduce the objective gap of a smooth convex optimization problem faster than ordinary gradient descent. Their behavior depends on the precise momentum rule. Attouch, Chbani, Fadili, and Riahi study a discrete rule with an additional difference of consecutive gradients, motivated by an…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationDynamical Systems·Captain: mikedeng1

First-Order Optimization Algorithms via Inertial Systems with Hessian Driven Damping IV: For µ-Strongly Convex f, (DIN)2√µ,β Trajectories Satisfy f(x(t)) − min f ≤ Ce^{−√µ(t−t₀)/2}Research Paper

Accelerated first-order methods for convex minimization, such as Nesterov's method and Polyak's heavy ball method, are now routinely studied through their continuous-time limits: second-order differential equations whose trajectories descend toward a minimizer. In the time-continuous setting the convergence analysis is a Lyapunov argument, and a good…

9 thms3 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimal Transport·Captain: mikedeng1

Regularization via Mass Transportation I: Wasserstein-Robust Linear Classification with Label Flipping Is a Finite Convex ProgramResearch Paper

A classifier trained from finitely many examples can perform well on those examples while responding poorly to changes in the feature distribution or to mislabeled observations. Distributionally robust learning addresses this by choosing a classifier against every probability distribution within a specified distance of the empirical distribution. The…

9 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization 1: All Four Frank-Wolfe Variants Reach Duality Gap ≤ 2βC_f(1+δ)/(K+2), β = 27/8, Within K IterationsResearch Paper

The Frank–Wolfe method, also called the conditional-gradient method, minimizes a smooth convex objective over a compact convex set while asking only for a minimizer of a linear function over that set. In domains where a linear optimization oracle is easier than a projection, this distinction changes which algorithms are practical. Examples in Jaggi's paper…

5 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization 2: With (1/γ)-Smooth Losses, SDCA Reaches Expected Duality Gap ε after (n + 1/(λγ))·log((n + 1/(λγ))/ε) IterationsResearch Paper

Regularized loss minimization (training a linear predictor with a convex loss and an ℓ2\ell_2ℓ2​ penalty) covers support vector machines, ridge and logistic regression, and much of classical linear learning. A standard way to solve these problems at scale is dual coordinate ascent: optimize the dual problem one coordinate, i.e. one training example, at a time.…

12 thms3 active usersReviewed
PreviousPage 40 of 93Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me