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
Machine LearningProbabilityRandom Matrix Theory+1·Captain: mikedeng1

The Power of Convex Relaxation: Near-Optimal Matrix Completion I: Exact Nuclear-Norm Recovery with Quadratic Dependence on the RankResearch Paper

Matrix completion asks to recover a low-rank matrix from a small random subset of its entries. It models collaborative filtering (a ratings matrix with most entries missing), sensor-network localization from partial distance matrices, and system identification. The natural estimator, the matrix of least rank that agrees with the observations, is NP-hard to…

14 thms2 active usersReviewed
Machine LearningOptimizationProbability+1·Captain: Shuze Chen

Bias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in ℓp\ell_pℓp​ GeometriesResearch Paper

Stochastic convex optimization (SCO) asks for an approximate minimizer of a convex function that can only be probed through noisy subgradients. Two features of modern instances are not captured by the textbook Euclidean, bounded-variance setting. First, the natural geometry is often an ℓp norm with p>2p>2p>2: the feasible region is an ℓp ball and the Lipschitz…

15 thms1 active userReviewed
OptimizationQuantum InformationTheoretical Computer Science·Captain: Shuze Chen

Convex optimization on moment polytopes: Hadamard mirror descent and efficient algorithms for quantum functionals and other tensor parametersResearch Paper

Strassen's asymptotic spectrum of tensors governs the asymptotic rank and subrank of tensors, and with them questions such as the exponent of matrix multiplication. The quantum functionals of Christandl, Vrana and Zuiddam (CVZ23) were the first explicit family of universal spectral points for complex tensors of arbitrary order. They are defined as maxima of…

20 thms1 active userReviewed
Computational ComplexityMachine Learning·Captain: iris

Universal Hardness From Masking ChannelsResearch Paper

Given a class C\mathcal CC of predictors (Boolean circuits of bounded size, models of a fixed architecture), why is a labeling fff hard to approximate by members of C\mathcal CC? The hardcore lemma of complexity theory answers this for Boolean labels and the 0-1 loss: if every c∈Cc\in\mathcal Cc∈C errs on a δ\deltaδ-fraction of inputs, then there is a measure μ\muμ of…

31 thms1 active userReviewed
Machine LearningOperations Research·Captain: mikedeng1

Minimax Alternating Regret for the Experts Problem and Online Convex OptimizationResearch Paper

Alternating regret measures an online learner using both its action before a loss is revealed and its next action, chosen after seeing that loss. This timing arises when two players update their strategies alternately: one response is evaluated against two successive states of the opponent. Researchers studying online learning and game dynamics therefore…

17 thms1 active userReviewed
Linear OptimizationOptimizationTheoretical Computer Science·Captain: iris

Accelerated Parallel Algorithms for Packing Linear ProgrammingResearch Paper

A packing linear program asks for max⁡x≥0, Ax≤1⟨1,x⟩\max_{x\ge0,\ Ax\le\mathbf 1}\langle\mathbf 1,x\ranglemaxx≥0, Ax≤1​⟨1,x⟩ with A∈R≥0m×nA\in\mathbb R^{m\times n}_{\ge0}A∈R≥0m×n​. Packing LPs model resource allocation, fractional matching and fractional knapsack, and they are subroutines in approximation algorithms for scheduling and combinatorial auctions. The standard goal is low accuracy: a feasible x^\hat xx^…

25 thms1 active userReviewed
Functional AnalysisMachine LearningOptimization·Captain: iris

When Do Gradients Suffice? A Characterization of First-Order Convex OptimizationResearch Paper

First-order methods (gradient descent, Mirror Descent, their stochastic and accelerated variants) are the default tools of large-scale convex optimization, and their guarantees are usually stated in a Euclidean or ℓp\ell_pℓp​ geometry. A basic question underlies all of them: in which normed spaces can a convex Lipschitz function on the unit ball be minimized to…

66 thms1 active userReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: iris

Universal Acceleration: New Approaches to Heavy Ball DiscretizationResearch Paper

Two accelerated methods sit at the centre of first-order convex optimization. Nesterov's accelerated gradient descent (Nesterov 1983) minimizes an LLL-smooth, μ\muμ-strongly convex function in O(L/μlog⁡(1/ε))O(\sqrt{L/\mu}\log(1/\varepsilon))O(L/μ​log(1/ε)) gradient queries. Monteiro–Svaiter acceleration (Monteiro–Svaiter 2013) accelerates proximal-type steps, and Carmon et al. 2020 used it…

25 thms1 active userReviewed
Bandit AlgorithmsMachine LearningOperations Research+1·Captain: iris

Optimal Learning for Structured Bandits: DUSA Has Asymptotic Regret at Most (1+ε)(C(P)+ε(1+Σₓ∆(x,P))) log T, Matching the Lower Bound C(P) as ε → 0, with O(log T) Exploration RoundsResearch Paper

In a multi-armed bandit a learner repeatedly pulls one of finitely many arms and observes a random reward, trying to earn as much as an omniscient learner who knows the best arm. In many operations problems the arms are not unrelated: in dynamic pricing the probability of no sale is monotone in the price, in assortment or dosage problems mean rewards vary…

20 thms1 active userReviewed
Operations ResearchOptimization·Captain: iris

Parametric Semidefinite Programming: Geometry of the Trajectory of Solutions: Under LICQ, Strict Feasibility and Continuous Data, Every Optimal Point Unique From the Left Is One of Six TypesResearch Paper

A semidefinite program (SDP) minimizes a linear function of a symmetric matrix under linear constraints and positive semidefiniteness. In parametric SDP the data depend on a parameter, often time. The motivating example of Bellon, Henrion, Kungurtsev and Mareček comes from power systems: semidefinite relaxations of alternating-current optimal power flow are…

39 thms1 active userReviewed
Operations ResearchOptimization·Captain: iris

Technical Note—Dual Approach for Two-Stage Robust Nonlinear Optimization: The Dualized Linear Reformulation Has the Same Feasible Decisions and Optimal ValueResearch Paper

In two-stage robust optimization a decision maker fixes a here-and-now decision xxx, an adversary then picks an uncertain parameter ζ\zetaζ from an uncertainty set U\mathcal UU, and finally a wait-and-see decision yyy is chosen with knowledge of ζ\zetaζ. When the objective and constraints are linear in yyy, a large toolbox is available: linear decision rules,…

14 thms1 active userReviewed
Operations ResearchOptimization·Captain: iris

An Optimal High-Order Tensor Method for Convex Optimization: Algorithm 2 Attains the Rate k−(3d+1)/2k^{-(3d+1)/2}k−(3d+1)/2 with an Explicit ConstantResearch Paper

Many problems in statistics, signal processing and operations research have the composite form min⁡xf(x)+h(x)\min_x f(x)+h(x)minx​f(x)+h(x): a smooth convex loss fff plus a convex, possibly nonsmooth term hhh that encodes a regularizer or a constraint. First-order methods use only ∇f\nabla f∇f; high-order (tensor) methods also use the derivatives ∇2f,…,∇df\nabla^2 f,\dots,\nabla^d f∇2f,…,∇df and minimize a…

17 thms1 active userReviewed
Linear algebraOptimization·Captain: iris

Necessary and Sufficient Conditions for Rank-One-Generated Cones: Two LMIs Are ROG iff a Nonzero Combination of M1,M2M_1, M_2M1​,M2​ Is PSD or M1=Sym(ac⊤)M_1 = \mathrm{Sym}(ac^\top)M1​=Sym(ac⊤), M2=Sym(bc⊤)M_2 = \mathrm{Sym}(bc^\top)M2​=Sym(bc⊤)Research Paper

A quadratically constrained quadratic program (QCQP) minimizes a quadratic function subject to quadratic constraints. Binary integer programs, max-cut, and many robust and polynomial optimization problems can be written this way. Any QCQP has a lifted form in which the vector variable xxx is replaced by the matrix X=xx⊤X = xx^\topX=xx⊤; dropping the rank constraint on XXX…

26 thms1 active userReviewed
Information TheoryMachine LearningOptimization·Captain: mikedeng1

Quadratic Memory Is Necessary for Optimal Query Complexity in Convex Optimization: Center of Mass Is Pareto Optimal: under d^(2−δ) bits of memory, first-order methods need Ω̃(d^(1+δ/3)) queriesResearch Paper

Minimizing a convex Lipschitz function over the unit ball of Rd\mathbb R^dRd to accuracy ϵ\epsilonϵ takes Θ(dlog⁡(1/ϵ))\Theta(d\log(1/\epsilon))Θ(dlog(1/ϵ)) first-order queries when ddd is small compared with 1/ϵ1/\epsilon1/ϵ, and cutting-plane methods such as the center-of-mass method attain this rate (Nemirovski–Yudin 1983). They do so by storing their whole cutting history, about …

18 thms1 active userReviewed
Operations ResearchOptimizationProbability·Captain: Shuze Chen

Robust Optimization XII: Finite-Horizon Robust Bellman RecursionTextbook

A routing decision can have a known immediate cost while its consequences depend on uncertain weather. A controller observes the current state, chooses an action, and then faces a random next state. A policy optimized for one estimated transition model may perform poorly when those estimates change. Chapter 13 of Ben-Tal, El Ghaoui and Nemirovski, Robust…

4 thms1 active userReviewed
Algorithmic Game TheoryEconomicsProbability·Captain: mikedeng1

Constrained Information Design: The Value of an Information Design Problem with Equality and Inequality Constraints Equals the Concave Hull of the Constraint-Modified Objective at the PriorResearch Paper

In information design (Bayesian persuasion), a designer commits to a signal about an unknown state, and every signal induces a distribution over the receiver's posterior beliefs. Kamenica and Gentzkow (2011) showed that the distributions a signal can induce are exactly the Bayes-plausible ones, those whose mean posterior is the prior, and that the…

7 thms1 active userReviewed
Algorithmic Game TheoryEconomicsFunctional Analysis·Captain: mikedeng1

Infinite-Dimensional Fisher Markets and Tractable Fair Division 1: The Eisenberg–Gale Programs Attain Their Optima, One at a Pure Allocation, and Optimal Pairs Are Exactly the Market EquilibriaResearch Paper

A Fisher market divides a supply of goods among buyers with fixed budgets. In a finite market, each good is a separate coordinate. Fair division can instead involve a continuum of items, such as locations along an interval or points in a region, where a buyer's valuation varies measurably from point to point. Finite dimensional existence and duality…

9 thms1 active userReviewed
Operations ResearchProbability·Captain: mikedeng1

Arbitrage and Duality in Nondominated Discrete-Time Models II: Nondominated Optional Decomposition — a Supermartingale Under Every Martingale Measure Is V₀ + H•S − KResearch Paper

In a financial market with a single probability model, the Optional Decomposition Theorem describes the processes that can be dominated by trading. If a process VVV is a supermartingale under every equivalent martingale measure, then it can be written as an initial value plus a stochastic integral against the stock price, minus an increasing process that…

10 thms1 active userReviewed
Optimization·Captain: mikedeng1

DC Programming and DCA: Thirty Years of Developments: For f = g − h with g, h ∈ Γ₀(ℝⁿ), at x ∈ ri(dom g) ∩ ri(dom h) d-Stationarity of f Is Equivalent to Strong Criticality ∅ ≠ ∂h(x) ⊂ ∂g(x)Research Paper

DC programming is the minimization of a function f=g−hf = g - hf=g−h that is a difference of two convex functions. The class contains every C2C^2C2 function on a compact convex set and most nonconvex models of sparse learning, clustering, combinatorial relaxations and robust optimization, and its standard method, the DC Algorithm (DCA), replaces hhh by its affine minorant…

10 thms1 active userReviewed
Machine LearningOptimizationProbability·Captain: mikedeng1

Stochastic Model-Based Minimization of Weakly Convex Functions 4: Under Convexity, Stochastic Model-Based Minimization Reaches Expected Function Gap (½‖x₀−x*‖² + L²γ²)/(γ√(T+1))Research Paper

Many problems in statistical learning and signal processing take the form of minimizing an expectation f(x)=Eξ[F(x,ξ)]f(x)=\mathbb E_\xi[F(x,\xi)]f(x)=Eξ​[F(x,ξ)] plus a regularizer or constraint r(x)r(x)r(x), where the only access to fff is through samples ξ∼P\xi\sim Pξ∼P. The classical tool is the stochastic (proximal) subgradient method, which replaces fff at the current point by a random linear…

6 thms1 active userReviewed
Machine LearningOptimization·Captain: mikedeng1

Katyusha: The First Direct Acceleration of Stochastic Gradient Methods 1: Katyusha Converges at the Accelerated Linear Rate (1+√(σ/(3Lm)))^(−Sm) on Strongly Convex Finite SumsResearch Paper

A finite-sum optimization problem asks for one vector that performs well across many component objectives. In empirical risk minimization, each component can represent the loss from one data point. A full gradient uses every component, whereas a stochastic gradient uses one component and can be much cheaper per step. The latter carries sampling noise, so a…

6 thms1 active userReviewed
Discrete GeometryInformation TheoryProbability+1·Captain: mikedeng1

Universality in Polytope Phase Transitions and Message Passing Algorithms 3: Projected Cross-Polytopes Have Weak Neighborliness ρ∗(δ) for Sub-Gaussian Matrices with a Gaussian ComponentResearch Paper

Sparse recovery asks when a vector with few nonzero coordinates can be reconstructed from fewer linear measurements than unknowns. A related geometric question asks how many faces of a high-dimensional cross-polytope survive a random linear projection. The two questions meet at the same threshold: uniqueness of a minimum-one-norm solution corresponds to a…

16 thms1 active userReviewed
OptimizationProbability·Captain: mikedeng1

A Block Successive Upper-Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization 2: Randomized BSUM-M Converges to Primal-Dual Optimal Solutions Almost SurelyResearch Paper

Many large convex problems in signal processing, networking and statistics have a separable objective coupled by linear constraints: KKK blocks of variables, each with its own nonsmooth regularizer and its own feasible set, tied together by ∑kEkxk=q\sum_k E_kx_k=q∑k​Ek​xk​=q. The alternating direction method of multipliers (ADMM) is the standard tool for such problems when K=2K=2K=2.…

12 thms1 active userReviewed
Optimization·Captain: mikedeng1

A Block Successive Upper-Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization 1: Cyclic BSUM-M Converges to Primal-Dual Optimal SolutionsResearch Paper

Many problems in signal processing, machine learning and power systems have the form of a convex objective that is a sum of a smooth coupled term and nonsmooth block-separable terms, minimized subject to linear equality constraints that couple KKK blocks of variables: basis pursuit, demand response control in smart grids, and distributed estimation are the…

7 thms1 active userReviewed
Optimization·Captain: mikedeng1

From Error Bounds to the Complexity of First-Order Descent Methods for Convex Functions 2: For Convex Functions, KL Inequalities Give Error Bounds and Moderate Error Bounds Give KL InequalitiesResearch Paper

Complexity bounds for first-order methods (proximal gradient, forward–backward splitting, alternating minimization) rest on a quantitative description of how a function grows away from its set of minimizers. Two such descriptions are in common use. An error bound controls the distance to the minimizers by the function value; a Kurdyka–Łojasiewicz (KL)…

8 thms1 active userReviewed
PreviousPage 7 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