Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Convex Optimization

746 missions · 569 completed

Missions

Open177Completed569All746
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 8: Semi-AFB for min over Q of h + g Contracts ℒ_k by 1/(1 + α_k) and Has the Rate of Theorem 5.1Research Paper

Many convex problems in signal processing, statistics and control have the composite form "smooth loss plus nonsmooth regulariser, subject to a simple constraint": a least-squares or entropy term hhh, a sparsity or total-variation penalty ggg, and a feasible set QQQ such as a box, a simplex or a cone. Accelerated proximal gradient methods (FISTA, Beck and…

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

Sinkhorn Distributionally Robust Optimization 2: Biased Stochastic Mirror Descent with SG or RT-MLMC Subgradient Estimators Reaches a δ-Optimal SolutionResearch Paper

Sinkhorn distributionally robust optimization (Wang, Gao and Xie, arXiv:2109.11926) hedges a learning or decision problem against distribution shift. It minimizes the worst-case expected loss over all distributions within an entropically regularized optimal-transport distance (the Sinkhorn distance) of a nominal distribution P^\widehat{\mathbb P}P. Strong…

10 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Linear Convergence of First Order Methods for Non-Strongly Convex Optimization III: Projected Gradient Contracts dist(·, X*) at Every Feasible Point If and Only If f Has Quadratic Functional GrowthResearch Paper

Linear convergence of first order methods is classically tied to strong convexity. Many problems in data fitting, machine learning and control are not strongly convex, yet gradient methods are observed to converge linearly on them: least squares with a rank-deficient matrix, the dual of a linearly constrained quadratic program, f(x)=g(Ax)f(x) = g(Ax)f(x)=g(Ax) with ggg strongly…

10 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Linear Convergence of First Order Methods for Non-Strongly Convex Optimization VI: Feasible Descent Methods Converge Linearly in Function Values under Quadratic Functional GrowthResearch Paper

Many first order methods used in large-scale convex optimization do not take an exact projected gradient step. Proximal point iterations, random or cyclic coordinate descent, extragradient methods and matrix splitting methods all produce iterates that behave like a projected gradient step corrupted by an error which is small relative to the step itself. Luo…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Multistage Distributionally Robust Mixed-Integer Programming with Decision-Dependent Moment-Based Ambiguity Sets III: Under Slater, the Delage–Ye-Type Stage Bellman Equation Is One SDP MinimizationResearch Paper

In many multistage decision problems the probability law of the next uncertainty depends on the decision taken now: opening a facility changes the demand it attracts, a price changes the distribution of sales, maintenance changes failure rates. Distributionally robust optimization (DRO) handles an imperfectly known law by optimizing against the worst…

10 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Linear Convergence of First Order Methods for Non-Strongly Convex Optimization II: Quadratic Functional Growth with Constant κ Gives the Global Error Bound with Constant κ/(1 + μ + √(1 + μ))Research Paper

First order methods (projected gradient, fast gradient) converge only sublinearly on general smooth convex problems, at rates O(1/k)O(1/k)O(1/k) and O(1/k2)O(1/k^2)O(1/k2) in function value. Linear convergence is classically proved under strong convexity, which fails for many problems arising in practice: least squares with a rank-deficient matrix, dual problems of linearly…

7 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Linear Convergence of First Order Methods for Non-Strongly Convex Optimization VII: g(Ax) with g Strongly Convex and Smooth Is Quasi-Strongly Convex on a Polyhedron with κ = σ_g/θ²(A, C)Research Paper

Linear convergence of gradient-type methods is classically proved under strong convexity. Many problems that arise in practice are not strongly convex: dual formulations of linearly constrained convex problems, least-squares and logistic-type regression with rank-deficient data matrices, convex quadratic programs, and routing problems in data networks all…

7 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Linear Convergence of First Order Methods for Non-Strongly Convex Optimization I: Strong ⇒ Quasi-Strong Convexity ⇒ Quadratic Gradient Growth ⇒ Quadratic Under-Approximation ⇒ Functional GrowthResearch Paper

First-order methods (projected gradient, fast gradient, feasible descent) converge linearly on smooth strongly convex problems, but many problems met in practice are not strongly convex: least squares with a rank-deficient matrix, the dual of a linearly constrained problem, or g(Ax)g(Ax)g(Ax) with ggg strongly convex and AAA singular. Such problems have a whole set of…

8 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization 2: If g Is Restricted Strongly Convex and α < 2μ_g λmin(W̃)/L_f², ‖z^k − z*‖²_G Converges Q-Linearly to 0Research Paper

In decentralized consensus optimization, nnn agents connected by a communication network cooperatively solve

8 thms3 active usersReviewed
Optimization·Captain: mikedeng1

EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization 1: For 0 < α < 2λmin(W̃)/L_f, EXTRA Converges and Its Optimality Residuals Are O(1/k) on Average, o(1/k) at BestResearch Paper

In decentralized consensus optimization a connected network of nnn agents cooperatively solves

15 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

K-Adaptability in Two-Stage Robust Binary Programming 1: Under Objective Uncertainty, min{dim 𝒴, rk Q} + 1 Policies Attain the Two-Stage Optimal ValueResearch Paper

Many planning problems are made in two stages: a first decision is fixed before an uncertain parameter is observed, and a second, corrective decision is made afterwards. When the second-stage decisions are binary (which route, which facility, which crew), the resulting two-stage robust binary programs are notoriously hard: the second-stage decision is a…

11 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

K-Adaptability in Two-Stage Robust Binary Programming 4: The ε-Approximations (6ε) Converge Uniformly to the K-Adaptability ProblemResearch Paper

Two-stage robust optimization models decisions taken in two steps around an uncertain parameter: a here-and-now decision xxx is fixed before the parameter ξ\xiξ is revealed, and a wait-and-see decision yyy adapts to it, and the decision maker guards against the worst ξ\xiξ in an uncertainty set Ξ\XiΞ. When the second-stage decisions are binary, as in routing,…

7 thms3 active usersReviewed
Complexity TheoryMachine LearningOptimization·Captain: mikedeng1

Tight Complexity Bounds for Optimizing Composite Objectives III: Any Deterministic Algorithm with Gradient and Prox Oracles Needs Ω(m√(γ/λ)·log(λε₀/(γε))) Queries on Smooth Strongly Convex SumsResearch Paper

Many problems in machine learning and statistics minimize an average of component losses, F(x)=1m∑i=1mfi(x)F(x)=\frac1m\sum_{i=1}^m f_i(x)F(x)=m1​∑i=1m​fi​(x): one term per training example, per data shard, or per block of a decomposed objective. Incremental methods such as SAG, SVRG, SAGA, SDCA and their accelerated variants touch one component at a time, so the natural measure of their work…

10 thms3 active usersReviewed
🏆Completed
Control TheoryOptimization·Captain: mikedeng1

Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints II: Gradients of m-Strongly Convex Functions with L-Lipschitz Gradient Satisfy the Weighted Off-by-One ρ-Hard IQCResearch Paper

First-order methods (gradient descent, Nesterov's accelerated method, the Heavy-ball method) are the workhorses of large-scale convex optimization, and their worst-case convergence rates on smooth strongly convex functions are classical objects of study. Lessard, Recht and Packard (arXiv:1408.3595v7, SIAM J. Optim. 26(1), 2016, doi:10.1137/15M1009597)…

11 thms3 active usersReviewed
🏆Completed
Control TheoryOptimization·Captain: mikedeng1

Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints III: Heavy-Ball Tuned for Quadratics Converges to a 3-Cycle, Not the Minimizer, of a Strongly Convex f with L/m = 25Research Paper

The Heavy-ball method of Polyak, xk+1=xk−α∇f(xk)+β(xk−xk−1)x_{k+1}=x_k-\alpha\nabla f(x_k)+\beta(x_k-x_{k-1})xk+1​=xk​−α∇f(xk​)+β(xk​−xk−1​), adds a momentum term to gradient descent. On strongly convex quadratics with curvature between mmm and LLL, a classical eigenvalue analysis gives the step size and momentum that minimise the worst-case linear rate, α=4/(L+m)2\alpha=4/(\sqrt L+\sqrt m)^2α=4/(L​+m​)2 and …

10 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Distributionally Robust Joint Chance Constraints with Second-Order Moment Information II: Over Scaling Parameters, Worst-Case CVaR Is Essentially Exact for Joint Chance ConstraintsResearch Paper

A chance constraint asks that a decision x∈Rnx\in\mathbb R^nx∈Rn satisfy uncertain inequalities with high probability. In the setting of Zymler, Kuhn and Rustem (Math. Program. 137, 2013), mmm affine inequalities yi0(x)+yi(x)⊤ξ~≤0y_i^0(x)+y_i(x)^\top\tilde\xi\le0yi0​(x)+yi​(x)⊤ξ~​≤0, whose coefficients depend affinely on xxx, must hold jointly with probability at least 1−ϵ1-\epsilon1−ϵ. Joint chance constraints…

17 thms3 active usersReviewed
🏆Completed
Machine LearningOptimizationProbability·Captain: mikedeng1

Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz Algorithm: SGD with Step γ < 1/sup L Has E‖x_k − x⋆‖² ≤ [1 − 2γμ(1 − γ sup L)]^k ‖x₀ − x⋆‖² + γσ²/(μ(1 − γ sup L))Research Paper

Stochastic gradient descent (SGD) minimizes an objective that is an expectation, F(x)=Ei∼Dfi(x)F(x) = \mathbb E_{i\sim\mathcal D} f_i(x)F(x)=Ei∼D​fi​(x), by stepping along the gradient of one randomly drawn component at a time. It is the workhorse of large-scale machine learning, where FFF is an average loss over training examples, and it also contains the randomized Kaczmarz method for…

8 thms3 active usersReviewed
🏆Completed
Linear algebraOptimization·Captain: mikedeng1

Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization 3: Hankel-Matrix SDP Lower Bounds for Minimizing a Power Sum Subject to Fixed Lower Power SumsResearch Paper

Many polynomial optimization problems are invariant under permuting the variables: the objective and the constraints are symmetric polynomials. Lasserre's moment–sum-of-squares hierarchy solves such problems by a sequence of semidefinite programs whose size grows quickly with the number of variables and the degree, and symmetry is the main tool for…

6 thms3 active usersReviewed
Complexity TheoryMachine LearningOptimization·Captain: mikedeng1

Tight Complexity Bounds for Optimizing Composite Objectives I: Any Deterministic Algorithm with Gradient and Prox Oracle Access Needs Ω(mLB/ε) Queries on Sums of m Convex L-Lipschitz FunctionsResearch Paper

Many optimization problems minimize the average of component losses: one loss per observation, machine, or term in an objective. When an algorithm can inspect one component at a time, the number of component queries is a useful measure of work. A component oracle can provide more than a value or subgradient: a proximal point summarizes a global minimization…

8 thms3 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

A Modern Introduction to Online Learning XI: Constrained Online Convex Optimization Reduces to Unconstrained Learning on Distance-Penalized Surrogate LossesTextbook

An online learner repeatedly chooses a point, observes a loss, and is judged by the difference between its accumulated loss and that of a fixed competitor. In practice, an available learner may operate on a broad feasible set WWW, while the application permits decisions only in a smaller set VVV. Replacing each output by a feasible point changes the learner's…

9 thms3 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

A Modern Introduction to Online Learning XIII: Online Mirror Descent Has Dynamic Regret (B_ψ(u_T; x_1) + Q·P(u_1, …, u_T))/η + (η/(2λ)) Σ_t ‖g_t‖⋆²Textbook

In online learning, a learner chooses a point before seeing each round's loss. Ordinary regret compares the learner with one fixed point chosen after all rounds. That comparison can be too coarse when a useful action changes over time. A portfolio allocation, a prediction rule, or an operating point may need to move after the environment shifts. Dynamic…

7 thms3 active usersReviewed
🏆Completed
Dynamical SystemsOptimization·Captain: mikedeng1

A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights V: The Speed Restarted ODE Converges Linearly for Strongly Convex fResearch Paper

Nesterov's accelerated gradient method minimizes a convex function fff with LLL-Lipschitz gradient at the rate O(1/k2)O(1/k^2)O(1/k2), which is optimal among first-order methods. For a μ\muμ-strongly convex fff the method with the generic momentum coefficient (k−1)/(k+2)(k-1)/(k+2)(k−1)/(k+2) does not exploit the strong convexity: Su, Boyd and Candès show in §4.2 of arXiv:1503.01243 that its rate…

10 thms3 active usersReviewed
🏆Completed
Linear algebraOptimization·Captain: mikedeng1

Phase Recovery, MaxCut and Complex Semidefinite Programming 1: For Injective A, Nonzero b and Solvable |Ax| = b, PhaseCutMod Is Tight Whenever PhaseLift IsResearch Paper

Phase recovery (also called phase retrieval) asks to reconstruct a complex signal from the magnitudes of linear measurements of it, the phases being lost. It arises wherever detectors record intensities only: X-ray crystallography, diffraction imaging, astronomy and optics, where a sensor measures ∣⟨ai,x⟩∣2|\langle a_i, x\rangle|^2∣⟨ai​,x⟩∣2 and not ⟨ai,x⟩\langle a_i, x\rangle⟨ai​,x⟩. The…

9 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Relatively Smooth Convex Optimization by First-Order Methods, and Applications III: The Primal Gradient Scheme Solves D-Optimal Design to Accuracy ε within 2n ln(2(f(x⁰)−f*)/ε)/ε IterationsResearch Paper

In D-optimal design, a statistician chooses weights for a collection of candidate observations. The weights determine an information matrix, and maximizing its determinant favors a design that estimates several parameters jointly with a small confidence region. The same determinant objective appears in the minimum-volume enclosing ellipsoid problem. These…

12 thms3 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

A Modern Introduction to Online Learning V: Online Mirror Descent with a λ-Strongly Convex Regularizer Has Regret max_t B_ψ(u; x_t)/η_T + Σ_t η_t‖g_t‖⋆²/(2λ)Textbook

Online learning studies repeated decisions made before their losses are known. A learner chooses a point, observes a loss function, and then uses that observation to choose the next point. The natural performance measure is regret: the learner's cumulative loss minus the cumulative loss of one fixed competitor chosen after the sequence is known. A regret…

7 thms3 active usersReviewed
PreviousPage 13 of 30Next

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