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
Machine LearningOptimization·Captain: mikedeng1

Naive Feature Selection: A Nearly Tight Convex Relaxation for Sparse Naive Bayes: The Sparse Multinomial Relaxation Bound Is Tight up to Four Features, ψ(k − 4) ≤ ϕ(k) ≤ ψ(k) ≤ ϕ(k + 4)Research Paper

Naive Bayes is one of the oldest and cheapest classifiers for text and count data: given word counts for documents in two classes, it fits one multinomial distribution per class by maximum likelihood and classifies by the likelihood ratio. Its cost is a single pass over the data. In high-dimensional applications (text, genomics) one also wants the…

13 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization: The Framework Returns an ε-Near-Stationary Point Within an Explicit Number of IterationsResearch Paper

Many problems in robust optimization, adversarial learning, distributionally robust learning and min-max games have the max-structured form

10 thms2 active usersReviewed
Algebraic GeometryOperations ResearchOptimization·Captain: mikedeng1

On Computing the Nonlinearity Interval in Parametric Semidefinite Optimization: The Set of Transition Points of the Optimal Partition Is FiniteResearch Paper

Sensitivity analysis asks how the solution of an optimization problem changes when its data move. For linear optimization the answer has been known since the 1990s: as the objective is perturbed along a fixed direction, the optimal partition (which variables can be positive at an optimum and which slacks can) stays constant on open intervals and changes…

11 thms2 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Approximate Parametric Computation of Minimum-Cost Flows with Convex Costs: Linear Splines of the Marginal Costs with Bounded Step Sizes Give an (α, β)-Approximate Minimum-Cost Flow FunctionResearch Paper

Flow networks model the movement of material, traffic, electricity, or gas through connected systems. In many such models, the required net flow at each vertex varies with a parameter, so the object of interest is a whole family of optimal flows rather than one solution. When edge costs are nonlinear, solving a new optimization problem for every parameter…

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

A Study of Convex Convex-Composite Functions via Infimal Convolution with Applications: Under a Slater-Type Condition the Conjugate of g∘F Is an Attained Minimum over the Negative Polar ConeResearch Paper

Convex optimization often minimizes a function obtained by applying one convex function to the output of another map. The inner map may be vector valued, and its components need not be linear. To understand sensitivity, optimality conditions, and dual formulations for such a convex composite, one needs its Fenchel conjugate. Standard formulas for an affine…

9 thms2 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: mikedeng1

Aggregating Distributed Energy Resources: Efficiency and Market Power I: A Profit-Seeking Aggregator with Two-Part Pricing Attains the Benchmark Welfare, Dispatch and PricesResearch Paper

Distributed energy resources (DERs) — rooftop solar, home batteries, electric vehicles — turn electricity consumers into prosumers who can both buy and sell power. Their individual capacities are far too small to bid in a wholesale electricity market directly, so regulators have opened these markets to DER aggregators, intermediaries that pool many small…

9 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOptimization·Captain: mikedeng1

Infinite-Dimensional Fisher Markets and Tractable Fair Division 2: For Linear Valuations on [0,1] the Feasible Utility Set Is a Projection of Linear and Parabolic ConstraintsResearch Paper

A Fisher market divides a supply of goods among buyers with different values and budgets. In many fair division models, the goods form a continuum: pieces of time, land, or a divisible resource can be allocated in arbitrarily small amounts. A direct description of all possible buyer utilities then appears to require one allocation function for every buyer.…

9 thms2 active usersReviewed
Algorithmic Game TheoryEconomics·Captain: mikedeng1

Infinite-Dimensional Fisher Markets and Tractable Fair Division 3: The Quasilinear Eisenberg–Gale Programs Attain Their Optima and Characterize Quasilinear EquilibriaResearch Paper

A Fisher market allocates a common supply of items among buyers with separate budgets. When the items form a continuum, such as positions in a measurable interval, a buyer's valuation and the market price are functions rather than finite lists. This is a useful model for divisible resources and for settings in which an allocation can be described as a…

10 thms2 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Real-Time Spatial–Intertemporal Pricing and Relocation in a Ride-Hailing Network: Near-Optimal Policies and the Value of Dynamic Pricing 1: Arc Balancing Control Has Loss O(log(1+n)^{3/2}/n^{2/3})Research Paper

A ride-hailing firm chooses prices while drivers move through a city. A trip from one region uses a driver immediately and returns that driver at another region only after a travel delay. Prices affect which trips are requested, but the actual requests fluctuate. A plan that ignores these fluctuations can run out of available drivers at a busy origin even…

7 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryProbability·Captain: mikedeng1

Persuading Risk-Conscious Agents: A Geometric Approach I: The Sender's Persuasion Problem Is Solved by a Convex Program over Conv(P_a ∪ {0})Research Paper

Bayesian persuasion studies a sender who observes a state of the world and commits in advance to a randomized disclosure rule, in order to influence the action of a receiver who updates her belief by Bayes' rule. Since Kamenica and Gentzkow (2011) the model has been applied to platform design, recommendation systems, queue information and rating systems.…

7 thms2 active usersReviewed
Dynamic ProgrammingOperations ResearchOptimization+1·Captain: mikedeng1

Convergence Analysis of Sampling-Based Decomposition Methods for Risk-Averse Multistage Stochastic Convex Programs 1: Almost Sure Convergence of the Risk-Averse Sampling-Based Decomposition AlgorithmResearch Paper

Multistage stochastic programs model sequential decisions under uncertainty: hydro-thermal scheduling, portfolio management and capacity planning are standard examples. Their dynamic programming equations involve recourse functions (cost-to-go functions) of the decision history, which cannot be computed exactly. Stochastic Dual Dynamic Programming (SDDP),…

18 thms2 active usersReviewed
Control TheoryLinear algebraOptimization·Captain: mikedeng1

Quadratic Matrix Inequalities with Applications to Data-Based Control V: A Reduced LMI in P Alone and an Explicit Data-Based Stabilizing GainResearch Paper

Data-driven control asks for a controller computed directly from measured trajectories of an unknown system, without first identifying a model. When the measurements are corrupted by noise, many systems explain the same data, and a controller is acceptable only if it works for all of them. Van Waarde, Camlibel, Eising and Trentelman (arXiv:2203.12959) model…

12 thms2 active usersReviewed
🏆Completed
Graph TheoryOptimization·Captain: mikedeng1

Shortest Paths in Graphs of Convex Sets I: The Perspective Mixed-Integer Convex Program (5.5) Has the Same Optimal Value as the Shortest-Path Problem in a Graph of Convex SetsResearch Paper

Many planning problems combine a discrete choice with a continuous one. A robot moving through a cluttered room chooses which free regions to traverse and where exactly to cross between them; a vehicle chooses a sequence of operating modes and a trajectory within each mode. Marcucci, Umenberger, Parrilo and Tedrake (arXiv:2101.11565, SIAM J. Optim. 2024, doi…

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

On the tightness of SDP relaxations of QCQPs 5: The Multiplicity Bound k ≥ aff dim{b(γ) : γ ∈ F} + 1 Cannot Be Lowered by OneResearch Paper

A quadratically constrained quadratic program (QCQP) minimizes a quadratic function subject to quadratic inequality and equality constraints. QCQPs contain max-cut, binary programming, the trust-region subproblem and many problems from signal processing and control, and are NP-hard in general. The standard convex approach is the Shor semidefinite relaxation,…

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

On the tightness of SDP relaxations of QCQPs 4: Quadratic Eigenvalue Multiplicity k ≥ m + 1 Gives conv(D ∩ H) = D_SDP ∩ H and Opt = Opt_SDPResearch Paper

A quadratically constrained quadratic program (QCQP) minimizes a quadratic function subject to quadratic inequality and equality constraints. QCQPs model trust-region subproblems, max-cut and other binary programs, phase retrieval, and many problems in signal processing and control; in general they are NP-hard. The standard tool for bounding and solving…

10 thms2 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Bridging Bayesian and Minimax Mean Square Error Estimation via Wasserstein Distributionally Robust Optimization 2: The Fully Adaptive Frank-Wolfe Algorithm Converges LinearlyResearch Paper

The Frank-Wolfe algorithm (also called the conditional gradient method) minimizes a smooth convex function over a compact convex set using only a linear minimization oracle in place of a projection. Each step solves a linearized problem over the feasible set and moves toward its solution. This makes it the method of choice when projections are expensive but…

11 thms2 active usersReviewed
🏆Completed
Dynamical SystemsOptimization·Captain: mikedeng1

Understanding the Acceleration Phenomenon via High-Resolution Differential Equations V: Along the High-Resolution ODE of NAG-C, inf ‖∇f(X(u))‖² ≤ (12 + 9sL)‖x₀ − x⋆‖²/(2√s(t³ − t₀³))Research Paper

Nesterov's accelerated gradient method for smooth convex functions, called NAG-C in the source paper, minimizes an LLL-smooth convex function fff with function values decreasing at the rate O(L/k2)O(L/k^2)O(L/k2). That rate is optimal among first-order methods (Nesterov, 1983). A line of work starting with Su, Boyd & Candès (2016) studies such methods through ordinary…

9 thms2 active usersReviewed
Operations ResearchProbability·Captain: mikedeng1

Arbitrage and Duality in Nondominated Discrete-Time Models I: Under NA(𝒫) the Superhedging Price Equals the Supremum of Expectations over Martingale Measures and Is AttainedResearch Paper

Classical arbitrage pricing fixes one probability measure PPP describing the market and asks for the cheapest way to dominate a payoff PPP-almost surely. When the model itself is uncertain, this choice is not available: a trader who only trusts a family P\mathcal PP of possible models wants a hedge that works under every one of them. Two literatures meet here. Rob…

21 thms2 active usersReviewed
Machine LearningOptimizationProbability·Captain: mikedeng1

Distributed Stochastic Gradient Tracking Methods I: With a Constant Stepsize, DSGT's Limiting Mean-Square Error Is at Most (Γ+1)ασ²/(Γμn) Plus a Network TermResearch Paper

Many learning and estimation problems are solved by a network of agents: each agent holds part of the data, can talk only to its neighbours, and wants to compute the minimizer of the average of all agents' objectives. Examples are sensor networks, multi-robot systems, and data-parallel training without a central server (Nedić and Ozdaglar 2009; Lian et al.…

18 thms2 active usersReviewed
Control TheoryGraph TheoryOptimization·Captain: mikedeng1

Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs 2: Push-DIGing Converges R-Linearly over Time-Varying Directed Graphs for Every Step Size Below 1.5(1−δ)²/(μ̄J₂)Research Paper

In distributed optimization, nnn agents cooperatively minimize the average f(x)=1n∑i=1nfi(x)f(x)=\frac1n\sum_{i=1}^n f_i(x)f(x)=n1​∑i=1n​fi​(x) of private cost functions fi:Rp→Rf_i:\mathbb R^p\to\mathbb Rfi​:Rp→R, exchanging information only with their current neighbours in a communication network. The model covers sensor networks, multi-robot coordination and machine learning with data split across machines,…

15 thms2 active usersReviewed
Optimization·Captain: mikedeng1

On the Convergence of Decentralized Gradient Descent II: For Convex Smooth fᵢ the Mean Iterate Has Objective Error r̄(k) ≤ 4C²/(αk) Until r̄ Falls to C√2·αL_hD/(1 − β)Research Paper

In decentralized optimization, nnn agents connected by a communication network jointly minimize a sum of private functions without a central coordinator: each agent sees only its own fif_ifi​ and talks only to its neighbours. Applications include sensor networks, distributed estimation, multi-agent control and learning over data spread across machines. The…

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

Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints I: A Feasible LMI and a ρ-Hard IQC Certify the Linear Rate ‖ξₖ − ξ⋆‖ ≤ √cond(P) ρᵏ ‖ξ₀ − ξ⋆‖Research Paper

First-order methods such as the gradient method, Nesterov's accelerated method and the Heavy-ball method are usually analysed one at a time, each with its own hand-built potential function. Lessard, Recht and Packard (SIAM J. Optim. 26(1), 2016; read here in arXiv:1408.3595v7) observed that such a method is a linear dynamical system in feedback with the…

7 thms2 active usersReviewed
Complexity TheoryMachine LearningOptimization·Captain: mikedeng1

Tight Complexity Bounds for Optimizing Composite Objectives II: Any Deterministic Algorithm with Gradient and Prox Oracle Access Needs Ω(m√(γB²/ε)) Queries on Sums of m Convex γ-Smooth FunctionsResearch Paper

Many problems in machine learning and statistics minimize an average of mmm convex losses, one per data point or per block of data. Incremental methods such as SAG, SVRG, SAGA, SDCA, Finito and Katyusha exploit this finite-sum structure: each step touches one component fif_ifi​ instead of the whole average, and for smooth components the best of them reach accuracy …

12 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Distributionally Robust Convex Optimization I: Under the Nesting Condition, a Worst-Case Expectation Constraint over a Standardized Ambiguity Set Is Equivalent to a Finite Conic SystemResearch Paper

A constraint E[v(x,z~)]≤w\mathbb E[v(x,\tilde z)] \le wE[v(x,z~)]≤w on a decision xxx requires the distribution of the random vector z~\tilde zz~. In practice that distribution is known only partially: its support, a few moments, or the probability mass of some regions estimated from data. Distributionally robust optimization asks that the constraint hold for every distribution…

7 thms2 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

A Modern Introduction to Online Learning XII: Coordinate-Wise Krichevsky–Trofimov Betting Has Parameter-Free Regret ‖u‖₁L∞√(2T ln(1 + e‖u‖∞T/ε)) + dεL∞Textbook

In online convex optimization, a learner makes a prediction before seeing the next loss. A standard regret guarantee often depends on a learning rate chosen using the size of the comparator that will be assessed later. That comparator is unknown during play. Chapter 13 of Orabona's textbook uses coin betting to obtain a bound that adapts to every comparator…

7 thms2 active usersReviewed
PreviousPage 24 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