Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Convex Optimization

744 missions · 566 completed

Missions

Open178Completed566All744
Machine LearningOperations ResearchStatistics·Captain: Shuze Chen

Shape-Constrained Regression Using Sum of Squares Polynomials: Almost-sure consistency of convex sum-of-squares estimatorsResearch Paper

Regression estimates an unknown relationship between features and responses from noisy observations. In many applications, a qualitative property of that relationship is known before data are collected. A production response may exhibit convexity, or a response may have a known directional derivative bound. Enforcing such information throughout a continuous…

18 thms4 active usersReviewed
Operations ResearchOptimal TransportOptimization·Captain: mikedeng1

Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls 1: Copositive Programs (28) Are Exact under Complete Recourse and Converge to (1) as δ ↓ 0Research Paper

Two-stage decision problems split decisions into a here-and-now decision xxx, taken before an uncertain parameter ξ\xiξ is observed, and a wait-and-see (recourse) decision yyy, taken after. Stochastic programming minimizes the expected total cost under a known distribution of ξ\xiξ; robust optimization minimizes the worst-case cost over a support set. Distributional…

19 thms4 active usersReviewed
Algorithmic Game TheoryOperations ResearchOptimization+1·Captain: mikedeng1

On Synchronous, Asynchronous, and Randomized Best-Response Schemes for Stochastic Nash Games 3: Asynchronous Inexact Best Response with Delays Reaches an ϵ-NE in Explicitly Bounded SG StepsResearch Paper

Many equilibrium problems in operations research have the form of a stochastic Nash game: each of NNN players minimizes an expected cost that depends on the strategies of the others, and the expectation can only be sampled. The paper's introduction lists applications in generation-capacity and power markets and in communication networks (Abada, de Maere…

19 thms4 active usersReviewed
Operations ResearchOptimization·Captain: mikedeng1

Self-Scaled Barriers and Interior-Point Methods for Convex Programming III: An Affine Potential-Reduction Step Lowers the Potential by at Least 1 − ln 2, and by (‖p‖²/|p|²)(1 − ln 2) When µ ≥ 2νResearch Paper

Potential-reduction methods solve a linear or conic program by driving down a single merit function that combines the objective gap with a barrier for the constraint cone. For linear programming the primal version goes back to Karmarkar (1984) and, without Karmarkar's special problem form, to Gonzaga (1990, Math. Programming 49, 7–21), whose method reduces…

15 thms4 active usersReviewed
Operations ResearchOptimization·Captain: mikedeng1

Primal-Dual Interior-Point Methods for Self-Scaled Cones I: After One Short Step from N(β), λ₂(x₊, s₊) ≤ (2 + δ − κ)(ϵ + κ)²/((1 − δ)²(1 − κ)³)Research Paper

Linear programming, second-order cone programming and semidefinite programming are all instances of conic linear programming: minimize a linear function over the intersection of an affine subspace with a closed convex cone. Primal-dual interior-point methods solve these problems in polynomially many iterations and are the algorithms behind most conic…

17 thms4 active usersReviewed
Markov ChainOperations ResearchStochastic Systems·Captain: mikedeng1

An Adaptive Algorithm for Finding the Optimal Base-Stock Policy in Lost Sales Inventory Systems with Censored Demand: Adaptive(α, β) Has Per-Period Regret O(N(L)^(−1/3)) at α = β = 1/2Research Paper

Periodic-review inventory systems with lost sales and a positive replenishment lead time are a basic model of retail and spare-parts operations: demand that cannot be met from stock is lost, and an order placed today arrives τ\tauτ periods later. Even with a known demand distribution the optimal policy depends on the whole vector of outstanding orders and is…

12 thms4 active usersReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: Shuze Chen

Polynomial-Time Differentially Private Synthetic Graph Release with Nearly-Linear Additive ErrorResearch Paper

Releasing a weighted graph under edge-level differential privacy is a basic task in private data analysis: the vertex set is public, the weight of every pair of vertices is private, and a released synthetic graph should preserve the answers to a rich family of queries. Cut queries are the canonical family, because many graph optimization problems (Max-Cut,…

23 thms3 active usersReviewed
Computational GeometryFunctional Analysis·Captain: mikedeng1

Deterministic Terminal Embedding with Optimal Target Dimension for Euclidean SpaceResearch Paper

A database of points can be reduced to fewer coordinates while approximately preserving distances among its stored points. Many geometric applications also compare those points with centers or queries supplied later. A guarantee only about pairs already in the database does not cover every such comparison. A terminal embedding asks for one map that…

23 thms3 active usersReviewed
Markov ChainQuantum InformationTheoretical Computer Science·Captain: iris

Improved Upper and Lower Bounds for Quantum Convex-Body Volume EstimationResearch Paper

Computing the volume of a convex body is a basic problem of algorithmic convex geometry. In the membership-oracle model every deterministic algorithm with polynomially many queries can only approximate the volume within a factor exponential in ddd (Bárány–Füredi 1987), while randomized algorithms achieve any relative accuracy with polynomially many queries…

33 thms3 active usersReviewed
Graph TheoryOptimizationTheoretical Computer Science·Captain: Shuze Chen

Efficient Correlation Clustering in Single-pass Graph Streams: Deterministic and Adversarially RobustResearch Paper

Correlation clustering asks for a partition of a vertex set that agrees as much as possible with pairwise "similar / dissimilar" labels. It is a standard model for deduplication and community detection, introduced by Bansal, Blum and Chawla (2004); minimizing disagreements is APX-hard, and a line of offline work has pushed the approximation ratio from 3 (Ail…

23 thms3 active usersReviewed
Probability·Captain: mikedeng1

Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear QueriesResearch Paper

A private query mechanism must balance the accuracy of its answers with the information it reveals about individual records. It also consumes randomness. When many queries are answered, generating the necessary independent random bits becomes a resource question of its own. Randomness complexity measures the expected number of unbiased bits consumed, in the…

17 thms3 active usersReviewed
ProbabilityRandom Matrix TheoryTheoretical Computer Science·Captain: iris

Sharp Phase Transition for Ellipsoid FittingResearch Paper

Given mmm random points in Rd\mathbb R^dRd, is there a centered ellipsoid through all of them? This ellipsoid fitting problem was introduced by Saunderson (PhD thesis, MIT, 2011) and studied by Saunderson, Chandrasekaran, Parrilo and Willsky (2012) in connection with decomposing a matrix into a diagonal and a low-rank part. It is also a basic test case for…

29 thms3 active usersReviewed
CombinatoricsInformation TheoryProbability+1·Captain: iris

Optimal e(γ+o(1))ne^{(\gamma+o(1))n}e(γ+o(1))n-Approximation of the Permanent of Positive Semidefinite MatricesResearch Paper

The permanent of a matrix A∈Cn×nA\in\mathbb C^{n\times n}A∈Cn×n is per(A)=∑σ∈Sn∏i=1nAi,σ(i)\mathrm{per}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^n A_{i,\sigma(i)}per(A)=∑σ∈Sn​​∏i=1n​Ai,σ(i)​. Computing it exactly is #P-hard even on 0/1 matrices (Valiant 1979). For nonnegative entries a randomized approximation scheme exists (Jerrum, Sinclair, Vigoda 2004). For a Hermitian positive semidefinite matrix the entries may have…

37 thms3 active usersReviewed
Numerical AnalysisOptimizationTheoretical Computer Science·Captain: iris

Solving ppp-norm regression in matrix multiplication timeResearch Paper

Given a matrix A∈Rn×dA\in\mathbb R^{n\times d}A∈Rn×d of full column rank and a vector b∈Rnb\in\mathbb R^nb∈Rn, ℓp\ell_pℓp​ regression asks for a minimizer of ∥Ax−b∥p\|Ax-b\|_p∥Ax−b∥p​. The case p=2p=2p=2 is least squares; p∈{1,∞}p\in\{1,\infty\}p∈{1,∞} is equivalent to linear programming; the values in between interpolate between linear system solving and linear programming and arise in data analysis and in flow…

27 thms3 active usersReviewed
Machine LearningOptimization·Captain: iris

Exact Feasibility and Privacy Amplification for Linearly Constrained OptimizationResearch Paper

Many allocation problems split a fixed public budget among participants whose costs depend on private records. They are instances of linearly constrained composite optimization,

43 thms3 active usersReviewed
Numerical AnalysisOptimization·Captain: iris

Benign Degeneracy for First-Order Methods in Exact Boolean Moment-SOS RelaxationsResearch Paper

Minimizing a polynomial fff over the Boolean cube {±1}n\{\pm1\}^n{±1}n contains MAX-CUT, Ising ground states and many other combinatorial problems. The moment–sum-of-squares (moment–SOS) hierarchy replaces the cube by a semidefinite program (SDP) of order ddd; when the relaxation is exact, its optimum is the rank-one moment matrix of the Boolean minimizer, and an optimal …

29 thms3 active usersReviewed
Operations ResearchOptimization·Captain: iris

Silver Rate Is (Almost) Optimal for Gradient DescentResearch Paper

Gradient descent (GD) with a predetermined stepsize schedule H=(h1,…,hn)H=(h_1,\dots,h_n)H=(h1​,…,hn​) is the method xt=xt−1−ht∇f(xt−1)x_t=x_{t-1}-h_t\nabla f(x_{t-1})xt​=xt−1​−ht​∇f(xt−1​), 1≤t≤n1\le t\le n1≤t≤n, with the stepsizes fixed before the run. With the constant stepsize 1/L1/L1/L it converges at rate O(n−1)O(n^{-1})O(n−1) on convex LLL-smooth functions, and the classical lower bound Ω(n−2)\Omega(n^{-2})Ω(n−2) of Nemirovsky and Yudin holds for every…

32 thms3 active usersReviewed
Graph TheoryOptimizationProbability·Captain: marwahaha

Grothendieck inequalities for semidefinite programs with rank constraintResearch Paper

The graphical Grothendieck problem with rank constraint maximizes a quadratic form over unit vectors assigned to the vertices of a graph. Depending on the rank, the same problem is MAX CUT, Grothendieck's inequality, the ground state of a spin model, or the value of a quantum XOR game.

22 thms3 active usersReviewed
Operations ResearchOptimizationProbability·Captain: iris

Efficient Algorithms for a Class of Stochastic Hidden Convex Optimization and Its Applications in Network Revenue Management: Explicit Global Convergence Bound for Mirror Stochastic GradientResearch Paper

Many operations management models choose a decision xxx whose effect is filtered through randomness: a booking limit xxx is truncated by random demand ξ\xiξ, so the realized sales are x∧ξx\wedge\xix∧ξ; an order quantity is scaled by a random yield. The resulting stochastic program

25 thms3 active usersReviewed
Operations ResearchOptimization·Captain: iris

Proximal-Like Incremental Aggregated Gradient Method with Linear Convergence Under Bregman Distance Growth Conditions: PLIAG Converges Linearly at Rate 1/(1+αμ)Research Paper

Large-scale learning and signal-processing problems often have the form of a sum of many convex components plus a nonsmooth regularizer, min⁡x∑n=1Nfn(x)+h(x)\min_x \sum_{n=1}^N f_n(x) + h(x)minx​∑n=1N​fn​(x)+h(x). Incremental aggregated gradient (IAG) methods process such sums by refreshing the gradient of only some components per iteration and reusing older, delayed gradients for the rest. This…

26 thms3 active usersReviewed
Operations ResearchOptimizationProbability·Captain: iris

Data-Driven Distributionally Robust CVaR Portfolio Optimization Under A Regime-Switching Ambiguity Set: For Every ℓm Cost, the Worst-Case CVaR Problem Is the Convex Program (12)Research Paper

A portfolio manager who minimizes the conditional value-at-risk (CVaR) of the portfolio loss needs the distribution of asset returns, but only has a finite history of them. Plugging the empirical distribution into the CVaR formula of Rockafellar and Uryasev (2002) gives portfolios that perform poorly out of sample. Distributionally robust optimization (DRO)…

30 thms3 active usersReviewed
Operations ResearchOptimization·Captain: iris

Difference-of-Convex Algorithm with Extrapolation for Nonconvex, Nonsmooth Optimization Problems: Bounded DCAe Sequences Converge to a Critical Point under the Kurdyka–Łojasiewicz PropertyResearch Paper

Many estimation problems in statistics and machine learning minimize a smooth data-fitting loss plus a nonconvex sparsity-promoting penalty: compressed sensing, sparse dictionary learning, phase retrieval, Poisson inverse problems and nonnegative matrix completion. Penalties such as SCAD, MCP and the exponential penalty are differences of convex functions (D…

24 thms3 active usersReviewed
Dynamical SystemsOperations ResearchOptimization·Captain: iris

Monotone Inclusions, Acceleration and Closed-Loop Control: Every Global Trajectory Has Ergodic Gap O(t−(p+1)/2)O(t^{-(p+1)/2})O(t−(p+1)/2) and Pointwise Residue O(t−p/2)O(t^{-p/2})O(t−p/2)Research Paper

A monotone inclusion asks for a point xxx of a real Hilbert space H\mathcal HH with 0∈Ax0\in Ax0∈Ax, where AAA is a set-valued monotone operator. Convex minimization, convex-concave saddle points and monotone variational inequalities are all of this form. The basic method is the proximal point algorithm of Rockafellar (1976), the fixed-point iteration of the resolvent …

16 thms3 active usersReviewed
Functional AnalysisOperations ResearchOptimization·Captain: iris

A Perturbation Framework for Convex Minimization and Monotone Inclusion Problems with Nonlinear Compositions: Lagrangian, Dual and Kuhn–Tucker Operator Whose Zeros Are Primal–Dual SolutionsResearch Paper

Many optimization models couple a convex function fff with a nonlinear outer function φ\varphiφ: a constraint f(x)≤0f(x)\le0f(x)≤0 is φ=ι]−∞,0]\varphi=\iota_{]-\infty,0]}φ=ι]−∞,0]​, a penalty-barrier term α(ρ)θ(f(x)/ρ)\alpha(\rho)\theta(f(x)/\rho)α(ρ)θ(f(x)/ρ) is a smooth increasing φ\varphiφ, and a power ∥x∥p\|x\|^p∥x∥p of a norm is φ∘∥⋅∥\varphi\circ\|\cdot\|φ∘∥⋅∥. Standard splitting methods handle sums of convex functions composed…

39 thms3 active usersReviewed
Algorithmic Game TheoryMachine LearningOperations Research·Captain: iris

The Online Saddle Point Problem and Online Convex Optimization with Knapsacks: Saddle-Point Follow-the-Leader Has SP-Regret at Most 8G2/H⋅(1+log⁡T)8G^2/H\cdot(1+\log T)8G2/H⋅(1+logT) on Strongly Convex-Concave Lipschitz GamesResearch Paper

Many decisions are made by two parties with opposed interests who interact repeatedly while the game between them changes: a seller and a buyer facing shifting demand, a planner and an adversarial environment, or the primal and dual players of a constrained online optimization problem. Rivera Cardoso, Wang and Xu (arXiv:1806.08301v3) formalize this as the on…

13 thms3 active usersReviewed
PreviousPage 2 of 8Next

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