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
Linear algebraNumerical AnalysisOperations Research+1·Captain: mikedeng1

Robust Solutions to Least-Squares Problems with Uncertain Data III: Structured Robust Least Squares Is Solved Exactly by a Semidefinite ProgramResearch Paper

Least squares fits a model Ax≈bAx \approx bAx≈b as if the data (A,b)(A, b)(A,b) were exact. In practice they are measured, rounded or estimated, and the least-squares solution can be very sensitive to such errors. El Ghaoui and Lebret (SIAM J. Matrix Anal. Appl. 18(4), 1997) proposed to treat the errors as deterministic, unknown but bounded, and to choose xxx minimizing the wor…

14 thms4 active users
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

The Generalized Quasi-Variational Inequality Problem I: Existence for the Generalized Implicit Complementarity Problem under Strong CopositivityResearch Paper

Variational inequalities and complementarity problems are the standard formulation of equilibrium in operations research and mathematical economics: traffic equilibria, spatial price equilibria, Nash equilibria of convex games, and the optimality conditions of constrained optimization all take this form. Many applications have two features that the…

17 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

On Polyhedral Approximations of the Second-Order Cone I: A Compact Polyhedral Approximation of the Lorentz ConeResearch Paper

Conic quadratic programs (second-order cone programs) minimize a linear objective subject to linear constraints and constraints of the form ∥Aℓx−bℓ∥2≤cℓTx−dℓ\|A_\ell x-b_\ell\|_2\le c_\ell^Tx-d_\ell∥Aℓ​x−bℓ​∥2​≤cℓT​x−dℓ​. They model robust linear programs with ellipsoidal uncertainty, truss topology design, contact problems with Coulomb friction, and convex quadratically constrained quadratic…

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

On Minimizing a Convex Function Subject to Linear Inequalities I: Beale's Simplex Method for a Convex Quadratic Function TerminatesResearch Paper

Quadratic programming, the minimization of a convex quadratic function subject to linear constraints, is the simplest nonlinear extension of linear programming. It arises in least-squares estimation with sign constraints, in portfolio selection, and as the subproblem solved at each iteration of Newton-type methods for general smooth convex programs. E. M.…

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

An Exact Duality Theory for Semidefinite Programming and Its Complexity Implications: The Extended Lagrange–Slater Dual Has Zero Duality Gap and Attains Its OptimumResearch Paper

Semidefinite programming (SDP) optimizes a linear function over the intersection of the cone of positive semidefinite matrices with an affine subspace. It contains linear programming as the diagonal case and is the computational core of relaxations in combinatorial optimization, control theory and polynomial optimization. Its standard duality theory,…

14 thms4 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization·Captain: mikedeng1

First-Order and Stochastic Optimization Methods for Machine Learning VII: Gradient Sliding for Composite OptimizationTextbook

Composite convex programs — objectives split into a smooth piece and a nonsmooth piece — are ubiquitous in data analysis: LASSO-type inverse problems, regularized empirical-risk minimization, and total-variation-type image reconstruction all minimize f(x)+h(x)+χ(x)f(x)+h(x)+\chi(x)f(x)+h(x)+χ(x) over a convex set, where fff is smooth (a data-fidelity term, often expensive to…

5 thms4 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization·Captain: mikedeng1

First-Order and Stochastic Optimization Methods for Machine Learning III: Stochastic Mirror DescentTextbook

Machine learning's canonical training objective — minimize an expected or empirical risk over a data distribution — is almost never observed exactly: at each step an algorithm sees only a noisy gradient sample (a minibatch gradient, a single-example gradient, a simulation draw). Stochastic mirror descent (Nemirovski, Juditsky, Lan & Shapiro 2009) is the…

5 thms4 active users
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Introduction to Online Convex Optimization XIII: Blackwell's Approachability Theorem and Online Convex OptimizationTextbook

Von Neumann's minimax theorem (Chapter VIII) settles two-player zero-sum games with scalar payoffs. In 1956, Blackwell asked the natural generalization: what can a player guarantee in a repeated game with vector-valued payoffs, where "winning" means driving the average payoff into a target set rather than above a target value? For decades the resulting…

12 thms4 active users
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Introduction to Online Convex Optimization XII: The Online Boosting MethodTextbook

Chapter XI boosted a weak learner into a strong one for a single offline fit to a fixed sample. Chapter 12 asks the analogous question online: when the pool of experts is too large to run Hedge over directly (the contextual-learning setting, where "experts" are policies mapping contexts to actions and their number is exponential), can black-box access to a…

12 thms4 active users
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Introduction to Online Convex Optimization IX: From Online Convex Optimization to PAC LearningTextbook

Every algorithm in Chapters I–VIII minimizes regret, an online, adversarial performance measure with no reference to a data-generating distribution. Chapter 9 asks what regret minimization buys in the classical statistical learning setting, where examples are drawn i.i.d. from a fixed distribution and the goal is a hypothesis that generalizes well to unseen…

7 thms4 active users
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Introduction to Online Convex Optimization VII: The Online Conditional Gradient AlgorithmTextbook

Every algorithm through Chapter VI updates its iterate by a Euclidean projection onto the decision set KKK. For many decision sets that arise in practice — bounded-nuclear-norm matrices (matrix completion / recommendation systems), the flow polytope (network routing), the Birkhoff–von Neumann polytope (ranking/permutations), matroid polytopes — a projection…

10 thms4 active users
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Introduction to Online Convex Optimization IV: The Online Newton Step AlgorithmTextbook

Online convex optimization measures a decision maker against the best fixed decision in hindsight, and the standard guarantee — achieved, for instance, by online gradient descent — is regret growing like O(T)O(\sqrt T)O(T​) over TTT rounds. This rate is unimprovable for general convex losses: an adversary can always force Ω(T)\Omega(\sqrt T)Ω(T​) regret against any algorithm.…

13 thms4 active users
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Introduction to Online Convex Optimization X: Efficient Adaptive Regret for Online Convex OptimizationTextbook

Every regret guarantee through Chapter IX compares the algorithm to the single best fixed decision in hindsight. That comparison is meaningless when the environment itself changes: a commuter's best route differs on weekdays versus weekends, an investor's best portfolio differs in a bull versus a bear market. A standard sublinear-regret algorithm, competing…

9 thms4 active users
🏆Completed
Machine LearningProbabilityRandom Matrix Theory+1·Captain: mikedeng1

High-Dimensional Probability III: Grothendieck's InequalityTextbook

Many hard combinatorial optimization problems — finding the maximum cut of a graph, deciding the ground state of an Ising spin system, bounding the correlation of a physical system — can be written as maximizing a bilinear form over sign vectors xi∈{−1,1}x_i \in \{-1, 1\}xi​∈{−1,1}. Exhaustive search over 2n2^n2n sign patterns is intractable, so practitioners relax the problem:…

13 thms4 active users
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Introduction to Online Convex Optimization III: Online Gradient DescentTextbook

Online convex optimization (OCO) models a repeated decision process: at each round a learner picks a point in a convex set, an adversary (or the world) reveals a convex cost function, the learner pays that cost at its own point, and the process repeats. No statistical assumption on the sequence of costs is made. This model, introduced by Zinkevich…

8 thms4 active users
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Introduction to Online Convex Optimization I: Learning from Expert Advice and the Hedge AlgorithmTextbook

Consider a decision maker who must choose, at each of TTT rounds, between two actions on the advice of NNN "experts," none of which is known in advance to be reliable. This is the prediction-from-expert-advice problem, introduced by Littlestone and Warmuth [Littlestone & Warmuth, The Weighted Majority Algorithm, FOCS 1989/Inf. Comput. 1994] and generalized to…

9 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Introduction to Stochastic Programming VI: Jensen and Edmundson-Madansky BoundsTextbook

Two-stage stochastic programs with recourse require evaluating Q(x)=Eξ[Q(x,ξ)]Q(x) = \mathbb E_\xi[Q(x,\xi)]Q(x)=Eξ​[Q(x,ξ)], the expected value of a recourse function, at every candidate first-stage decision xxx. When ξ\xiξ is high-dimensional or continuously distributed, this expectation is a multivariate integral of a piecewise-linear, generally nondifferentiable integrand, and classical…

8 thms4 active users
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Convex Optimization V: Newton's MethodTextbook

The classical convergence theory of smooth convex minimization. For a function that is mmm-strongly convex and MMM-smooth (mI⪯∇2f(x)⪯MImI \preceq \nabla^2 f(x) \preceq MImI⪯∇2f(x)⪯MI), gradient descent converges linearly, while Newton's method exhibits its famous two phases: a damped phase in which every backtracking step decreases the objective by a fixed amount γ\gammaγ, and a quadrati…

12 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Convex Optimization II: KKT ConditionsTextbook

The Karush–Kuhn–Tucker conditions are the central result of convex optimization: for a convex differentiable problem satisfying Slater's condition, a point is optimal exactly when primal feasibility, dual feasibility, complementary slackness and Lagrangian stationarity hold. This mission formalizes Chapters 4–5 of Boyd & Vandenberghe end to end — the…

15 thms4 active usersReviewed
Linear algebraNumerical Analysis·Captain: mikedeng1

A Fast and Accurate Algorithm for the p→qp \to qp→q Norm of Sparse Non-Negative MatricesResearch Paper

The p→qp \to qp→q norm of a matrix generalizes the largest singular value (p=q=2p = q = 2p=q=2) to ℓp\ell_pℓp​ geometries. For general matrices it is efficiently computable only when p=1p = 1p=1, q=∞q = \inftyq=∞, or p=q∈{1,2,∞}p = q \in \{1, 2, \infty\}p=q∈{1,2,∞}, and in the non-hypercontractive regime p≥q≥1p \ge q \ge 1p≥q≥1 it is NP-hard to approximate within any constant factor for 1<q≤p<21 < q \le p < 21<q≤p<2 or …

22 thms3 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
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…

37 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
🏆Completed
Algorithmic Game TheoryOptimization·Captain: mikedeng1

Robustly Obedient Data Driven Persuasion under State-dependent Sender PayoffsResearch Paper

In Bayesian persuasion (Kamenica and Gentzkow, 2011, https://doi.org/10.1257/aer.101.6.2590), a Sender commits to a signaling policy that maps the state of the world to recommendations, and a Receiver who knows the prior updates on the recommendation and acts. The standard analysis assumes the Sender knows the prior. In many applications the Sender instead…

8 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
PreviousPage 9 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