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

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
🏆Completed
Operations ResearchOptimal TransportOptimization·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
Numerical AnalysisOptimization·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
Numerical AnalysisOptimization·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
Dynamical SystemsOptimization·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 LearningOptimization·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
Machine LearningOptimization·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
🏆Completed
AnalysisOperations ResearchOptimization·Captain: mikedeng1

A Primal-Dual Interior-Point Algorithm for Nonsymmetric Exponential-Cone Optimization 3: The Exponential-Cone Barrier Does Not Have Negative CurvatureResearch Paper

Interior-point methods for conic optimization are best understood on symmetric cones: the nonnegative orthant, the second-order cone and the cone of positive semidefinite matrices. On these cones the barrier functions are self-scaled, and Nesterov and Todd showed that every primal-dual pair (x,s)(x, s)(x,s) then has a unique scaling point www with s=F′′(w)xs = F''(w)xs=F′′(w)x and …

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

A Primal-Dual Interior-Point Algorithm for Nonsymmetric Exponential-Cone Optimization 1: Along the Combined Corrector Direction the Residuals and the Complementarity Gap Both Scale by 1 − α(1 − γ)Research Paper

Conic optimization over the exponential cone Kexp⁡=cl⁡{x∈R3:x1≥x2ex3/x2, x2>0}K_{\exp}=\operatorname{cl}\{x\in\mathbb R^3: x_1\ge x_2e^{x_3/x_2},\ x_2>0\}Kexp​=cl{x∈R3:x1​≥x2​ex3​/x2​, x2​>0} models entropy, relative entropy, logistic regression, log-sum-exp and geometric programming. Unlike the nonnegative orthant, the second-order cone and the semidefinite cone, the exponential cone is not symmetric (self-scaled), so the…

8 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems 3: For Block-Constrained Problems, Uniform Coordinate Descent Has Rate n/(n + k), Linear Under Strong ConvexityResearch Paper

Coordinate descent methods update one block of variables at a time. They are the method of choice when the number of variables is so large that even one full gradient is too expensive, while a single partial derivative is cheap: support vector machines, ℓ1\ell_1ℓ1​-regularized regression, and large sparse least-squares problems are the standard examples. Yu.…

8 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems 4: Accelerated Coordinate Descent ACDM Has Expected Error at Most (n/(k + 1))²·(2‖x₀ − x*‖₁² + (f(x₀) − f*)/n²)Research Paper

Coordinate descent methods update one block of variables at a time. For problems with millions or billions of variables, where even one full gradient is too expensive to compute or store, a step that touches a single block can be orders of magnitude cheaper than a full gradient step. Nesterov's Efficiency of coordinate descent methods on huge-scale…

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

Online Learning and Online Convex Optimization 1: Follow-the-Regularized-Leader with a σ-Strongly-Convex Regularizer Has Regret at Most R(u) − min R + TL²/σResearch Paper

Online convex optimization is a repeated game between a learner and an environment. In each round the learner commits to a vector, the environment then reveals a convex loss function, and the learner pays the loss of its vector. No statistical assumption is made about how the losses are generated; they may be chosen adversarially. Performance is measured…

8 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems 2: On a Regularized Objective, RCDM(1, x₀) Finds an ε-Solution with Probability ≥ β Within the Iteration Bound (3.11)Research Paper

Randomized coordinate descent updates one block of variables per iteration, chosen at random. For problems whose dimension makes even one full gradient expensive (the "huge-scale" problems of the title, such as sparse least squares or truss topology design), a coordinate step can cost a tiny fraction of a gradient step. Nesterov's paper (CORE Discussion…

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

Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization 2: For F Smooth at the Optimum, SGD's Last and Averaged Iterates Attain 2µG²/(λ²T) and 16µG²/(λ²T)Research Paper

Stochastic gradient descent (SGD) is the standard method for minimizing an expected loss F(w)=Ez[ℓ(w,z)]F(w) = \mathbb E_z[\ell(w, z)]F(w)=Ez​[ℓ(w,z)] when only noisy gradients are available: in machine learning, www is a predictor, zzz a random example, and each step uses the gradient of the loss on one fresh example. When FFF is strongly convex, as for regularized learning problems such as…

9 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems 1: Random Block Coordinate Descent RCDM(α, x₀) Has Expected Error at Most 2·S_α·R²_{1−α}(x₀)/(k + 4)Research Paper

Many large optimization problems arising in machine learning, statistics and network analysis have so many variables that computing a single full gradient is already expensive, while a single partial derivative, or a gradient with respect to a small block of variables, is cheap. Coordinate descent methods exploit this: at each iteration they update one…

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

A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets 2: For n ≥ 8L/μ, SAG with Step 1/(2nμ) after an SG Warm Start Converges at Rate (1 − 1/(8n))ᵏResearch Paper

Many problems in machine learning are finite-sum problems: minimize the average of nnn loss functions, one per training example,

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

Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization 3: SGD with Full Averaging Suffers an Ω(log(T)/T) Rate on a Non-Smooth Strongly Convex ProblemResearch Paper

Stochastic gradient descent (SGD) is the standard first-order method for stochastic convex optimization and for training linear predictors on large data sets: at each step it queries a noisy subgradient of the objective, takes a step against it and projects back onto the feasible set. When the objective is strongly convex, the classical online-learning…

7 thms3 active usersReviewed
🏆Completed
Linear algebraOperations ResearchOptimization·Captain: mikedeng1

On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues: If m > k(n − k), Extreme Optima of Affine EV_k Have λ_k = λ_{k+1} with Multiplicity ≥ n − τResearch Paper

Minimizing the sum of the kkk largest eigenvalues of a symmetric matrix that depends affinely on parameters is a basic problem of eigenvalue optimization (survey: A. S. Lewis and M. L. Overton, Eigenvalue optimization, Acta Numerica 5, 1996, doi:10.1017/S0962492900002646). Its objective is convex, and fkf_kfk​ is differentiable at BBB exactly when …

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

Sample Size Selection in Optimization Methods for Machine Learning 1: With Batch Sizes n_k ≥ a^k, Dynamic Batch Steepest Descent Converges Linearly in Expectation, E[J(w_k) − J(w*)] ≤ Cρ^kResearch Paper

Training a model in machine learning means minimizing an expected loss over a data distribution, using a finite sample from it. Two families of methods dominate. Stochastic gradient methods step along the gradient of the loss at one data point: each step is cheap, but the noise forces small steps and many sequential iterations. Batch methods average the…

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

Sample Size Selection in Optimization Methods for Machine Learning 2: Steepest Descent with Gradient Error ‖g_k − ∇J(w_k)‖ ≤ θ‖g_k‖ Contracts J by 1 − βλ/L per StepResearch Paper

Training a machine-learning model usually means minimizing an expected or empirical loss J(w)J(w)J(w) over parameters w∈Rmw \in \mathbb{R}^mw∈Rm. Exact gradients of such objectives are expensive, because each one requires a pass over the whole data set; practical methods replace ∇J(wk)\nabla J(w_k)∇J(wk​) by a cheaper approximation gkg_kgk​, for instance a gradient computed on a subsample.…

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

Primal and Dual Linear Decision Rules in Stochastic and Robust Optimization 2: With Random Recourse, the SDP (3.14) Conservatively Approximates the Linear Decision Rule Problem, Exactly for l = 1Research Paper

In a one-stage stochastic program a decision maker observes a random outcome ξ\xiξ and then picks a decision x(ξ)x(\xi)x(ξ), subject to constraints that depend on ξ\xiξ, so as to minimize expected cost. The optimization variable is a whole function xxx, and computing the optimal value is #P-hard even for a uniform distribution on the unit cube (Dyer and Stougie, 2006,…

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

Distributionally Robust Optimization and Its Tractable Approximations 3: The Infimal Convolution of π¹, π², π³ Bounds the Worst Case over the Intersected Families and Improves on EachResearch Paper

Two-stage and multistage stochastic programs ask for decisions that react to uncertainty revealed over time. When the distribution of the uncertainty is known only partially, one optimizes against the worst distribution in a family F\mathbb FF consistent with what is known: a support set, a range for the mean, a covariance matrix, bounds on how fast the tails…

10 thms3 active usersReviewed
🏆Completed
Functional AnalysisOptimization·Captain: mikedeng1

A Monotone+Skew Splitting Model for Composite Monotone Inclusions in Duality: The Inexact Primal–Dual Forward–Backward–Forward Iterates Converge Weakly to a Primal and a Dual SolutionResearch Paper

Many problems in convex optimization, variational inequalities, mechanics, traffic equilibrium and signal processing reduce to finding a zero of a monotone operator on a Hilbert space. Frequently that operator is a sum A+L∗∘B∘LA + L^*\circ B\circ LA+L∗∘B∘L of a monotone operator and a monotone operator composed with a linear map and its adjoint, and one also wants the…

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

Solving Semidefinite-Quadratic-Linear Programs Using SDPT3: The HKM and NT Search Directions of Second-Order Cone Programming Are Invariant Under Automorphic ScalingResearch Paper

Second-order cone programming (SOCP) minimizes a linear function over the intersection of an affine subspace with a product of Lorentz cones. It contains convex quadratically constrained programs, robust linear programs with ellipsoidal uncertainty, and many norm-minimization problems, and it is solved in practice by primal–dual interior-point methods. At…

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

Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems: Error √2ΘL/(αN) After N StepsResearch Paper

Monotone variational inequalities (v.i.) cover convex minimization, convex–concave saddle-point problems, Nash equilibria of convex games and complementarity problems. Matrix games and other large saddle-point problems are typical cases. At large scale, first-order methods that use only values of the operator and simple auxiliary minimizations are the…

18 thms3 active users
PreviousPage 12 of 23Next

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