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 LearningOperations ResearchOptimization·Captain: mikedeng1

Logarithmic Regret Algorithms for Online Convex Optimization 2: Logarithmic Regret of the Online Newton StepResearch Paper

Online convex optimization models repeated decision making against an unknown, possibly adversarial environment: in each round t=1,…,Tt=1,\dots,Tt=1,…,T a player picks a point xtx_txt​ of a convex set P⊆Rn\mathcal P\subseteq\mathbb R^nP⊆Rn, and only then learns a convex cost function ftf_tft​ and pays ft(xt)f_t(x_t)ft​(xt​). Performance is measured by regret, the excess of the total cost over that of…

16 thms6 active users
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Convex Optimization VI: Self-Concordance and the Barrier MethodTextbook

Why do interior-point methods solve convex programs in O(mlog⁡(1/ε))O(\sqrt{m}\log(1/\varepsilon))O(m​log(1/ε)) Newton steps? Nesterov and Nemirovskii's answer is self-concordance: a convex function whose third derivative is controlled by its second, ∣φ′′′(t)∣≤2 φ′′(t)3/2|\varphi'''(t)| \le 2\,\varphi''(t)^{3/2}∣φ′′′(t)∣≤2φ′′(t)3/2 along every line, admits a Newton analysis with absolute constants and no condition number —…

20 thms6 active users
🏆Completed
Algorithmic Game TheoryMachine LearningOptimization·Captain: iris

Solving Optimization Problems with Blackwell Approachability: CBA+ Has θ-Weighted Average Regret at Most 2κL(θ_T/ω_T)√(Σω_t²)/Σθ_t Whenever θ_{t+1}/θ_t ≥ ω_{t+1}/ω_tResearch Paper

Large convex–concave saddle-point problems min⁡x∈Xmax⁡y∈YF(x,y)\min_{x\in\mathcal X}\max_{y\in\mathcal Y}F(x,y)minx∈X​maxy∈Y​F(x,y) arise in matrix games, extensive-form games, distributionally robust optimization and many convex programs written in min–max form. A standard way to solve them is the repeated game framework: two regret minimizers, one per player, play against each other, and the…

24 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: iris

An Augmented Lagrangian Approach to Conically Constrained Nonmonotone Variational Inequality Problems: ALAVI Iterates Are Bounded, Cluster Points Solve (VIS), and Minty Cluster Points Are LimitsResearch Paper

Variational inequalities describe equilibria: Nash equilibria of convex games, saddle points of convex–concave problems, traffic equilibria and the KKT conditions of optimization problems are all solutions of a variational inequality. When the operator is monotone, a large body of first-order methods (extragradient, forward–backward–forward, the Golden…

28 thms5 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: Shuze Chen

Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning: Exact convex reformulation of worst-case riskResearch Paper

A nominal probability distribution describes the uncertainty available to a decision maker, but it need not equal the distribution that will generate future observations. Wasserstein distributionally robust optimization evaluates a loss against every probability law within a prescribed transport distance of the nominal law. The resulting worst-case risk is…

18 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Intersection Disjunctions for Reverse Convex Sets: The Basis Cone Outside the Recession-Cone Inner Approximation of the Convex Set Is a Union of |N2| + 1 Disjunctive TermsResearch Paper

A reverse convex set is the part of a polyhedron that lies outside an open convex set: P∖CP\setminus CP∖C, where P={x∈R+n:Ax=b}P=\{x\in\mathbb{R}^n_+ : Ax=b\}P={x∈R+n​:Ax=b} and C⊆RnC\subseteq\mathbb{R}^nC⊆Rn is open and convex. Such sets arise whenever a model forbids a convex region: integrality (a lattice-free convex set contains no feasible point in its interior), bilevel programs, where the…

9 thms5 active usersReviewed
🏆Completed
OptimizationProbability·Captain: mikedeng1

Proximal Gradient Methods with Adaptive Subspace Sampling: Random Subspace Proximal Gradient Descent Converges Linearly in ExpectationResearch Paper

Large-scale composite problems min⁡xf(x)+g(x)\min_x f(x)+g(x)minx​f(x)+g(x), with a smooth loss fff and a nonsmooth regularizer or constraint ggg, are routinely solved by proximal gradient methods. When the dimension is large, computing the full gradient at every step is expensive, and randomized coordinate descent updates only a few coordinates at a time. Classical proximal coordinate…

11 thms5 active usersReviewed
🏆Completed
Control TheoryLinear algebraOptimization·Captain: mikedeng1

Quadratic Matrix Inequalities with Applications to Data-Based Control III: Petersen's Lemma Recovered from the Matrix S-LemmasResearch Paper

Robust control repeatedly meets linear matrix inequalities that must hold for every value of an unknown, norm-bounded matrix. A typical instance is

12 thms5 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Linear Convergence of First Order Methods for Non-Strongly Convex Optimization IV: Projected Gradient on a Quasi-Strongly Convex f Has dist²(x^k, X*) ≤ ((1 − μ)/(1 + μ))^k dist²(x^0, X*)Research Paper

The projected gradient method is the basic algorithm for minimising a smooth convex function over a closed convex set. For an objective with an LfL_fLf​-Lipschitz gradient it converges at the sublinear rate f(xk)−f∗≤Lf∥x0−x∗∥2/(2k)f(x^k)-f^*\le L_f\|x^0-x^*\|^2/(2k)f(xk)−f∗≤Lf​∥x0−x∗∥2/(2k), and the classical way to obtain a linear (geometric) rate is to assume strong convexity. Many objectives that arise in…

13 thms5 active users
🏆Completed
Algorithmic Game TheoryDynamical Systems·Captain: mikedeng1

Learning in Games via Reinforcement and Regularization 2: Under Regularized Reinforcement Learning, Every Strict Nash Equilibrium Is Asymptotically StableResearch Paper

In a repeated game, players who do not know the payoff structure can still learn by reinforcement: each player keeps a running score for every action, the cumulative payoff that action would have earned, and plays a mixed strategy that favours actions with high scores. Turning scores into mixed strategies through a regularized best response (maximize score…

12 thms5 active usersReviewed
🏆Completed
Algorithmic Game TheoryDynamical Systems·Captain: mikedeng1

Learning in Games via Reinforcement and Regularization 3: In 2-Player Zero-Sum Games with an Interior Equilibrium, Time-Averaged Play Converges to the Nash SetResearch Paper

Learning dynamics in games describe how players who repeatedly interact adjust their strategies from observed payoffs. A central question is whether such dynamics lead to Nash equilibrium. For the replicator dynamics, the canonical model of evolutionary game theory, the answer is negative in general: in Matching Pennies and in generic zero-sum games with a…

10 thms5 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

On the Convergence of Decentralized Gradient Descent I: Under (Restricted) Strong Convexity Every Agent Satisfies ‖x₍ᵢ₎(k) − x*(k)‖ ≤ c₃ᵏ‖x*(0)‖ + c₄/√(1 − c₃²) + αD/(1 − β)Research Paper

In decentralized optimization a group of agents minimizes a sum of functions without a central coordinator: agent iii knows only its own function fif_ifi​ and can exchange vectors only with its neighbours in a communication network. The setting covers sensor networks, multi-robot coordination and data-parallel learning in which the data cannot be pooled. The basic…

14 thms5 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Relatively Smooth Convex Optimization by First-Order Methods, and Applications I: The Primal Gradient Scheme Attains f(x^k) − f(x) ≤ μD_h(x,x⁰)/((1+μ/(L−μ))^k − 1) ≤ (L−μ)D_h(x,x⁰)/kResearch Paper

Gradient methods for convex minimisation are usually analysed under two assumptions on the objective fff: its gradient is Lipschitz continuous (LLL-smoothness), and, for linear rates, fff is strongly convex. Many objectives met in practice satisfy neither on their whole domain. The D-optimal design objective −ln⁡det⁡(∑ixiaiai⊤)-\ln\det(\sum_i x_i a_i a_i^\top)−lndet(∑i​xi​ai​ai⊤​), the univariate…

10 thms5 active users
🏆Completed
Machine LearningOptimizationProbability·Captain: mikedeng1

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition VI: Randomized Proximal Coordinate Descent Has Expected Rate (1 − μ/(dL))^kResearch Paper

Many problems in machine learning and statistics have the composite form min⁡xF(x)=f(x)+g(x)\min_x F(x)=f(x)+g(x)minx​F(x)=f(x)+g(x), where fff is a smooth loss and ggg is a non-smooth regularizer such as λ∥x∥1\lambda\|x\|_1λ∥x∥1​. When ggg is separable, g(x)=∑igi(xi)g(x)=\sum_i g_i(x_i)g(x)=∑i​gi​(xi​), the method of choice at scale is often randomized proximal coordinate descent: at each step one coordinate is drawn at random and a…

13 thms5 active users
🏆Completed
OptimizationProbability·Captain: mikedeng1

Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming 3: The Randomized Stochastic AG Method Bounds E‖∇Ψ(x_R^md)‖² on Nonconvex Problems and Is Optimal on Convex OnesResearch Paper

In stochastic programming the objective Ψ(x)=Eξ[F(x,ξ)]\Psi(x)=\mathbb E_\xi[F(x,\xi)]Ψ(x)=Eξ​[F(x,ξ)] is an expectation that cannot be evaluated, and an algorithm sees only noisy gradients G(x,ξ)G(x,\xi)G(x,ξ) drawn from a stochastic first-order oracle. Stochastic gradient descent and its relatives are the standard methods. For convex Ψ\PsiΨ the optimal rate is known: Lan's accelerated stochastic…

21 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Proximal Algorithms I: A Point Minimizes f + g Exactly When It Is a Fixed Point of the Forward-Backward Operator x ↦ prox_λg(x − λ∇f(x))Research Paper

Many convex optimization problems combine a smooth loss with a term that is easy to handle through minimization but awkward to differentiate. A constraint can be represented by an indicator function that is zero on the feasible set and +∞+\infty+∞ outside it. A norm penalty can be finite yet nonsmooth. The proximal gradient method handles such objectives by…

11 thms5 active usersReviewed
🏆Completed
Linear algebraNumerical Analysis·Captain: mikedeng1

Low-rank Matrix Recovery via Iteratively Reweighted Least Squares Minimization 1: IRLS-M Converges to the Nuclear-Norm Minimizer Under the Strong Rank Null Space PropertyResearch Paper

Many data problems ask for a matrix of low rank from far fewer linear measurements than it has entries: matrix completion (recommender systems, where a few ratings of a large user–item table are observed), system identification, and quantum state tomography. Minimizing the rank under the measurement constraints is NP-hard in general. The standard convex…

19 thms5 active usersReviewed
🏆Completed
Linear algebraOptimization·Captain: mikedeng1

Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization 1: If δ_5r < 1/10, Nuclear Norm Minimization Recovers Every Matrix of Rank at Most r ExactlyResearch Paper

Many problems in system identification, collaborative filtering, low-dimensional embedding and model reduction ask for the simplest matrix consistent with a set of linear observations, where "simplest" means "of least rank". Given a linear map A:Rm×n→Rp\mathcal A:\mathbb R^{m\times n}\to\mathbb R^pA:Rm×n→Rp and a vector b∈Rpb\in\mathbb R^pb∈Rp, the affine rank minimization problem is

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

Semidefinite Programming 1: If the Primal or the Dual Semidefinite Program Is Strictly Feasible Then p* = d*, and If Both Are, Both Optimal Sets Are NonemptyResearch Paper

A semidefinite program minimizes a linear objective subject to a matrix being positive semidefinite. It includes linear programs and many matrix optimization problems, while allowing constraints on eigenvalues that ordinary coordinate inequalities cannot express. Vandenberghe and Boyd’s 1996 survey helped establish this form as a common language for…

16 thms5 active usersReviewed
🏆Completed
OptimizationProbability·Captain: mikedeng1

Primal-dual subgradient methods for convex problems 2: Stochastic Simple Averages Reach E[φ(x̄ₖ)] − φ* ≤ β̂ₖ₊₁(γd(x*) + L²/(2σγ))/(k+1)Research Paper

Many decision problems under uncertainty take the form of minimizing an expected cost φ(x)=Eξf(x,ξ)\varphi(x) = \mathbb E_\xi f(x, \xi)φ(x)=Eξ​f(x,ξ) over a convex feasible set, where ξ\xiξ is a random parameter whose distribution can be sampled but not integrated in closed form. Evaluating φ\varphiφ even approximately can cost exponentially many evaluations of fff in the dimension of ξ\xiξ,…

18 thms5 active users
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

METRIC: A Multi-Echelon Technique for Recoverable Item Control 1: The Marginal Conditions on the Convex Hull of Each Item's Decreasing Cost Function Determine a Unique Optimal AllocationResearch Paper

Service organizations keep repairable spare parts at a depot and at operating bases. Stock has a purchase or holding cost, while insufficient stock leaves backorders. Craig Sherbrooke's METRIC study describes how to evaluate such a system and distribute additional units among item types. Its fifth computational stage compares the reduction in expected…

22 thms5 active users
🏆Completed
Operations ResearchOptimizationStochastic Systems·Captain: mikedeng1

Loss Networks 1: The Primal Problem Has a Unique Optimum x_r = ν_r ∏_j (1 − B_j)^{A_jr}; the Conditions on B Are Solvable, Uniquely if rank A = J, and Biject with Dual OptimaResearch Paper

A loss network carries calls that require capacity on one or more links. A call is accepted only when every required link has enough free circuits; otherwise it is lost. This makes the traffic on different links dependent even when calls on different routes arrive independently. Network operators need to know where capacity constraints bind and how offered…

11 thms5 active usersReviewed
🏆Completed
Machine LearningOptimizationProbability·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity XV: SVRG with η = 1/(10β) and k = 20κ Contracts the Expected Optimality Gap by 0.9 per EpochTextbook

Many optimization problems in machine learning minimize an average of losses, one loss for each observation. A full gradient step examines every observation, while a stochastic gradient step examines one. The latter is cheaper per step, but its sampled gradient can remain noisy even near the optimum. Section 6.3 of Bubeck's monograph studies stochastic…

14 thms5 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity III: Projected Subgradient Descent with η = R/(L√t) Satisfies f(average) − f(x*) ≤ RL/√tTextbook

Many convex optimization problems in machine learning and statistics have objectives that are convex but not differentiable: hinge losses, ℓ1\ell_1ℓ1​ penalties, maxima of finitely many affine functions, and the dual functions of Lagrangian relaxations. Methods that rely on gradients do not apply to them directly, while cutting-plane methods such as the…

15 thms5 active users
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity II: For t ≥ 2n² log(R/r) the Ellipsoid Method Satisfies f(x_t) − min f ≤ (2BR/r)·exp(−t/(2n²))Textbook

The ellipsoid method is the cutting-plane algorithm that settled the polynomial-time solvability of linear programming and, more generally, of convex optimization over any set that comes with an efficient separation oracle. It was introduced for convex minimization by Shor and by Yudin and Nemirovski in the 1970s, and Khachiyan used it in 1979 to give the…

11 thms5 active usersReviewed
PreviousPage 2 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