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

Stochastic Model-Based Minimization of Weakly Convex Functions 5: Under μ-Strong Convexity, Model-Based Minimization with β_t = μ(t+1)/2 Reaches Expected Function Gap O(1/(μT))Research Paper

Many problems in statistical learning and signal processing minimize 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), with access to fff only through samples ξ∼P\xi\sim Pξ∼P. The standard tool is the stochastic (proximal) subgradient method, which replaces fff at the current point by a random linear function. Two other methods use…

6 thms2 active usersReviewed
Machine LearningOptimization·Captain: mikedeng1

A Two-Timescale Stochastic Algorithm Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic: Explicit Error Bounds for TTSA with a Strongly Convex Outer ObjectiveResearch Paper

Bilevel optimization asks for an outer decision while an inner optimization problem responds to that decision. In hyperparameter selection, for example, the outer objective evaluates a model whose parameters are chosen by a training problem. A two-timescale algorithm updates both levels in one stochastic loop, so its outer step uses an inner solution that…

10 thms2 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness III: Adaptive Restarts Take at Most ⌈2C(q+2)/(αβ)⌉ Inner Steps and Converge Linearly on Sharp ProblemsResearch Paper

First order primal–dual algorithms are used when a linear program is too large for a direct factorization or when matrix operations are cheaper than solving a sequence of linear systems. Their basic guarantees often bound an averaged duality gap by a quantity proportional to 1/t1/t1/t after ttt steps. A restart discards the current inner iteration history and…

8 thms2 active usersReviewed
Information TheoryOptimizationQuantum Information·Captain: mikedeng1

Semidefinite Programming Hierarchies for Constrained Bilinear Optimization I: The Linearly Constrained de Finetti SDP Hierarchy Satisfies Q ≤ SDPₙ ≤ Q + ‖G‖∞·d_B²(d_B+1)·√((2 ln 2) log d_A / n)Research Paper

Many problems in quantum information theory ask for the maximum of a linear functional over pairs of quantum states, one on each of two systems, subject to linear constraints on each state. The best success probability of an approximate quantum error-correcting code of given size is of this form: the encoder and the decoder are quantum channels, their Choi…

17 thms2 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness II: Fixed-Frequency Restarts Shrink the Distance to the Solution Set by β per Restart on Sharp ProblemsResearch Paper

Linear programs at very large scale are increasingly solved by first-order primal-dual methods, which use only matrix-vector products instead of matrix factorizations. Such methods parallelize well and have a small memory footprint, but on their own they are slow to reach moderate or high accuracy. Applegate, Hinder, Lu and Lubin (arXiv:2105.12715, Math.…

8 thms2 active usersReviewed
🏆Completed
Linear OptimizationOptimization·Captain: mikedeng1

Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness I: The LP Saddle-Point Problem Is 1/(H(K)√(1+4R²))-Sharp on Every Ball W_R(0)Research Paper

First-order primal-dual methods (PDHG, extragradient, ADMM) are the engine of a new generation of large-scale linear programming solvers, such as PDLP, because they need only matrix–vector products with the constraint matrix. Their textbook guarantees for convex–concave saddle-point problems are sublinear, O(1/t)O(1/t)O(1/t) for the averaged iterate, while in practice…

7 thms2 active usersReviewed
Random Matrix TheoryStatistics·Captain: mikedeng1

Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization: Convex Relaxation Attains Near-Optimal Frobenius, Entrywise and Spectral Norm ErrorsResearch Paper

Matrix completion asks for a low-rank matrix from a small random subset of its entries. It models collaborative filtering (recommendation systems), sensor-network localisation, and structure from motion. In practice the revealed entries are corrupted by noise, and the most widely used estimator is nuclear-norm regularized least squares: fit the observed…

17 thms2 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization+1·Captain: mikedeng1

Incremental Proximal Methods for Large Scale Convex Optimization II: With a Randomized Order and a Diminishing Stepsize, Incremental Subgradient-Proximal Methods Converge Almost Surely to an OptimumResearch Paper

Many problems in statistical learning, signal processing and distributed optimization minimize a sum of a large number mmm of convex components over a convex set: a data-fit term per sample plus a regularizer or constraint per sample. When mmm is large, a method that processes one component per iteration is often far cheaper per step than one that evaluates the…

7 thms2 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions V: Relaxed PRS on Squared Distances Converges Linearly Under Bounded Linear RegularityResearch Paper

The convex feasibility problem asks for a point in the intersection of closed convex sets. It underlies signal and image reconstruction, phase retrieval relaxations, and the constraint handling inside larger optimization methods. The workhorse algorithms are projection methods: the method of alternating projections (MAP), going back to von Neumann for…

15 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationStatistics·Captain: mikedeng1

Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization 2: When √(λ0/λ2) > M the Perspective Relaxation Is at Least as Strong as the Big-M and PR(∞) RelaxationsResearch Paper

Best subset selection with ridge shrinkage asks for a coefficient vector β∈Rp\beta\in\mathbb R^pβ∈Rp that fits a response y∈Rny\in\mathbb R^ny∈Rn through a design matrix X∈Rn×pX\in\mathbb R^{n\times p}X∈Rn×p while using few nonzero coefficients:

7 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationStatistics·Captain: mikedeng1

Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization 1: The Perspective Interval Relaxation Is a Least Squares Problem with a Separable Reverse-Huber or ℓ1 PenaltyResearch Paper

Best subset selection with ridge shrinkage asks for a sparse linear model: given a design matrix X∈Rn×pX\in\mathbb R^{n\times p}X∈Rn×p and responses y∈Rny\in\mathbb R^ny∈Rn, minimize

6 thms2 active usersReviewed
Optimization·Captain: mikedeng1

Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods I: For the Proximal Gradient Method, the Error Bound Condition Is Equivalent to Quadratic GrowthResearch Paper

A large share of the optimization problems solved in statistics, signal processing and machine learning have the composite form

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

Fast Convergence of Inertial Dynamics and Algorithms with Asymptotic Vanishing Viscosity 2: For Strongly Convex Φ and α > 3, Φ(x(t)) − min Φ, ‖x(t) − x*‖² and ‖ẋ(t)‖² Are O(t^(−2α/3))Research Paper

Nesterov's accelerated gradient method minimizes a smooth convex function at the rate O(k−2)\mathcal O(k^{-2})O(k−2) in the number of iterations kkk, against O(k−1)\mathcal O(k^{-1})O(k−1) for plain gradient descent. Su, Boyd and Candès (arXiv:1503.01243) observed that, as the step size tends to zero, Nesterov's scheme becomes the second-order differential equation

9 thms2 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods II: Dual Strict Complementarity and Firm Convexity of the Components Give the Error Bound for f(Ax) + g(x)Research Paper

Proximal gradient methods are used to minimize an objective with one smooth part and one convex part whose proximal map can be evaluated. A small proximal gradient step is a practical stopping signal, but it indicates proximity to an optimizer only when the objective has an appropriate error bound. Section 4 of Drusvyatskiy and Lewis gives conditions for…

10 thms2 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

From Error Bounds to the Complexity of First-Order Descent Methods for Convex Functions 3: ISTA for ℓ1-Regularized Least Squares Satisfies f(x_k) − min f ≤ (f(x_0) − min f)/q^k with q = 1 + 2aγ_R/b²Research Paper

The ℓ1-regularized least squares problem (the Lasso, or basis pursuit denoising) is the model problem of compressed sensing and sparse inverse problems: given a matrix A∈Rm×nA\in\mathbb R^{m\times n}A∈Rm×n, data d∈Rmd\in\mathbb R^md∈Rm and a weight μ>0\mu>0μ>0, one seeks a vector xxx that fits Ax≈dAx\approx dAx≈d while having few nonzero entries. The standard first-order method for it is the i…

14 thms2 active usersReviewed
Dynamical SystemsOptimization·Captain: mikedeng1

First-Order Optimization Algorithms via Inertial Systems with Hessian Driven Damping I: Under (G₂)–(G₃), (DIN-AVD)α,β,b Trajectories Satisfy f(x(t)) − min f = O(1/(t²w(t)))Research Paper

Accelerated first-order methods for convex minimization, starting with Nesterov's 1983 scheme, reach the rate f(xk)−min⁡f=O(1/k2)f(x_k)-\min f=\mathcal O(1/k^2)f(xk​)−minf=O(1/k2), which is optimal for the class of convex functions with Lipschitz gradient. Su, Boyd and Candès (NIPS 2014; JMLR 2016) showed that Nesterov's method is a discretization of the second-order ODE …

7 thms2 active usersReviewed
Machine LearningOptimization·Captain: mikedeng1

Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization 3: Under Refined Dual Strong Convexity, SDCA Reaches Expected Dual Sub-optimality ε after 2(n/s)·log(2/ε) IterationsResearch Paper

Regularized loss minimization covers support vector machines, logistic and ridge regression, and the absolute-deviation regression of robust statistics. Stochastic dual coordinate ascent (SDCA) solves these problems by maximizing the Fenchel dual one randomly chosen coordinate at a time. Shalev-Shwartz and Zhang (arXiv:1209.1873, JMLR 2013) gave the first…

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

Proximal Algorithms II: The Proximal Operator of a Norm Is v − λΠ_B(v/λ), B the Unit Ball of the Dual NormResearch Paper

Norms are the most common nonsmooth terms in convex optimization models. The ℓ1\ell_1ℓ1​ norm promotes sparsity in the lasso and in compressed sensing, the Euclidean norm of blocks of variables promotes group sparsity in the group lasso, and the nuclear norm promotes low rank. First-order methods for such models, notably the proximal gradient method, ADMM and…

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

Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization 2: For f = ‖x‖², Every k-Sparse Point of the Simplex Has Duality Gap ≥ 2/kResearch Paper

The Frank–Wolfe algorithm minimizes a smooth convex objective over a compact convex domain by choosing an atom through a linear optimization problem and moving toward it. On a domain that is the convex hull of atoms, each ordinary iteration introduces at most one new atom. That makes the method useful when a solution represented with few atoms is valuable,…

5 thms2 active usersReviewed
Machine LearningOptimization·Captain: mikedeng1

Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization 1: With L-Lipschitz Losses, SDCA Reaches Expected Duality Gap ε after ⌈n log(λn/(2L²))⌉ + n + 20L²/(λε) IterationsResearch Paper

Regularized loss minimization over linear predictors is the training problem behind support vector machines, logistic regression, ridge regression and their many variants. Given examples x1,…,xn∈Rdx_1,\dots,x_n\in\mathbb R^dx1​,…,xn​∈Rd, one minimizes an average of convex losses of the predictions w⊤xiw^\top x_iw⊤xi​ plus a quadratic penalty. Dual coordinate ascent (DCA) solves the…

13 thms2 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisOperations Research+1·Captain: mikedeng1

A Primal-Dual Interior-Point Algorithm for Nonsymmetric Exponential-Cone Optimization 2: Rank-One Recursions Factor Y₀(Y₀ᵀS₀)⁻¹Y₀ᵀ = VVᵀ and S₀(Y₀ᵀS₀)⁻¹S₀ᵀ = UUᵀResearch Paper

Quasi-Newton methods replace the Hessian of an objective by a matrix H≻0H \succ 0H≻0 that is updated from observed pairs of steps and gradient changes. The secant equation HS=YHS = YHS=Y asks the new matrix to map the observed steps SSS to the observed changes YYY. The best-known update is BFGS, which for ppp simultaneous pairs S,Y∈Rn×pS, Y \in \mathbb{R}^{n\times p}S,Y∈Rn×p reads

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

Online Learning and Online Convex Optimization 3: Winnow Makes at Most (Σₜ fₜ(u) + k log(d)/η)/(1 − 2η) Mistakes, and 8k log d on Separable k-Literal DisjunctionsResearch Paper

A monotone disjunction over ddd Boolean variables is a rule of the form x[i1]∨⋯∨x[ik]x[i_1]\vee\dots\vee x[i_k]x[i1​]∨⋯∨x[ik​]. Learning such a rule online — predicting the label of each example before it is revealed and paying one unit per wrong prediction — is the basic test case for learning when only a few of many features matter. Littlestone's Winnow algorithm (Littlestone 1988)…

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

Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems 5: RCDM with Adaptive Lipschitz Estimates (RACDM) Has Expected Error at Most 8nR₁²(x₀)/(16 + 3k)Research Paper

Random coordinate descent minimizes a smooth convex function f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R by updating one coordinate at a time, chosen at random. Each iteration needs a single partial derivative instead of the full gradient, which is what makes the method usable on problems whose dimension is in the millions or billions ("huge-scale" problems). Nesterov's…

8 thms2 active usersReviewed
🏆Completed
Functional AnalysisOperations Research·Captain: mikedeng1

Optimization of Convex Risk Functions 2: On a Banach Lattice, a Proper Convex Monotone Risk Function Is Continuous and Subdifferentiable on the Interior of Its DomainResearch Paper

Risk-averse stochastic optimization replaces the expected cost E[X]\mathbb E[X]E[X] of an uncertain outcome XXX by a risk function ρ(X)\rho(X)ρ(X): conditional value-at-risk, mean–semideviation and mean–upper-semideviation models, and the coherent and convex risk measures of Artzner, Delbaen, Eber and Heath and of Föllmer and Schied. Ruszczyński and Shapiro, Optimization of…

9 thms2 active usersReviewed
🏆Completed
Functional AnalysisOperations Research·Captain: mikedeng1

Optimization of Convex Risk Functions 1: Dual Representation of a Lower Semicontinuous Convex Risk Function, with Monotonicity, Translation Equivariance and Homogeneity Read Off Its Dual DomainResearch Paper

A risk function assigns to an uncertain cost XXX (a function of the random state ω\omegaω) a single number ρ(X)\rho(X)ρ(X) that a decision maker can minimize. Artzner, Delbaen, Eber and Heath (Math. Finance 9, 1999) singled out four axioms, convexity, monotonicity, translation equivariance and positive homogeneity, and called real-valued functions satisfying all four co…

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